Mathematics 327  Sample Exam #1 - SOLUTIONS  3 October 2000

Problem 1. Suppose a is rational and b is irrational. Prove that a + b and ab are both irrational.

Proof: (a+b) Suppose a ∈ ℚ and b ∈ ℝ\ℚ. Further suppose a = \frac{p}{q} with p, q ∈ ℤ, q ≠ 0. We proceed by contradiction. Suppose that a + b ∈ ℚ. By definition that means that a + b = \frac{n}{m} for some integers n, m ∈ ℤ, m ≠ 0. But then we have

b = \frac{n}{m} − \frac{p}{q} = \frac{nq − mp}{mq}.

Since both nq − mp, mq ∈ ℤ, mq ≠ 0 this means that b is rational. This contradict the hypothesis.

Proof: (ab) Note that this second statement is not true as stated. For example, a = 0, b = \sqrt{2}, and ab = 0 shows that it is false because 0 ∈ ℚ,\sqrt{2} ∈ ℝ \ ℚ but their product iz zero which is rational.. However, the statement is true if we assume that a ≠ 0. Congratulations if you were able to notice that!

The proof is almost identical to the one for the sum. Suppose a ∈ ℚ and b ∈ ℝ \ ℚ. Further suppose a = \frac{p}{q} with p, q ∈ ℤ, q ≠ 0. Since a ≠ 0 this means that p ≠ 0 as well. We proceed by contradiction. Suppose that ab ∈ ℚ. By definition, that means that ab = \frac{n}{m} for some integers n, m ∈ ℤ, m ≠ 0. But then we have

b = \frac{n}{m} · \frac{q}{p} = \frac{nq}{mp}.

Since both nq, mp ∈ ℤ, mp ≠ 0 this means that b is rational. This contradict the hypothesis.

Problem 2. Suppose A ∩ B = A. Determine A ∪ B =?

Note that, by definition of the intersection A ∩ B, for any two sets we have

A ∩ B ⊆ A, A ∩ B ⊆ B.

Since A ∩ B = A the second inclusion becomes A ⊆ B. But if A is a subset of B then A ∪ B = B.

Problem 3. Determine whether or not each of the binary relations R is reflexive symmetric, antisymmetric, or transitive:

a) A = {1, 2}, R = {(1, 2)}.

not reflexive (does not contain (1, 1)), not symmetric (contains (1, 2) but not (2, 1)), antisymmetric and transitive (any 1-element relation is always antisymmetric and transitive)

b) A = {1, 2, 3, 4}, R = {(1, 1), (1, 2), (2, 1), (3, 4)}.

not reflexive (does not contain (2, 2)), not symmetric (does not contain (4, 3) while it does contain (3, 4)), not antisymmetric( contains the two pairs (1, 2), (2, 1) whith 2 ≠ 1), transitive c) A = ℤ, (a, b) ∈ R if and only if ab ≥ 0.

reflexive (because a^{2} ≥ 0 for all a ∈ ℝ), symmetric (because ab ≥ 0 if and only if ba ≥ 0), not antisymmetric (because (1, 2) and (2, 1) are both in R), not transitive (becasue if (−1) · 0 ≥ 0 and 0 · 1 ≥ 0 but (−1) · 1 is negative).

d) A = ℝ, (a, b) ∈ R if and only if a^{2} = b^{2}.

reflexive because ((a, a) ∈ R (a^{2} = a^{2}) for all a ∈ ℝ), symmetric (because (a, b) ∈ R is true if and only if (b, a) ∈ R (a^{2} = b^{2} is the same as b^{2} = a^{2})), transitive (because a^{2} = b^{2} and b^{2} = c^{2} implies that a^{2} = c^{2}). This is an equivalence relation. The equivalence class of 0 is [0] = {0} and equivalence class of every other a ∈ ℝ is [a] = {−a, +a}. The quotient set can be identified with the interval [0, ∞).

Problem 4. Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. For a, b ∈ A define a ∼ b if ab is a perfect square.

a) List ordered pairs of this relation.

Each elemend of A is in relation with itself (relation is reflexive) so we have all the diagonal elements (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9) in “ ∼ ” ⊆ A × A. Since 1 ∼ 4 ∼ 9, and 2 ∼ 8 we have (1, 4), (4, 1), (1, 9), (9, 1), (4, 9), (9, 4) and (2, 8), (8, 2) in as well. By inspection, it is easy to see that this is all.

b) For each a ∈ A find the [a] ≡ ā = {x ∈ A | x ∼ a}

From part (a) we get [1] = [4] = [9] = {1, 4, 9} and [2] = [8] = {2, 8}, with [3] = {3},

[5] = {5}, [6] = {6}, [7] = {7}, for all the others.

c) Explain why ∼ is an equivalence relation on A.

It is reflexive as a^{2} is a perfect square. It is symmetric as ab being a perfect square is equivalent to ba being also one. It is also transitive which is obvious by inspection.

Note: This relation is an equivalence realtion not just on A but on ℕ as well. If a · b = k^{2} and b · c = l^{2} then, in fact a · c = \frac{k^{2}l^{2}}{b^{2}} = (kl/b)^{2}. One only has to show that b divides the product kl. We will prove it in class when we discuss factorization of integers.

Problem 5. Draw the Hesse diagram for the following partial order:

({{a}, {a, b}, {c}, {a, c}, {a, b, c}, {a, b, d}}, ⊆).

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ∘ ∘ ∘ {a} {a, b} {a, b, c}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}∘ ∘ ∘ {c} {a, c} {a, b, d}

Problem 6. Let f : A → A be defined by f(x) = x^{2} + 2.

a) Let A = ℤ. Determine if f is injective and surjective.

f(−1) = f(1) = 3 so f is not injective. f(x) = 4 has no solutions for x ∈ ℤ so that f is not surjective. b) Repeat part (a) for A = ℝ. f(−1) = f(1) = 3 so f is not injective. f(x) = 0 has no solutions for x ∈ ℤ so that f is not surjective.

Problem 7. Let X = {a, b} and Y = {1, 2, 3}.

a) List all the functions from X to Y.

f_{1} = {(a, 1), (b, 1)},  f_{2} = {(a, 1), (b, 2)},  f_{3} = {(a, 1), (b, 3)},
f_{4} = {(a, 2), (b, 1)},  f_{5} = {(a, 2), (b, 2)},  f_{6} = {(a, 2), (b, 3)},
f_{7} = {(a, 3), (b, 1)},  f_{8} = {(a, 3), (b, 2)},  f_{9} = {(a, 3), (b, 3)}.

b) List all the functions from Y to X.

g_{1} = {(1, a), (2, a), (3, a)}, g_{2} = {(1, a), (2, a), (3, b)},

g_{3} = {(1, a), (2, b), (3, a)}, g_{4} = {(1, a), (2, b), (3, b)},
g_{5} = {(1, b), (2, a), (3, a)}, g_{6} = {(1, b), (2, a), (3, b)},
g_{7} = {(1, b), (2, b), (3, a)}, g_{8} = {(1, b), (2, b), (3, b)}.

c) List all the injective functions from X to Y. f_{2}, f_{3}, f_{4}, f_{6}, f_{7}, f_{8} are all injective while f_{1}, f_{5}, f_{9} are not.

d) List all the surjective functions from X to Y. There are none.

Problem 8. 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, 4), (4, 5), (5, 3)},
g = {(1, 3), (2, 5), (3, 1), (4, 2), (5, 4)},
h = {(1, 2), (2, 2), (3, 4), (4, 3), (5, 1)}.

a) Find f ∘ g and g ∘ f.

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

b) Find f^{−1}, g^{−1}, and h^{−1} (if they exist). f^{−1} = {(2, 1), (1, 2), (4, 3), (5, 4), (3, 5)},

g^{−1} = {(3, 1), (5, 2), (1, 3), (2, 4), (4, 5)},

h^{−1} does not exist as h is not injective (h(1) = h(2) = 2).

c) Show that (f ∘ g)^{−1} = g^{−1} ∘ f^{−1} ≠ f^{−1} ∘ g^{−1}.

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

Problem 9.

a) Find the one-to-one correspondence between the intervals (1, ∞) and (3, ∞) Take f(x) = x + 2. This is injective and surjective map f : (1, ∞) → (3, ∞) as desired.

b) Find the one-to-one correspondence between the intervals (0, 1) and (a, b). We will construct a liner function f(x) = αx + β that does the job. How should we

choose the constants? Well, f(0) = a = β and f(1) = b = α + β. Hence, α = b − a. So take f(x) = (b−a)x+a. This is a liner function with non-zero slope. Any such function is injective. But f((0, 1)) = (a, b) by our choice of the constants so it must also be surjective.

Problem 10.

a) Write the number 1001 in base b = 2, 8. Since 1001 = 2^{9} + 2^{8} + 2^{7} + 2^{6} + 2^{5} + 2^{3} + 1 = 512 + 256 + 128 + 64 + 32 + 8 + 1 we get 1001 = (1111101001)_{2}. Since 1001 = 8^{3} + 7 · 8^{2} + 5 · 8 + 1 we get 1001 = (1751)_{8}.

b) Suppose in base 12 we use A to denote 10 and B to denote 11. What is 1BBA? (1BBA)_{12} = 10 + 11 · (12) + 11 · (12)^{2} + (12)^{3} = 3, 454.