Equivalence of Definitions of Transitive Closure (Set Theory)
Use standard technique to structure definition equivalence proof.
Until this has been finished, please leave {{refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
Establish the differences between the two definitions, which apparently are not exactly equivalent really.
You can help Proof Wiki by redesigning it.
To discuss this proof in more detail, feel free to use the talk page.
If you are able to fix this proof, then when you have done so you can remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your improvement is correct, add an invitation to {{Proofread}} the page (see the proofread template for usage).
Contents
Theorem
Let $x$ and $y$ be sets.
The following definitions of the concept of Transitive Closure in the context of Set Theory are equivalent:
Definition 1
Let $x$ be a set.
Then the transitive closure of $x$ is the smallest transitive superset of $x$.
Definition 2
Let $x$ be a set.
For each natural number $n \in \N_{\ge 0}$ let:
- $\bigcup^n x = \underbrace{\bigcup \bigcup \cdots \bigcup}_n x$
Then the transitive closure of $x$ is the union of the sets:
- $\left\{ {x}\right\}, x, \bigcup x, \bigcup^2 x, \dots, \bigcup^n x, \dots$
Proof
Let $x^t$ be the transitive closure of $x$ by Definition 2.
Let the mapping $G$ be defined as on that definition page.
$x \in x^t$
$x \in \left\{{x}\right\}$ by the definition of singleton.
Since $G \left({0}\right) = \left\{{0}\right\}$:
- $\left\{{x}\right\} \in G \left({\N}\right)$
Thus $x \in x^t$ by the definition of union.
$\Box$
$x^t$ is a Set
By Denumerable Class is Set, the image of $G$ is a set.
Thus $x^t$ is a set by the Axiom of Union.
$\Box$
$x^t$ is a Transitive Set
Let $y \in x^t$ and let $z \in y$.
By the definition of $x^t$:
- $\exists n \in \N: y \in G \left({n}\right)$
Then by definition of union:
- $\displaystyle z \in \bigcup G \left({n}\right)$
But by the definition of $G$:
- $z \in G \left({n^+}\right)$
Thus by the definition of $x^t$:
- $z \in x^t$
As this holds for all such $y$ and $z$, $x^t$ is transitive.
$\Box$
$x^t$ is Smallest
Let $m$ be a transitive set such that $x \in m$.
We will show by induction that $G \left({n}\right) \subseteq m$ for each $n \in \N$.
By Union is Smallest Superset, that will show that $x^t \subseteq m$.
Because $x \in m$:
- $G \left({0}\right) = \left\{{x}\right\} \subseteq m$
Suppose that $G \left({n}\right) \subseteq m$.
Then by Union is Increasing:
- $\displaystyle \bigcup G \left({n}\right) \subseteq \bigcup m$
Transitive set includes its union.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this point in more detail, feel free to use the talk page.
If you are able to explain it, then when you have done so you can remove this instance of {{Explain}} from the code.
Thus:
- $\displaystyle \bigcup G \left({n}\right) \subseteq m$
$\Box$
By Smallest Element is Unique, $x^t$ is the only set satisfying $(2)$.
$\blacksquare$
