# Proof that the rationals are countable.

• Sep 27th 2011, 04:54 AM
hmmmm
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
• Sep 27th 2011, 05:19 AM
emakarov
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.
• Sep 27th 2011, 06:33 AM
hmmmm
Re: Proof that the rationals are countable.
ah, is there any way to modify this or is it just plain wrong
• Sep 27th 2011, 06:44 AM
Plato
Re: Proof that the rationals are countable.
Quote:

Originally Posted by hmmmm
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}$?
• Sep 27th 2011, 06:56 AM
emakarov
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}^+$.
• Sep 27th 2011, 12:20 PM
hmmmm
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
• Sep 27th 2011, 02:40 PM
emakarov
Re: Proof that the rationals are countable.
Quote:

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.
• Sep 27th 2011, 02:54 PM
hmmmm
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)
• Sep 27th 2011, 03:29 PM
emakarov
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}$).
• Sep 27th 2011, 03:35 PM
hmmmm
Re: Proof that the rationals are countable.
ok thanks very much for all the help