Notes:

.To  obtain  full  marks  for  each  question,  relevant  and  clear  steps  must  be  included  in  the answers.

.Partial marks maybe awarded depending on the degree of completeness and clarity.

QUESTION 1: Proof Techniques                                                                    (20 marks)

(a) Use proof by contradiction to show that there does not exist any integers x andy such that 6x + 18y = 1. (3 marks)

(b) Let a be a positive real number, and the Statement S be: “if a is not rational number, then  6    a     is also not a rational number” .

1.   Prove the Statement S by contradiction.

2.   If you think the converse of the Statement S is true, prove it. If not, give a counter-example. (8 marks)

(c) For x, y, z ∈ ℤ, use proof by contradiction to show the following statement:

if x2 + y2 = z2, then at least one of x and y is even. (5 marks)

(d) For all integer  m ≥  1, use proof by induction to show that:

2m( )(m + 12  +  22  + 32  + … +  2m2 (4 marks)

QUESTION 2: Set Theory                         (32 marks)

(a) Let the universal set be ℕ,  A = {x ∈ ℕ  |  x is even and 3 < x < 11},

B = {x ∈ ℕ   x is odd and 2 < x < 10},  C = x ∈ ℕ   x is odd and 3 < x < 9} and D = d ∈ ℕ  d2  =  5}. Find the elements of the following expressions:

1.        B ∩ (A ∪ D)

2.        ~(  B − D) ∩ A)

3.         C ∪ D)∩ B Δ A)

4.         (  D ∪ B  ∩ A Δ B) ∪ B − A − D  )  ∩ C (8 marks)

(b) Let X and Y be sets, then   X  ⊆  Y  if and only if ~X   ⊆  ~Y. If you think that it is true, prove it. Otherwise, give a counterexample to show that it is false. (6 marks)

(c) Prove that the following sets are equal:

1.   A x (B ∪ C) = (A x B) ∪ (A x C)

2.   A x (B −  C) = (A x B) −   (A x C) ( 10 marks)

(d) Let X and Y be sets, and X ⊆ Y if and only if (Y − X) ∪ X = Y. If you think that it is true, prove it. Otherwise, give a counterexample to show that it is false. (8 marks)

QUESTION 3: Relations        (48 marks)

(a) Let  A = a ∈ ℤ  a ≠ 0 }  andR be the relation on the set  A  defined by

R ={(a,b)  a + b = 2c, where a,b,c ∈  A. Prove or disprove that R over A is an equivalence notion. (6 marks)

(b)      Let       A = 1,2,3,4 .            What      is      the      transitive      closure      of      the      relation 1,2 , 2,3), 03,4, 1,3 , 1,4 , 2,4  on A? Express your answer using ordered pairs. (4 marks)

(c) If A and B are both transitive relations, then their intersection is also transitive. If you think that it is true, prove it. If not, give a counter-example. (8 marks)

(d) Let R and S be two partial orders on a set X, and Tis a relation on X such that aTb (i.e. a,b ∈ X) if and only if both aRb and aSb hold. Is T also a partial order on X? Justify your answer with proofs and/or counterexamples (7 marks)

(e) Given the partial ordering on the following set A = {a, b, c, d, e} as {(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (a,e), (d,e)}, draw the corresponding Hasse diagram. (3 marks)

(f) Let A be the points in the plane (A = R × R). We say two points are equivalent if they are equal distance from the origin. So (x, y) ∼ (w, z) if x2+y2  = w2+z2. Show this is an equivalence relation on A and find the equivalent classes. ( 10 marks)

(g) For all a, b   ∈ Z+, we define a ◎bif a/b   ∈ Z+. Prove or disprove   ◎ is a partial order and/or a total order on Z+. ( 10 marks)