Transitive Closure Always Exists (Set Theory)

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Transitive_Closure_Always_Exists_(Set_Theory)&oldid=578496"