Transitive Closure Always Exists (Set Theory)

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be a set.

Let $G$ be a mapping such that $G \left({x}\right) = x \cup \bigcup x$.



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

$F \left({0}\right) = S$
$F \left({n^+}\right) = G \left({F \left({n}\right)}\right)$


Let $\displaystyle T = \bigcup_{n \mathop \in \omega} F \left({n}\right)$.


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 $F \left({\omega}\right)$, it is thus a set by the Axiom of Union.


Furthermore:

\(\displaystyle x\) \(\in\) \(\displaystyle T\) $\quad$ Assumption $\quad$
\(\displaystyle \implies \ \ \) \(\, \displaystyle \exists n: \, \) \(\displaystyle x\) \(\in\) \(\displaystyle F \left({n}\right)\) $\quad$ Definition of Indexed Union $\quad$
\(\displaystyle \implies \ \ \) \(\, \displaystyle \exists n: \, \) \(\displaystyle x\) \(\subseteq\) \(\displaystyle \bigcup F\left({n}\right)\) $\quad$ Set is Subset of Union $\quad$
\(\displaystyle y\) \(\in\) \(\displaystyle x\) $\quad$ Assumption $\quad$
\(\displaystyle \implies \ \ \) \(\, \displaystyle \exists n: \, \) \(\displaystyle y\) \(\in\) \(\displaystyle \bigcup F \left({n}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\, \displaystyle \exists n: \, \) \(\displaystyle y\) \(\in\) \(\displaystyle F \left({n+1}\right)\) $\quad$ definition of $F$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle y\) \(\in\) \(\displaystyle T\) $\quad$ definition of $T$ $\quad$



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 = F \left({0}\right)$

By Set is Subset of Union:

$\displaystyle S \subseteq \bigcup_{n \mathop \in \omega} F \left({n}\right)$

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 $P \left({n}\right)$ be the proposition:

$F \left({n}\right) \subseteq R$


Basis for the Induction

$P \left({0}\right)$ is the case:

$F \left({0}\right) \subseteq R$

which has been proved above.

This is our basis for the induction.


Induction Hypothesis

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


So this is our induction hypothesis:

$F \left({k}\right) \subseteq R$


Then we need to show:

$F \left({k+1}\right) \subseteq R$


Induction Step

This is our induction step:


\((1):\quad\) \(\displaystyle F \left({k}\right)\) \(\subseteq\) \(\displaystyle R\) $\quad$ Hypothesis $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \bigcup F \left({k}\right)\) \(\subseteq\) \(\displaystyle \bigcup R\) $\quad$ by Set Union Preserves Subsets $\quad$
\((2):\quad\) \(\displaystyle \) \(\subseteq\) \(\displaystyle R\) $\quad$ by Class is Transitive iff Union is Subset $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle F \left({k}\right) \cup \bigcup F \left({k}\right)\) \(\subseteq\) \(\displaystyle R\) $\quad$ by $(1)$, $(2)$, Set Union Preserves Subsets $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle F \left({k+1}\right)\) \(\subseteq\) \(\displaystyle R\) $\quad$ Definition of $F \left({k+1}\right)$ $\quad$

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


Therefore:

$F \left({n}\right) \subseteq R$ for all $n \in \omega$
$T \subseteq R$

$\blacksquare$


Sources