well ordering

**particlejohn** · July 17th 2008, 09:23 AM

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)?

**ThePerfectHacker** · July 17th 2008, 10:16 AM

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.

Thread: well ordering

LinkBack

Thread Tools

Display

well ordering

Similar Math Help Forum Discussions

help with well ordering principle

Well Ordering

well ordering principle

well-ordering

Well-Ordering

Search Tags