Exercises 0.3 #4

I) Let E be a correspondence from U to X. If (s0, x0) ∈ (ED)C then there is a t0 ∈ T such that (t0, x0) ∈ ED and (s0, t0) ∈ C. And there is a u0 ∈ U such that (u0, x0) ∈ E and (t0, u0) ∈ D. So (s0, u0) ∈ DC and (s0, x0) ∈ E(DC). Thus (ED)C ⊂ E(DC). If (s1, x1) ∈ E(DC) then there is a u1 ∈ U such that (u1, x1) ∈ E and (s1, u1) ∈ DC. And there is a t1 ∈ T such that (t1, u1) ∈ D and (s1, t1) ∈ C. So (t1, x1) ∈ ED and (s1, x1) ∈ (ED)C. Thus E(DC) ⊂ (ED)C. Therefore (ED)C = E(DC).

II) To do

Exercises 0.3 #2

~ ⊂ ℕ(2) × ℕ(2). If (a1, a2) ∈ ℕ(2) then a1 + a2 = a2 + a1. So ((a1, a2), (a1, a2)) ∈ ~. If ((a1, a2), (b1, b2)) ∈ ℕ(2) × ℕ(2) then a1 + b2 = a2 + b1. By commutativity b1 + a2 = b2 + a1, so ((b1, b2), (a1, a2)) ∈ ℕ(2) × ℕ(2). If ((a1, a2), (b1, b2)), ((b1, b2), (c1, c2)) ∈ ℕ(2) × ℕ(2) then a1 + b2 = a2 + b1 and b1 + c2 = b2 + c1. Subtracting gives a1 – c1 = a2 – c2, so a1 + c2 = a2 + c1. Thus ((a1, a2), (c1, c2)) ∈ ℕ(2) × ℕ(2). Hence ~ is an equivalence relation.

Exercises 0.3 #1

i) If m, n ∈ ℕ then m × n ∈ ℕ and m + n ∈ ℕ. So [X = {2k | k ∈ ℕ} ∪ {2k + 1 | k ∈ ℕ}] ⊂ ℕ. Let n ∈ ℕ. Since ℕ is not bounded above, there is a largest k ∈ ℕ such that 2k ≤ n. So 2k ≤ n < 2(k + 1) = 2k + 2. Because there is no natural number between a natural number and its successor, n = 2k or n = 2k + 1. So ℕ ⊂ X. Thus X = ℕ. Let m ∈ {2k | k ∈ ℕ} ∩ {2k + 1 | k ∈ ℕ}. Then m = 2k1 = 2k2 + 1 for k1, k2 ∈ ℕ. If k1 = k2 then 2k2 + 1 > 2k1. If k1 < k2 then 2k2 + 1 > 2k1. If k1 > k2 then k1 ≥ k2 + 1 > k2 ⇒ 2k1 > 2k2 + 1. Contradiction. Thus {2k | k ∈ ℕ} and {2k + 1 | k ∈ ℕ} are disjoint.

ii) Skipped (similar to (i)).

Exercises 0.2 #5

I) S = {s1, s2, s3}, T = {t1, t2}, A = {s1}, α = {(s1, t1), (s2, t1), (s3, t2)}, α(~A) = {t1, t2}, ~α(A) = {t2}. Thus α(~A) ⊄ ~α(A).

II) Suppose α is injective and α(~A) ⊄ ~α(A). Then there is a t ∈ T such that t ∈ α(~A) and t ∉ ~α(A) ⇒ there is an s1 ∈ ~A such that α(s1) = t and t ∈ α(A) ⇒ there is an s2 ∈ A such that α(s2) = t ⇒ α(s1) = α(s2) and s1 ≠ s2. Contradiction. Thus α is injective ⇒ α(~A) ⊂ ~α(A).

III) α is surjective can’t imply α(~A) ⊄ ~α(A), otherwise a bijective map would contradict part (II). α is surjective can’t imply α(~A) ⊂ ~α(A) by the example in part (I).

Exercises 0.2 #4

I) t ∈ α(A ∪ B) ⇒ there is an s ∈ A ∪ B such that α(s) = t ⇒ there is an s ∈ A or s ∈ B such that α(s) = t ⇒ t ∈ α(A) or t ∈ α(B). Thus α(A ∪ B) ⊂ α(A) ∪ α(B). t ∈ α(A) ∪ α(B) ⇒ there is an s ∈ A or s ∈ B such that α(s) = t ⇒ there is an s ∈ A ∪ B such that α(s) = t ⇒ t ∈ α(A ∪ B). Thus α(A) ∪ α(B) ⊂ α(A ∪ B).

II) t ∈ α(A ∩ B) ⇒ there is an s ∈ A ∩ B such that α(s) = t ⇒ there is an s ∈ A and s ∈ B such that α(s) = t ⇒ t ∈ α(A) and t ∈ α(B). Thus α(A ∩ B) ⊂ α(A) ∩ α(B).

III) α = { (s1, t1), (s2, t0), (s3, t0) }. A ⊂ S = { s1, s2 }. B ⊂ S = { s1, s3 }. α(A ∩ B) = { t1 }. α(A) ∩ α(B) = { t1, t0 }.

Exercises 0.2 #3

I) Let α: S → T. Suppose α is surjective and there exist maps β1, β2 of T into a set U such that β1 ≠ β2 but β1α = β2α. Then there is a t ∈ T such that β1(t) ≠ β2(t). And there is an s ∈ S such that α(s) = t. So β1(α(s)) ≠ β2(α(s)). Contradiction. Conversely, by contraposition, if α is not surjective define β1: T → U as the union of { (t, u0) | t ∈ im α, u0 an arbitrary fixed element in U } and { (t, u1) | t ∉ im α, u1 an arbitrary fixed element in U }. Define β2 as β1 with (t, u1) replaced by (t, u2), u1 ≠ u2 for every t ∉ im α. Thus β1α = β2α and β1 ≠ β2.

II) Suppose α is injective and there exist maps γ1, γ2 of a set U into S such that γ1 ≠ γ2 but αγ1 = αγ2. Then there is a u ∈ U such that γ1(u) ≠ γ2(u). So α(γ1(u)) ≠ α(γ2(u)). Contradiction. Conversely, by contraposition, if α is not injective there exists s1, s2 such that s1 ≠ s2 and α(s1) = α(s2). Define γ1: U → S as { (u, s1) | u ∈ U }. Define γ2: U → S as { (u, s2) | u ∈ U }. Thus γ1 ≠ γ2 but αγ1 = αγ2.

Exercises 0.2 #2

I) Let X ⊂ T be the set of all elements not in the range of α. Define β: T → S as the union of { (α(s), s) | s ∈ S } and U = { (x, s) | x ∈ X, s ∈ S }, (x, s1), (x, s2) ∈ U ⇒ s1 = s2. Since α is injective, β is well-defined. If s ∈ S β(α(s)) = s ⇒ βα = 1S. Conversely, suppose α is not injective. There exists s1, s2 such that α(s1) = α(s2) and s1 ≠ s2. So s1 = β(α(s1)) = β(α(s2)) = s2, contradicting s1 ≠ s2.

II) Since α is surjective, choose one and only one s in the fiber (section 0.3) over t ∈ im α such that (t, s) ∈ β for every t ∈ T. β is clearly a map and αβ = 1T. Conversely, suppose α is not surjective. Then there exists a t1 ≠ α(s) for every s ∈ S. Since αβ = 1T, α(β(t1)) = t1. Contradiction.

III) For part (I) if β is unique, every element t ∈ T must be in the range of α. Otherwise the image under β, of each t not in the range of α, can be made arbitrarily different. Thus contradicting the uniqueness of β.

For part (II) suppose β is unique and α is not injective. Then there exists s1, s2 such that α(s1) = α(s2) and s1 ≠ s2. If (α(s1), s1) ∈ β, replace it with (α(s1), s2). If (α(s1), s2) ∈ β, replace it with (α(s1), s1). Thus β is not unique. Contradiction.