Category Theory: September 12

Covered in Class

1. Coequalizers

   • Definition of equivalance relation and example of the rational numbers as pairs ℤ × ℤˣ (where ℤˣ = ℤ∖{0}) such that (a,b) ~ (c,d) iff ad = bc. Then ℚ = ℤ × ℤˣ / ~ 

   • Trivial example: Let A =  ℤ × ℤ. and let B = ℤ.  Let π₁, π₂ : A → B be the first and second projections. Then the coequalizer (E, e) is E = ⊤.

   • Let A ⊆  (ℤ × ℤˣ) × (ℤ × ℤˣ) be all pairs (a/b, c/d) such that ad=bc. and let B = ℤ × ℤˣ.  Let π₁, π₂ : A → B be the first and second projections. Then the coequalizer (E, e) is E = ℚ and e : B → E takes (a/b) to [a/b], it's equivalence class under ~.

   • An example which gives an idea of how to construct coequalizers for Set: Given A = ℕ, B = ℕ and f,g : A → B, define f(n) = n and g(n) = n/2 if n is even and 3n+1 if n is odd. Then (E,e) can be defined such that E = ℕ / ~ and e is the natural map, where m ~ n iff there is a path from m to n in the undirected graph in which there is an edge between m and n if g(m) = n.

2. The last example above used the 3x+1 function. There is an excellent book on the problem, and the two key articles Lagarias wrote for that book are available online for free, both well worth reading. See also Terry Tao's work on the problem.

   • The 3x + 1 Problem: An Overview

   • The 3x + 1 Problem and Its Generalizations

3. We didn't have time to get to pushouts.

Suggested Exercises

All exercises are optional; pick any that look interesting and feel free to create your own! I'll be around in the lab on Tuesday from 10-11 and from 12 to about 1:30 if anyone wants to discuss solutions; also I encourage you to work together and discuss the material with each other! Feel free to post also to the #category-theory Slack channel.

See also the exercises in Gilbert Bernstein's Machines, Monoids, Categories handout.

1. Enjoy the rest of the break before the start of the school year!