MATH327 – HOMEWORK SOLUTIONS HOMEWORK #5

Section 2.2: Problems 1, 4, 6, 8, 9 Section 2.3: Problems 3,4,13,17

Krzysztof Galicki Problem 2.2.1.

a) f : ℚ → ℚ defined by f(x) = 3x + 5 is clearly both injective and surjective. Hence, the inverse exists and it is g(x) = \frac{1}{3}(x − 5), where g : ℚ → ℚ.

b) f : ℝ → ℝ defined by f(x) = x^{3} − 2 is bijective. Hence, the inverse exists and it is g(x) = (x + 2)^{1/3}, where g : ℝ → ℝ.

c) f : ℝ → ℝ defined by f(x) = x|x| is clearly injective and surjective. Hence, the inverse exists and it is

g(x) = \{ \begin{matrix}\sqrt{x} & if x ≥ 0 \\ −\sqrt{−x} & if x ≤ 0, \end{matrix}

where g : ℝ → ℝ.

d) β : (3/4, ∞) → ℝ defined by β(x) = log_{2}(3x−4) is bijective. Hence, the inverse exists and it is g(x) = \frac{1}{3}(2^{x} + 4), where g : ℝ → (3/4, ∞).

Problem 2.2.4. Let S = {1, 2, 3, 4, 5} and T = {1, 2, 3, 8, 9} and define f : S → T and g : S → S by

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

a) f ∘ g : S → T and we get f(g(1)) = f(2) = 1, f(g(2)) = f(2) = 1, f(g(3)) = f(1) = 8, f(g(4)) = f(3) = 9, f(g(5)) = f(2) = 1. Hence,

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

g ∘ f is not defined since the domain of g and the range of f are different. f ∘ f is not defined for the same reason. Finally, g ∘ g : S → S and we get g(g(1)) = g(2) = 2, g(g(2)) = g(2) = 2, g(g(3)) = g(1) = 2, g(g(4)) = g(3) = 1, g(g(5)) = g(2) = 2. Hence,

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

b) f is both injective and surjective. g is neither: g(1) = g(2) and {4, 5} are not in its range.

c) Since f is both injective and surjective, its inverse exists and

f^{−1} = {(8, 1), (9, 3), (3, 4), (1, 2), (2, 5)}.

d) Since g is not injective it does not have an inverse.

Problem 2.2.6. Let S = {1, 2, 3, 4} and f, g : S → S be

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

Both functions are bijective and f^{−1} = {(3, 1), (2, 2), (4, 3), (1, 4)},

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

We have

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

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

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

b) f ∘ g^{−1} ∘ g = f.

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

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

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

d) g ∘ g^{−1} ∘ f = f.

e) We have

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

Problem 2.2.8. Let f, g, h : ℝ → ℝ be defined by

f(x) = x + 2, g(x) = \frac{1}{x^{2} + 1}, h(x) = 3.

We have

f^{−1}(x) = x − 2.

Then

g ∘ f(x) = \frac{1}{(x + 2)^{2} + 1},

f ∘ g(x) = \frac{1}{x^{2} + 1} + 2,

h ∘ g ∘ f(x) = 3,

g ∘ h ∘ f(x) = \frac{1}{10},

g ∘ f^{−1} ∘ f(x) = g(x),

f^{−1} ∘ g ∘ f(x) = \frac{1}{(x + 2)^{2} + 1} − 2.

Problem 2.2.9. Let f, g, h : ℝ^{+} → ℝ be

f(x) = \frac{x}{x + 1}, g(x) = \frac{1}{x}, h(x) = x + 1.

Then

g ∘ f(x) = \frac{x + 1}{x},

f ∘ g(x) = \frac{1}{x + 1},

h ∘ g ∘ f(x) = \frac{x + 1}{x} + 1,

f ∘ g(x) ∘ h = \frac{1}{x + 2}.

Problem 2.3.3.

a) f = {(x, 14), (y, −3), ({a, b, c}, t)} is one of the 6 examples of such correspondences.

b) f : 2ℤ → 17ℤ, f(2k) = 17k, where k is any integer.

c) f : ℕ × ℕ → {a + bi ∈ ℂ | a, b ∈ ℕ} defined by f(a, b) = a + bi.

d) f : ℕ × ℕ → ℕ × ℤ, where

f(a, b) = \{ \begin{matrix}(a, k − 1) & if b = 2k, k ∈ ℕ \\ (a, −k) & if b = 2k − 1, k ∈ ℕ \end{matrix}

e) f : ℕ → {m/n | m ∈ ℕ, n = 1, 2}, where

f(a) = \{ \begin{matrix}k & if a = 2k, k ∈ ℕ \\ k/2 & if a = 2k − 1, k ∈ ℕ \end{matrix}

Problem 2.3.4. This is false as shown by the example 2ℤ ⊂ ℤ. The inclusion is proper but the sets have the same cardinality. The following theorems are true.

Theorem 1: Let A ⊊ B and let B be finite, that is cardinality |B| < ∞. Then |A| < |B|.

Proof: Since B is finite we can identify B with an N-element set {1, 2, ..., N} for some N and then |B| = N. Since A is a proper subset of B, A will be in one-to-one correspondence with a proper subset of {1, 2, ..., N} and therefore |A| < N. This proves the theorem.

Theorem 2: Let A ⊆ B. Then |A| ≤ |B|.

Proof: The inclusion A ⊆ B is an injective map (but not surjective, unless A = B). By definition, |A| ≤ |B| if there exists any injective function f : A → B.

Problem 2.3.13.

a) The set S = {x ∈ ℝ | 1 < x < 2} is uncountable as it is in one-to-one correspondence with the open interval (0, 1), via the function f(x) = x − 1. The latter is uncountable via the diagonal argument.

b) The set S = \{x ∈ ℚ | 1 < x < 2\} countably infinite. It is infinite as 1 + \frac{1}{n+1} ∈ S for any n ∈ ℕ. On the other hand S is a proper subset of ℚ, so it must be countable by the fact that ℚ is countable (see Theorem 2 above).

c) The set S = {m/n | m, n ∈ ℕ, m < 100, 5 < n < 105} is finite as |S| ≤ 99 · 100 = 9900.

d) The set S = {m/n | m, n ∈ ℤ, m < 100, 5 < n < 105} is infinite as, every negative integer is an element of S (simply take m = −100k, n = 100). Furthermore, S is a proper subset of ℚ, so it must be countable by the fact that ℚ is countable.

e) Note that {a + ib) ∈ ℂ | a, b ∈ ℕ} = ℕ × ℕ and the latter set is countable.

f) The set S = {(a, b) ∈ ℚ × ℚ |a + b = 1} is in one-to-one correspondence with the set ℚ via mapping f(a, b) = a. Hence it is infinitely countable.

g) The set S = \{(a, b) ∈ ℝ × ℝ | b = \sqrt{1 − a^{2}}\} is in one-to-one correspondence with the set (−1, 1), via the map f(a, b) = a. On the other hand, the open interval (−1, 1) is in is in one-to-one correspondence with the open interval (0, 1) via the map g(x) = \frac{x+1}{2}. Hence, S is uncountable.

Problem 2.3.17. Theorem: If A is countable so is A × A.

Proof: By definition, if A is countable then either A is finite, or there exists a bijection f : A → ℕ. in the first case the Cartesian product is also finite, hence, countable. In the second case, observe that the map F : A × A → ℕ × ℕ, defined by

F (a_{1}, a_{2}) = (f(a_{1}), f(a_{2}))

is also a bijection. Hence,

|A × A| = |ℕ × ℕ| = |ℕ| = ℵ_{0}.