HOMEWORK 2 : DUE FRIDAY 29, 6 PM Please submit the assignment on time on Moodle. The submission should be a PDF file. It could be either typed or scanned. Make sure that the quality of your scan is good, and everything is legible. You can use one of the many free scanning apps out there. (For example, Adobe Scan.) You should not upload photos. If you need help with scanning, please contact me. You are encouraged to discuss the homework problems with your classmates. However, your final submitted homework must reflect your personal understanding of the material. Your solution must be written by you in your own words. You are not allowed to copy an answer from another student or from any other source. Please make sure your solutions are well organized. Make sure the structure of the proofs is clear and logically sound. Question 1. Consider the following sets, which are subsets of the rational numbers Q . With respect to the usual ordering of the rational numbers, determine whether they are bounded from below or from above. If the set E is bounded from above, determine whether there is a rational number which is the least upper bound sup E , and whether it is in the set E or not. If the set is bounded from below, determine whether there is a rational number which is the greatest lower bound inf E , and whether it is in the set E or not. (1) E = x | x = 0 or x = 1 n 2 for n = 1 , 2 , 3 , ... ; (2) E = Z \ { 1 , 2 , 3 , . . . } ; (3) E = 1 n + ( 1) n | n = 1 , 2 , 3 , ... . Question 2. Let f be a function from X to Y and let B Y . Show that f (( f 1 ( B ))) = B . Give an example showing that equality need not hold if f is not onto Y . Question 3. Let f : X Y and g : Y Z be two functions. Prove that (1) if g f is injective, then f is injective; (2) if g f is surjective, then g is surjective. Question 4. (1) Prove that if a R \ Q and b Q ( a is irrational and b is rational), then a + b is irrational. (2) Prove that p · 2 is irrational for any rational p Q , p ̸ = 0. (3) Prove that between any two rational numbers there is an irrational number. Question 5. Let S R be some subset. Consider the following statements. I For any real number x R there is some y S so that x < y . II For any two real numbers x, y , if x < y there there is some z S so that x < z < y . III For any x S there is some y S so that x + y = 0. Answer the following two questions. (1) For each of the statements above, write the formal negation of the state- ments. Do not just write "not ...". Use the rules that negation of "for all" is "there exists", negation of "and" is "or", etc. 1
2 HOMEWORK 2 : DUE FRIDAY 29, 6 PM (2) For each of the following cases, determine whether the statements above are true or not. Explain your answers. (a) S = N ; (b) S = Z ; (c) S = Q ; (d) S = x R | x 2 4 . Extra challenges (not to be submitted). Question. Recall that we proved in class that the principle of mathematical induc- tion is logically equivalent to the well-ordering principle. Therefore, any statement that can be proved using the well-ordering principle, can also be proved using in- duction. Recall briefly that in the proof of the theorem that Q is dense in R , we used the well-ordering principle to prove the following statement. ( ) Given any real number x > 0 , m N , such that m 1 x < m. In view of the previous paragraph, prove ( ) using the principle of mathematical induction, instead of the well-ordering principle.
Uploaded by LieutenantMouse2814 on coursehero.com