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?
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
how is this obvious?
I have no clue on how to show that they map to each other, but I do have a proof showing that $\displaystyle \mathbb{N}\times \mathbb{N}$ and [tex]\mathbb{Q}\times \mathbb{Q}[/Math] are 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?
From what else you write this is really all we ned to show.
Let the end points of the rational interval be $\displaystyle q_1$ and $\displaystyle q_2$ with $\displaystyle q_1<q_2$, then we introduce a map $\displaystyle f$ which takes the interval $\displaystyle (q_1,q_2)$ to the ordered pair $\displaystyle (q_1,q_2)$ . This is a 1-1 map of the intervals to a subset of the set of ordered pairs.
RonL
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