Proof that the rationals are countable.

**hmmmm** · September 27th 2011, 04:54 AM

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

**emakarov** · September 27th 2011, 05:19 AM

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.

**hmmmm** · September 27th 2011, 06:33 AM

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

**Plato** · September 27th 2011, 06:44 AM

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

**emakarov** · September 27th 2011, 06:56 AM

Consider reducing rational fractions to lowest terms.

Spoiler:

**hmmmm** · September 27th 2011, 12:20 PM

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

**emakarov** · September 27th 2011, 02:40 PM

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.

**hmmmm** · September 27th 2011, 02:54 PM

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)

**emakarov** · September 27th 2011, 03:29 PM

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

**hmmmm** · September 27th 2011, 03:35 PM

ok thanks very much for all the help

Thread: Proof that the rationals are countable.

LinkBack

Thread Tools

Display

Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Re: Proof that the rationals are countable.

Similar Math Help Forum Discussions

Second countable, countable, proof...

Proof that the intersection of infinitely many countable sets is countable.

[SOLVED] Rationals and countable intersection of open sets

Sum of three squares of rationals (proof)

proof by induction on rationals

Search Tags