Equivalence of Definitions of Transitive Closure (Set Theory)
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 \set x$ by the definition of singleton.
Since $\map G 0 = \set 0$:
- $\set x \in \map G \N$
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 Unions.
$\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 \map G n$
Then by definition of union:
- $\displaystyle z \in \bigcup \map G n$
But by the definition of $G$:
- $z \in \map G {n^+}$
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 $\map G n \subseteq m$ for each $n \in \N$.
By Union is Smallest Superset, that will show that $x^t \subseteq m$.
Because $x \in m$:
- $\map G 0 = \set x \subseteq m$
Suppose that $\map G n \subseteq m$.
Then by Union is Increasing:
- $\displaystyle \bigcup \map G n \subseteq \bigcup m$
Thus:
- $\displaystyle \bigcup \map G n \subseteq m$
$\Box$
By Smallest Element is Unique, $x^t$ is the only set satisfying $(2)$.
$\blacksquare$