/Solutions

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.

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 ℕ.

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.

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.