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

MATH220 December 2011

• Q1 (a) • Q1 (b) • Q1 (c) • Q1 (d) • Q1 (e) • Q1 (f) • Q2 (a) • Q2 (b) • Q3 • Q4 • Q5 (a) • Q5 (b) • Q6 (a) • Q6 (b) • Q7 (a) • Q7 (b) • Q8 •

Other MATH220 Exams

• April 2011 • April 2005 • December 2011 • December 2010 • December 2009 •

[hide] 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!

[show] Hint
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.

If you are stuck on a problem: Read the solution slowly and as soon as you feel you could finish the problem on your own, hide it and work on the problem. Come back later to the solution if you are stuck or if you want to check your work.
If you want to check your work: Don't only focus on the answer, problems are mostly marked for the work you do, make sure you understand all the steps that were required to complete the problem and see if you made mistakes or forgot some aspects. Your goal is to check that your mental process was correct, not only the result.

[show] Solution 1
Found a typo? Is this solution unclear? Let us know here. Please rate my easiness! It's quick and helps everyone guide their studies. 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.

[show] Solution 2
Found a typo? Is this solution unclear? Let us know here. Please rate my easiness! It's quick and helps everyone guide their studies. Another way to find a denumerable proper subset goes as follow: use the fact that the set A has a bijection with the natural numbers to define a proper subset of all the elements mapped to an even natural number, realize that this will be a proper and denumerable subset of the set A. 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 $\displaystyle B=\{a\in A\mid g(a){\text{ is even}}\}$ 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 ${\begin{aligned}h:B&\to \mathbb {N} \\b&\mapsto {\frac {g(b)}{2}}\end{aligned}}$ 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 $\displaystyle h(b)=h(b')$ by definition of the function h we have that $\displaystyle {\frac {g(b)}{2}}={\frac {g(b')}{2}}$ and thus $\displaystyle g(b)=g(b')$ 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.