Countably infinite set & Uncountably infinite set

Countably infinite set:

A set is countably infinite if there is a one-to-one (objective) correspondence between 'elements of the set' and 'natural numbers'.

Uncountably infinite set:

A set is Uncountably infinite if there is no one-to-one correspondence between 'elements of the set' and 'natural numbers'.

Examples of countably infinite sets :

(i) Set of "Natural numbers" is a trivial example.

N = {1, 2, 3, 4, 5,....}

(ii) "Set of integers (Z)"

Explanation:

Let a function f : Z → N be defined as

f(0) = 1

f(x) = 2x if x > 0

f(x) = – 2x + 1 if x < 0

0	→	1
1	→	2
– 1	→	3
2	→	4
– 2	→	5
...............
...............

Hence all integers are mapped to natural numbers.

(iii) Set of "Rational numbers (Q)"

Explanation :

Before proving 'Q' to be a countably infinite set,

let us prove an important theorem about union of countable sets.

'A', 'B' be two countable sets.

Let A = {a₁, a₂, a₃, a₄ .....}

B = {b₁, b₂, b₃, b₄ .....}

Let A ⋃ B = C	=	{a₁, b₁, a₂, b₂, a₃, b₃,.....}
	=	{c₁, c₂, c₃, c₄.....c_n...}

a₁ → 1

b₁ → 2

a₂ → 3

b₂ → 4

..............

a_n → 2n – 1

b_n → 2n

There is one-one correspondence between elements of 'C' and 'N'.

Hence union of two countable sets is countable.

A positive rational number 'q' is of the form a/b where a, b ∈ N

Arrange rational numbers in the orders of a + b.

If a + b for two rational numbers is same, arrange them in the order of 'a'

First element corresponds to 1, second to 2 and so on.

Hence rational numbers set is countably infinite set.

Note : The ordering of elements need not be same as given above.

It is merely one of many possible orderings.

Example of uncountably infinite set :

Set of "Irrational numbers"

Explanation :

Assume irrational number set to be countable.

One of the possible orderings can be represented by

Consider an irrational number.

_ . x₁ x₂ x₃ x₄ _ _ _ _ _

(x₁ ≠ a₁, x₂ ≠ a₂, x₃≠ a₃,...... x_n ≠ a_n for any n)

Choose any digit x_n other than a_n.

By doing so we can always create an irrational numbers which is not listed in the ordering.

Hence the set of "irrational numbers" is uncountable.