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 is called transitive if either of the following equivalent conditions holds:
* whenever
, and
, then
.
* whenever
, and
is not an
urelement, then
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
.
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 ...
is transitive if every element of
is a subset of
.
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
and
leading to the construction of the
von Neumann universe and
Gödel's constructible universe 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
and
themselves are transitive classes.
This is a complete list of all finite transitive sets with up to 20 brackets:
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Properties
A set
is transitive if and only if
, where
is the
union of all elements of
that are sets,
.
If
is transitive, then
is transitive.
If
and
are transitive, then
and
are transitive. In general, if
is a class all of whose elements are transitive sets, then
and
are transitive. (The first sentence in this paragraph is the case of
.)
A set
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 ...
,
The power set of a transitive set without urelements is transitive.
Transitive closure
The transitive closure of a set
is the smallest (with respect to inclusion) transitive set that includes
(i.e.
). Suppose one is given a set
, then the transitive closure of
is
Proof. Denote
and
. Then we claim that the set
is transitive, and whenever
is a transitive set including
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
, hence
. This completes the proof.
Note that this is the set of all of the objects related to
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:
is a transitive closure of
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 ...
is an intersection of all transitive
supersets of
(that is, every transitive superset of
contains
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
is defined to be strongly transitive if, for each set
, there exists a transitive superset
with
. A strongly transitive class is automatically transitive. This strengthened transitivity assumption allows one to conclude, for instance, that
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
.
[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