Results 1 to 2 of 2

Thread: well ordering

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

    well ordering

    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)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by particlejohn View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help with well ordering principle
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: May 23rd 2011, 02:40 PM
  2. Well Ordering
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Sep 8th 2010, 04:04 AM
  3. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Aug 18th 2009, 02:18 PM
  4. well-ordering
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 10th 2009, 10:24 AM
  5. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 15th 2008, 08:13 AM

Search Tags


/mathhelpforum @mathhelpforum