**Problem 1 (20 marks)**

(a) List all possible functions f : {a, b, c} â†’ {0, 1}. (4 marks)

(b) Describe a connection between your answer for (a) and Pow({a, b, c}). (4 marks)

(c) In general, if card(A) = m and card(B) = n, how many:

(i) functions are there from A to B? (4 marks)

(ii) relations are there between A and B? (4 marks)

(iii) symmetric relations are there on A? (4 marks)

**Problem 2 (26 marks)**

For x, y âˆˆ Z we define the set:

Sx,y = {mx + ny : m, n âˆˆ Z}.

(a) Give five elements of S2,âˆ’3. (5 marks)

(b) Give five elements of S12,16. (5 marks)

For the following questions, let d = gcd(x, y) and z be the smallest positive number in Sx,y.

(c) Show that Sx,y âŠ† {n : n âˆˆ Z and d|n}. (4 marks)

(d) Show that {n : n âˆˆ Z and z|n} âŠ† Sx,y. (4 marks)

(e) Show that d â‰¤ z. (Hint: use (c)) (4 marks)

(f) Show that z â‰¤ d. (Hint: use (d)) (4 marks)

**Problem 3 (24 marks)**

We define the operation âˆ— on subsets of a universal set U as follows. For any two sets A and B:

A âˆ— B := Ac âˆª Bc.

Answer the following questions using the Laws of Set Operations (and any derived results given in lec- tures) to justify your answer:

(a) What is (A âˆ— B) âˆ— (A âˆ— B)? (6 marks)

(b) Express Ac using only A, âˆ— and parentheses (if necessary). (6 marks)

(c) Express âˆ… using only A, âˆ— and parentheses (if necessary). (6 marks)

(d) Express A B using only A, B, âˆ— and parentheses (if necessary). (6 marks)

**Problem 4 (20 marks)**

Let Î£ = {a, b}. Define R âŠ† Î£âˆ— Ã— Î£âˆ— as follows:

(w, v) âˆˆ R if there exists z âˆˆ Î£âˆ— such that v = wz.

(a) Give two words w, v âˆˆ Î£âˆ— such that (w, v) âˆˆ/ R and (v, w) âˆˆ/ R. (4 marks)

(b) What is Râ†({aba})? (4 marks)

(c) Show that R is a partial order. (12 marks)

**Problem 5 (10 marks)**

Show that for all x, y, z âˆˆ Z:

If x|yz and gcd(x, y) = 1 then x|z.

(Hint: Use the connection between gcd(x, y) and Sx,y shown in Problem 2.)