2 Countability
2 Countability
Definition 2.1 (Equivalent Sets). Two sets A and B are said to be equivalent if
there is a one-one correspondence between the sets A and B.
i.e. ∃ a bijective map f : A → B and is denoted by A ∼ B.
Example 2.2. Exercise
Show that the relation ∼ is an equivalence relation.
Definition 2.3. A set X is said to be finite if either X = φ or X is equivalent to
{1, 2, , 3, ...n} for some natural number n.
Definition 2.4. A set X is said to be infinite if n ∈ N such that X ∼ {1, 2, ..., n}.
Definition 2.5. A set X is said to be countable if either X is finite or is equivalent
to N .
e.g.1) N is countable as N ∼ N.
2) Z is countable i.e. Z ∼ N.
Define f⎧: Z → N
⎨ 2n, n≥1
f (n) =
⎩ 1 − 2n, n ≤ 0.
To show f is one-one, let f (n1 ) = f (n2 )
⇒ 2n1 = 2n2 or 1 − 2n1 = 1 − 2n2
⇒ n1 = n 2
To show that f is onto, let m ∈ N. Suppose m is odd.
⇒ m = 1 − 2x, x ∈ N
1−m
⇒x= 2
≤0
Then f (x) = 1 − 2(x) = 1 − 2 1−m
2
=1−1+m=m
Now suppose m is even.
⇒ 2|m
Dr. Rupali S. Jain 9 Dr.B. Surendranath Reddy
2 Countability
m
Then take x = 2
∈Z
f (x) = 2x = 2( m2 ) = m
∴ f is onto.
Z ∼ N and hence it is countable.
Example 2.6. Show that N × N is countable. i.e. N × N ∼ N.
Proof. Given any natural number k ∈ N, ∃ m, n ∈ N such that
k = 2m−1 (2n − 1)
Define f : N → N × N by
f (k) = (m, n).
Let f (k1 ) = f (k2 )
⇒ 2m1 −1 (2n1 − 1) = 2m2 −1 (2n2 − 1)
⇒ m1 = m2 and n1 = n2
∴ f is one to one.
To show onto, let (m, n) ∈ N × N then take k = 2m−1 (2n − 1) and
f (k) = (m, n)
⇒ f is onto.
∴N×N∼N
N × N is countable.
Theorem 2.7. If A and B are countable then A × B is countable.
Proof. Since A and B are countable, ∃ bijective maps f : A → N and g : B → N.
Define h : A × B → N × N by
h ((a, b)) = (f (a), g(b))
then h is well defined.
Let h ((a1 , b1 )) = h ((a2 , b2 ))
⇒ (f (a1 ), g(b1 )) = (f (a1 ), g(b2 ))
Dr. Rupali S. Jain 10 Dr.B. Surendranath Reddy
2 Countability
⇒ f (a1 ) = f (a2 ) and g(b1 ) = g(b2 )
⇒ a1 = a2 and b1 = b2
⇒ (a1 , b1 ) = (a2 , b2 ).
∴ h is 1-1.
To show onto, let (m, n) ∈ N × N. Since f and g are onto ∃ a ∈ A and b ∈ B such
that f (a) = m and g(b) = n
h ((a, b)) = (f (a), g(b)) = (m, n)
⇒ h is onto.
∴ h is bijective.
A × B ∼ N × N.
Since N × N ∼ N
⇒ A × B is countable.
Theorem 2.8. If An ’s are countable then ∪∞
n=1 An is also countable.
i.e.Countable union of countable sets is countable.
Proof. Since each An is countable, we can represent An ’s as follows
A1 : {a11 , a12 , a13 , ...}
A2 : {a21 , a22 , a23 , ...}
An : {an1 , an2 , an3 , ..}.
Then ∪∞
n=1 An = {aij |(i, j) ∈ N × N}
Now define f : ∪∞
n=1 An → N × N by
f (aij ) = (i, j).
Suppose f (aij ) = f (alm )
(i, j) = (l, m)
i = l, j = m
⇒ f is 1-1.
To show onto, let (i, j) ∈ N × N.
Dr. Rupali S. Jain 11 Dr.B. Surendranath Reddy
2 Countability
Then aij ∈ ∪∞
n=1 An such that f (aij ) = (i, j) and hence f is onto
⇒ ∪∞
n=1 An ∼ N × N
⇒ ∪∞
n=1 An is countable.
Theorem 2.9. The set of rational numbers Q is countable.
Proof. For n ≥ 1, define An = { m
n
|m ∈ Z}. Clearly ∪∞
n=1 An ⊂ Q Since for any q ∈ Q,
m
we can write q = n
,m ∈ Z, n ≥ 1.
⇒ Q ⊂ ∪∞
n=1 An
Therefore, Q = ∪∞
n=1 An
Now we will show that each An is countable.
Define f : An → Z by
f(m
n
) = m.
Suppose f ( mn1 ) = f ( mn2 )
⇒ m1 = m 2
⇒ f is one-one.
k
Let k ∈ Z. Then n
∈ An
∴ f ( nk ) = k
⇒ f is onto.
⇒ An ∼ Z.
Since Z is countable, An is also countable.
Since Q = ∪∞
n=1 An and each An is countable, Q is also countable.
Theorem 2.10. If A is an infinite subset of N then A is countable.
Proof. Let A ⊂ N be an infinite set.
Since A = ∅, by well ordering principle there exists a least element say x1 .Then
x1 ≥ 1
Also A \ {x1 } = ∅ again by well ordering principle, let x2 be the least element of
Dr. Rupali S. Jain 12 Dr.B. Surendranath Reddy
2 Countability
A \ {x1 }.
Then x1 < x2 and x2 ≥ 2
By repeating this same arguments, we get, x1 < x2 < x3 < ... such that xn ≥ n is the
least element of A \ {x1 , x2 , ...xn−1 }.
We will show that A \ {x1 , x2 , ...} = ∅.
Suppose not. Then ∃ m ∈ A such that m = xi ∀ i.
Take S = {k ∈ N|xk > m}.
Since xm ≥ m and m = xm , we get xm > m and so m ∈ S.
∴ By well ordering principle S has least element say n
⇒ 1, 2, ..., n − 1 ∈
/ S and n ∈ S
⇒ x1 < x2 < ... < xn−1 < m and xn > m
⇒ x1 < x2 < ... < xn−1 < m < xn .
Since xn is the least element of A \ {x1 , x2 , ..., xn−1 }
⇒ xn ≤ m, which is a contradiction.
∴ A \ {x1 , x2 , ...} = ∅
⇒ A = {x1 , x2 , ...}.
∴ A is countable.
Corollary 2.11. Any subset of a countable set is countable.
Theorem 2.12. (0, 1) is uncountable where (0, 1) = {x|0 < x < 1}.
Proof. Suppose (0, 1) is countable, then (0, 1) = {x1 , x2 , ...}.
We can write each xi in decimal expansion as follows:
x1 = 0.a11 a12 a13 ...
x2 = 0.a21 a22 a23 ...
x3 = 0.a31 a32 a33 ....
Define y = 0.b11 b22 b33 ...
Dr. Rupali S. Jain 13 Dr.B. Surendranath Reddy
2 Countability
⎧
⎨ 2, if a = 2;
nn
Where bnn =
⎩ 3, if a = 2.
nn
⇒ ann = bnn ∀ n
Then y ∈ (0, 1) but y = xn ∀n
Which is a contradiction.
∴ (0, 1) is uncountable.
Theorem 2.13. R is uncountable.
Proof. We know that (0, 1) is uncountable. Suppose R is countable then (0, 1) ⊂ R
is also countable. Which is a contradiction.
⇒ R is uncountable.
Theorem 2.14. R/Q is uncountable.
Proof. Suppose R/Q is countable then R = Q ∪ (R/Q) is also countable. Which is a
contradiction.
⇒ R/Q is uncountable.
Dr. Rupali S. Jain 14 Dr.B. Surendranath Reddy
