Equivalence of Definitions of Ordinal

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Ordinal are equivalent:

Definition 1

Let $S$ be a set.

Let $\Epsilon \! \restriction_S$ be the restriction of the epsilon relation on $S$.


Then $S$ is an ordinal if and only if:

$S$ is a transitive set
$\Epsilon \! \restriction_S$ strictly well-orders $S$.


Definition 2

Let $A$ be a set.

Then $A$ is an ordinal if and only if $A$ is:

transitive
epsilon-connected, that is:
$\forall x, y \in A: x \ne y \implies x \in y \lor y \in x$
well-founded


Definition 3

An ordinal is a strictly well-ordered set $\struct {S, \prec}$ such that:

$\forall a \in S: S_a = a$

where $S_a$ is the initial segment of $S$ determined by $a$.


From the definition of an initial segment, and Ordering on Ordinal is Subset Relation, we have that:

$S_a = \set {x \in S: x \subsetneqq a}$


From Initial Segment of Ordinal is Ordinal we have that $S_a$ is itself an ordinal.


Proof

Definition 1 is equivalent to Definition 2

This follows immediately from the definition of a strict well-ordering.

$\Box$


Definition 1 implies Definition 3

Let $S$ be an ordinal according to Definition 1.

Let $a \in S$.

Then:

\(\displaystyle S_a\) \(=\) \(\displaystyle \left\{ {x \in S: x \in_S a}\right\}\) Definition of Initial Segment
\(\displaystyle \) \(=\) \(\displaystyle \left\{ { x: x \in S \land x \in a}\right\}\)
\(\displaystyle \) \(=\) \(\displaystyle S \cap a\) Definition of Set Intersection
\(\displaystyle \) \(=\) \(\displaystyle a\) as $a \subseteq S$ by transitivity

$\Box$


Definition 3 implies Definition 1

Let $\left({S, \prec}\right)$ be an ordinal according to Definition 3.

Let $a \in S$.

Then $a = S_a \subseteq S$ and so $S$ is transitive.


Also, by the definition of set equality:

\(\displaystyle \forall x: x \in a\) \(\iff\) \(\displaystyle x \in S_a\)
\(\displaystyle \iff \ \ \) \(\displaystyle \forall x: x \in a\) \(\iff\) \(\displaystyle \left({x \in S \land x \prec a}\right)\)


It has been shown that if $x, a \in S$ then:

$x \in a \iff x \prec a$


Therefore, $\prec \; = \left({S, S, R}\right)$ where

\(\displaystyle R\) \(=\) \(\displaystyle \left\{ {\left({x, a}\right) \in S \times S: x \prec a}\right\}\)
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {\left({x, a}\right) \in S \times S: x \in a}\right\}\)
\(\displaystyle \) \(=\) \(\displaystyle \in_S\) Definition of Epsilon Restriction

Hence $\prec \; = \Epsilon {\restriction_S}$.

$\blacksquare$


Sources