In set theory , a set A is called transitive if either of the following equivalent conditions hold:
whenever x ∈ A , and y ∈ x , then y ∈ A .
whenever x ∈ A , and x is not an urelement , then x is a subset of A . Similarly, a class M is transitive if every element of M is a subset of M .
Examples [ edit ] 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 V α and L α von Neumann universe V and Gödel's constructible universe L are transitive sets. The universes L and V 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 [ edit ] A set X is transitive if and only if
⋃
X
⊆
X
{\textstyle \bigcup X\subseteq X}
⋃
X
{\textstyle \bigcup X}
union of all elements of X that are sets,
⋃
X
=
{
y
∣
(
∃
x
∈
X
)
y
∈
x
}
{\textstyle \bigcup X=\{y\mid (\exists x\in X)y\in x\}}
X is transitive, then
⋃
X
{\textstyle \bigcup X}
X and Y are transitive, then X ∪Y ∪{X ,Y } is transitive. In general, if X is a class all of whose elements are transitive sets, then
X
∪
⋃
X
{\textstyle X\cup \bigcup X}
A set X which does not contain urelements is transitive if and only if it is a subset of its own power set ,
X
⊂
P
(
X
)
.
{\textstyle X\subset {\mathcal {P}}(X).}
Transitive closure [ edit ] The transitive closure of a set X is the smallest (with respect to inclusion) transitive set which contains X . Suppose one is given a set X , then the transitive closure of X is
TC
(
X
)
=
⋃
{
X
,
⋃
X
,
⋃
⋃
X
,
⋃
⋃
⋃
X
,
⋃
⋃
⋃
⋃
X
,
…
}
.
{\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
X
0
=
X
{\textstyle X_{0}=X}
X
n
+
1
=
⋃
X
n
{\textstyle X_{n+1}=\bigcup X_{n}}
T
=
TC
(
X
)
=
⋃
n
=
0
∞
X
n
{\displaystyle T=\operatorname {TC} (X)=\bigcup _{n=0}^{\infty }X_{n}}
is transitive, and whenever
T
1
{\textstyle T_{1}}
X
{\textstyle X}
T
⊆
T
1
{\textstyle T\subseteq T_{1}}
Assume
y
∈
x
∈
T
{\textstyle y\in x\in T}
x
∈
X
n
{\textstyle x\in X_{n}}
n
{\textstyle n}
y
∈
⋃
X
n
=
X
n
+
1
{\textstyle y\in \bigcup X_{n}=X_{n+1}}
X
n
+
1
⊆
T
{\textstyle X_{n+1}\subseteq T}
y
∈
T
{\textstyle y\in T}
T
{\textstyle T}
Now let
T
1
{\textstyle T_{1}}
X
n
⊆
T
1
∀
n
{\textstyle X_{n}\subseteq T_{1}\ \forall n}
T
⊆
T
1
{\textstyle T\subseteq T_{1}}
X
0
=
X
⊆
T
1
{\textstyle X_{0}=X\subseteq T_{1}}
X
n
⊆
T
1
{\textstyle X_{n}\subseteq T_{1}}
X
n
+
1
=
⋃
X
n
⊆
⋃
T
1
{\textstyle X_{n+1}=\bigcup X_{n}\subseteq \bigcup T_{1}}
T
1
{\textstyle T_{1}}
⋃
T
1
⊆
T
1
{\textstyle \bigcup T_{1}\subseteq T_{1}}
X
n
+
1
⊆
T
1
{\textstyle X_{n+1}\subseteq T_{1}}
Note that this is the set of all of the objects related to X by the transitive closure of the membership relation.
Transitive models of set theory [ edit ] 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 [2]
See also [ edit ] References [ edit ] Ciesielski, Krzysztof (1997), Set theory for the working mathematician , London Mathematical Society Student Texts, 39 , Cambridge: Cambridge University Press , ISBN 0-521-59441-3 , Zbl 0938.03067 Goldblatt, Robert (1998), Lectures on the hyperreals. An introduction to nonstandard analysis , Graduate Texts in Mathematics , 188 , New York, NY: Springer-Verlag , ISBN 0-387-98464-X , Zbl 0911.03032 Jech, Thomas (2008) [originally published in 1973], The Axiom of Choice , Dover Publications , ISBN 0-486-46624-8 , Zbl 0259.02051 External links [ edit ] 
