Thread: countable rational endpoints proof

Show that a set consisting of open intervals with rational endpoints is countable.

I was thinking of applying the Cantor Diagonal Argument then claiming that the given interval is a subset of all rationals. Would this be a correct assumption?

Originally Posted by lllll

Show that a set consisting of open intervals with rational endpoints is countable.

I was thinking of applying the Cantor Diagonal Argument then claiming that the given interval is a subset of all rationals. Would this be a correct assumption?

Proof Sketch:

1. The rationals are countable

2. The set of open intervals with rational end points is equivalent in the obvious way to a subset of the set of all ordered pairs of rationals.

3. Because of 1. there is a 1-1 onto map from NxN to QxQ.

4. NxN is countable hence there is a 1-1 onto map from N to NxN

5. from 4. and 3. there is a 1-1 onto map from N to QxQ, hence QxQ is countable.

6. A subset of a countable set is countable hence; the set of open intervals with rational end points is countable.

(proof of 4. is an easy modification of the usual proof of the countability of Q).

(note the "1-1" wherever it appears above is redundant "onto" will do, but its more intuitive if we leave the "1-1" conditions in)

RonL

Originally Posted by CaptainBlack

2. The set of open intervals with rational end points is equivalent in the obvious way to a subset of the set of all ordered pairs of rationals.

how is this obvious?

Originally Posted by CaptainBlack

3. Because of 1. there is a 1-1 onto map from NxN to QxQ.

I have no clue on how to show that they map to each other, but I do have a proof showing that and [tex]\mathbb{Q}\times \mathbb{Q}[/Math] are countable.

Originally Posted by CaptainBlack

4. NxN is countable hence there is a 1-1 onto map from N to NxN

5. from 4. and 3. there is a 1-1 onto map from N to QxQ, hence QxQ is countable.

From what I said about 4, do I still have to show these, or can I just apply the proofs that I have, which would make 3 redundant... right?

Originally Posted by CaptainBlack

2. The set of open intervals with rational end points is equivalent in the obvious way to a subset of the set of all ordered pairs of rationals.

how is this obvious?

From what else you write this is really all we ned to show.

Let the end points of the rational interval be and with , then we introduce a map which takes the interval to the ordered pair . This is a 1-1 map of the intervals to a subset of the set of ordered pairs.

RonL

Originally Posted by lllll

I have no clue on how to show that they map to each other, but I do have a proof showing that and are countable.

Countability of two infinite sets implies the existance of such a map between the sets.

(there are 1-1 onto maps from the naturals to each set, which are of neccesity are invertable and so the composition of one of these with the inverse of the other provides the required map between the sets)

(If you are operating with a definition of countably infinite as there being a map from N onto the set, or some other definition, you will need the proof that there is a 1-1 map that does the same job. Being rather literal minded I work with enumerable as meaning there is an enumeration which for an infinite set inplies a 1-1 onto map)

RonL