The Azimuth Project
Applied Category Theory - Chapter 1 - Puzzles

Applied Category Theory

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!

  • Puzzle 11.

Show that if the monotone map f:AB f: A \to B has an inverse g:BA g : B \to A that is also a monotone map, gg is both a right adjoint and a left adjoint of ff .

  • Puzzle 12. Find a right adjoint for ff: that is, a function g:g : \mathbb{N} \to \mathbb{N} with f(m)n if and only if mg(n) for all m,nmathbbNf(m) \le n \text{ if and only if } m \le g(n) \text{ for all } m,n \in mathbb{N}. How many right adjoints can you find?

  • Puzzle 13. Find a left adjoint for ff: that is

  • 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 *:PXPY f_{\ast} : PX \to PY is a monotone function.

  • Puzzle 18. Does f * 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 *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 *:PYPXf^{\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:i : \mathbb{N} \to \mathbb{R} have a left adjoint? Does it have a right adjoint? If so, what are they?

  • Puzzle 22 What operation on subsets corresponds to the logical operation “not”? Describe this operation in the language of posets, so it has a chance of generalizing to other posets. Based on your description, find some posets that do have a “not” operation and some that don’t.

  • Puzzle 24 Show that f !:PXPY f_{!}: PX \rightarrow PY is the right adjoint of f *:PXPY f^{\ast}: PX \rightarrow PY .

  • Puzzle 28 Show that if \(P\) is a partition of a set \(X\), and we define a relation \(\sim_P\) on \(X\)

  • Puzzle 29 Show that if \(\sim\) is an equivalence relation on a set \(X\), we can define a partition \(P_\sim\) on \(X\)

  • Puzzle 31 Show that the previous two puzzles give a one-to-one correspondence between partitions of \(X\) and equivalence relations on \(X\).

  • Puzzle 32 Proposition 1.11 of [Seven Sketches]

  • Puzzle 33 Is an equivalence relation always a preorder?