Prove: Let $\displaystyle X \subset \bold{N}$. Then $\displaystyle X$ is at most countable. Let $\displaystyle A_{0} := X$, and let $\displaystyle a_{0} := \min(A_{0})$. Then $\displaystyle A_{n++} := A_{n} - \{a_{n} \}$ and $\displaystyle a_{n++} := \min(A_{n++})$. So basically after removing the first smallest element, $\displaystyle a_0$, then $\displaystyle a_1$ is the second smallest element, etc.. Is this on the right track? Could I maybe let $\displaystyle a_{0} := \max(A_0)$, and $\displaystyle A_{n++} := A_{n}- \{a_{n}\}$ and $\displaystyle a_{n++} := \max(A_{n++})$ (e.g. take away the maximum elements)?
Prove: Let $\displaystyle X \subset \bold{N}$. Then $\displaystyle X$ is at most countable.
$\displaystyle X$ is either finite or infinite. If $\displaystyle X$ is finite then by definition there is a bijection $\displaystyle f: X\to n$. And there is an injection $\displaystyle g:n\mapsto \mathbb{N}$. Then $\displaystyle g\circ f: X\mapsto \mathbb{N}$ is an injection and so $\displaystyle X$ is at most countable. Thus, it is safe to assume $\displaystyle X$ is infinite. Define the sequence $\displaystyle a_0 = \min (X)$ and $\displaystyle a_{n+1} = X - \min \{ a_k | k \leq n\}$. There are two reasons why such a sequence exists. One, we assumed that $\displaystyle 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 $\displaystyle \{ a_n | n\in \mathbb{N} \} = X$ (argue by contradiction). Also the function $\displaystyle a:\mathbb{N}\mapsto X$ is one-to-one by construction. Thus, $\displaystyle |\mathbb{N}| = |X|$. And this completes the proof.