Transitive envelope (quantity)

The transitive hull of a set (often called for transitive closure ) is the smallest superset of that is transitive . The existence and uniqueness can be proven in ZF (the axiom of choice is not necessary for this). The substitution scheme and the axiom of infinity are decisive . Since is the smallest transitive superset of , then applies if and only if is transitive. ${\displaystyle X}$ ${\displaystyle TC(X)}$ ${\displaystyle X}$ ${\displaystyle TC(X)}$ ${\displaystyle X}$ ${\displaystyle TC(X)=X}$ ${\displaystyle X}$

construction

By induction on it can be shown that for every set a function exists with which ${\displaystyle \mathbb {N} }$ ${\displaystyle X}$ ${\displaystyle f_{X}}$ ${\displaystyle \operatorname {dom} (f_{X})=\mathbb {N} _{0}}$

• ${\displaystyle f_{X}(0)=X}$
• ${\displaystyle \forall n\in \mathbb {N} _{0}:f_{X}(n+1)=\bigcup f_{X}(n)}$

Fulfills. The substitution scheme now ensures the existence of the set

${\displaystyle M_{X}:=\{f_{X}(n)|n\in \mathbb {N} _{0}\}}$

and exists because of the axiom of union

${\displaystyle \bigcup M_{X}}$,

which one can quickly prove the required properties. So it applies ${\displaystyle TC(X)}$

${\displaystyle TC(X)=\bigcup _{n\in \mathbb {N} _{0}}f_{X}(n)}$.

Remarks

An iterated set union is defined here, namely

${\displaystyle f_{X}(n)={\bigcup }^{n}X}$, special . ${\displaystyle X=\{x|x\in X\},\ \;\bigcup X=\{x|(\exists y\in X)x\in y\}}$

If the element relation is understood as a homogeneous relation, then on the right side there is the n -fold concatenation of with itself, i.e. its n . Potency (see relation §Homogeneous relations : powers). This can be further simplified too ${\displaystyle \in }$ ${\displaystyle \in }$ ${\displaystyle {\in }^{n}}$

${\displaystyle f_{X}(n)={\bigcup }^{n}X=\{x|x{\in }^{n+1}X\}}$, such as

${\displaystyle M_{X}=\{{\bigcup }^{n}X|n\in \mathbb {N} _{0}\}=\{X,\bigcup X,\bigcup \bigcup X,\bigcup \bigcup \bigcup X,\bigcup \bigcup \bigcup \bigcup X,\ldots \}}$.

The transitive envelope then becomes too

${\displaystyle TC(X)=\bigcup M_{X}=\bigcup _{n=1}^{\infty }\{x|x\in ^{n}X\}=\bigcup _{n=0}^{\infty }{\bigcup }^{n}X}$.

application

In many proofs in set theory one needs the transitivity of a set for a certain argument. If one can also show that the statement is valid for a set , if one finds a superset for which it is valid, then it makes sense to move from to the transitive envelope. ${\displaystyle X}$ ${\displaystyle Y\supseteq X}$ ${\displaystyle X}$

A similar procedure can be found, for example, in the proof of the epsilon induction method .

generalization

Let be a set with a homogeneous relation on it. The - transitive envelope is then given by ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle R}$

${\displaystyle TC_{R}(X):=\bigcup _{n=0}^{\infty }\{x|(\exists y\in X)x\,R^{n}y\}=\{x|(\exists y\in X)x\,R^{*}y\}}$ 

This is the archetype of under , the reflexive-transitive envelope of the relation . is the smallest superset of that is -transitive . In the case, the generalized definition replicates the special case above. ${\displaystyle X}$ ${\displaystyle R^{*}}$ ${\displaystyle R}$ ${\displaystyle TC_{R}(X)}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle R=\in }$

See also

• Transitive envelope (relation)

Remarks

1. ↑ The axiom of union was, of course, needed beforehand to prove the existence of the function . ${\displaystyle f_{X}}$

1. ↑ ^{a b} are ad hoc designations ${\displaystyle f_{X},M_{X}}$
2. ↑ ^{a b} With understood as a homogeneous relation and the transitive envelope can also be understood as ${\displaystyle \in }$ ${\displaystyle {\in }^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}{\in }^{n}}$

   ${\displaystyle TC(X)=\{x|x{\in }^{+}X\}}$.

   See e.g. BG O'Regan: for homogeneous relations , Gerard O'Regan: Guide to Discrete Mathematics. Sets, Relations and Functions (=  Texts in Computer Science (TCS) ). Springer International Publishing, Switzerland 2016, p. ${\displaystyle R^{*}:=\textstyle \bigcup _{n\in {\mathbb {N} _{0}}}R^{n},\ \;R^{+}:=\textstyle \bigcup _{n\in {\mathbb {N} }}R^{n}}$ ${\displaystyle R}$ 25-51 , doi : 10.1007 / 978-3-319-44561-8_2 . Page 39.
3. ↑ Using Replacement to prove transitive closure is a set without recursion , on: StackExchange Mathematics, as of: 2018
4. ↑ Wolfram Pohlers: Set Theory (PDF) , University of Münster, Institute for Mathematical Logic and Basic Research, Lecture Script, SS 1994, page 31. The definition given there is similar to the one given here under construction, but has been converted into an equivalent, more easily readable one.