It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 719

Options

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:

- Martin Giese and Arno Schönegge, Any two countable densely ordered sets without endpoints are isomorphic - a formal proof with KIV, Universität Karlsruhe, Fakultät für Informatik, Technical Report No. 50/95, December 1995.

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

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]|) . $$

`>**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]|) . $$`

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. $$

`>**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. $$`

I think that needs tweaking, @Keith – with a poset we are simply

suppliedwith 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\).`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\\).`

Anindya is right.

`Anindya is right.`

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.

`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.`