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 conce ...
, 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 ...
is called transitive if either of the following equivalent conditions hold:
* whenever
, and
, then
.
* whenever
, and
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
is a
subset
In mathematics, 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 are ...
of
.
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 differentl ...
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 least n ...
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 cove ...
, 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
In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by ''V'', is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (Z ...
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 ...
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 universe. Acc ...
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
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
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
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 s ...
of the membership relation, since the union of a set can be expressed in terms of the
relative product
In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplic ...
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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicon ...
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 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 \rangle be ...
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 manage ...
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 form ...
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 history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers. The standard way to resolve these debates is to define the operations of calculus using epsilon–delta ...
, 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 homog ...
*
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