Alternative Definition of Ordinal in Well-Founded Theory

From ProofWiki
Jump to navigation Jump to search

Theorem

A set $S$ is an ordinal if and only if $S$ is transitive and $\forall x, y \in S: \paren {x \in y \lor x = y \lor y \in x}$.


Proof

Forward Implication

Let $S$ be an ordinal.

By Alternative Definition of Ordinal, $S$ is transitive and strictly well-ordered by the epsilon relation.

By Strict Well-Ordering is Strict Total Ordering, $S$ is strictly totally ordered by $\in$.

Thus:

$\forall x, y \in S: \paren {x \in y \lor x = y \lor y \in x}$

$\Box$


Reverse Implication

Let $S$ be a transitive set such that for any $x, y \in S$, $x \in y \lor y \in x \lor x = y$.

We first show that $\in$ is a strict ordering of $S$.


Asymmetric
Let $x, y \in S$.

By Epsilon Relation is Strictly Well-Founded, $\set {x, y}$ has a strictly minimal element under $\in$.

Thus $x \notin t$ or $y \notin x$.


Transitive
Let $x, y, z \in S$ with $x \in y$ and $y \in z$.

By assumption, $x = z$, $x \in z$, or $z \in x$.

Aiming for a contradiction, suppose that $x = z$.

Then $x \in y$ and $y \in x$, contradicting the fact that $\Epsilon$ is asymmetric.

Suppose that $z \in x$.

Then $x \in y$, $y \in z$, and $z \in x$.

Thus the set $\set {x, y, z}$ has no strictly minimal element under $\Epsilon$, contradicting Epsilon Relation is Strictly Well-Founded.

Thus $x \in z$.

Thus $\in$ is a strict ordering of $S$.


Let $T$ be a non-empty subset of $S$.

By Epsilon Relation is Strictly Well-Founded, $T$ has a strictly minimal element $m$ under $\Epsilon$.

From Strictly Minimal Element is Minimal Element, $m$ is a minimal element of $T$ under $\Epsilon$.

From Minimal Element in Toset is Unique and Smallest, $m$ is the smallest element of $T$.

It follows by definition that $\Epsilon$ strictly well-orders $S$.

Thus by Alternative Definition of Ordinal, $S$ is an ordinal.

$\blacksquare$


Also see


Sources