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

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.

Re: Proof that the rationals are countable.

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

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 $\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}$?

Re: Proof that the rationals are countable.

Consider reducing rational fractions to lowest terms.

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

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, $\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.

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)

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}$).

Re: Proof that the rationals are countable.

ok thanks very much for all the help