You need to download the Exam template from the class websit…
You need to download the Exam template from the class website and use that for taking this exam. You also need to scan in all 9 pages including the cover page even if you do not write on all of them. I. Answer each of the following 10 questions T (for True) and F (for False) only. No justification is necessary. (2 points each) i) The set of integers with respect to the relation > is a partially ordered set. ii) Let S be a partially orderd set. Then the greatest lower bound for a subset A is the least element of A. iii) The set of all pairs of integers is equinumerous to the set of all rational numbers. iv) The set of all decimal numbers in the interval (0,1) that end in a string of 0s is uncountably infinite. v) The set of all decimal numbers in the interval (0, 1) that have an infinite number of nonzero digits is countably infinite. vi) The negation of a statement with a universal quantifier is a statement with an existential quantifier. vii) The statement ( x)( y)(P(x,y)) is logically equivalent to ( y)( x)(P(x, y)). viii) The statement ( x)( y)(P(x,y)) is logically equivalent to ( y)( x)(P(x,y)) ix) 51/2 is a rational number. x) The sum of a rational number and an irrational number is always an irrational number. II. Write the negation of the following statements using quantifiers whenever possible. (30 points: 10 each) a) Everybody loves somebody. b) No one has yet done that. c) If one works hard, one will pass the exam. III. Prove the following: (30 points: 15 each) a) n2 < 2n for all integers n>=5. b) Let {hn|n 0 } denote a sequence defined by h0 =1, h1=2, h2=3 and hk= hk-1 +hk-2+hk-3, for all integers k 3. Prove that hn 3n for all integers n 0. IV a) Prove that = 2n (15 points) b) Prove that (-1)i 2n-i =1 (15 points) V. In a small town of 500 residents, should there be at least two residents who have the same birthday? Explain. (20 points) VI. Prove that 91/3 is irrational. Is it an algebraic number? Give reasons for both answers. (20 points) VII. Define a relation R on the set of all real numbers by xRy if and only if x2 y2. Is this partial order on the set of all real numbers? Prove or give a counter-example. (20 points) VIII. Prove or give a counter-example to disprove. a) For all subsets A, B, and C of any set S, (A-B) U (C-B) = (AUC)-B. (15 points) b) For all subsets A, B and C of any set S, (A-B) U (B-C) = A-C. (15 points).