Set Contained in Smallest Transitive Set

From ProofWiki
Jump to navigation Jump to search


Theorem

Let $S$ be a set.

Then there exists a transitive set $G$ such that:

$S \subseteq G$

and:

if $Q$ is any transitive set such that $S \subseteq Q$, then $G \subseteq Q$.


Proof

Construction of $G$

Let $U$ be the class of all sets.

Define the mapping $F: \N \to U$ recursively:

$F \left({0}\right) = S$
$F \left({n + 1}\right) = \bigcup F \left({n}\right)$

Applying the axiom of union inductively, $F \left({n}\right)$ is a set for each $n \in \N$.

Let $\displaystyle G = \bigcup_{i \mathop = 0}^\infty F \left({i}\right)$.

By the axiom of union, $G$ is a set.


Transitivity

It is to be proved that $G$ is transitive.

That is:

$a \in b, b \in G \implies a \in G$

Let $a \in b$ and $b \in G$.

By the definition of $G$, there exists $n \in \N$, $b \in F \left({n}\right)$.

By the definition of $F$:

$F \left({n + 1}\right) = \bigcup F \left({n}\right)$.

Then by the definition of union:

$a \in F \left({n + 1}\right)$

Thus by the definition of $G$:

$a \in G$.

$\Box$


Minimality

It is to be proved that if $Q$ is a transitive set and $S \subseteq Q$ then $G \subseteq Q$.



Let $Q$ be transitive and $S \subseteq Q$.

Define $F$ as above.

Prove by induction that $F \left({n}\right) \subseteq Q$ for each $n$.

$\blacksquare$