HOME

TheInfoList



OR:

In
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
, a branch of
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a set A is called transitive if either of the following equivalent conditions holds: * whenever x \in A, and y \in x, then y \in A. * whenever x \in A, and x is not an urelement, then x is a
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of A. Similarly, a
class Class, Classes, or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used d ...
M is transitive if every element of M is a subset of M.


Examples

Using the definition of
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
s suggested by
John von Neumann John von Neumann ( ; ; December 28, 1903 – February 8, 1957) was a Hungarian and American mathematician, physicist, computer scientist and engineer. Von Neumann had perhaps the widest coverage of any mathematician of his time, in ...
, 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
universe The universe is all of space and time and their contents. It comprises all of existence, any fundamental interaction, physical process and physical constant, and therefore all forms of matter and energy, and the structures they form, from s ...
s V and L 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 \bigcup X \subseteq X, where \bigcup X is the union of all elements of X that are sets, \bigcup 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 \ 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=\.) A set X that does not contain urelements is transitive if and only if it is a subset of its own
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
, X \subseteq \mathcal(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(X)). Suppose one is given a set X, then the transitive closure of X is \operatorname(X) = \bigcup \left\. Proof. Denote X_0 = X and X_ = \bigcup X_n. Then we claim that the set T = \operatorname(X) = \bigcup_^\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_. Since X_ \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_ = \bigcup X_n \subseteq \bigcup T_1. But T_1 is transitive so \bigcup T_1 \subseteq T_1, hence X_ \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. The transitive closure of a set can be expressed by a first-order formula: x is a transitive closure of y
iff In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both ...
x is an intersection of all transitive supersets of y (that is, every transitive superset of y contains x 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 A formal system is an abstract structure and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms. In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in ma ...
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 is defined to be strongly transitive if, for each set S\in\mathcal, there exists a transitive superset T with S\subseteq T\subseteq\mathcal. A strongly transitive class is automatically transitive. This strengthened transitivity assumption allows one to conclude, for instance, that \mathcal contains the domain of every
binary relation In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...
in \mathcal.Goldblatt (1998) p.161


See also

*
End extension In model theory and set theory, which are disciplines within mathematics, a model \mathfrak=\langle B, F\rangle of some axiom system of set theory T in the language of set theory is an end extension of \mathfrak=\langle A, E\rangle , in symbols \ ...
*
Transitive relation In mathematics, a binary relation on a set (mathematics), set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Every partial order and every equivalence relation is transitive. For example ...
*
Supertransitive class In set theory, a supertransitive class is a transitive class which includes as a subset the power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set ...


References

* * * {{Mathematical logic Set theory