Mathematics 327  Exam #1 – SOLUTIONS  9 October 2000

Problem 1. Let A, B, C be sets. Show that, in general, (A \ B) \ C ≠ A \ (B \ C). Solution 1: Observe here that if B = ∅, (A \ B) \ C = A \ C and A \ (B \ C) = A. So, any example with B = ∅ and C not disjoint with A will do: say A = {1, 2}, B = ∅, C = {1}, for instance. Solution 2: We could also look for an example by setting B = C. Then (A\B)\C = A\B while A \ (B \ C) = A. If B is not disjoint with A we will always get an example. Take A = {1, 2}, B = C = {1}. Problem 2. Determine whether or not each of the binary relations R is reflexive, symmetric, antisymmetric, or transitive:

a) A = {1, 2, 3, 4}, R = {(1, 1), (1, 2), (2, 1), (3, 4), (4, 3)}. reflexive: NO, (2, 2) ∉ R. symmetric: YES, for each (a, b) ∈ R also (b, a) ∈ R. antisymmetric: NO, (2, 1) ∈ R and (1, 2) ∈ R but 1 ≠ 2. transitive: NO, (2, 1) ∈ R and (1, 2) ∈ R but (2, 2) ∉ R.

b) A = ℝ, (a, b) ∈ R if and only if a − b ≤ 3. reflexive: YES, a − a = 0 ≤ 3 so (a, a) ∈ R for all a. symmetric: NO, (−10, −1) ∈ R but (−1, −10) ∉ R. antisymmetric: NO: if a − b ≤ 3 and b − a ≤ 3 that implies that −3 ≤ a − b ≤ 3. But this does not mean that a = b. For example, (2, 1) and (1, 2) are both in R but 1 ≠ 2. transitive: NO, clearly, (4, 1) ∈ R and (1, 0) ∈ R but (4, 0) ∉ R.

c) A = ℤ, (a, b) ∈ R if and only if a + b = 10. reflexive: NO, (6, 6) ∉ R, for example. symmetric: YES, if (a, b) ∈ R so is (b, a). antisymmetric: NO, for example both (4, 6) and (6, 4) are in R. transitive: NO, for example (11, −1) ∈ R and (−1, 11) ∈ R but (11, 11) ∉ R.

d) A = ℕ, (a, b) ∈ R if and only if \frac{a}{b} ∈ ℕ. reflexive: YES, a/a = 1 for all natural numbers a. symmetric: NO, (2, 1) ∈ R but (1, 2) ∉ R. antisymmetric: YES, if a/b is natural and b/a is natural that means that a = b. transitive: YES, if a/b is natural and b/c is natural so is their product, which is simply a/c.

Problem 3. Let S = {1, 2, 3, 4, 5}, and let f, g, h : S → S be the function defined by

f = {(1, 2), (2, 1), (3, 3), (4, 5), (5, 4)},
g = {(1, 5), (2, 3), (3, 1), (4, 2), (5, 4)},
h = {(1, 2), (2, 2), (3, 2), (4, 3), (5, 1)}.

a) f ∘ g = {(1, 4), (2, 3), (3, 2), (4, 1), (5, 5)}, g ∘ f = {(1, 3), (2, 5), (3, 1), (4, 4), (5, 2)}.

b) f^{−1} = {(1, 2), (2, 1), (3, 3), (4, 5), (5, 4)}, g^{−1} = {(1, 3), (2, 4), (3, 2), (4, 5), (5, 1)}, h^{−1} does not exist as h is not bijective.

c) f^{2} = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)} = id, f^{3} = f, f^{4} = id. What is f^{2k} = id, and f^{2k+1} = f.

Problem 4. In each case determine if the function is injective (1-1) and/or surjective (onto):

a) f : ℕ → ℕ, f(n) = 3n: injective but not surjective because f(n) = 3n = 1 has no solutions in natural numbers.

b) f : ℝ → ℝ, f(x) = 3x: injective and surjective.

c) f : ℝ^{2} → ℝ, f(x, y) = x: surjective but not injective as f(1, 0) = f(1, 1) = 1.

d) f : ℝ → ℝ, f(x) = x^{4} − x^{2}: not injective as f(0) = f(1) = 0. Not surjective as x^{4} − x^{2} = x^{2}(x^{2} − 1) > −1 and hence f(x) = −1 has no solutions. To see that take x^{4} − x^{2} = −1. This means that (x^{2} − 1)^{2} + x^{2} = 0. But this is impossible.

Problem 5.

a) Write the number 10001 in base b = 2: 10001 = (10011100010001)_{2}.

b) Let x = (10001)_{3} and y = (111)_{3}. Compute the sum x + y and the product x · y in base b = 3: As x = 3^{4} + 1 = 82 and y = 3^{2} + 3 + 1 = 13. We have

x + y = 95 = 3^{4} + 3^{2} + 3 + 2 = (10112)_{3},
xy = 1066 = 3^{6} + 3^{5} + 3^{4} + 3^{2} + 3 + 1 = (1110111)_{3}.

BONUS PROBLEM. Suppose m, n ∈ ℤ and n^{2} + 1 = 2m. Prove that m is a sum of two squares (i.e., m = p^{2} + q^{2} where p, q are some integers).

Proof: Note that n has to be odd for n^{2} + 1 to be even. Take n = 2k + 1. We get (2k + 1)^{2} + 1 = 2m which means that 4k^{2} + 4k + 2 = 2m. let us divide by 2:

m = 2k^{2} + 2k + 1 = k^{2} + (k^{2} + 2k + 1) = k^{2} + (k + 1)^{2}