HOME

TheInfoList



OR:

In
set theory Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly concern ...
, a branch of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
A is called transitive if either of the following equivalent conditions hold: * whenever x \in A, and y \in x, then y \in A. * whenever x \in A, and x is not an
urelement In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ''ur-'', 'primordial') is an object that is not a set, but that may be an element of a set. It is also referred to as an atom or individual. Theory There ...
, then x is a
subset In mathematics, set ''A'' is a subset of a set ''B'' if all 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 are unequal, then ''A'' is a proper subset of ...
of A. Similarly, a
class Class 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 differently ...
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 (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest c ...
, 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 In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It ...
L are transitive sets. The
universe The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the univers ...
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 post ...
, 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 In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
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 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
interpretation Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...
s of set theory in itself, usually called
inner model In set theory, a branch of mathematical logic, an inner model for a theory ''T'' is a substructure of a model ''M'' of a set theory that is both a model for ''T'' and contains all the ordinals of ''M''. Definition Let L = \langle \in \rangl ...
s. The reason is that properties defined by bounded formulas are
absolute Absolute may refer to: Companies * Absolute Entertainment, a video game publisher * Absolute Radio, (formerly Virgin Radio), independent national radio station in the UK * Absolute Software Corporation, specializes in security and data risk manag ...
for transitive classes. A transitive set (or class) that is a model of a
formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A fo ...
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.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 relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive. Definition A hom ...
*
Supertransitive class In set theory, a supertransitive class is a transitive class which includes as a subset the power set of each of its elements. Formally, let ''A'' be a transitive class. Then ''A'' is supertransitive if and only if :(\forall x)(x\in A \to \mathca ...


References

* * * {{Mathematical logic Set theory