# Thread: well ordering

1. ## well ordering

Prove: Let $X \subset \bold{N}$. Then $X$ is at most countable. Let $A_{0} := X$, and let $a_{0} := \min(A_{0})$. Then $A_{n++} := A_{n} - \{a_{n} \}$ and $a_{n++} := \min(A_{n++})$. So basically after removing the first smallest element, $a_0$, then $a_1$ is the second smallest element, etc.. Is this on the right track? Could I maybe let $a_{0} := \max(A_0)$, and $A_{n++} := A_{n}- \{a_{n}\}$ and $a_{n++} := \max(A_{n++})$ (e.g. take away the maximum elements)?

2. Originally Posted by particlejohn
Prove: Let $X \subset \bold{N}$. Then $X$ is at most countable.
$X$ is either finite or infinite. If $X$ is finite then by definition there is a bijection $f: X\to n$. And there is an injection $g:n\mapsto \mathbb{N}$. Then $g\circ f: X\mapsto \mathbb{N}$ is an injection and so $X$ is at most countable. Thus, it is safe to assume $X$ is infinite. Define the sequence $a_0 = \min (X)$ and $a_{n+1} = X - \min \{ a_k | k \leq n\}$. There are two reasons why such a sequence exists. One, we assumed that $X$ is infinite and therefore its elements never get exhausted at any finite stage. Two, the existence of such a function is gaurentted by the Recursion Theorem. Now argue that $\{ a_n | n\in \mathbb{N} \} = X$ (argue by contradiction). Also the function $a:\mathbb{N}\mapsto X$ is one-to-one by construction. Thus, $|\mathbb{N}| = |X|$. And this completes the proof.