Prove that the set 1xx N 11 12 13 is countable a By describ

Prove that the set {1/x|x N^+} = {1/1, 1/2, 1/3,...} is countable, (a) By describing a way to list the elements. (b) By giving an explicit function and showing that it is a bijection.

Solution

(a) Let S={1/x / x belongs to N+} = {1/1, 1/2, 1/3, ...}

We describe a way to list the elements in the form:

Let S map each element to a natural number by,

S                    N

1/1--------------1

1/2--------------2

1/3--------------3

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

1/N--------------N

The given set and the set of natural numbers have the same cardinality. Though the set of natural numbers is infinite, yet there exists a one-to-one correspondence with the given set and the set of natural numbers. Hence the given set is countable [Proved].

(b) We define an explicit function by,

f(x)=1/x, x belongs to the set of positive natural numbers.

Here let, x_{1 =} 1/2, x_{2 =} 1/3. So, x₁ not equal to x₂ implies f(x₁) not equal to f(x₂) [ Since 2 is no equal to 3]

Therefore, the function is injective [one to one].

Also as each element has a distinct pre-image , so the function is surjective [ onto function].

Hence the above function is a bijection.

As the elements of the given set can be mapped to a distinct element of the image set of natural numbers, i.e, they have a one-to-one correspondenc and also the same cardinality, hence the set is countable [Note : A countable set is either a countable set or countably infinite] [solved]