The Azimuth Project
Applied Category Theory - Chapter 1 - Puzzles (Rev #2, changes)

Exercises [from the book]

Puzzles [from the forum lectures]

• Puzzle 1. What is a “poset” according to Chapter 1 of Fong and Spivak’s book?

• Puzzle 2. How does their definition differ from the usual definition found in, e.g., Wikipedia or the nLab?

• Puzzle 3. What do mathematicians usually call the thing that Fong and Spivak call a poset?

• Puzzle 4. List some interesting and important examples of posets that haven’t already been listed in other comments in this thread.

• Puzzle 5. Why is this property called “trichotomy”?

• Puzzle 6. How do reflexivity and transitivity of ≤ follow from the rules of a category, if we have a category with at most one morphism from any object x to any object y, and we write x≤y when there exists a morphism from x to y?

• Puzzle 7. Why does any set with a reflexive and transitive relation ≤ yield a category with at most one morphism from any object x to any object y? That is: why are reflexivity and transitivity enough?

• Puzzle 10. There are many examples of monotone maps between posets. List a few interesting ones!

Definition. Given preorders \(A,\le_A\) and \(B,\le_B\), a Galois connection] is a monotone map \(f : A \to B\) together with a monotone map \(g: B \to A\) such that

for all \(a \in A, b \in B\). In this situation we call \(f\) the left adjoint and \(g\) the right adjoint.

So, the right adjoint of \(f\) is a way of going back from \(B\) to \(A\) that’s related to \(f\) in some way.

• Puzzle 11. Show that if the monotone map \(f: A \to B\) has an inverse \(g : B \to A \) that is also a monotone map, \(g\) is both a right adjoint and a left adjoint of \(f\).

Here’s one easy example to get you started. Let \(\mathbb{N}\) be the set of natural numbers with its usual notion of \(\le\). There’s a function \(f : \mathbb{N} \to \mathbb{N}\) with \(f(x) = 2x \). This function doesn’t have an inverse. But:

• Puzzle 12. Find a right adjoint for \(f\): that is, a function \(g : \mathbb{N} \to \mathbb{N}\) with

for all \(m,n \in \mathbb{N}\). How many right adjoints can you find?

• Puzzle 13. Find a left adjoint for \(f\): that is, a function \(g : \mathbb{N} \to \mathbb{N}\) with

for all \(m,n \in \mathbb{N}\). How many left adjoints can you find?

• Puzzle 14. Find the function g:ℕ→ℕ such that g(b) is the largest possible natural number a with 2a≤b.

• Puzzle 15. Find the function g:ℕ→ℕ such that g(b) is the smallest possible natural number a with b≤2a.

• Puzzle 16. What’s going on here? What’s the pattern you see, and why is it working this way?

• Puzzle 17. Show that \( f_{\ast} : PX \to PY \) is a monotone function.

• Puzzle 18. Does \( f_{\ast} \) always have a left adjoint? If so, describe it. If not, give an example where it doesn’t, and some conditions under which it does have a left adjoint.

• Puzzle 19. Does \(f_{\ast}\) always have a right adjoint? If so, describe it. If not, give an example where it doesn’t, and some conditions under which it does have a right adjoint.

• Puzzle 20. Does \(f^{\ast}: PY \rightarrow PX \) have a right adjoint of its own?

• Puzzle TR1. Why precisely must g(b) be a least upper bound of the set?

• Puzzle 21. Does the monotone function \(i : \mathbb{N} \to \mathbb{R}\) have a left adjoint? Does it have a right adjoint? If so, what are they?