1. A big union

For each i∈ℕ, define

• A_i = { j∈ℕ | j < i }

Define

• B = { A_i | i∈ℕ }

What is ∪B, the union of all elements of B? Prove your answer.

1.1. Solution

∪B = ℕ. Proof: Let x∈ℕ. Then x∈A_x+1∈B and so x∈∪B. It follows that ℕ⊆∪B. For the other direction, if x∈∪B, then x∈A_i for some i. But A_i⊆ℕ so x∈ℕ. Thus ∪B⊆ℕ.

2. A big sum

Let f(n) = 0⋅1 + 1⋅2 + 2⋅3 + 3⋅4 + ... + n(n+1). Prove that f(n) = n(n+1)(n+2)/3 for all n in ℕ.

2.1. Solution

We proceed by induction on n. For n = 0, we have f(0) = 0⋅1 = 0 = 0⋅1⋅2/3. Now suppose that the hypothesis holds for n, and we will show that it also holds for n+1. Compute

• f(n+1) = f(n) + (n+1)(n+2) = n(n+1)(n+2)/3 + (n+1)(n+2) = [n(n+1) + 3(n+1)] (n+2)/3 = [(n+3)(n+1)](n+2)/3 = (n+1)(n+2)(n+3)/3

and the induction hypothesis continues to hold for n+1.

3. Functions

Let f:A→B and g:B→C.

1. Prove or disprove: if f is bijective, and g is bijective, then their composition g∘f is bijective.
2. Prove or disprove: if g∘f is bijective, then f and g are both bijective.

3.1. Solution

1. Proof: Suppose f and g are both bijective. Then f(x) = f(y) if and only if x = y. But then g(f(x)) = g(f(y)) ⇔ f(x) = f(y) ⇔ x = y, and so g∘f is bijective.
2. Disproof: Let A = { 0 }, B = { 0, 1 }, C = A. Let f(x) = g(x) = 0 for all x. Then g∘f(0) = 0. This is surjective (it covers all elements of C) and injective (it never maps two distinct elements of A to the same element of C, since there aren't two distinct elements of C); it follows that it is bijective. But g isn't, since it maps both 0 and 1 to 0.

4. Cancellation

Let F be the set of all functions from ℕ to ℕ. A function f in F has the left cancellation property if

• f∘g = f∘h ⇒ g = h

for all g, h in F, where two functions g and h are equal if and only if g(x) = h(x) for all x in their common domain.

Show that f has the left cancellation property if and only if f is injective.

4.1. Solution

Suppose first that f is injective. Choose g and h and suppose that f∘g = f∘h. Then for any x∈ℕ, f(g(x)) = f(h(x)). But if f is injective, then for any x and y, if f(x) = f(y) then x = y. So in particular if f(g(x)) = f(h(x)) then g(x) = h(x). Since this holds for all x, we have g = h.

Now suppose that f is not injective. We will show that f does not have the left cancellation property by exhibiting a particular bad g and h for which f∘g = f∘h but g≠h. Since f is not injective, there exist distinct x, y such that f(x)=f(y). Define g by g(n) = n for all n, and h by h(n) = n for all n≠y, with h(y)=x. Clearly g≠h. Observe though that for any n≠y, g(n)=h(n)=n and f(g(n))=f(h(n)), and for n=y, g(n)=y and h(n)=x, but since f(x)=f(y) we again have f(g(n))=f(h(n)). It follows that f does not have the left cancellation property.