# Transitive set

Last updated

In set theory, a branch of mathematics, a set ${\displaystyle A}$ is called transitive if either of the following equivalent conditions hold:

## Contents

• whenever ${\displaystyle x\in A}$, and ${\displaystyle y\in x}$, then ${\displaystyle y\in A}$.
• whenever ${\displaystyle x\in A}$, and ${\displaystyle x}$ is not an urelement, then ${\displaystyle x}$ is a subset of ${\displaystyle A}$.

Similarly, a class ${\displaystyle M}$ is transitive if every element of ${\displaystyle M}$ is a subset of ${\displaystyle M}$.

## Examples

Using the definition of ordinal numbers suggested by John von Neumann, ordinal numbers are defined as hereditarily transitive sets: an ordinal number is a transitive set whose members are also transitive (and thus ordinals). The class of all ordinals is a transitive class.

Any of the stages ${\displaystyle V_{\alpha }}$ and ${\displaystyle L_{\alpha }}$ leading to the construction of the von Neumann universe ${\displaystyle V}$ and Gödel's constructible universe ${\displaystyle L}$ are transitive sets. The universes ${\displaystyle V}$ and ${\displaystyle L}$ themselves are transitive classes.

This is a complete list of all finite transitive sets with up to 20 brackets: [1]

• ${\displaystyle \{\},}$
• ${\displaystyle \{\{\}\},}$
• ${\displaystyle \{\{\},\{\{\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\},\{\{\{\}\}\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\}\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\},\{\{\},\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\{\},\{\{\}\}\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\}\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\},\{\{\{\}\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\{\}\},\{\{\},\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\},\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\{\}\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\}.}$

## Properties

A set ${\displaystyle X}$ is transitive if and only if ${\textstyle \bigcup X\subseteq X}$, where ${\textstyle \bigcup X}$ is the union of all elements of ${\displaystyle X}$ that are sets, ${\textstyle \bigcup X=\{y\mid \exists x\in X:y\in x\}}$.

If ${\displaystyle X}$ is transitive, then ${\textstyle \bigcup X}$ is transitive.

If ${\displaystyle X}$ and ${\displaystyle Y}$ are transitive, then ${\displaystyle X\cup Y}$ and ${\displaystyle X\cup Y\cup \{X,Y\}}$ are transitive. In general, if ${\displaystyle Z}$ is a class all of whose elements are transitive sets, then ${\textstyle \bigcup Z}$ and ${\textstyle Z\cup \bigcup Z}$ are transitive. (The first sentence in this paragraph is the case of ${\displaystyle Z=\{X,Y\}}$.)

A set ${\displaystyle X}$ that does not contain urelements is transitive if and only if it is a subset of its own power set, ${\textstyle X\subseteq {\mathcal {P}}(X).}$ The power set of a transitive set without urelements is transitive.

## Transitive closure

The transitive closure of a set ${\displaystyle X}$ is the smallest (with respect to inclusion) transitive set that includes ${\displaystyle X}$ (i.e. ${\textstyle X\subseteq \operatorname {TC} (X)}$). [2] Suppose one is given a set ${\displaystyle X}$, then the transitive closure of ${\displaystyle X}$ is

${\displaystyle \operatorname {TC} (X)=\bigcup \left\{X,\;\bigcup X,\;\bigcup \bigcup X,\;\bigcup \bigcup \bigcup X,\;\bigcup \bigcup \bigcup \bigcup X,\ldots \right\}.}$

Proof. Denote ${\textstyle X_{0}=X}$ and ${\textstyle X_{n+1}=\bigcup X_{n}}$. Then we claim that the set

${\displaystyle T=\operatorname {TC} (X)=\bigcup _{n=0}^{\infty }X_{n}}$

is transitive, and whenever ${\textstyle T_{1}}$ is a transitive set including ${\textstyle X}$ then ${\textstyle T\subseteq T_{1}}$.

Assume ${\textstyle y\in x\in T}$. Then ${\textstyle x\in X_{n}}$ for some ${\textstyle n}$ and so ${\textstyle y\in \bigcup X_{n}=X_{n+1}}$. Since ${\textstyle X_{n+1}\subseteq T}$, ${\textstyle y\in T}$. Thus ${\textstyle T}$ is transitive.

Now let ${\textstyle T_{1}}$ be as above. We prove by induction that ${\textstyle X_{n}\subseteq T_{1}}$ for all ${\displaystyle n}$, thus proving that ${\textstyle T\subseteq T_{1}}$: The base case holds since ${\textstyle X_{0}=X\subseteq T_{1}}$. Now assume ${\textstyle X_{n}\subseteq T_{1}}$. Then ${\textstyle X_{n+1}=\bigcup X_{n}\subseteq \bigcup T_{1}}$. But ${\textstyle T_{1}}$ is transitive so ${\textstyle \bigcup T_{1}\subseteq T_{1}}$, hence ${\textstyle X_{n+1}\subseteq T_{1}}$. This completes the proof.

Note that this is the set of all of the objects related to ${\displaystyle X}$ by the transitive closure of the membership relation, since the union of a set can be expressed in terms of the relative product of the membership relation with itself.

The transitive closure of a set can be expressed by a first-order formula: ${\displaystyle x}$ is a transitive closure of ${\displaystyle y}$ iff ${\displaystyle x}$ is an intersection of all transitive supersets of ${\displaystyle y}$ (that is, every transitive superset of ${\displaystyle y}$ contains ${\displaystyle x}$ as a subset).

## Transitive models of set theory

Transitive classes are often used for construction of interpretations of set theory in itself, usually called inner models. The reason is that properties defined by bounded formulas are absolute for transitive classes.

A transitive set (or class) that is a model of a formal system of set theory is called a transitive model of the system (provided that the element relation of the model is the restriction of the true element relation to the universe of the model). Transitivity is an important factor in determining the absoluteness of formulas.

In the superstructure approach to non-standard analysis, the non-standard universes satisfy strong transitivity.[ clarification needed ] [3]

## Related Research Articles

In mathematics, the axiom of regularity is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set A contains an element that is disjoint from A. In first-order logic, the axiom reads:

In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain. A binary relation over sets X and Y is a new set of ordered pairs (x, y) consisting of elements x in X and y in Y. It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case n = 2 of an n-ary relation over sets X1, ..., Xn, which is a subset of the Cartesian product

In topology, the closure of a subset S of points in a topological space consists of all points in S together with all limit points of S. The closure of S may equivalently be defined as the union of S and its boundary, and also as the intersection of all closed sets containing S. Intuitively, the closure can be thought of as all the points that are either in S or "very near" S. A point which is in the closure of S is a point of closure of S. The notion of closure is in many ways dual to the notion of interior.

In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is also a topological space with the property that the vector space operations are also continuous functions. Such a topology is called a vector topology and every topological vector space has a uniform topological structure, allowing a notion of uniform convergence and completeness. Some authors also require that the space is a Hausdorff space. One of the most widely studied categories of TVSs are locally convex topological vector spaces. This article focuses on TVSs that are not necessarily locally convex. Banach spaces, Hilbert spaces and Sobolev spaces are other well-known examples of TVSs.

In mathematics, specifically in topology, the interior of a subset S of a topological space X is the union of all subsets of S that are open in X. A point that is in the interior of S is an interior point of S.

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. It was first used by Paul Cohen in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory.

In mathematics, a binary relation R on a set X is reflexive if it relates every element of X to itself.

In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets and is .

In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets it is the unique minimal transitive superset of R.

In mathematics, in set theory, the constructible universe, denoted by L, is a particular class of sets that can be described entirely in terms of simpler sets. L is the union of the constructible hierarchyLα. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this paper, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result.

In functional analysis and related areas of mathematics an absorbing set in a vector space is a set which can be "inflated" or "scaled up" to eventually always include any given point of the vector space. Alternative terms are radial or absorbent set. Every neighborhood of the origin in every topological vector space is an absorbing subset.

In set theory, a prewellordering on a set is a preorder on that is strongly connected and well-founded in the sense that the induced relation defined by is a well-founded relation.

In set theory, -induction, also called epsilon-induction or set-induction, is a principle that can be used to prove that all sets satisfy a given property. Considered as an axiomatic principle, it is called the axiom schema of set induction.

A Dynkin system, named after Eugene Dynkin is a collection of subsets of another universal set satisfying a set of axioms weaker than those of 𝜎-algebra. Dynkin systems are sometimes referred to as 𝜆-systems or d-system. These set families have applications in measure theory and probability.

In mathematics, an upper set of a partially ordered set is a subset with the following property: if s is in S and if x in X is larger than s, then x is in S. In other words, this means that any x element of X that is to some element of S is necessarily also an element of S. The term lower set is defined similarly as being a subset S of X with the property that any element x of X that is to some element of S is necessarily also an element of S.

This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC and in NFU, the version of Quine's New Foundations shown to be consistent by R. B. Jensen in 1969.

In topology and related fields of mathematics, a sequential space is a topological space whose topology can be completely characterized by its convergent/divergent sequences. They can be thought of as spaces that satisfy a very weak axiom of countability, and all first-countable spaces are sequential.

In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This is analogous to the arithmetical hierarchy, which provides a similar classification for sentences of the language of arithmetic.

In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption of transitivity is dropped. On a set, an algebraic structure with empty family of operations, tolerance relations are simply reflexive symmetric relations. A set that possesses a tolerance relation can be described as a tolerance space. Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré.

This is a glossary of set theory.

## References

1. "Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group)". OEIS.
2. Ciesielski, Krzysztof (1997). Set theory for the working mathematician. Cambridge: Cambridge University Press. p. 164. ISBN   978-1-139-17313-1. OCLC   817922080.
3. Goldblatt (1998) p.161