Prove that the following sets are countably infinite 1 Q 01

Prove that the following sets are countably infinite.

1) Q [0,1]

2) The set of prime numbers

We\'re not supposed to construct an explict bijection on Z⁺ but that\'s the only way I could do these. Can someone please help me prove these without doing that please???

Solution

All rational numbers are well ordered set.

Hence the rational numbers in the set  Q [0,1] consists of all rational numbers between 0 and 1.

Between any two rational numbers there are infinite rational numbers hence the set is infinite.

Since well ordered set for any a,b, ... we can write a<b<c.....

We can find a map such that least element is mapped on to 1, next least to 2, etc.

Thus we can find a one to one correspondence between the set  Q [0,1] and set of natural numbers though the set  Q [0,1] is infinite.

Hence the set  Q [0,1] is infinitely countable.

----------------------------------------------------------------------------------------------

2) The set of prime numbers:

The prime numbers can be written well in ascending order.

as 2,5,7, 11, 13,....

Let f: set of prime numbers to natural numbers as f(2) = 1, f(5) = 2, .... in ascending order

This is possible hence the set of prime numbers is infinitely countable