[FrontPage] [TitleIndex] [WordIndex

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


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

1.1. Solution

∪B = ℕ. Proof: Let x∈ℕ. Then x∈Ax+1∈B and so x∈∪B. It follows that ℕ⊆∪B. For the other direction, if x∈∪B, then x∈Ai for some i. But Ai⊆ℕ 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

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

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.

2014-06-17 11:57