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

- All Categories 2.2K
- Applied Category Theory Course 354
- Applied Category Theory Seminar 4
- Exercises 149
- Discussion Groups 49
- How to Use MathJax 15
- Chat 480
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 149
- Azimuth Forum 29
- Azimuth Project 189
- - Strategy 108
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 711
- - Latest Changes 701
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 21
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 39

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