Transitive set

Short description: Class of mathematical set whose elements are all subsets

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

whenever [math]\displaystyle{ x \in A }[/math], and [math]\displaystyle{ y \in x }[/math], then [math]\displaystyle{ y \in A }[/math].
whenever [math]\displaystyle{ x \in A }[/math], and [math]\displaystyle{ x }[/math] is not an urelement, then [math]\displaystyle{ x }[/math] is a subset of [math]\displaystyle{ A }[/math].

Similarly, a class [math]\displaystyle{ M }[/math] is transitive if every element of [math]\displaystyle{ M }[/math] is a subset of [math]\displaystyle{ M }[/math].

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 [math]\displaystyle{ V_\alpha }[/math] and [math]\displaystyle{ L_\alpha }[/math] leading to the construction of the von Neumann universe [math]\displaystyle{ V }[/math] and Gödel's constructible universe [math]\displaystyle{ L }[/math] are transitive sets. The universes [math]\displaystyle{ V }[/math] and [math]\displaystyle{ L }[/math] themselves are transitive classes.

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

[math]\displaystyle{ \{\}, }[/math]
[math]\displaystyle{ \{\{\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}, \{\{\{\}\}\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}, \{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\{\}, \{\{\}\}\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}, \{\{\{\}\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}, \{\{\}\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\{\}\}\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, }[/math]
[math]\displaystyle{ \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}. }[/math]

Properties

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

If [math]\displaystyle{ X }[/math] is transitive, then [math]\displaystyle{ \bigcup X }[/math] is transitive.

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

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

Transitive closure

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

[math]\displaystyle{ \operatorname{TC}(X) = \bigcup \left\{ X,\; \bigcup X,\; \bigcup\bigcup X,\; \bigcup\bigcup\bigcup X,\; \bigcup\bigcup\bigcup\bigcup X, \ldots\right\}. }[/math]

Proof. Denote [math]\displaystyle{ X_0 = X }[/math] and [math]\displaystyle{ X_{n+1} = \bigcup X_n }[/math]. Then we claim that the set

[math]\displaystyle{ T = \operatorname{TC}(X) = \bigcup_{n=0}^\infty X_n }[/math]

is transitive, and whenever [math]\displaystyle{ T_1 }[/math] is a transitive set including [math]\displaystyle{ X }[/math] then [math]\displaystyle{ T \subseteq T_1 }[/math].

Assume [math]\displaystyle{ y \in x \in T }[/math]. Then [math]\displaystyle{ x \in X_n }[/math] for some [math]\displaystyle{ n }[/math] and so [math]\displaystyle{ y \in \bigcup X_n = X_{n+1} }[/math]. Since [math]\displaystyle{ X_{n+1} \subseteq T }[/math], [math]\displaystyle{ y \in T }[/math]. Thus [math]\displaystyle{ T }[/math] is transitive.

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

Note that this is the set of all of the objects related to [math]\displaystyle{ X }[/math] 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: [math]\displaystyle{ x }[/math] is a transitive closure of [math]\displaystyle{ y }[/math] iff [math]\displaystyle{ x }[/math] is an intersection of all transitive supersets of [math]\displaystyle{ y }[/math] (that is, every transitive superset of [math]\displaystyle{ y }[/math] contains [math]\displaystyle{ x }[/math] 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]

References

↑ "Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).". https://oeis.org/A004111.
↑ Ciesielski, Krzysztof (1997). Set theory for the working mathematician. Cambridge: Cambridge University Press. p. 164. ISBN 978-1-139-17313-1. OCLC 817922080. https://www.worldcat.org/oclc/817922080.
↑ Goldblatt (1998) p.161

Ciesielski, Krzysztof (1997), Set theory for the working mathematician, London Mathematical Society Student Texts, 39, Cambridge: Cambridge University Press, ISBN 0-521-59441-3
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
Jech, Thomas (2008), The Axiom of Choice, Dover Publications, ISBN 0-486-46624-8

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Transitive set. Read more

[1] "Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).". https://oeis.org/A004111.

[2] Ciesielski, Krzysztof (1997). Set theory for the working mathematician. Cambridge: Cambridge University Press. p. 164. ISBN 978-1-139-17313-1. OCLC 817922080. https://www.worldcat.org/oclc/817922080.

[3] Goldblatt (1998) p.161

[1]

[2]

[3]

v t e Mathematical logic
General	Formal language Formation rule Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Rule of inference Relation Theorem Logical consequence Type theory Symbol Syntax Theory
Systems	Formal system Deductive system Axiomatic system Hilbert style systems Natural deduction Sequent calculus
Traditional logic	Proposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagram
Propositional calculus and Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables Many-valued logic
Predicate logic	First-order Quantifiers Predicate Second-order Monadic predicate calculus
Naive set theory	Set Empty set Element Enumeration Extensionality Finite set Infinite set Subset Power set Countable set Uncountable set Recursive set Domain Codomain Image Map Function Relation Ordered pair
Set theory	Foundations of mathematics Zermelo–Fraenkel set theory Axiom of choice General set theory Kripke–Platek set theory Von Neumann–Bernays–Gödel set theory Morse–Kelley set theory Tarski–Grothendieck set theory
Model theory	Model Interpretation Non-standard model Finite model theory Truth value Validity
Proof theory	Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax
Computability theory	Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function

Anonymous

Search

Transitive set

Namespaces

More

Page actions

Contents

Examples

Properties

Transitive closure

Transitive models of set theory

See also

References

Navigation

Navigation

Help

Translate

Wiki tools

Wiki tools

Anonymous

Search

Transitive set

Examples

Properties

Transitive closure

Transitive models of set theory

See also

References

Navigation

Wiki tools

Page tools

Other projects

Categories