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.
This is a complete list of all finite transitive sets with up to 20 brackets:[1]
Properties
A set is transitive if and only if , where is the union of all elements of that are sets, .
If is transitive, then is transitive.
If and are transitive, then and are transitive. In general, if is a class all of whose elements are transitive sets, then and are transitive. (The first sentence in this paragraph is the case of .)
A set that does not contain urelements is transitive if and only if it is a subset of its own power set, The power set of a transitive set without urelements is transitive.
Transitive closure
The transitive closure of a set is the smallest (with respect to inclusion) transitive set that includes (i.e. ).[2] Suppose one is given a set , then the transitive closure of is
Proof. Denote and . Then we claim that the set
is transitive, and whenever is a transitive set including then .
Assume . Then for some and so . Since , . Thus is transitive.
Now let be as above. We prove by induction that for all , thus proving that : The base case holds since . Now assume . Then . But is transitive so , hence . This completes the proof.
Note that this is the set of all of the objects related to 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: is a transitive closure of iff is an intersection of all transitive supersets of (that is, every transitive superset of contains 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.
^"Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group)". OEIS.
^Ciesielski, Krzysztof (1997). Set theory for the working mathematician. Cambridge: Cambridge University Press. p. 164. ISBN978-1-139-17313-1. OCLC 817922080.
Ciesielski, Krzysztof (1997), Set theory for the working mathematician, London Mathematical Society Student Texts, vol. 39, Cambridge: Cambridge University Press, ISBN0-521-59441-3, Zbl 0938.03067
transitive, theory, branch, mathematics, displaystyle, called, transitive, either, following, equivalent, conditions, hold, whenever, displaystyle, displaystyle, then, displaystyle, whenever, displaystyle, displaystyle, urelement, then, displaystyle, subset, d. In set theory a branch of mathematics a set A displaystyle A is called transitive if either of the following equivalent conditions hold whenever x A displaystyle x in A and y x displaystyle y in x then y A displaystyle y in A whenever x A displaystyle x in A and x displaystyle x is not an urelement then x displaystyle x is a subset of A displaystyle A Similarly a class M displaystyle M is transitive if every element of M displaystyle M is a subset of M displaystyle M Contents 1 Examples 2 Properties 3 Transitive closure 4 Transitive models of set theory 5 See also 6 ReferencesExamples EditUsing 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 a displaystyle V alpha and L a displaystyle L alpha leading to the construction of the von Neumann universe V displaystyle V and Godel s constructible universe L displaystyle L are transitive sets The universes V displaystyle V and L 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 EditA set X displaystyle X is transitive if and only if X X textstyle bigcup X subseteq X where X textstyle bigcup X is the union of all elements of X displaystyle X that are sets X y x X y x textstyle bigcup X y mid exists x in X y in x If X displaystyle X is transitive then X textstyle bigcup X is transitive If X displaystyle X and Y displaystyle Y are transitive then X Y displaystyle X cup Y and X Y X Y displaystyle X cup Y cup X Y are transitive In general if Z displaystyle Z is a class all of whose elements are transitive sets then Z textstyle bigcup Z and Z Z textstyle Z cup bigcup Z are transitive The first sentence in this paragraph is the case of Z X Y displaystyle Z X Y A set X displaystyle X that does not contain urelements is transitive if and only if it is a subset of its own power set X P X textstyle X subseteq mathcal P X The power set of a transitive set without urelements is transitive Transitive closure EditThe transitive closure of a set X displaystyle X is the smallest with respect to inclusion transitive set that includes X displaystyle X i e X TC X textstyle X subseteq operatorname TC X 2 Suppose one is given a set X displaystyle X then the transitive closure of X displaystyle 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 and X n 1 X n textstyle X n 1 bigcup X n Then we claim that the set 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 is a transitive set including X textstyle X then T T 1 textstyle T subseteq T 1 Assume y x T textstyle y in x in T Then x X n textstyle x in X n for some n textstyle n and so y X n X n 1 textstyle y in bigcup X n X n 1 Since X n 1 T textstyle X n 1 subseteq T y T textstyle y in T Thus T textstyle T is transitive Now let T 1 textstyle T 1 be as above We prove by induction that X n T 1 textstyle X n subseteq T 1 for all n displaystyle n thus proving that T T 1 textstyle T subseteq T 1 The base case holds since X 0 X T 1 textstyle X 0 X subseteq T 1 Now assume X n T 1 textstyle X n subseteq T 1 Then X n 1 X n T 1 textstyle X n 1 bigcup X n subseteq bigcup T 1 But T 1 textstyle T 1 is transitive so T 1 T 1 textstyle bigcup T 1 subseteq T 1 hence X n 1 T 1 textstyle X n 1 subseteq T 1 This completes the proof Note that this is the set of all of the objects related to X 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 x displaystyle x is a transitive closure of y displaystyle y iff x displaystyle x is an intersection of all transitive supersets of y displaystyle y that is every transitive superset of y displaystyle y contains x displaystyle x as a subset Transitive models of set theory EditTransitive 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 See also EditEnd extension Transitive relation Supertransitive classReferences Edit Number of rooted identity trees with n nodes rooted trees whose automorphism group is the identity group OEIS Ciesielski Krzysztof 1997 Set theory for the working mathematician Cambridge Cambridge University Press p 164 ISBN 978 1 139 17313 1 OCLC 817922080 Goldblatt 1998 p 161 Ciesielski Krzysztof 1997 Set theory for the working mathematician London Mathematical Society Student Texts vol 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 vol 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 Retrieved from https en wikipedia org w index php title Transitive set amp oldid 1109080624 Transitive closure, wikipedia, wiki, book, books, library,
