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 (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 universes
and
themselves are transitive classes.
This is a complete list of all finite transitive sets with up to 20 brackets:[1]
![{\displaystyle \{\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a34fd8df4091d46da8c89ed0bfcb6ff7262e5a1)
![{\displaystyle \{\{\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdbd7338354c06837327ae1749e8b97fdcf08df9)
![{\displaystyle \{\{\},\{\{\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04fb0d89b398f050845a189e03edcce79367d3cc)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5a2a0726f2db7fd26001502cce4dff7ae842c5a)
![{\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21b46629b032abd1fb296ea2d004b195b87c0715)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef3ef830be13244094a99afa20ce09ce649e3afa)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aefc5a43df0495c19e3751a8b65b3869c605347a)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a155fa47bd37b39aa264d713de0a05ed625c6f3f)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/981ba5352ebf790f9e5a0c742408a56771e26af3)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c283344ddfe7b9e3cede9c4130376adbadf7ad82)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9be856984743f0d24b3517cf01638e40a60d4aa9)
![{\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e91fc6188c28636e66c1d1cbd70322b9ebaf2969)
![{\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/066dd6e271e94bd000a9b2b74be0d186985c8334)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ee3e0bf012f6a7a3d73de698a89d05be9023481)
![{\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98a9c07d53653c827a12ab1ba8b170f199bf56cd)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/492cb3ba982fbb5c4347e83f81a11d4434f3fae8)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2be01923249a115e08be6f3187a2eb34124b341d)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34e330423b1174cab70e2d2fe97a4aedc780b53d)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f97f44cc3440614c0d5b9a1c582ee81ac386ccb)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1d1558834de271c9a198720c2f91b9e66e8c9d4)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1fd2f664748031f69f723abb0cadd07f2ec886f9)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49952b15cc926f08f4f9d6e628ad7ff2c538b70d)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6dac6847f288c40dfd6ef65794edb4cf65d20eb7)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71f822c32be1924979cfa3923883de4c95314cad)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea984b25ae318414cd61a8f57c30024759686ffb)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\},\{\{\{\}\}\}\}\},\{\{\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56b6ff3bf14caa8bc7e4b2f879be26cbf9d6e34c)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57ad67e2487b858f5457e972a8e90a90be117074)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14c1ed2be27e7fa461a712537e11fe96a6408ea0)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2815c22480caa4b83ca55c2ab6b4ff55a57bef6c)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\}\}\},\{\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/618693ab64785a756d2d70baae343a56f7cd00dc)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b1bc4adfb381b6f83125f7197a535acf0558939)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5b6490256e5315bcfd1adbcbc29947e31eef940)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf2938d8d1815f0dbb6edcab40e0e3b581717d1f)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\},\{\{\},\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f76511ee79ff42e242343ab5960f10e5497e5fde)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dcde1c475da4c7da92feb24c90e0446efba8c1d)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\{\},\{\{\}\}\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ce6521534b2e49f176c514b3967f25c74ccdfe5)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/327dbff968e21c62b91c48489cb217928493e09f)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\}\}\},\{\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e2c58df0b19e8469f580534e29697680109824a)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\},\{\{\{\}\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62051b9c124055c7abaceb5dee6a3b943130684b)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c42fba8bcb467751dacaef5550775b5e1166050)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\{\}\},\{\{\},\{\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7845cf817057db43996118f61004b8375163a6e5)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec12da2cc84bd26899d144bd90e4e0e7045fefa3)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\},\{\{\}\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea583e5c56b087fc9ba8b3eccc51656074a5a358)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ad20744e654425d49d39e2f6992c1f43a3b1c47)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\{\}\}\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80d423d314db85a663fd9378fca84b7fd522ead6)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74e2b0f98f7f9c45aa6568aee8c2a6a3aff19b52)
![{\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b46d2da3d4d4fec453aaf4c6e22e04c387a09913)
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,
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.
).[2] Suppose one is given a set
, then the transitive closure of
is
![{\displaystyle \operatorname {TC} (X)=\bigcup \left\{X,\;\bigcup X,\;\bigcup \bigcup X,\;\bigcup \bigcup \bigcup X,\;\bigcup \bigcup \bigcup \bigcup X,\ldots \right\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc10b3026dac94b5c8c873c24742809e0759e82f)
Proof. Denote
and
. Then we claim that the set
![{\displaystyle T=\operatorname {TC} (X)=\bigcup _{n=0}^{\infty }X_{n))](https://wikimedia.org/api/rest_v1/media/math/render/svg/a406d6b8cb8a19f902b0ea506eda26a100d5e47b)
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
is an intersection of all transitive supersets of
(that is, every transitive superset of
contains
as a subset).