If I assume that the set of two-touples 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 s.t. . Then we can see that the positive rationals are countable.

Making the similar bijection s.t. . Then we see that the negative rationals are countable.

If we the take , 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, 06:19 AM

emakarov

Re: Proof that the rationals are countable.

The mapping , is not a function because it maps the same element of the domain into different elements of the codomain.

Sep 27th 2011, 07: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, 07: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 is countable: define . Show that is an injection.
Subsets of countable sets are countable. Can you identify the positive rationals with a subset of ?

Sep 27th 2011, 07:56 AM

emakarov

Re: Proof that the rationals are countable.

Consider reducing rational fractions to lowest terms.

Spoiler:

Suppose 0 is not in . There is a natural injection . Conversely, where is in lowest terms is an injection from to . Therefore, by Cantor–Bernstein–Schroeder theorem, .

Alternatively, in addition to the injection , there is a surjection .

Sep 27th 2011, 01: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. 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, 03: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, is an injection but not a surjection: e.g., (2, 2) is not in the image.

Sep 27th 2011, 03: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 was not a bijection (as it was not a function) because it takes the same elements in to different elements in X for example .

I was asking if we could not just consider the set of all fractions where are distinct elements, and then create the bijection as before. We would then have that this set is countable and that 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, 04:29 PM

emakarov

Re: Proof that the rationals are countable.

The set of all fractions where are distinct elements seems to be the same as . We just write instead of . So you could directly show that is a subset of (or, more precisely, that there is an injection from to ).