Relationship between Transitive Closure Definitions

From ProofWiki
Jump to: navigation, search


Theorem

Let $x$ be a set.

Let $a$ be the smallest set such that $x \in a$ and $a$ is transitive.

Let $b$ be the smallest set such that $x \subseteq b$ and $b$ is transitive.


Then $a = b \cup \left\{ {x}\right\}$.


Proof

We have that:

$x \in a$

and $a$ is transitive.

So:

$x \subseteq a$

Thus by the definition of $b$ and of smallest set:

$b \subseteq a$

Since we also have $x \in a$:

$b \cup \left\{ {x}\right\} \subseteq a$


$x \in \left\{ {x}\right\}$, so:

$x \in b \cup \left\{ {x}\right\}$

$b \cup \left\{ {x}\right\}$ is transitive:

If $p \in b$ then:

$p \subseteq b \subseteq b \cup \left\{ {x}\right\}$.

If $p \in \left\{ {x}\right\}$ then:

$p = x$

So by the definition of $b$:

$p \subseteq b \subseteq b \cup \left\{ {x}\right\}$

Thus by the definition of $a$:

$a \subseteq b \cup \left\{ {x}\right\}$

Thus the theorem holds by definition of set equality.

$\blacksquare$