Page 41 - DMTH401_REAL ANALYSIS

Unit 2: Algebraic Structure and Countability

is a one-to-one correspondence. Hence Z – N. Thus the set of integers is a denumerable set Notes
and hence a countable set.
(ii) Let E denote the set of all even natural numbers. Then the mapping f: N  E defined as
f(n) = 2n is a one-one correspondence. Hence the set E of even natural numbers is a
denumerable set and hence a countable set.

(iii) Let D denote the set of all odd integers and E the set of even integers. Then the, mapping
f: E  D, defined as f(n) = n + 1 is a one-one correspondence. Thus E ~ D, But, E – N,
therefore D – N. Hence D is a denumerable set and hence a countable set.
We observe that a set S is denumerable if and only if it is of the form {a,, a,, a, ....} for distinct
elements a,, a,, a, ..... For, in this case the mapping f(a ) = n is one-one mapping of S onto N i.e. the
n
sets {a,, a,, a , .....} and the set N are equivalent.
3
If we consider the set S = {2, 3, 4, .....}, we find that the mapping f: N  S defined as f(n) = n + 1
2 2
is one-one and onto. Thus S is denumerable. Similarly if we consider S = {3, 4,....} or S = {k, k +
2 3 k
1, .....}, then we find that all these are denumerable sets and hence are countable sets.
We have seen that the set of integers is countable.

Now we discuss the countability of the rational and real numbers. Here is an interesting theorem.
Theorem 2: Every infinite subset of a denumerable set is denumerable.
Proof: Let S be a denumerable set. Then S can be written as
S = {a,, a,, a , ....}.
3
Let A be an infinite subset of S. We want to show that A is also denumerable.
You can see that the elements of S are designated by subscripts 1, 2, 3, .... Let n, be the smallest
subscript for which a  A. Then consider the set A – {a }. Again, in this new set, let n be the
n1 n1 2
smallest subscript such that a  A – {a,,,}.
n2
Let n be the smallest subscript such that
k
a  A – {a , a , ......, a }.
nk n1 n2 nk–1
Note that such an element a always exists for each k  N as A is infinite. For, then
nk
a , a , ...., a }  Æ
A = { n n n
1 2 k
for each k  N. Thus, we can write

a , a , a , ...., a , .... } .
A = { n n n n
1 2 3 k
Define f: N  A by f(k) = a . Then it can be verified that f is a one-one correspondence. Hence A
nk
is denumerable. This completes the proof of the theorem.
Now consider the sets S = {6, 8, 10, 12, ....} and T = {3, 5, 7, 9, 11, ....}, which are both denumerable.
Their union S  T = {3, 5, 6, 7, 8, 9, ....} is an infinite subset of N and hence its denumerable. Again,
if S = (–1, 0, 1, 2} and T = {20, 40, 60, 80, ....}, then we see that S  T = (–1, 0, 1, 2, 20, 40, 60, ....} is a
denumerable set. Note that in each case S  T = 0. In fact, you can prove a general result in the
following exercise.
Thus, it follows that the union of any two countable sets is countable.
Indeed, let S and T be any two countable sets. Then S and T are either finite or denumerable.

If S and T are both finite, then S  T is also a finite set and hence S  T is countable.

LOVELY PROFESSIONAL UNIVERSITY 35