Options

Exercises and Puzzles 3 - Chapter 1

edited May 6 in Exercises

I'm in Leiden now, and this morning I will be kicking off the "Adjoint School" for Applied Category Theory 2018. (Yes, that's a pun.)

I'll talk about a category with open chemical reaction networks as morphisms and pose the problem of using this category to study how the cell uses ATP to power other reactions. Three other researchers will pose other problems, and for the rest of the week we'll work with students to solve these problems.

But our school here must go on! Please try these exercises and then see what other folks have written about them:

This puzzle asks you to count something involving partitions of a 4-element set. If you want a hard combinatorics problem, trying counting it for partitions of an \(n\)-element set. I'd suggest trying to use a generating function, since the easiest way to count partitions uses a generating function.

For this one you can get extra credit for giving a clear characterization of the poset of all numbers \( \{1,2,3,\dots \} \) ordered by divisibility. There's a good way to think about this poset.

Here for extra credit you could try to characterize the poset of real numbers with its usual ordering \(\le\). Cantor did this for the rational numbers: any dense totally ordered countable set without lower or upper bound is isomorphic, as a poset, to the rational numbers with its usual ordering! If you're curious about this result try:

It gives an ordinary human-readable proof and then a fully formal proof built using the Karlsruhe Interactive Verifier.

Puzzle 5. A totally ordered set, also known as a linearly ordered set, is one such that for any two elements \(x\) and \(y\) either \(x \le y\) or \(y \le x\). This property is also called trichotomy. Why?

For extra credit: does the property deserve to be called trichotomy if you are using intuitionistic logic?

Finally, here are two more puzzles connected to Lecture 3. I mentioned that a poset is the same as a category with at most one morphism from any object \(x\) to any object \(y\), where we write \(x \le y\) when there exists a morphism from \(x\) to \(y\).

Puzzle 6. How do reflexivity and transitivity of \(\le\) follow from the rules of a category, if we have a category that's a poset?

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

To see all the exercises in Chapter 1, go here.

Comments

  • 1.
    edited April 23

    Puzzle 6. How do reflexivity and transitivity of \(\le\) follow from the rules of a category, if we have a category that's a poset?

    If we note that given a category \( C \), we can define a relation \( \leq_C \) using the Hom-sets of \( C \) as such, $$ a \leq_C b = \mathrm{min}(1,|\mathrm{Hom}_C[a,b]|), $$ then reflexivity comes from the identity morphism of each object, $$ a \leq_C a \Leftrightarrow \mathrm{min}(1,|\mathrm{Hom}_C[a,a]|), $$ and transitivity comes from composition of morphisms, $$ (a \leq_C b ) \cap (b \leq_Cc) \rightarrow a \leq_C b \\ \Leftrightarrow \\ \mathrm{min}(1,|\mathrm{Hom}_C[a,b]|) \cdot \mathrm{min}(1,|\mathrm{Hom}_C[b,c]|) \rightarrow \mathrm{min}(1,|\mathrm{Hom}_C[a,c]|) . $$

    Comment Source:>**Puzzle 6.** How do reflexivity and transitivity of \\(\le\\) follow from the rules of a category, if we have a category that's a poset? If we note that given a category \\( C \\), we can define a relation \\( \leq_C \\) using the Hom-sets of \\( C \\) as such, $$ a \leq_C b = \mathrm{min}(1,|\mathrm{Hom}_C[a,b]|), $$ then reflexivity comes from the identity morphism of each object, $$ a \leq_C a \Leftrightarrow \mathrm{min}(1,|\mathrm{Hom}_C[a,a]|), $$ and transitivity comes from composition of morphisms, $$ (a \leq_C b ) \cap (b \leq_Cc) \rightarrow a \leq_C b \\ \Leftrightarrow \\ \mathrm{min}(1,|\mathrm{Hom}_C[a,b]|) \cdot \mathrm{min}(1,|\mathrm{Hom}_C[b,c]|) \rightarrow \mathrm{min}(1,|\mathrm{Hom}_C[a,c]|) . $$
  • 2.
    edited April 23

    Puzzle 5. A totally ordered set, also known as a linearly ordered set, is one such that for any two elements \(x\) and \(y\) either \(x \le y\) or \(y \le x\). This property is also called trichotomy. Why?

    Unrolling the definition of \(x \le y \), $$ x \leq y \\ \Leftrightarrow \\ x < y \text{ or } x = y, $$ and applying it we see that, $$ x \leq y \text{ or } y \leq x \\ \Leftrightarrow \\ x < y \text{ or } x = y \text{ or } y = x \text{ or } y < x, $$ and then by applying anti-symmetry of \( x = y \) and \( y = x \) we get the trichotomy, $$ x \leq y \text{ or } y \leq x \\ \Leftrightarrow \\ x < y \text{ or } x = y \text{ or } y < x. $$

    Comment Source:>**Puzzle 5.** A **totally ordered set**, also known as a **linearly ordered set**, is one such that for any two elements \\(x\\) and \\(y\\) either \\(x \le y\\) or \\(y \le x\\). This property is also called **trichotomy**. Why? Unrolling the definition of \\(x \le y \\), $$ x \leq y \\ \Leftrightarrow \\ x < y \text{ or } x = y, $$ and applying it we see that, $$ x \leq y \text{ or } y \leq x \\ \Leftrightarrow \\ x < y \text{ or } x = y \text{ or } y = x \text{ or } y < x, $$ and then by applying anti-symmetry of \\( x = y \\) and \\( y = x \\) we get the trichotomy, $$ x \leq y \text{ or } y \leq x \\ \Leftrightarrow \\ x < y \text{ or } x = y \text{ or } y < x. $$
  • 3.

    I think that needs tweaking, @Keith – with a poset we are simply supplied with the \(\le\) relation, so there is no "definition" to unroll. It's the \(\lt\) relation we need to define, by setting \(x\lt y\) iff \(x\le y\) and not \(y\le x\).

    Comment Source:I think that needs tweaking, @Keith – with a poset we are simply *supplied* with the \\(\le\\) relation, so there is no "definition" to unroll. It's the \\(\lt\\) relation we need to define, by setting \\(x\lt y\\) iff \\(x\le y\\) and not \\(y\le x\\).
  • 4.

    Anindya is right.

    Comment Source:Anindya is right.
  • 5.

    Wait, is the poset of positive naturals ordered by divisibility just the free symmetric monoidal category generated by taking primes as objects and arrows \(p \to p \otimes q\) for all \(p, q\)? Section 25.2 from John's book Quantum Techniques for Stochastic Mechanics made me think of this.

    Comment Source:Wait, is the poset of positive naturals ordered by divisibility just the free symmetric monoidal category generated by taking primes as objects and arrows \\(p \to p \otimes q\\) for all \\(p, q\\)? Section 25.2 from John's book [Quantum Techniques for Stochastic Mechanics](https://arxiv.org/abs/1209.3632) made me think of this.
Sign In or Register to comment.