Results 1 to 10 of 10

Math Help - Proof that the rationals are countable.

  1. #1
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Proof that the rationals are countable.

    Is this proof ok?

    If I assume that the set of two-touples X \{(a,b):a,b\in \mathbb{N}\} is countable (which I think follows directly from the proof the the countable union of countable sets is countable).

    Can we make the natural bijection f:\mathbb{Q}^+\rightarrow X s.t.
    \frac{a}{b}\rightarrow (a,b). Then we can see that the positive rationals are countable.

    Making the similar bijection g:\mathbb{Q}^-\rightarrow X s.t.
    \frac{a}{b}\rightarrow (-a,b). Then we see that the negative rationals are countable.

    If we the take (\mathbb{Q}^+\bigcup \{0\}\bigcup\mathbb{Q}^-)=\mathbb{Q}, then as the countable union of countable sets is countable we have that $\mathbb{Q}$ is countable.

    Note: I make the bijection to the set of two-touples as it is countable, so it has a bijection to the natural numbers and the composition of bijhections is a bijection.

    Thanks for any help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof that the rationals are countable.

    The mapping f:\mathbb{Q}^+\to X, f\left(\frac{a}{b}\right)=(a,b) is not a function because it maps the same element of the domain into different elements of the codomain.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Proof that the rationals are countable.

    ah, is there any way to modify this or is it just plain wrong
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1785
    Awards
    1

    Re: Proof that the rationals are countable.

    Quote Originally Posted by hmmmm View Post
    ah, is there any way to modify this or is it just plain wrong
    Here is one way to show that \mathbb{N}\times\mathbb{N} is countable: define f(a,b)=2^a\cdot 3^b. Show that f is an injection.
    Subsets of countable sets are countable. Can you identify the positive rationals with a subset of \mathbb{N}\times\mathbb{N}?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof that the rationals are countable.

    Consider reducing rational fractions to lowest terms.

    Spoiler:
    Suppose 0 is not in \mathbb{N}. There is a natural injection \mathbb{N}\to\mathbb{Q}^+. Conversely, \left(\frac{a}{b}\right)\mapsto(a,b) where \frac{a}{b} is in lowest terms is an injection from \mathbb{Q}^+ to \mathbb{N}\times\mathbb{N}\equiv\mathbb{N}. Therefore, by Cantor–Bernstein–Schroeder theorem,  \mathbb{Q}^+\equiv\mathbb{N}.

    Alternatively, in addition to the injection \mathbb{N}\to\mathbb{Q}^+, there is a surjection \mathbb{N}\times\mathbb{N}\to\mathbb{Q}^+.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Proof that the rationals are countable.

    Ah ok thanks very much I get that.

    However you said that the mapping is not a bijection as it sends the same element to different elements of the set X e.g. \frac{2}{2}\ \mbox{and}\ 1 go to different elements but is this not some extra structure specific the rationals?

    If we didn't consider this structure is this a bijection? because then the reduced rationals would be a subset of this?

    thanks for any help
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof that the rationals are countable.

    If we didn't consider this structure is this a bijection?
    I need more specifics to answer. What exactly is the domain of the alleged bijection? If the domain is the set of all fractions in lowest terms, \left(\frac{a}{b}\right)\mapsto(a,b) is an injection but not a surjection: e.g., (2, 2) is not in the image.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Proof that the rationals are countable.

    Sorry for not being too clear

    I meant when you said that my origional mapping f:\mathbb{Q}^+\rightarrow X\ s.t. \frac{a}{b}\rightarrow (a,b) was not a bijection (as it was not a function) because it takes the same elements in  \mathbb{Q}^+ to different elements in X for example  \frac{2}{2}\ \mbox{and}\ \frac{1}{1}.

    I was asking if we could not just consider the set of all fractions where  \frac{2}{2}\ \mbox{and}\ \frac{1}{1} are distinct elements, and then create the bijection as before. We would then have that this set is countable and that \mathbb{Q}^+ is a subset of this set and is so countable?

    thanks for any help (sorry if I am not being that clear)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof that the rationals are countable.

    The set of all fractions where  \frac{2}{2}\ \mbox{and}\ \frac{1}{1} are distinct elements seems to be the same as \mathbb{N}\times\mathbb{N}. We just write \frac{a}{b} instead of (a, b). So you could directly show that \mathbb{Q}^+ is a subset of \mathbb{N}\times\mathbb{N} (or, more precisely, that there is an injection from \mathbb{Q}^+ to \mathbb{N}\times\mathbb{N}).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Dec 2008
    Posts
    288

    Re: Proof that the rationals are countable.

    ok thanks very much for all the help
    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, 08:08 AM
  2. Replies: 1
    Last Post: February 9th 2010, 02:51 PM
  3. [SOLVED] Rationals and countable intersection of open sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 8th 2010, 07:16 PM
  4. Sum of three squares of rationals (proof)
    Posted in the Algebra Forum
    Replies: 7
    Last Post: April 12th 2009, 09:26 AM
  5. proof by induction on rationals
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 22nd 2009, 12:00 PM

Search Tags


/mathhelpforum @mathhelpforum