EXAM

Exam 2 Math 157

Thursday, October 17, 2013

ANSWERS

Problem 0. Bonus. “lapidate” means kill by throwing stones at.

Problem 1. Let x ≥ −1. Prove that for all n ∈ ℕ we have (1 + x)^{n} ≥ 1 + xn.

Answer: We use induction. When n = 1, the statement (1 + x)^{n} ≥ 1 + xn is the statement

(1 + x)^{1} ≥ 1 + x,

which is true since both sides are equal. Now, assume the statement is true for some natural number k. That is, assume

(1 + x)^{k} ≥ 1 + xk.

Consider (1 + x)^{k+1}:

(1 + x)^{k+1} = (1 + x)^{k}(1 + x)
≥ (1 + kx)(1 + x)  because (1 + x)^{k} ≥ 1 + xk and (1 + x) ≥ 0
= 1 + (k + 1)x + kx^{2}
≥ 1 + (k + 1)x  because kx^{2} ≥ 0.

This proves that if the statement is true for k, then the statement is true for k + 1, completing our proof by induction.

Problem 2. Let X and Y be sets and f : X → Y be a function. Consider the following

argument: Suppose that f : X → Y is not injective. Then there exist elements x, z ∈ X with f(x) = f(z) and x ≠ z. Let A = {x}. Note that z ∈ X \ A so

f(z) ∈ f(X \ A).

Since x ∈ A, f(x) ∈ f(A), so

f(x) ∉ Y \ f(A).

Since f(x) = f(z), we’ve found an element in f(X \ A) that is not in Y \ f(A). Therefore, f(X \ A) ⊈ Y \ f(A).

Which of the following propositions does the argument above prove?

(a) If f is injective, then for all A ⊆ X we have f(X \ A) ⊆ Y \ f(A).

(b) If f is injective, then there exists a set A ⊆ X with f(X \ A) ⊆ Y \ f(A).

(c) If for all subsets A ⊆ X we have f(X \ A) ⊆ Y \ f(A), then f is injective.

(d) If f is injective, then for all A ⊆ X we have Y \ f(A) ⊆ f(X \ A).

(e) If for all sets A ⊆ X we have Y \ f(A) ⊆ f(X \ A), then f is injective.

(f) If f is not injective, then for all A ⊆ X we have f(X \ A) ⊈ Y \ f(A). Answer: (c). The argument proves that if f is not injective, there exists a set A ⊆ X for which f(X\A) ⊈ Y \ f(A). This proves that if for all sets A ⊂ X we have f(X \ A) ⊈ Y \ f(A), then f is injective.

Problem 3. Give an example of a function f : X → Y and a set A ⊆ X for which

f^{−1}(f(A)) ≠ A.

Answer: Let X = {1, 2, 3, 4} and Y = {a, b, c, d} and define

f : X → Y
1 ↦ a
2 ↦ b
3 ↦ b
4 ↦ c

Let A = {1, 2}. Then

f^{−1}(f(A)) = f^{−1}({a, b}) = {1, 2, 3} ≠ A.

Problem 4. True or False. Right answer +1, wrong answer −1, no answer 0.

(a) The field axioms of ℝ imply that 1 + 1 ≠ 0.

Answer:

False. To see that it’s false, note that {0, 1} with addition defined by

0 + 0 = 0,  0 + 1 = 1 + 0 = 1,  1 + 1 = 0

and multiplication defined by

0 × 0 = 0,  0 × 1 = 1 × 0 = 0,  1 × 1 = 1

satisfies all the field axioms that ℝ satisfies and 1 + 1 = 0.

(b) For all functions f : X → Y and for all sets C ⊆ Y, we have f^{−1}(Y \C) = X \f^{−1}(C).

Answer:

True. Here’s a proof.

Let f : X → Y be a function and C ⊆ Y. To show that f^{−1}(Y \ C) ⊆ X \ f^{−1}(C), let x ∈ f^{−1}(Y \ C). This means that f(x) ∈ Y \ C. So, f(x) ∉ C. Since f(x) ∉ C, we know x ∉ f^{−1}(C), implying that x ∈ X \ f^{−1}(C).

To show that X \ f^{−1}(C) ⊆ f^{−1}(Y \ C), let x ∈ X \ f^{−1}(C). So x ∉ f^{−1}(C). This implies that f(x) ∉ C. Therefore f(x) ∈ Y \ C. This says that x ∈ f^{−1}(Y \ C) as needed.

Problem 4. Continued.

(c) For all functions f : X → Y and for all sets C ⊆ Y, we have f(f^{−1}(C)) = C.

Answer:

False. Let X = {1, 2, 3, 4} and Y = {a, b, c, d} and define

f : X → Y
1 ↦ a
2 ↦ b
3 ↦ b
4 ↦ c

Let C = {b, d}. Then f^{−1}(C) = {2, 3} and f(f^{−1}(C)) = {b}.

(d) For all injective functions f : X → Y and for all sets A ⊆ X we have f^{−1}(f(A)) = A.

Answer:

True. Here’s a proof.

First, we’ll prove that for all functions f : X → Y and all subsets A ⊂ X, we have A ⊆ f^{−1}(f(A)). So, suppose f : X → Y is a function and A ⊆ X. Let x ∈ A. Then f(x) ∈ f(A). Since f^{−1}(f(X)) consists of all elements x ∈ X with f(x) ∈ f(A), we have x ∈ f^{−1}(f(A)).

Now we will prove that if f is injective, we have f^{−1}(f(A)) = A. So, let x ∈ f^{−1}(f(A)). This means that f(x) ∈ f(A). This means that there exists a z ∈ A with f(z) = f(x). Since f is injective, x = z, and we find x ∈ A.