# Transitive Closure Always Exists (Set Theory)

## Contents

## Theorem

Let $S$ be a set.

Let $G$ be a mapping such that $\map G x = x \cup \bigcup x$.

Let $F$ be defined using the Principle of Recursive Definition:

- $\map F 0 = S$

- $\map F {n^+} = \map G {\map F n}$

Let $\displaystyle T = \bigcup_{n \mathop \in \omega} \map F n$.

Then:

- $T$ is a set and is transitive

- $S \subseteq T$

- If $R$ is transitive and $S \subseteq R$, then $T \subseteq R$.

That is, given any set $S$, there is an explicit construction for its transitive closure.

## Proof

$\omega$ is a set by the Axiom of Infinity.

Thus by the Axiom of Replacement, the image of $\omega$ under $F$ is also a set.

Since $T$ is the union of $\map F \omega$, it is thus a set by the axiom of unions.

Furthermore:

\(\displaystyle x\) | \(\in\) | \(\displaystyle T\) | Assumption | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\, \displaystyle \exists n: \, \) | \(\displaystyle x\) | \(\in\) | \(\displaystyle \map F n\) | Definition of Union of Family | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\, \displaystyle \exists n: \, \) | \(\displaystyle x\) | \(\subseteq\) | \(\displaystyle \bigcup \map F n\) | Set is Subset of Union | ||||||||

\(\displaystyle y\) | \(\in\) | \(\displaystyle x\) | Assumption | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\, \displaystyle \exists n: \, \) | \(\displaystyle y\) | \(\in\) | \(\displaystyle \bigcup \map F n\) | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\, \displaystyle \exists n: \, \) | \(\displaystyle y\) | \(\in\) | \(\displaystyle \map F {n + 1}\) | Definition of $F$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle y\) | \(\in\) | \(\displaystyle T\) | Definition of $T$ |

By the above equations:

- $x \in T \land y \in x \implies y \in T$

Thus by definition $T$ is transitive.

$\Box$

We have that:

- $S = \map F 0$

- $\displaystyle S \subseteq \bigcup_{n \mathop \in \omega} \map F n$

So $S \subseteq T$.

$\Box$

Finally, suppose that $S \subseteq R$ and $R$ is transitive.

$T \subseteq R$ follows by finite induction:

For all $n \in \omega$, let $\map P n$ be the proposition:

- $\map F n \subseteq R$

### Basis for the Induction

$\map P 0$ is the case:

- $\map F 0 \subseteq R$

which has been proved above.

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.

So this is our induction hypothesis:

- $\map F k \subseteq R$

Then we need to show:

- $\map F {k + 1} \subseteq R$

### Induction Step

This is our induction step:

\((1):\quad\) | \(\displaystyle \map F k\) | \(\subseteq\) | \(\displaystyle R\) | Hypothesis | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \bigcup \map F k\) | \(\subseteq\) | \(\displaystyle \bigcup R\) | Set Union Preserves Subsets | |||||||||

\((2):\quad\) | \(\displaystyle \) | \(\subseteq\) | \(\displaystyle R\) | Class is Transitive iff Union is Subset | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \map F k \cup \bigcup \map F k\) | \(\subseteq\) | \(\displaystyle R\) | by $(1)$, $(2)$, Set Union Preserves Subsets | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \map F {k + 1}\) | \(\subseteq\) | \(\displaystyle R\) | Definition of $\map F {k + 1}$ |

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

- $\map F n \subseteq R$ for all $n \in \omega$

- $T \subseteq R$

$\blacksquare$

## Sources

- 1971: Gaisi Takeuti and Wilson M. Zaring:
*Introduction to Axiomatic Set Theory*: $\S 9.1$