Reference no: EM13919256

1. Construct counterexamples to the following statements:

(a) For x ∈ R: 'If x is not rational then χ - 1/ χ is not rational'.        

(b) For p ∈ N: 'If p is prime then 2p - 1 or 2p + 1 is prime'.            

(c) For functions f(χ): 'If the range of f(χ) contains the values -1 and 1, then it contains the  interval [-1, 1]'.

(d) For 3 × 3 matrices A: 'A³ = 0 implies A² = 0'.   

2. Put one of the phrases 'sufficient', 'necessary', 'necessary and sufficient' or 'neither necessary nor sufficient' into the gaps in the following propositions to make them true. In all cases you must explain why your stated answer is correct. You must provide full proofs or give suitable counterexamples to justify your answers.

(a) For real χ: "χ³ is not rational is a ____ condition for χ is not rational." 

(b) For functions f(χ), g(χ) defined on R: "f(χ)g(χ) is continuous is a_______ condition for f(χ) is continuous and g(χ) is continuous."                     

(c) For 2 × 2 matrices A, B:  "AB = 0 is a______ condition for A = 0 or B = 0."

(d) For natural n: "p is prime is a ______ condition for 3p + 1 is prime."  

3. (a) Prove that the number 2^1/3 + 3^1/2 is algebraic (recall that a number is called algebraic if it solves a polynomial equation with integer coefficients).           

(b) Prove by contradiction that the number 2^1/3 + 3^1/2 is not rational.      

4. Proof by induction:

(a) Prove by induction that the number 3⁴ⁿ + 4³ⁿ⁺² is divisible by 17.         

(b) Prove by induction the inequality 2ⁿ > n³ for n ≥ 10.  

(c) The sequence a_n is defined recursively as a_n+1 = 7a_n - 10a_n-1, a₀ = 3, a₁ = 6. Conjecture a formula for a_n and prove it by induction.

(d) The power set of a set A, denoted P(A), is defined to be the set of all subsets of A. For instance, if A = {1, 2}, then P(A) = {∅, {1}, {2}, {1, 2}}. Note that P(A) is a set which contains sets as elements, and that the empty set, ∅, is a subset of all sets.

Prove by induction that if A is a set containing n elements then its power set, P(A), has 2n elements. (Without loss of generality you may take A = {1, 2, . . . , n}.) To understand how the inductive step works, it may help if you see how the subsets of a set with, say, four elements can be related to those of a set with three.