Science:Math Exam Resources/Courses/MATH220/December 2011/Question 05 (b)
Question 05 (b)
Let A be a denumerable set. Prove that there exists a proper subset B of A such that B is denumerable.
If you are stuck, check the hint below. Consider it for a while. Does it give you a new idea on how to approach the problem? If so, try it!
Start with writing a bijection ƒ: A → N then going from there.
Checking a solution serves two purposes: helping you if, after having used the hint, you still are stuck on the problem; or if you have solved the problem and would like to check your work.
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
Let a be the element of the set A which is mapped to the integer 1, that is
Then define the set B to be the subset containing all the elements of the set A except for the element a, that is
Note that B is a proper subset of A. To show this subset is denumerable, define a function to the natural numbers as follow
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 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
For injectivity, suppose that you have elements b and b' of the set Bsuch that
By definition of the function g this means that
and so that
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.
Another way to find a denumerable proper subset goes as follow:
Details of this proof are described here.
Since the set A is denumerable there must exist a bijection g: A → N from that set to the natural numbers. We define the set B to be all the elements of the set A that are mapped to an even number, that is
We need to show that the set B is a proper subset of A and is denumerable. It is a proper subset since it doesn't contain any element that are mapped to an odd number. To show it is denumerable, we define the function
and show that it is a bijection.
It is surjective since for any natural number m there is an element of the set A which maps to the number 2m and since that's an even integer, that element of the set A is a member of the subset B, let's call it b for now. Then since g(b) = 2m, then h(b) = m and thus the function h is surjective.
To show injectivity, consider two elements b and b' of the set B such that
by definition of the function h we have that
but since g is a bijection, it is also an injection and we can conclude that b = b', and so the function h is injective.