Results 1 to 5 of 5

Math Help - countable rational endpoints proof

  1. #1
    Senior Member
    Joined
    Jan 2008
    From
    Montreal
    Posts
    311
    Awards
    1

    countable rational endpoints proof

    Show that a set consisting of open intervals with rational endpoints is countable.

    I was thinking of applying the Cantor Diagonal Argument then claiming that the given interval is a subset of all rationals. Would this be a correct assumption?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by lllll View Post
    Show that a set consisting of open intervals with rational endpoints is countable.

    I was thinking of applying the Cantor Diagonal Argument then claiming that the given interval is a subset of all rationals. Would this be a correct assumption?
    Proof Sketch:

    1. The rationals are countable

    2. The set of open intervals with rational end points is equivalent in the obvious way to a subset of the set of all ordered pairs of rationals.

    3. Because of 1. there is a 1-1 onto map from NxN to QxQ.

    4. NxN is countable hence there is a 1-1 onto map from N to NxN

    5. from 4. and 3. there is a 1-1 onto map from N to QxQ, hence QxQ is countable.

    6. A subset of a countable set is countable hence; the set of open intervals with rational end points is countable.

    (proof of 4. is an easy modification of the usual proof of the countability of Q).

    (note the "1-1" wherever it appears above is redundant "onto" will do, but its more intuitive if we leave the "1-1" conditions in)

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2008
    From
    Montreal
    Posts
    311
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post

    2. The set of open intervals with rational end points is equivalent in the obvious way to a subset of the set of all ordered pairs of rationals.
    how is this obvious?

    Quote Originally Posted by CaptainBlack View Post
    3. Because of 1. there is a 1-1 onto map from NxN to QxQ.
    I have no clue on how to show that they map to each other, but I do have a proof showing that \mathbb{N}\times \mathbb{N} and [tex]\mathbb{Q}\times \mathbb{Q}[/Math] are countable.

    Quote Originally Posted by CaptainBlack View Post
    4. NxN is countable hence there is a 1-1 onto map from N to NxN

    5. from 4. and 3. there is a 1-1 onto map from N to QxQ, hence QxQ is countable.
    From what I said about 4, do I still have to show these, or can I just apply the proofs that I have, which would make 3 redundant... right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post

    2. The set of open intervals with rational end points is equivalent in the obvious way to a subset of the set of all ordered pairs of rationals.
    how is this obvious?
    From what else you write this is really all we ned to show.

    Let the end points of the rational interval be q_1 and q_2 with q_1<q_2, then we introduce a map f which takes the interval (q_1,q_2) to the ordered pair (q_1,q_2) . This is a 1-1 map of the intervals to a subset of the set of ordered pairs.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by lllll View Post
    I have no clue on how to show that they map to each other, but I do have a proof showing that \mathbb{N}\times \mathbb{N} and \mathbb{Q}\times \mathbb{Q} are countable.
    Countability of two infinite sets implies the existance of such a map between the sets.

    (there are 1-1 onto maps from the naturals to each set, which are of neccesity are invertable and so the composition of one of these with the inverse of the other provides the required map between the sets)

    (If you are operating with a definition of countably infinite as there being a map from N onto the set, or some other definition, you will need the proof that there is a 1-1 map that does the same job. Being rather literal minded I work with enumerable as meaning there is an enumeration which for an infinite set inplies a 1-1 onto map)

    RonL
    Last edited by CaptainBlack; October 8th 2008 at 08:49 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Second countable, countable, proof...
    Posted in the Differential Geometry Forum
    Replies: 13
    Last Post: February 18th 2011, 07:08 AM
  2. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  3. Covering rational numbers by countable open intervals
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: September 26th 2009, 06:44 PM
  4. proof of countable
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2008, 11:30 AM
  5. Proof (countable)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 13th 2007, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum