Science:Math Exam Resources/Courses/MATH220/December 2011/Question 05 (b)/Solution 1

The core idea of this solution is to say that if the set A is denumerable, then we can remove any element a from this set and obtain a proper subset which is also denumerable. We will show below how to precisely prove that this subset is denumerable.

Since the set A is denumerable, there exists a bijection from that set to the set of natural numbers. Let ƒ be this bijection, that is

$f:A\to \mathbb {N}$

Let a be the element of the set A which is mapped to the integer 1, that is

$\displaystyle a=f^{-1}(1)$

Then define the set B to be the subset containing all the elements of the set A except for the element a, that is

$\displaystyle B=A\backslash \{a\}$

Note that B is a proper subset of A. To show this subset is denumerable, define a function $g$ to the natural numbers as follow

${\begin{aligned}g:B&\to \mathbb {N} \\b&\mapsto f(b)-1\end{aligned}}$

Notice that each element of the set B is mapped by ƒ to an integer greater or equal to 2 (since we removed a who precisely was the integer mapped to 1), so the function g simply assigns the natural number just below. We claim that this $g$ is bijective.

To show surjectivity, notice that each natural number m is the image by the function g of the element which was mapped to m+1 by the function ƒ. We can write this as

$\displaystyle m=g(f^{-1}(m+1))$

For injectivity, suppose that you have elements b and b' of the set Bsuch that

$\displaystyle g(b)=g(b')$

By definition of the function g this means that

$\displaystyle f(b)-1=f(b')-1$

and so that

$\displaystyle f(b)=f(b')$

And since we know that the function ƒ is a bijection (and in particular is injective) we can conclude that b = b', and thus the function g is injective.

Since g is both surjective and injective it is a bijection and thus the set B is denumerable.