Question 05 (b)
Let A be a denumerable set. Prove that there exists a proper subset B of A such that B is denumerable.
Make sure you understand the problem fully: What is the question asking you to do? Are there specific conditions or constraints that you should take note of? How will you know if your answer is correct from your work only? Can you rephrase the question in your own words in a way that makes sense to you?
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.