Equivalence of Definitions of Transitive Closure (Set Theory)

From ProofWiki
Jump to: navigation, search


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$



Thus:

$\displaystyle \bigcup G \left({n}\right) \subseteq m$

$\Box$


By Smallest Element is Unique, $x^t$ is the only set satisfying $(2)$.

$\blacksquare$