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{\mathbb{N}}$

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

$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

$B=A\mathrm{\setminus }\{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{array}{rl}g:B& \to \mathbb{\mathbb{N}}\\ b& \mapsto f(b)-1\end{array}$

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

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

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

$g(b)=g(b^{\prime })$

By definition of the function g this means that

$f(b)-1=f(b^{\prime })-1$

and so that

$f(b)=f(b^{\prime })$

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.