Transitive set

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_\alpha and L_\alpha leading to the construction of the von Neumann universe V and Gödel's constructible universe L are transitive sets. The universes V and L themselves are transitive classes. This is a complete list of all finite transitive sets with up to 20 pairs of brackets: • \{\}, • \{\{\}\}, • \{\{\}, \{\{\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}, \{\{\{\}\}\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}, \{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\{\}, \{\{\}\}\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}, \{\{\{\}\}\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\}\}, \{\{\{\}\}\}\}, \{\{\}, \{\{\}\}, \{\{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}, \{\{\}\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\{\}\}, \{\{\}, \{\{\}\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\{\{\}\}\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\{\}, \{\{\}\}\}\}, \{\{\}, \{\{\}\}\}\}, • \{\{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \{\{\}, \{\{\}\}\}, \{\{\}, \{\{\{\}\}\}\}\}. == Properties ==

A set X is transitive if and only if \bigcup X \subseteq X, where \bigcup X is the union of all elements of X that are sets, \bigcup X = \{y \mid \exists x \in X: y \in x\}. If X is transitive, then \bigcup X is transitive. If X and Y are transitive, then X\cup Y and X \cup Y \cup \{X,Y\} are transitive. In general, if Z is a class all of whose elements are transitive sets, then \bigcup Z and Z\cup\bigcup Z are transitive. (The first sentence in this paragraph is the case of Z=\{X,Y\}.) A set X that does not contain urelements is transitive if and only if it is a subset of its own power set, X \subseteq \mathcal{P}(X). The power set of a transitive set without urelements is transitive. == Transitive closure ==

The transitive closure of a set X is the smallest (with respect to inclusion) transitive set that includes X (i.e. X \subseteq \operatorname{TC}(X)). Suppose one is given a set X, then the transitive closure of X is \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 and X_{n+1} = \bigcup X_n. Then we claim that the set T = \operatorname{TC}(X) = \bigcup_{n=0}^\infty X_n is transitive, and whenever T_1 is a transitive set including X then T \subseteq T_1. Assume y \in x \in T. Then x \in X_n for some n and so y \in \bigcup X_n = X_{n+1}. Since X_{n+1} \subseteq T, y \in T. Thus T is transitive. Now let T_1 be as above. We prove by induction that X_n \subseteq T_1 for all n, thus proving that T \subseteq T_1: The base case holds since X_0 = X \subseteq T_1. Now assume X_n \subseteq T_1. Then X_{n+1} = \bigcup X_n \subseteq \bigcup T_1. But T_1 is transitive so \bigcup T_1 \subseteq T_1, hence X_{n+1} \subseteq T_1. This completes the proof. Note that this is the set of all of the objects related to 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. ==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. Here, a class \mathcal{C} is defined to be strongly transitive if, for each set S\in\mathcal{C}, there exists a transitive superset T with S\subseteq T\subseteq\mathcal{C}. A strongly transitive class is automatically transitive. This strengthened transitivity assumption allows one to conclude, for instance, that \mathcal{C} contains the domain of every binary relation in \mathcal{C}. ==See also==