Results 1 to 2 of 2

Math Help - well ordering

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

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

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by particlejohn View Post
    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.
    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: September 8th 2010, 04:04 AM
  3. well ordering principle
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 18th 2009, 02:18 PM
  4. well-ordering
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 10th 2009, 10:24 AM
  5. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 08:13 AM

Search Tags


/mathhelpforum @mathhelpforum