Transitive Closure Always Exists (Set Theory)
Theorem
Let $S$ be a set.
Let $G$ be a mapping such that $\map G x = x \cup \bigcup x$.
This article, or a section of it, needs explaining. In particular: Domain and range of $G$ needed You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code. |
Let $F$ be defined using the Principle of Recursive Definition:
- $\map F 0 = S$
- $\map F {n^+} = \map G {\map F n}$
Let $\ds 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:
\(\ds x\) | \(\in\) | \(\ds T\) | Assumption | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists n: \, \) | \(\ds x\) | \(\in\) | \(\ds \map F n\) | Definition of Union of Family | |||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists n: \, \) | \(\ds x\) | \(\subseteq\) | \(\ds \bigcup \map F n\) | Set is Subset of Union of Family | |||||||||
\(\ds y\) | \(\in\) | \(\ds x\) | Assumption | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists n: \, \) | \(\ds y\) | \(\in\) | \(\ds \bigcup \map F n\) | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists n: \, \) | \(\ds y\) | \(\in\) | \(\ds \map F {n + 1}\) | Definition of $F$ | |||||||||
\(\ds \leadsto \ \ \) | \(\ds y\) | \(\in\) | \(\ds T\) | Definition of $T$ |
This article, or a section of it, needs explaining. In particular: domain of $n$ You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code. |
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$
By Set is Subset of Union of Family:
- $\ds 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:
\(\text {(1)}: \quad\) | \(\ds \map F k\) | \(\subseteq\) | \(\ds R\) | Hypothesis | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \bigcup \map F k\) | \(\subseteq\) | \(\ds \bigcup R\) | Set Union Preserves Subsets | ||||||||||
\(\text {(2)}: \quad\) | \(\ds \) | \(\subseteq\) | \(\ds R\) | Class is Transitive iff Union is Subclass | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \map F k \cup \bigcup \map F k\) | \(\subseteq\) | \(\ds R\) | by $(1)$, $(2)$, Set Union Preserves Subsets | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \map F {k + 1}\) | \(\subseteq\) | \(\ds 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$