Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 1. A big union

For each i∈ℕ, define

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

Define

• B = { Ai | 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.

2014-06-17 11:57