# Thread: Proof that the rationals are countable.

1. ## Proof that the rationals are countable.

Is this proof ok?

If I assume that the set of two-touples $\displaystyle 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 $\displaystyle f:\mathbb{Q}^+\rightarrow X$ s.t.
$\displaystyle \frac{a}{b}\rightarrow (a,b)$. Then we can see that the positive rationals are countable.

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

If we the take $\displaystyle (\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

2. ## Re: Proof that the rationals are countable.

The mapping $\displaystyle f:\mathbb{Q}^+\to X$, $\displaystyle 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.

3. ## Re: Proof that the rationals are countable.

ah, is there any way to modify this or is it just plain wrong

4. ## Re: Proof that the rationals are countable.

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 $\displaystyle \mathbb{N}\times\mathbb{N}$ is countable: define $\displaystyle f(a,b)=2^a\cdot 3^b$. Show that $\displaystyle f$ is an injection.
Subsets of countable sets are countable. Can you identify the positive rationals with a subset of $\displaystyle \mathbb{N}\times\mathbb{N}$?

5. ## Re: Proof that the rationals are countable.

Consider reducing rational fractions to lowest terms.

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

Alternatively, in addition to the injection $\displaystyle \mathbb{N}\to\mathbb{Q}^+$, there is a surjection $\displaystyle \mathbb{N}\times\mathbb{N}\to\mathbb{Q}^+$.

6. ## 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. $\displaystyle \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

7. ## 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, $\displaystyle \left(\frac{a}{b}\right)\mapsto(a,b)$ is an injection but not a surjection: e.g., (2, 2) is not in the image.

8. ## Re: Proof that the rationals are countable.

Sorry for not being too clear

I meant when you said that my origional mapping $\displaystyle 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 $\displaystyle \mathbb{Q}^+$ to different elements in X for example $\displaystyle \frac{2}{2}\ \mbox{and}\ \frac{1}{1}$.

I was asking if we could not just consider the set of all fractions where $\displaystyle \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 $\displaystyle \mathbb{Q}^+$ is a subset of this set and is so countable?

thanks for any help (sorry if I am not being that clear)

9. ## Re: Proof that the rationals are countable.

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

10. ## Re: Proof that the rationals are countable.

ok thanks very much for all the help