In set theory, a branch of mathematics, a setA 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 classM is transitive if every element ofM is a subset of M.
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. The class of all ordinals is a transitive class. Any of the stages Vα and Lα leading to the construction of the von Neumann universeV and Gödel's constructible universeL 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:
Properties
A set X is transitive if and only if, where is the union of all elements of X that are sets,. If X is transitive, then is transitive. If X and Y are transitive, then X∪Y∪ is transitive. In general, if X is a class all of whose elements are transitive sets, then is transitive. A set X 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 X is the smallest transitive set that contains X. Suppose one is given a set X, then the transitive closure of X is Proof. Denote and. Then we claim that the set is transitive, and whenever is a transitive set containing 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 whence. 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 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 satisfystrong transitivity.
