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).
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
{\displaystyle \bigcup X\subseteq X}
⋃
X
{\displaystyle \bigcup X}
union of all elements of X that are sets,
⋃
X
=
{
y
∣
(
∃
x
∈
X
)
y
∈
x
}
{\displaystyle \bigcup X=\{y\mid (\exists x\in X)y\in x\}}
X is transitive, then
⋃
X
{\displaystyle \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
{\displaystyle 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
)
.
{\displaystyle 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
⋃
{
X
,
⋃
X
,
⋃
⋃
X
,
⋃
⋃
⋃
X
,
⋃
⋃
⋃
⋃
X
,
…
}
.
{\displaystyle \bigcup \{X,\bigcup X,\bigcup \bigcup X,\bigcup \bigcup \bigcup X,\bigcup \bigcup \bigcup \bigcup X,\ldots \}.}
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. 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 ] 
