Friday, November 11, 2011

Ordinals and the natural numbers

1Ordinals¶

1.1Elements of ordinals¶

Proof that any element of any ordinal is also an ordinal.

Suppose $a \in A$ where $A$ is an ordinal.

Claim: $a$ is also an ordinal.

Proof: First, $a$ is transitive. ie: if $y \in x \in a \to y \in a$. Now we check the other properties:

• Irreflexivity: No $b \in a$ satisfies $b \in b$. If $b \in a$, then $b \in A$ so $b \notin b$.
• Antisymmetry: Suppose $b,c \in a$ then $b, c \in A$, so we can't have $b \in c \land c \in b$.
• Transitivity: Suppose $b,c,d \in a, b \in c \land c \in d$. Then $b,c,d \in A$. So $b \in d$ (since $\in$ is transitive on $A$).
• Totality: Say $b,c \in a$ then $b,c \in A$. So $b \in c \lor b = c \lor c \in b$.
• Well-foundedness: Suppose $B \subseteq a \land B \neq 0$. So $B \subseteq A$. So there is an element $b \in B$ such that no $c \in B$ is an element of $b$. $\blacksquare$

We usually use $\alpha, \beta, \gamma, \sigma$ for ordinals.

Also, when $\alpha \in \beta$ we often just write $\alpha < \beta$

1.2Relatedness of ordinals¶

Claim: Suppose $\alpha, \beta$ are ordinals, then $\alpha \in \beta$ or $\alpha = \beta$ or $\beta \in \alpha$

Proof: by counterexample

Suppose $\alpha, \beta$ is a counterexample. Consider $A \subseteq S \alpha$ such that $x \in A \iff \exists$ ordinal $y$ such
that $x \notin y$ and $y \neq x$ and $y \notin x$.

Since $\alpha \in A$, $A \neq \varnothing$.

Let $a_0$ be the smallest element of $A$.

Choose $\beta_1$ ordinal such that $a_0 \notin \beta_1$ or $\alpha_0 \neq \beta_1$ or $\beta_1 \notin \alpha_0$.

Let $\beta_0$ be the smallest element of $B = \{y \in S\beta_1, \alpha_0 \notin y, \alpha_0 \neq y, y \notin \alpha_0)$.

We can now show $\alpha_0 \subseteq \beta_0$. Say $\sigma \in \alpha_0$. Then $\sigma \notin A (\sigma \in S \alpha)$.

So $\sigma \in \beta_0$ or $\sigma = \beta_0$ or $\beta_0 \in \sigma$.

$\sigma = \beta_0$ is out ($\beta_0 \notin \alpha_0)$.

$\beta_0 \in \sigma$ is out (otherwise $\beta_0 \in \sigma \in \alpha_0$ so $\beta_0 \in \alpha_0$).

So $\sigma \in \beta_0$ (so $\alpha \subseteq \beta_0$).

Say $\delta \in \beta_0$ ($\delta\in B$).

So $\delta \in \alpha_0$ or $\delta = \alpha_0$ or $\alpha_0 \in \delta$.

$\delta = \alpha_0$ is out since $\alpha_0 \notin \beta_0$.

$\alpha_0 \in \delta$ is out because if true $\alpha_0 \in \delta \in \beta_0 \to \alpha_0 \in \beta_0$.

So $\delta \in \alpha_0$.

This implies $\beta_0 \subseteq \alpha_0$. This then implies $\alpha_0 = \beta_0$, our final contradiction. $\blacksquare$

1.3The natural numbers¶

A set $X$ is called inductive if $\varnothing \in X$ and whenever $x \in X$, then $Sx \in X = (x \cup \{x\})$

$n$ is a natural number if

1. $n$ is an ordinal
2. $n$ is an element of every inductive set

(the axiom of infinity says $\exists x(x $ is inductive $)$

Fact: If there is an inductive $X$, then there is a smallest such set.

ie: there is $\omega$ such that

1. $\omega$ is inductive
2. for any inductive $Y, \omega \subseteq Y$

Proof: Let $\omega$ be $x \in X:$ x is an element of every inductive set $\}$ (given $X$ this exists due to comprehension).

$0 \in \omega$ in $0 \in X$ and $0 \in $ every inductive set.

Suppose $x \in \omega$, then $x \in X$ and $x$ in Y.

So $Sx \in X$ and $Sx$ is in Y

So $Sx \in \omega$

So $\omega$ is inductive.

Suppose $x \in \omega$ and Y is an inductive set then $x \in Y$ so $\omega \subset Y$

Given $\omega$, I claim all its elements are ordinals.

0 is an ordinal.

Consider $\{x \in \omega:$ x is an ordinal $\} = A$

$A \subset \omega$

I claim $A$ is inductive.

$0 \in A$

If $x \in A$, then $x \in \omega$ and $x$ is an ordinal. So $Sx \in \omega$ and $Sx$ is an ordinal. So $Sx \in A$. $A$ is inductive.

Hence $\omega \subset A$. So $\omega = A$

Finiteness: A set $x$ is finite if there is a bijection between $x$ and a natural number. (If $x$ is not finite, it is infinite)

Fact: $\omega$ is infinite (if it exists)

It is, in a sense, the smallest infinite set.

Claim: If $A \subset \omega$ is not finite there is a bijection between $f: \omega \to A$

Rough "proof" A has a smallest element $a_0$

$f(0) = a_0$

$A \backslash \{a_0\} \neq \varnothing$ so it has a smallest element ($a_1$).

Let $f(1) = a_1$.

Generally given, $a_0, \ldots, a_n \in A$

$A \backslash \{a_0, \ldots, a_n\}$ has a smallest element.

Let $f(n) = a_n$ for all $n \in \omega$

We say $A,B$ have the same cardinality (or size) $A \sim B$ if there is a bijection $f: A \to B$ (onto)

$\omega \sim \mathbb{Z} \sim \mathbb{Q}$. That is $\omega$ is the same size as the integers and the rationals.

For any set $A, A \not \sim \mathcal{P}(A)$