Successor Set of Ordinal is Ordinal

From ProofWiki
Jump to: navigation, search

Theorem

Let $S$ be an ordinal.

Then its successor set $S^+ = S \cup \set S$ is also an ordinal.


Proof

Since $S$ is transitive, it follows by Successor Set of Transitive Set is Transitive that $S^+$ is transitive.

We now have to show that $S^+$ is strictly well-ordered by the epsilon restriction $\Epsilon \! \restriction_{S^+}$.

So suppose that a subset $A \subseteq S^+$ is non-empty.

Then:

\(\displaystyle A\) \(=\) \(\displaystyle A \cap \paren {S \cup \set S}\) Intersection with Subset is Subset and Definition of Successor Set
\(\displaystyle \) \(=\) \(\displaystyle \paren {A \cap S} \cup \paren {A \cap \set S}\) Intersection Distributes over Union

Let us refer to the above equation by the symbol $\paren 1$.

We need to show that $A$ has a smallest element.


We first consider the case where $A \cap S$ is empty.

By equation $\paren 1$, it follows that $A \cap \set S$ is non-empty (because $A$ is non-empty).

Therefore, $S \in A$. That is, $\set S \subseteq A$.

By Union with Empty Set and Intersection with Subset is Subset, equation $\paren 1$ implies that $A \subseteq \set S$.

Therefore, $A = \set S$ by the definition of set equality.

So $S$ is the smallest element of $A$.


We now consider the case where $A \cap S$ is non-empty.

By Intersection is Subset, $A \cap S \subseteq S$; by the definition of a well-ordered set, there exists a smallest element $x$ of $A \cap S$.

Let $y \in A$.

If $y \in S$, then $y \in A \cap S$; therefore, by the definition of the smallest element, either $x \in y$ or $x = y$.

Otherwise, $y = S$, and so $x \in S = y$.

That is, $x$ is the smallest element of $A$.

$\blacksquare$


Sources