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

- All Categories 2.3K
- Chat 495
- Study Groups 6
- Biological Models 1
- Categorical Network Theory 1
- Programming with Categories 4
- Review Sections 6
- MIT 2020: Programming with Categories 53
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 64
- Azimuth Code Project 110
- Statistical methods 2
- Drafts 1
- Math Syntax Demos 15
- Wiki - Latest Changes 0
- Strategy 111
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 708

Options

Last time we took our beloved preorders and combined them with another kind of mathematical gadget - monoids - to get "monoidal preorders". Preorders say when can get something from something else. Monoids let us combine things. Monoidal preorders let us do both!

This is a common trick in math: taking two mathematical structures and blending or "hybridizing" them to get a new one. It's good to think carefully about it:

A

**preorder**is a set \(X\) with a relation \(\le\) that's reflexive and transitive.A

**monoid**is a set \(X\) where we can combine elements using an associative operation \(\otimes\), together with an element \(I\) that has no effect when we combine it with anything else: \(I \otimes x = x = x \otimes I\).

But to hybridize these, we don't just rudely slap them together. We want our \(\le\) relation to get along with our "combining" operation \(\otimes\)! So, we define a **monoidal preorder** to be a thing \( (X, \le, \otimes, I) \) such that \( (X,\le \) is a preorder, \( (X, \otimes, I) \) is a monoid, and also

$$ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .$$ This last condition is the magic pixie dust that makes monoidal preorders really interesting.

On the one hand this condition makes perfect sense: if you can get \(x\) from \(x'\) and \(y\) from \(y'\), you should be able to get \(x\) combined with \(y\) from \(x'\) combined with \(y'\).

But on the other hand, you might wonder if it's really "magic". Did finding this condition require a burst of inspiration? Or could there be some systematic way to have found it? Indeed there is!

**Puzzle 66.** What's another way to state this last condition using ideas we've already discussed? Hint: it's a property of the function \(\otimes: X \times X \to X\).

A good category theorist knows lots of systematical ways to find good definitions, which convert "magic" to "method".

A lot of the monoidal preorders will be talking about are "symmetric". This means that given \(x\) combined with \(y\), you can always get \(y\) combined with \(x\).

**Definition.** A monoidal preorder \( (X, \le, \otimes, I) \) is **symmetric** if

$$ y \otimes x \le x \otimes y $$ for all \(x,y\in X\).

Since \(x\) and \(y\) are *anything*, we can switch their roles and conclude that

$$ y \otimes x \le x \otimes y \textrm{ and } x \otimes y \le y \otimes x $$ for all \(x,y\) in a symmetric monoidal preorder. You might guess that this implies \(x \otimes y = y \otimes x\), but no! This will follow if our preorder is a poset, since a poset is a preorder where

$$ a \le b \textrm{ and } b \le a \textrm{ implies } a = b .$$ But it's not true in general:

**Puzzle 67.** A monoidal preorder is **commutative** if \(x \otimes y = y \otimes x\) for all \(x,y\). Find a symmetric monoidal preorder that is not commutative.

There are lots of great examples of symmetric monoidal preorders. For starters, many of your favorite number systems:

The set \(\mathbb{R}\) of real numbers with the usual \(\le\), the binary operation \(+: \mathbb{R} \times \mathbb{R} \to \mathbb{R} \) and the element \(0 \in \mathbb{R}\) is a symmetric monoidal preorder.

Same for the set \(\mathbb{Q}\) of rational numbers.

Same for the set \(\mathbb{Z}\) of integers.

Same for the set \(\mathbb{N}\) of natural numbers.

In fact, all these are commutative monoidal posets. But we've also seen some other examples in our discussion of chemistry and Petri nets in Lecture 19. For example, take this Petri net:

This describes the formation of water from hydrogen and oxygen atoms (in an idealized and unrealistic way - it's not really that simple). From this you can create a symmetric monoidal preorder where the elements are expressions like this:

$$ a \text{H} + b \text{O} + c \text{H}_2\text{O} $$
where \(a,b,c\in \mathbb{N}\). Mathematical chemists call these **complexes**. There's an operation for combining complexes, called \(+\), and it's defined this way:

$$ (a \text{H} + b \text{O} + c \text{H}_2\text{O} ) + (a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} ) = (a+a') \text{H} + (b+b') \text{O} + (c+c') \text{H}_2\text{O} $$ This \(+\) operation is associative, and the element

$$ 0 = 0 \text{H} + 0 \text{O} + 0 \text{H}_2\text{O} $$ has the property that \(0 + x = x = x + 0 \) for any complex. So, the set of complexes becomes a monoid. The only question is how we define \(\le\).

**Puzzle 68.** How should we define \(\le\) on the set of complexes to get a symmetric monoidal preorder, if the only nontrivial chemical reaction we want to describe is the one shown below?

**Puzzle 69.** Is this symmetric monoidal preorder a poset?

**Puzzle 70.** Suppose we *also* consider the reverse reaction:

How should we change our definition of \(\le\) to get a new symmetric monoidal preorder? Is this a poset?

## Comments

If we don't allow negative numbers, are the above constructions of chemicals, multisets?

If so, then the above puzzles can be solved by letting the monoid part in the monoidal poset be given by the operations of multisets.

`If we don't allow negative numbers, are the above constructions of chemicals, [multisets](https://ncatlab.org/nlab/show/multiset)? If so, then the above puzzles can be solved by letting the monoid part in the monoidal poset be given by the operations of multisets.`

I already specified the monoid part of these monoidal preorders before stating the first puzzle. The puzzles ask what's the preorder part: that is, when does one complex count as \(\le \) another. This depends on what reactions we allow.

Yes, we can think of a complex

$$ a \text{H} + b \text{O} + c \text{H}_2\text{O} $$ as a multisubset of the set \( \{\textrm{H}, \textrm{O}, \textrm{H}_2\textrm{O} \} \). Alternatively, and perhaps less stressfully, we can think of it as an ordered triple \( (a,b,c) \) of natural numbers. The monoid operation is just the usual addition of these triples.

`I already specified the monoid part of these monoidal preorders before stating the first puzzle. The puzzles ask what's the preorder part: that is, when does one complex count as \\(\le \\) another. This depends on what reactions we allow. Yes, we can think of a complex \[ a \text{H} + b \text{O} + c \text{H}_2\text{O} \] as a multisubset of the set \\( \\{\textrm{H}, \textrm{O}, \textrm{H}_2\textrm{O} \\} \\). Alternatively, and perhaps less stressfully, we can think of it as an ordered triple \\( (a,b,c) \\) of natural numbers. The monoid operation is just the usual addition of these triples.`

On puzzle 68: Part of me wants to introduce an energy term, but that would just end up as another kind of raw material. So what we're really looking for is Petri-reachability.

Edit: I think I misread the question, I didn't realize that the only reaction to be considered is the first \(H_2O\) diagram. I'm still not sure I know what John meant, I'll have to try again later. Thanks to Michael Hong for his proposed solution, which made me doubt everything!

`On puzzle 68: Part of me wants to introduce an energy term, but that would just end up as another kind of raw material. So what we're really looking for is Petri-reachability. Edit: I think I misread the question, I didn't realize that the only reaction to be considered is the first \\(H_2O\\) diagram. I'm still not sure I know what John meant, I'll have to try again later. Thanks to Michael Hong for his proposed solution, which made me doubt everything!`

Puzzle 68Define \((a, b, c) \leq (a', b', c')\) if and only if \(a \gt a', b \gt b' \, and \, c \lt c'\).Puzzle 69This is a poset since \(\otimes\) is + and + is commutative.Puzzle 70Define \((a, b, c) \leq (a', b', c')\) if and only if \(a \lt a', b \lt b' \, and \, c \gt c'\). This is also a poset.`**Puzzle 68** Define \\((a, b, c) \leq (a', b', c')\\) if and only if \\(a \gt a', b \gt b' \, and \, c \lt c'\\). **Puzzle 69** This is a poset since \\(\otimes\\) is + and + is commutative. **Puzzle 70** Define \\((a, b, c) \leq (a', b', c')\\) if and only if \\(a \lt a', b \lt b' \, and \, c \gt c'\\). This is also a poset.`

I noticed Michael posted a solution while I was writing mine. I will post anyways and think about his answer after.

Puzzle 68/69Let's start by defining an order on the set of complexes \((a,b,c) \text{ where } a,b,c \in \mathbb{N}\) with a representing \(\text{H}\), b representing \(\text{O}\) and c representing \(\text{H}_2\text{O}\) without taking the reaction into account. We say that:$$ (a,b,c) \le (a',b',c') \text{ if } a \le a' \text{ and } b \le b' \text{ and } c \le c' $$ We can interpret this as meaning: Given a complex \(C' = (a',b',c')\), I can get the sub-complex \(C = (a,b,c)\) if all compontents of \(C\) are present in \(C'\). This ordering forms a symmetric monoidal poset under addition of natural numbers with the unit \((0,0,0)\).

Now we can add the reaction by demanding, that anytime we have a multiple of \(2\text{ H} + \text{O}\) we can get that many \(\text{H}_2\text{O}\). Thus we add additional ordering given by: $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ for } n \in \mathbb{N} \text{ and } a \ge 2, b \ge 1$$ Given this additional structure, we still have at least a preorder since:

$$ (a-2n,b-n,c+n) \le (a-2n,b-n,c+n) \text{ (reflexivity) } $$ $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (a,b,c) \le (a',b',c') \text{ implies } (a-2n,b-n,c+n) \le (a',b',c') \text{ (transitivity) } $$ We even retain the poset structure since given \((a-2n,b-n,c+n) \le (a,b,c)\) we can't also have \((a,b,c) \le (a-2n,b-n,c+n)\) for \(n \ge 1\) since \(a \not\le a-2n\) and \(b \not\le b-n\) and in the case \(n=0\), \((a,b,c) = (a,b,c)\).

Edit: corrected mistaken \(c \not\le c+n\) and \(n \le 1 \)in the above sectionIt remains to be shown that this new poset also forms a symmetric monoidal poset under addition of natural numbers with the unit \((0,0,0)\).

$$ \text{Unit laws hold since: } (0+a-2n,0+b-n,0+c+n) \le (a-2n,b-n,c+n) \le (a-2n+0,b-n+0,c+n+0)$$ $$ \text{Associativity holds since: } ([(a-2n)+(a'-2n')]+(a''-2n''),[(b-n)+(b'-n')]+(b''-n''),[(c+n)+(c'+n')]+(c''+n'')) $$ $$ \le ((a-2n)+[(a'-2n')+(a''-2n'')],(b-n)+[(b'-n')+(b''-n'')],(c+n)+[(c'+n')+(c''+n'')]) \text{ for all } a,a',a'',b,b',b'',c,c',c''$$ This leaves: \( x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' \). Our new structure provides two extra cases: $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d-2m,e-m,f+m) \le (d,e,f) \text{ should imply } ((a-2n)+(d-2m),(b-n)+(e-m),(c+n)+(f+m)) \le (a+d,b+e,d+f)$$ This is the case since: $$((a-2n)+(d-2m),(b-n)+(e-m),(c+n)+(f+m)) = ((a+d)-2(n+m),(b+e)+(n-m),(c+f)+(n+m)) \le (a+d,b+e,d+f) $$ By taking \(a'=a+d, b'=b+e, d'=d+f, n'=n+m\)

and

$$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d,e,f) \le (d',e',f') \text{ should imply } (a-2n+d,b-n+e,c+n+f) \le (a+d',b+e',c+f')$$ We can do this component-wise: $$a \le a \text{ and } d \le d' \text{ in our original symmetric monoidal poset implies: } a+d \le a+d' \text{ so: } a-2n+d \le (a+d')$$ $$b \le b \text{ and } e \le e' \text{ in our original symmetric monoidal poset implies: } b+e \le b+e' \text{ so: } b-n+e \le (b+e')$$ $$c+n+f \le c+f' \text{ since } c+n \le c \text { for all } n \text { and we know } f \le f'$$ (This last line seems somewhat circular to me, so I'm not sure if it's correct...)

Finally, symmetry is guaranteed by the fact that both addition an subtraction of natural numbers are commutative. Thus, provided the above arguments are correct we indeed have a symmetric monoidal poset.

Edit: changed preorder to poset`I noticed Michael posted a solution while I was writing mine. I will post anyways and think about his answer after. **Puzzle 68/69** Let's start by defining an order on the set of complexes \\((a,b,c) \text{ where } a,b,c \in \mathbb{N}\\) with a representing \\(\text{H}\\), b representing \\(\text{O}\\) and c representing \\(\text{H}_2\text{O}\\) without taking the reaction into account. We say that: $$ (a,b,c) \le (a',b',c') \text{ if } a \le a' \text{ and } b \le b' \text{ and } c \le c' $$ We can interpret this as meaning: Given a complex \\(C' = (a',b',c')\\), I can get the sub-complex \\(C = (a,b,c)\\) if all compontents of \\(C\\) are present in \\(C'\\). This ordering forms a symmetric monoidal poset under addition of natural numbers with the unit \\((0,0,0)\\). Now we can add the reaction by demanding, that anytime we have a multiple of \\(2\text{ H} + \text{O}\\) we can get that many \\(\text{H}_2\text{O}\\). Thus we add additional ordering given by: $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ for } n \in \mathbb{N} \text{ and } a \ge 2, b \ge 1$$ Given this additional structure, we still have at least a preorder since: $$ (a-2n,b-n,c+n) \le (a-2n,b-n,c+n) \text{ (reflexivity) } $$ $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (a,b,c) \le (a',b',c') \text{ implies } (a-2n,b-n,c+n) \le (a',b',c') \text{ (transitivity) } $$ We even retain the poset structure since given \\((a-2n,b-n,c+n) \le (a,b,c)\\) we can't also have \\((a,b,c) \le (a-2n,b-n,c+n)\\) for \\(n \ge 1\\) since \\(a \not\le a-2n\\) and \\(b \not\le b-n\\) and in the case \\(n=0\\), \\((a,b,c) = (a,b,c)\\). *Edit: corrected mistaken \\(c \not\le c+n\\) and \\(n \le 1 \\)in the above section* It remains to be shown that this new poset also forms a symmetric monoidal poset under addition of natural numbers with the unit \\((0,0,0)\\). $$ \text{Unit laws hold since: } (0+a-2n,0+b-n,0+c+n) \le (a-2n,b-n,c+n) \le (a-2n+0,b-n+0,c+n+0)$$ $$ \text{Associativity holds since: } ([(a-2n)+(a'-2n')]+(a''-2n''),[(b-n)+(b'-n')]+(b''-n''),[(c+n)+(c'+n')]+(c''+n'')) $$ $$ \le ((a-2n)+[(a'-2n')+(a''-2n'')],(b-n)+[(b'-n')+(b''-n'')],(c+n)+[(c'+n')+(c''+n'')]) \text{ for all } a,a',a'',b,b',b'',c,c',c''$$ This leaves: \\( x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' \\). Our new structure provides two extra cases: $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d-2m,e-m,f+m) \le (d,e,f) \text{ should imply } ((a-2n)+(d-2m),(b-n)+(e-m),(c+n)+(f+m)) \le (a+d,b+e,d+f)$$ This is the case since: $$((a-2n)+(d-2m),(b-n)+(e-m),(c+n)+(f+m)) = ((a+d)-2(n+m),(b+e)+(n-m),(c+f)+(n+m)) \le (a+d,b+e,d+f) $$ By taking \\(a'=a+d, b'=b+e, d'=d+f, n'=n+m\\) and $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d,e,f) \le (d',e',f') \text{ should imply } (a-2n+d,b-n+e,c+n+f) \le (a+d',b+e',c+f')$$ We can do this component-wise: $$a \le a \text{ and } d \le d' \text{ in our original symmetric monoidal poset implies: } a+d \le a+d' \text{ so: } a-2n+d \le (a+d')$$ $$b \le b \text{ and } e \le e' \text{ in our original symmetric monoidal poset implies: } b+e \le b+e' \text{ so: } b-n+e \le (b+e')$$ $$c+n+f \le c+f' \text{ since } c+n \le c \text { for all } n \text { and we know } f \le f'$$ (This last line seems somewhat circular to me, so I'm not sure if it's correct...) Finally, symmetry is guaranteed by the fact that both addition an subtraction of natural numbers are commutative. Thus, provided the above arguments are correct we indeed have a symmetric monoidal poset. *Edit: changed preorder to poset*`

Michael wrote:

I assume you are using the opposite convention I was using above where \(x \le y \) means "If we have \(x\) we can get \(y\)". I'm also assuming that you meant \((a, b, c) \leq (a', b', c')\) if and only if \(a \ge a', b \ge b' \, and \, c \le c'\), since under your original definition \((a,b,c) \not\le (a,b,c)\) since \(a \not\gt a\), \( b \not\gt b\) and \(c \not\lt c \).

Using this modified definition it is indeed the case that \((2,1,0) \le (0,0,1) \) as desired. But it is also the case that \((2,1,0) \le (0,0,8) \) which violates conservation of mass (probably undesired) as well as \((1,1,0) \le (0,0,1) \) which does not take the stoichiometry of the reaction into account (probably also undesired).

As far as I understood the question we need to take the set of all possible complexes into account, not just the ones resulting from valid applications of the Petri net.

`Michael wrote: >Define \\((a, b, c) \leq (a', b', c')\\) if and only if \\(a \gt a', b \gt b' \, and \, c \lt c'\\). I assume you are using the opposite convention I was using above where \\(x \le y \\) means "If we have \\(x\\) we can get \\(y\\)". I'm also assuming that you meant \\((a, b, c) \leq (a', b', c')\\) if and only if \\(a \ge a', b \ge b' \, and \, c \le c'\\), since under your original definition \\((a,b,c) \not\le (a,b,c)\\) since \\(a \not\gt a\\), \\( b \not\gt b\\) and \\(c \not\lt c \\). Using this modified definition it is indeed the case that \\((2,1,0) \le (0,0,1) \\) as desired. But it is also the case that \\((2,1,0) \le (0,0,8) \\) which violates conservation of mass (probably undesired) as well as \\((1,1,0) \le (0,0,1) \\) which does not take the stoichiometry of the reaction into account (probably also undesired). As far as I understood the question we need to take the set of all possible complexes into account, not just the ones resulting from valid applications of the Petri net.`

Here is my attempt at

Puzzle 66.The condition of the monoidal preorder arises if \(\otimes\) is a

monotonemap between the product preorder \(X \times X\) and the original preorder \(X\).If \(\otimes\) is a monotone map then, for all pairs \( (x, y), (x' , y') \in X \times X \), we have:

Using the definition of the relation \(\le_{X \times X}\) in the product preorder, we arrive at the condition of the monoidal preorder:

`Here is my attempt at **Puzzle 66**. The condition of the monoidal preorder arises if \\(\otimes\\) is a _monotone_ map between the product preorder \\(X \times X\\) and the original preorder \\(X\\). If \\(\otimes\\) is a monotone map then, for all pairs \\( (x, y), (x' , y') \in X \times X \\), we have: - \\((x, y) \le_{X \times X} (x', y')\\) implies \\(x \otimes y \le_{X} x' \otimes y'\\). Using the definition of the relation \\(\le_{X \times X}\\) in the product preorder, we arrive at the condition of the monoidal preorder: - \\(x \le_X x'\\) and \\(y \le_X y'\\) imply \\(x \otimes y \le_{X} x' \otimes y'\\).`

Puzzle 68/69 alternativeA simpler approach that doesn't use the inclusion ordering would be the following construction:We start by fulfilling reflexivity by defining \((a,b,c) \le (a,b,c) \forall a,b,c\). Then we construct the ordering given by the Petri net as follows:

$$\text{As long as } a \ge 2n \text{ and } b \ge n, (a-2n,b-n,c+n) \le (a,b,c) $$ This gives us a set of 'reaction sequences' as well as discrete elements that can't react (sequences of length 0). E.g \( (2,1,0) \rightarrow (0,0,1) \) and \( (5,3,1) \rightarrow (3,2,2) \rightarrow (1,1,3) \) and \((0,1,0)\). These reaction sequences are linear (since we don't generate branches) and disjoint from one another (since each element has at most one direct predecessor). This construction forms a poset since reflexivity is fulfilled and transitivity is guaranteed in the linear sequences and is trivial on the discrete elements such as \((0,1,0)\). Furthermore there are no equivalent elements (loops) except when \( (a,b,c) \le (a,b,c) \) .

It thus remains to be shown that we have a symmetric monoidal poset under addition of natural numbers with the unit \( (0,0,0) \). Unit laws and associativity follow by the above proof in #5.

\( x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' \) holds on the discrete elements since \( (a,b,c) \le (a,b,c) \) and \( (d,e,f) \le (d,e,f) \) do indeed imply \( (a+d,b+e,c+f) \le (a+d,b+e,c+f) \). It also holds on elements in (the same) sequence(s) since as shown above:

This just takes you to a new sequence. Furthermore, it holds on combinations of a sequence and a discrete element since \( (a-2n,b-n,c+n) \le (a,b,c)\) and \( (d,e,f) \le (d,e,f)\) implies \( (a-2n+d,b-n+e,c+n+f) \le (a+d,b+e,c+f)\). This also takes you to a different sequence.

In contrast to #5 we don't have to show that in general: $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d,e,f) \le (d',e',f') \text{ should imply } (a-2n+d,b-n+e,c+n+f) \le (a+d',b+e',c+f')$$ since we have shown this for all the special cases that our construction creates.

Thus, provided the above arguments are correct we would have a symmetric monoidal poset.

I'm sure there is a more elegant way of showing that this and #5 work (provided they actually do). Looking forward to being corrected and/or refined.

`**Puzzle 68/69 alternative** A simpler approach that doesn't use the inclusion ordering would be the following construction: We start by fulfilling reflexivity by defining \\((a,b,c) \le (a,b,c) \forall a,b,c\\). Then we construct the ordering given by the Petri net as follows: $$\text{As long as } a \ge 2n \text{ and } b \ge n, (a-2n,b-n,c+n) \le (a,b,c) $$ This gives us a set of 'reaction sequences' as well as discrete elements that can't react (sequences of length 0). E.g \\( (2,1,0) \rightarrow (0,0,1) \\) and \\( (5,3,1) \rightarrow (3,2,2) \rightarrow (1,1,3) \\) and \\((0,1,0)\\). These reaction sequences are linear (since we don't generate branches) and disjoint from one another (since each element has at most one direct predecessor). This construction forms a poset since reflexivity is fulfilled and transitivity is guaranteed in the linear sequences and is trivial on the discrete elements such as \\((0,1,0)\\). Furthermore there are no equivalent elements (loops) except when \\( (a,b,c) \le (a,b,c) \\) . It thus remains to be shown that we have a symmetric monoidal poset under addition of natural numbers with the unit \\( (0,0,0) \\). Unit laws and associativity follow by the above proof in [#5]( https://forum.azimuthproject.org/discussion/comment/17960/#Comment_17960 ). \\( x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' \\) holds on the discrete elements since \\( (a,b,c) \le (a,b,c) \\) and \\( (d,e,f) \le (d,e,f) \\) do indeed imply \\( (a+d,b+e,c+f) \le (a+d,b+e,c+f) \\). It also holds on elements in (the same) sequence(s) since as shown above: > $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d-2m,e-m,f+m) \le (d,e,f) \text{ should imply } ((a-2n)+(d-2m),(b-n)+(e-m),(c+n)+(f+m)) \le (a+d,b+e,d+f)$$ >This is the case since: >$$((a-2n)+(d-2m),(b-n)+(e-m),(c+n)+(f+m)) = ((a+d)-2(n+m),(b+e)+(n-m),(c+f)+(n+m)) \le (a+d,b+e,d+f) $$ >By taking \\(a'=a+d, b'=b+e, d'=d+f, n'=n+m\\) This just takes you to a new sequence. Furthermore, it holds on combinations of a sequence and a discrete element since \\( (a-2n,b-n,c+n) \le (a,b,c)\\) and \\( (d,e,f) \le (d,e,f)\\) implies \\( (a-2n+d,b-n+e,c+n+f) \le (a+d,b+e,c+f)\\). This also takes you to a different sequence. In contrast to [#5]( https://forum.azimuthproject.org/discussion/comment/17960/#Comment_17960 ) we don't have to show that in general: $$ (a-2n,b-n,c+n) \le (a,b,c) \text{ and } (d,e,f) \le (d',e',f') \text{ should imply } (a-2n+d,b-n+e,c+n+f) \le (a+d',b+e',c+f')$$ since we have shown this for all the special cases that our construction creates. Thus, provided the above arguments are correct we would have a symmetric monoidal poset. I'm sure there is a more elegant way of showing that this and [#5]( https://forum.azimuthproject.org/discussion/comment/17960/#Comment_17960 ) work (provided they actually do). Looking forward to being corrected and/or refined.`

re

Puzzle 67– how about we take the set of finite "words" on an "alphabet" (including the empty word)• this is a monoid by string concatenation, eg CAT \(\otimes\) FISH \(=\) CATFISH

• it is a preorder by word length, eg CAT \(\leq\) DOG, DOG \(\leq\) CAT, CAT \(\leq\) FISH, FISH \(\nleq\) DOG

• the monoid structure preserves \(\leq\), so it is a monoidal preorder

• it is symmetric, eg CATFISH \(\leq\) FISHCAT and FISHCAT \(\le\) CATFISH

• but it is not commutative, since CATFISH \(\neq\) FISHCAT

`re **Puzzle 67** – how about we take the set of finite "words" on an "alphabet" (including the empty word) • this is a monoid by string concatenation, eg CAT \\(\otimes\\) FISH \\(=\\) CATFISH • it is a preorder by word length, eg CAT \\(\leq\\) DOG, DOG \\(\leq\\) CAT, CAT \\(\leq\\) FISH, FISH \\(\nleq\\) DOG • the monoid structure preserves \\(\leq\\), so it is a monoidal preorder • it is symmetric, eg CATFISH \\(\leq\\) FISHCAT and FISHCAT \\(\le\\) CATFISH • but it is not commutative, since CATFISH \\(\neq\\) FISHCAT`

Dan wrote:

Yes, that's my preferred answer to this puzzle! Saying that \(\otimes : X \times X \to X\) is monotone is equivalent to the condition

$$ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .$$ for all \(x,x',y,y' \in X\). It's nice to compress condition into a simple phrase. So, we can give this more conceptual definition, equivalent to the one given before:

Definition.Amonoidal preorderis a preorder that's also a monoid, for which the multiplication is a monotone function.Terse and elegant! If we knew more category theory we could do even better:

Definition.Amonoidal preorderis a monoid in the category of preorders.This is the truly slick way to blend the definitions of "monoid" and "preorder". But we're not at this level of sophistication yet, in this course!

`Dan wrote: > Here is my attempt at **Puzzle 66**. > The condition of the monoidal preorder arises if \\(\otimes\\) is a _monotone_ map between the product preorder \\(X \times X\\) and the original preorder \\(X\\). Yes, that's my preferred answer to this puzzle! Saying that \\(\otimes : X \times X \to X\\) is monotone is equivalent to the condition \[ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .\] for all \\(x,x',y,y' \in X\\). It's nice to compress condition into a simple phrase. So, we can give this more conceptual definition, equivalent to the one given before: **Definition.** A **monoidal preorder** is a preorder that's also a monoid, for which the multiplication is a monotone function. Terse and elegant! If we knew more category theory we could do even better: **Definition.** A **monoidal preorder** is a monoid in the category of preorders. This is the truly slick way to blend the definitions of "monoid" and "preorder". But we're not at this level of sophistication yet, in this course!`

Robert wrote:

In Puzzle 68 I was asking this. Suppose there's just one chemical reaction you can do:

When can you turn

$$ a \text{H} + b \text{O} + c \text{H}_2\text{O} $$ into

$$ a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} $$ using this reaction? Here \(a,b,c\) and \(a',b',c'\) are natural numbers.

For example, you

canturn$$ 4 \text{H} + 2 \text{O} + \text{H}_2\text{O} $$ into

$$ 3 \text{H}_2\text{O} $$ using this reaction. (Of course you have to use it twice, but that's okay.) You

cannotturn$$ 3 \text{H} + 2 \text{O} + \text{H}_2\text{O} $$ into

$$ \text{O} + 2 \text{H}_2\text{O} $$ using this reaction. So, what's the general rule? If you want, you can abbreviate

$$ a \text{H} + b \text{O} + c \text{H}_2\text{O} $$ as a list of 3 natural numbers \( (a,b,c) \), and write

$$ (a',b',c') \le (a,b,c) $$ to mean "you can turn \( a \text{H} + b \text{O} + c \text{H}_2\text{O} \) into \( a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} \)."

Michael Hong tried answering this question in Comment 4:

This is the right

kindof answer, but it's not the right answer. If this were true, we would have \( (1,1,0) \le (0,0,1) \), meaning we could turn \(\text{H} + \text{O}\) into \(\text{H}_2\text{O}\). That would be cool, but actually we can't do that using this reaction:Marius gives an interesting alternative answer in Comment 8. Do you think this answer is correct?

`Robert wrote: > I'm still not sure I know what John meant, I'll have to try again later. In Puzzle 68 I was asking this. Suppose there's just one chemical reaction you can do: <center><img width = "250" src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/H2O-II.png"></center> When can you turn \[ a \text{H} + b \text{O} + c \text{H}_2\text{O} \] into \[ a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} \] using this reaction? Here \\(a,b,c\\) and \\(a',b',c'\\) are natural numbers. For example, you _can_ turn \[ 4 \text{H} + 2 \text{O} + \text{H}_2\text{O} \] into \[ 3 \text{H}_2\text{O} \] using this reaction. (Of course you have to use it twice, but that's okay.) You _cannot_ turn \[ 3 \text{H} + 2 \text{O} + \text{H}_2\text{O} \] into \[ \text{O} + 2 \text{H}_2\text{O} \] using this reaction. So, what's the general rule? If you want, you can abbreviate \[ a \text{H} + b \text{O} + c \text{H}_2\text{O} \] as a list of 3 natural numbers \\( (a,b,c) \\), and write \[ (a',b',c') \le (a,b,c) \] to mean "you can turn \\( a \text{H} + b \text{O} + c \text{H}_2\text{O} \\) into \\( a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} \\)." Michael Hong tried answering this question in Comment 4: > **Puzzle 68.** Define \\((a, b, c) \leq (a', b', c')\\) if and only if \\(a \gt a', b \gt b' \, and \, c \lt c'\\). This is the right _kind_ of answer, but it's not the right answer. If this were true, we would have \\( (1,1,0) \le (0,0,1) \\), meaning we could turn \\(\text{H} + \text{O}\\) into \\(\text{H}_2\text{O}\\). That would be cool, but actually we can't do that using this reaction: <center><img width = "250" src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/H2O-II.png"></center> Marius gives an interesting alternative answer in Comment 8. Do you think this answer is correct?`

Anindya wrote:

I like that!

Here's another: take any monoid \(X\) that's not commutative, and give it a preorder such that \(x \le y\) for

all\(x,y \in X\). Then this is a symmetric monoidal preorder that's not commutative.Sometimes in math it pays to be ruthless.

`Anindya wrote: > **Puzzle 67** – how about we take the set of finite "words" on an "alphabet" (including the empty word) > • this is a monoid by string concatenation, eg CAT \\(\otimes\\) FISH \\(=\\) CATFISH > • it is a preorder by word length, eg CAT \\(\leq\\) DOG, DOG \\(\leq\\) CAT, CAT \\(\leq\\) FISH, FISH \\(\nleq\\) DOG > • the monoid structure preserves \\(\leq\\), so it is a monoidal preorder > • it is symmetric, eg CATFISH \\(\leq\\) FISHCAT and FISHCAT \\(\le\\) CATFISH > • but it is not commutative, since CATFISH \\(\neq\\) FISHCAT I like that! Here's another: take any monoid \\(X\\) that's not commutative, and give it a preorder such that \\(x \le y\\) for _all_ \\(x,y \in X\\). Then this is a symmetric monoidal preorder that's not commutative. Sometimes in math it pays to be ruthless.`

John wrote in #11:

Based on this I think you are looking for:

$$ (a',b',c') \le (a,b,c) \text{ iff } c'-c = \frac{a-a'}{2} = b-b' \text{ and } c'-c \ge 0$$ I.e the amount of water we produce has to be exactly half the amount of hydrogen we consume as well as exactly the amount of oxygen we consume.

Edit: For the reversible case we can simply allow for 'negative production' by leaving off the \( c'-c \ge 0 \) condition.

`John wrote in #11: > So, what's the general rule? Based on this I think you are looking for: $$ (a',b',c') \le (a,b,c) \text{ iff } c'-c = \frac{a-a'}{2} = b-b' \text{ and } c'-c \ge 0$$ I.e the amount of water we produce has to be exactly half the amount of hydrogen we consume as well as exactly the amount of oxygen we consume. Edit: For the reversible case we can simply allow for 'negative production' by leaving off the \\( c'-c \ge 0 \\) condition.`

Puzzle 68.Borrowing a notational convenience from the temporal logic of actions, I like to notate the "next" value of a variable \(x\) using prime notation, \(x'\). So we can say that \((x, y, z) \le (x', y', z')\) iff \(\exists c \in \mathbb{N}. x = 2cx' \land y = cy' \land cz = z'\). This is (EDIT:not) the same rule as Marius' in #13, except the common factor \(c\) has not been eliminated, and the prime is used in the opposite convention. (EDIT:No, Marius' was closer to being correct than mine. See #16 for something that's hopefully completely correct.)Puzzle 70.Thanks to prime notation, we can flip the reaction by redefining "prime" to mean "previous". Symmetrically, we could prime un-primed variables, and de-prime primed variables.`**Puzzle 68.** Borrowing a notational convenience from the [temporal logic of actions](https://en.wikipedia.org/wiki/Temporal_logic_of_actions), I like to notate the "next" value of a variable \\(x\\) using prime notation, \\(x'\\). So we can say that \\((x, y, z) \le (x', y', z')\\) iff \\(\exists c \in \mathbb{N}. x = 2cx' \land y = cy' \land cz = z'\\). This is (**EDIT:** not) the same rule as Marius' in #13, except the common factor \\(c\\) has not been eliminated, and the prime is used in the opposite convention. (**EDIT:** No, Marius' was closer to being correct than mine. See #16 for something that's hopefully completely correct.) **Puzzle 70.** Thanks to prime notation, we can flip the reaction by redefining "prime" to mean "previous". Symmetrically, we could prime un-primed variables, and de-prime primed variables.`

@Jonathan -

I don't think this is quite right.

For one, we want the following equation to be true:

$$ 2 H + O \to H_2O $$ But we also want

$$ H \to H $$ And we should be able to add the two equations together (as per the monoidal preorder rule), hence:

$$ 3 H + O \to H + H_2O $$ But that doesn't fit the scheme you and Marius propose...

`@Jonathan - I don't think this is quite right. For one, we want the following equation to be true: $$ 2 H + O \to H_2O $$ But we also want $$ H \to H $$ And we should be able to add the two equations together (as per the monoidal preorder rule), hence: $$ 3 H + O \to H + H_2O $$ But that doesn't fit the scheme you and Marius propose...`

@Matthew, you're right. There's probably some statement I could make about the free symmetric monoidal preorder generated by the desired reactions, but that's just kicking the can down the road. (See Section 25.2 of John's book, Quantum Techniques for Stochastic Mechanics.) Let's see if I can recover this.

(

EDIT:Also worth noting here that my thought process went badly off track when I said that Marius' and my rules were ultimately the same. Mine wasverywrong.)First, consider that every complex \((x, y, z)\) can be written uniquely as \((2x_q + x_r, y, z)\) with \(0 \le x_r < 2\) -- in other words, dividing \(x\) by 2 and getting a quotient and remainder. (We'd only be dividing the others by 1, so we'll leave them alone.)

Now, we say that \((2x_q + x_r, y, z) \le (2x'_q + x'_r, y', z')\) iff the following statements hold for some \(c \in \mathbb{N}\):

$$c = x_q - x'_q$$ $$0 = x_r - x'_r$$ $$c = y - y'$$ $$c = z' - z$$ When \(c = 0\), we get the reflexive case. As \(c\) increases, we utilize more of the available resources.

`@[Matthew](https://forum.azimuthproject.org/profile/1818/Matthew%20Doty), you're right. There's probably some statement I could make about the free symmetric monoidal preorder generated by the desired reactions, but that's just kicking the can down the road. (See Section 25.2 of John's book, [Quantum Techniques for Stochastic Mechanics](https://arxiv.org/abs/1209.3632).) Let's see if I can recover this. (**EDIT:** Also worth noting here that my thought process went badly off track when I said that Marius' and my rules were ultimately the same. Mine was _very_ wrong.) First, consider that every complex \\((x, y, z)\\) can be written uniquely as \\((2x_q + x_r, y, z)\\) with \\(0 \le x_r < 2\\) -- in other words, dividing \\(x\\) by 2 and getting a quotient and remainder. (We'd only be dividing the others by 1, so we'll leave them alone.) Now, we say that \\((2x_q + x_r, y, z) \le (2x'_q + x'_r, y', z')\\) iff the following statements hold for some \\(c \in \mathbb{N}\\): $$c = x_q - x'_q$$ $$0 = x_r - x'_r$$ $$c = y - y'$$ $$c = z' - z$$ When \\(c = 0\\), we get the reflexive case. As \\(c\\) increases, we utilize more of the available resources.`

I'm also rather confused now notationally, as I thought the convention was that \(x \le y\) means "given x we can get y". But it looks like we might be working in the opposite preorder:

@Matthew wrote:

I think you might mean \(2H\), not \(H\), given that you add your inequalities later and get a \(3H\) term.

`I'm also rather confused now notationally, as I thought the convention was that \\(x \le y\\) means "given x we can get y". But it looks like we might be working in the opposite preorder: > \[ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .\] > > **[...]** if you can get \\(x\\) from \\(x'\\) and \\(y\\) from \\(y'\\), you should be able to get \\(x\\) combined with \\(y\\) from \\(x'\\) combined with \\(y'\\). @[Matthew](https://forum.azimuthproject.org/profile/1818/Matthew%20Doty) wrote: > For one, we want the following equation to be true: > > $$H + O \leq H_2O$$ I think you might mean \\(2H\\), not \\(H\\), given that you add your inequalities later and get a \\(3H\\) term.`

Yeah, I clobbered the 2 coefficient in an edit, my bad. I've gone and fixed my mistake.

`> I think you might mean \\(2H\\), not \\(H\\), given that you add your inequalities later and get a \\(3H\\) term. Yeah, I clobbered the 2 coefficient in an edit, my bad. I've gone and fixed my mistake.`

Jonathan wrote:

I screwed up Lecture 18 but I've fixed it: now \(x \le y\) means "we can get \(x\) from \(y\)". If you get mixed up (as I often do), just remember 5 dollars \( \le \) 10 dollars: you can get less from more, not the other way.

`Jonathan wrote: > I thought the convention was that \\(x \le y\\) means "given x we can get y". I screwed up Lecture 18 but I've fixed it: now \\(x \le y\\) means "we can get \\(x\\) from \\(y\\)". If you get mixed up (as I often do), just remember 5 dollars \\( \le \\) 10 dollars: you can get less from more, not the other way.`

John wrote:

At the same time, \(F \le T\) and \(\{1, 2\} \le \{1, 2, 3\}\), where \(\le\) is \(\vdash\) and \(\subseteq\) appropriately. These are the two instances I lean on more. :/

I tend to remember \(x \le y\) as \(y\) being "more" than \(x\) with an appropriate notion of "more". With propositions it's "more permissive", and with sets it's just plain "more". In the case of resources, I expected "more" to be "more processed" or "later". I do see what you're saying about 10 being

literallymore than 5, so \(5 \le 10\) might model a "spending" action in a resource theory. It is a bit confusing, though, since the reactions are written analogously to \(10 \to 5\), i.e. the other way around.`John wrote: > $5 ≤ $10 At the same time, \\(F \le T\\) and \\(\\{1, 2\\} \le \\{1, 2, 3\\}\\), where \\(\le\\) is \\(\vdash\\) and \\(\subseteq\\) appropriately. These are the two instances I lean on more. :/ I tend to remember \\(x \le y\\) as \\(y\\) being "more" than \\(x\\) with an appropriate notion of "more". With propositions it's "more permissive", and with sets it's just plain "more". In the case of resources, I expected "more" to be "more processed" or "later". I do see what you're saying about 10 being _literally_ more than 5, so \\(5 \le 10\\) might model a "spending" action in a resource theory. It is a bit confusing, though, since the reactions are written analogously to \\(10 \to 5\\), i.e. the other way around.`

Jonathan wrote:

Right, me too usually. But when I discuss "resource theories", I start wanting "greater than" to mean something like "having more resources", or more money. So, I started out by flip-flopping between conventions when discussing Chapter 2, but I am now trying to consistently use a convention where \(x \le y\) means "you can get \(x\) from \(y\)". I think we're doomed to think about opposite categories (or at least "opposite posets") no matter what convention we choose, but I think beginners will find

$$ \textrm{ cake } \le \textrm{ cake } + \textrm{ ice cream } $$ less confusing than

$$ \textrm{ cake } + \textrm{ ice cream } \le \textrm{ cake }$$ Luckily, it's just a convention so it doesn't really matter.

`Jonathan wrote: > These are the two instances I lean on more. Right, me too usually. But when I discuss "resource theories", I start wanting "greater than" to mean something like "having more resources", or more money. So, I started out by flip-flopping between conventions when discussing Chapter 2, but I am now trying to consistently use a convention where \\(x \le y\\) means "you can get \\(x\\) from \\(y\\)". I think we're doomed to think about opposite categories (or at least "opposite posets") no matter what convention we choose, but I think beginners will find $$ \textrm{ cake } \le \textrm{ cake } + \textrm{ ice cream } $$ less confusing than $$ \textrm{ cake } + \textrm{ ice cream } \le \textrm{ cake }$$ Luckily, it's just a convention so it doesn't really matter.`

I'm a teaching assistant for a programming languages class this quarter, and it just occurred to me while looking at some EBNF grammars that we can get a noncommutative (and asymmetric!) monoidal preorder by considering

orderedcomplexes formed from the combined set of terminals and nonterminals in these grammars. Despite being asymmetric, this stillfeelsresource-y because we're consuming nonterminals to produce (nonterminals and) terminals. This seems to correspond with the notion of a semi-Thue system.There's also a very enjoyable puzzle of this type from Douglas Hofstadter's

Gödel, Escher, Bach, called the MU puzzle. The puzzle asks: given a set of four rules (akin to our "reactions" here), is it possible to get the string MU starting from the string MI? This is just another kind of reachability problem.`I'm a teaching assistant for a programming languages class this quarter, and it just occurred to me while looking at some [EBNF grammars](https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form) that we can get a noncommutative (and asymmetric!) monoidal preorder by considering _ordered_ complexes formed from the combined set of terminals and nonterminals in these grammars. Despite being asymmetric, this still _feels_ resource-y because we're consuming nonterminals to produce (nonterminals and) terminals. This seems to correspond with the notion of a [semi-Thue system](https://en.wikipedia.org/wiki/Semi-Thue_system). There's also a very enjoyable puzzle of this type from Douglas Hofstadter's _Gödel, Escher, Bach_, called the [MU puzzle](https://en.wikipedia.org/wiki/MU_puzzle). The puzzle asks: given a set of four rules (akin to our "reactions" here), is it possible to get the string MU starting from the string MI? This is just another kind of reachability problem.`

So here is my second attempt at

Puzzle 68(with \(x \leq y\) to mean given y, we can get x):Define \((a', b', c') \leq (a, b, c)\) when

If \(\frac{a}{2}=b\) then \(a'=0,\,b'=0,\,c'=c+b\)

If \(\frac{a}{2}\lt b\) then \(a'=0,\,b'=b-\frac{a}{2},\,c'=c+\frac{a}{2}\)

If \(\frac{a}{2}\gt b\) then \( a'=a-2b,\,b'=0,\,c'=c+b\)

If \(a=0\,or\,b=0\) then \(a'=a,\,b'=b,\,c'=c\)

Side question : does anybody know how to make a big curly left bracket with 4 rows and 1 column? I tried

/left/{/begin{matrix}a//b//c/end{matrix}/right. (i switched \ with / because it keeps trying to read it as a code.)

but doesn't seem to work.

`So here is my second attempt at **Puzzle 68** (with \\(x \leq y\\) to mean given y, we can get x): Define \\((a', b', c') \leq (a, b, c)\\) when 1. If \\(\frac{a}{2}=b\\) then \\(a'=0,\,b'=0,\,c'=c+b\\) 2. If \\(\frac{a}{2}\lt b\\) then \\(a'=0,\,b'=b-\frac{a}{2},\,c'=c+\frac{a}{2}\\) 3. If \\(\frac{a}{2}\gt b\\) then \\( a'=a-2b,\,b'=0,\,c'=c+b\\) 4. If \\(a=0\,or\,b=0\\) then \\(a'=a,\,b'=b,\,c'=c\\) Side question : does anybody know how to make a big curly left bracket with 4 rows and 1 column? I tried /left/{/begin{matrix}a//b//c/end{matrix}/right. (i switched \ with / because it keeps trying to read it as a code.) but doesn't seem to work.`

@Michael - I think you want to use

`\begin{cases}\end{cases}`

`@Michael - I think you want to use [`\begin{cases}\end{cases}`][wikia] [wikia]: http://latex.wikia.com/wiki/Cases_(LaTeX_environment)`

@Matthew Thanks!

`@Matthew Thanks!`

I like Marius Furter's answers to Puzzles 68 and 70 in comment #13. Here's how I'd do these puzzles.

In Puzzle 68 we're asking when we can turn

$$ a \text{H} + b \text{O} + c \text{H}_2\text{O} $$ into

$$ a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} $$ by repeatedly performing the reaction \( 2\text{H} + \text{O} \to \text{H}_2\text{O}\).

Each time we do this reaction we decrease \(a\) by 2, decrease \(b\) by 1 and increase \(c\) by 1. So, we can turn

$$ a \text{H} + b \text{O} + c \text{H}_2\text{O} $$ into

$$ a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} $$ precisely when

$$ (a',b',c') = (a - 2n, b - n, c + n) $$ for some \(n \in \mathbb{N}\).

If we also allow the reverse reaction, as in Puzzle 70, we can do it whenever

$$ (a',b',c') = (a - 2n, b - n, c + n) $$ for some \(n \in \mathbb{Z}\).

These answers can be converted into answers of the sort Marius gave.

I forget if someone answered my other question: which of these two relations define partial orders, as opposed to mere preorders?

`I like Marius Furter's answers to Puzzles 68 and 70 in [comment #13](https://forum.azimuthproject.org/discussion/comment/18009/#Comment_18009). Here's how I'd do these puzzles. In Puzzle 68 we're asking when we can turn \[ a \text{H} + b \text{O} + c \text{H}_2\text{O} \] into \[ a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} \] by repeatedly performing the reaction \\( 2\text{H} + \text{O} \to \text{H}_2\text{O}\\). Each time we do this reaction we decrease \\(a\\) by 2, decrease \\(b\\) by 1 and increase \\(c\\) by 1. So, we can turn \[ a \text{H} + b \text{O} + c \text{H}_2\text{O} \] into \[ a' \text{H} + b' \text{O} + c' \text{H}_2\text{O} \] precisely when \[ (a',b',c') = (a - 2n, b - n, c + n) \] for some \\(n \in \mathbb{N}\\). If we also allow the reverse reaction, as in Puzzle 70, we can do it whenever \[ (a',b',c') = (a - 2n, b - n, c + n) \] for some \\(n \in \mathbb{Z}\\). These answers can be converted into answers of the sort Marius gave. I forget if someone answered my other question: which of these two relations define partial orders, as opposed to mere preorders?`

@Marius, so far I agree with your answer in Comment 8.

One suggestion about the notation (but not the content!) of your ideas: I found it helpful to write the ordering as \( (a , b, c + n) \leq (a + 2n, b + n , c) \), for all \(a,b,c \in \mathbb{N}\). Translating this statement using John's meaning for \( \leq\) would give us "We can get \(a\) Hs, \(b\) Os, and \((c +n )\) H2Os from \((a + 2n)\) Hs, \((b +n)\) Os, and \(c \) H2Os". This jives with my understanding of the problem, and it gets rid of having to worry about \(a \geq 2n\) etc! Also reflexivity follows directly from the case where \(n = 0\).

Other than that I couldn't find a way of streamlining the proofs of the different properties we need to prove. I also did a lot of equation manipulation using the rules of addition. Did anyone else find a simplification?

`@Marius, so far I agree with your answer in <a href = "https://forum.azimuthproject.org/discussion/comment/17970/#Comment_17970"> Comment 8</a>. One suggestion about the notation (but not the content!) of your ideas: I found it helpful to write the ordering as \\( (a , b, c + n) \leq (a + 2n, b + n , c) \\), for all \\(a,b,c \in \mathbb{N}\\). Translating this statement using John's meaning for \\( \leq\\) would give us "We can get \\(a\\) Hs, \\(b\\) Os, and \\((c +n )\\) H2Os from \\((a + 2n)\\) Hs, \\((b +n)\\) Os, and \\(c \\) H2Os". This jives with my understanding of the problem, and it gets rid of having to worry about \\(a \geq 2n\\) etc! Also reflexivity follows directly from the case where \\(n = 0\\). Other than that I couldn't find a way of streamlining the proofs of the different properties we need to prove. I also did a lot of equation manipulation using the rules of addition. Did anyone else find a simplification?`

Sophie wrote:

I agree. This is much nicer and probably also easier to understand. Thanks!

John wrote:

Puzzle 69/70In theirreversible casethere is no way to proceed along a reaction sequence and end up where you started. Thus, there are no equivalent elements and it forms apartial order.In the

reversible caseone can also go backward along a reaction sequence, thus making all of the elements of a sequence equivalent. Thus, this is merely apreorder.Side note: If we wanted to turn this preorder into a partial order we would have to identify all elements of any given reaction sequence. This new element would correspond to the general atomic composition of this reaction sequence. E.g \( (2,1,0) \leftrightharpoons (0,0,1) \) would become one point signifying 2 H atoms and 1 O atom (which can in any allowed molecular configuration).

`Sophie wrote: > I found it helpful to write the ordering as \\( (a , b, c + n) \leq (a + 2n, b + n , c) \\), for all \\(a,b,c \in \mathbb{N}\\) I agree. This is much nicer and probably also easier to understand. Thanks! John wrote: > I forget if someone answered my other question: which of these two relations define partial orders, as opposed to mere preorders? **Puzzle 69/70** In the **irreversible case** there is no way to proceed along a reaction sequence and end up where you started. Thus, there are no equivalent elements and it forms a **partial order**. In the **reversible case** one can also go backward along a reaction sequence, thus making all of the elements of a sequence equivalent. Thus, this is merely a **preorder**. Side note: If we wanted to turn this preorder into a partial order we would have to identify all elements of any given reaction sequence. This new element would correspond to the general atomic composition of this reaction sequence. E.g \\( (2,1,0) \leftrightharpoons (0,0,1) \\) would become one point signifying 2 H atoms and 1 O atom (which can in any allowed molecular configuration).`

Jonathan wrote in #22:

I know that some computational chemists actually use term rewrite rules for expressing reactions.

One such language is called Reaction SMARTS.

Coley et al. (2017) wrote about extracting reaction SMARTs - they used 15 000 experimental reaction records from granted United States patents.

I am familiar with this and a couple other corpi, this one has the most noise (it is OCR data) :(

The problem is very hard, even with perfect data. You not only need to conserve matter, but also charge and account for stereochemistry. In addition, it is important to account for reaction rates - I understand one technique is to use various motifs on either side of the reaction equation as features for machine learning Gibbs free energy.

`[Jonathan wrote in #22](https://forum.azimuthproject.org/discussion/comment/18045/#Comment_18045): > There's also a very enjoyable puzzle of this type from Douglas Hofstadter's Gödel, Escher, Bach, called the MU puzzle. The puzzle asks: given a set of four rules (akin to our "reactions" here), is it possible to get the string MU starting from the string MI? This is just another kind of reachability problem. I know that some computational chemists actually use term rewrite rules for expressing reactions. One such language is called [Reaction SMARTS](http://www.rdkit.org/docs/RDKit_Book.html#reaction-smarts). [Coley et al. (2017)](https://pubs.acs.org/doi/full/10.1021/acscentsci.7b00064) wrote about extracting reaction SMARTs - they used 15 000 experimental reaction records from granted United States patents. I am familiar with this and a couple other corpi, this one has the most noise (it is OCR data) :( The problem is very hard, even with perfect data. You not only need to conserve matter, but also charge and account for [stereochemistry](https://en.wikipedia.org/wiki/Stereochemistry). In addition, it is important to account for reaction rates - I understand one technique is to use various motifs on either side of the reaction equation as features for machine learning Gibbs free energy.`

John, could you please recommend some paper/book/blog as a good introduction to such systematical methods? Progressing so far through the book/course already brought a lot of value, but conditions like this one for monoidal preorders make me feel uneasy. Handwavingly I knew that this is just another monotonicity condition, but why exactly this one, and how the form to express it was chosen? - questions like this bothered me this week. It's looks like some intuition was lost while trying to find the most concise representation of the structure of a monoidal product.

`>A good category theorist knows lots of systematical ways to find good definitions, which convert "magic" to "method". John, could you please recommend some paper/book/blog as a good introduction to such systematical methods? Progressing so far through the book/course already brought a lot of value, but conditions like this one for monoidal preorders make me feel uneasy. Handwavingly I knew that this is just another monotonicity condition, but why exactly this one, and how the form to express it was chosen? - questions like this bothered me this week. It's looks like some intuition was lost while trying to find the most concise representation of the structure of a monoidal product.`

Igor, I suspect the only way to learn how to 'convert "magic" to "method"' is a lot of practice.

Or to put it simply, I think there are no shortcuts to learning.

`Igor, I suspect the only way to learn how to 'convert "magic" to "method"' is a lot of practice. Or to put it simply, I think there are no shortcuts to learning.`

Igor wrote:

Any introduction to category theory contains these insights; two of my favorites are these free ones:

Tom Leinster,

Basic Category Theory, Cambridge Studies in Advanced Mathematics, Vol. 143, Cambridge University Press, 2014. (An introduction.)Emily Riehl,

Category Theory in Context, Dover, New York, 2016. (More advanced.)However,it's hard to get these insights without carefully studying several of these books andalsotalking to an expert several times a week for a long time. That's why I'm teaching this 6-month-long course!The solution is to ask me those questions! I'm not getting enough questions in this course.

I guess you're asking about this condition:

$$ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .$$ I wanted everyone to think about this condition, so I posed this puzzle:

Puzzle 66.What's another way to state this last condition using ideas we've already discussed? Hint: it's a property of the function \(\otimes : X \times X \to X\).The property is that \(\otimes : X \times X \to X\) is

monotone.Remember, given two preorders \(X\) and \(Y\) there's an important way to make \(X \times Y\) into a preorder, where we say \((x,y) \le (x',y') \) iff \(x \le x'\) and \(y \le y'\). This is the

product in the category of preorders- when you learn a bit more category theory you'll know what that means and why it's important. (Or maybe you already do!)So, when \(X\) is a preorder, so is \(X \times X\), and it makes a lot of sense, when studying

monoids that are also preorders, to demand that \(\otimes : X \times X \to X\) be monotone. This makes \(X\) into amonoid in the category of preorders.It's very similar to how an "associative algebra" is a monoid in the category of vector spaces, or a topological group is a group in the category of topological spaces. If these examples are unfamiliar, I apologize: they don't really matter, they just indicate that in math we're often faced with the task of hybridizing two structures, say A's and B's — and a good approach is often to define an "A in the category of B's".

This can be done systematically; it's called

internalization, and we're seeing an example when we're discussing monoidal preorders. There is a lot more to say about it:When you know internalization, you can just say:

Definition.A monoidal preorder is a monoid in the category of preorders.and this

impliesthe condition$$ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .$$ This is very nice.

However, that nLab page may be difficult to understand without a lot of experience in category theory! That's why I'm teaching this course.

Ask questions....

`Igor wrote: > John, could you please recommend some paper/book/blog as a good introduction to such systematical methods? Any introduction to category theory contains these insights; two of my favorites are these free ones: * Tom Leinster, _[Basic Category Theory](https://arxiv.org/abs/1612.09375)_, Cambridge Studies in Advanced Mathematics, Vol. 143, Cambridge University Press, 2014. (An introduction.) * Emily Riehl, _[Category Theory in Context](http://www.math.jhu.edu/~eriehl/context.pdf)_, Dover, New York, 2016. (More advanced.) _However,_ it's hard to get these insights without carefully studying several of these books and _also_ talking to an expert several times a week for a long time. That's why I'm teaching this 6-month-long course! > Progressing so far through the book/course already brought a lot of value, but conditions like this one for monoidal preorders make me feel uneasy. Handwavingly I knew that this is just another monotonicity condition, but why exactly this one, and how the form to express it was chosen? - questions like this bothered me this week. The solution is to ask me those questions! I'm not getting enough questions in this course. I guess you're asking about this condition: \[ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .\] I wanted everyone to think about this condition, so I posed this puzzle: **Puzzle 66.** What's another way to state this last condition using ideas we've already discussed? Hint: it's a property of the function \\(\otimes : X \times X \to X\\). The property is that \\(\otimes : X \times X \to X\\) is _monotone_. Remember, given two preorders \\(X\\) and \\(Y\\) there's an important way to make \\(X \times Y\\) into a preorder, where we say \\((x,y) \le (x',y') \\) iff \\(x \le x'\\) and \\(y \le y'\\). This is the **product in the category of preorders** - when you learn a bit more category theory you'll know what that means and why it's important. (Or maybe you already do!) So, when \\(X\\) is a preorder, so is \\(X \times X\\), and it makes a lot of sense, when studying _monoids that are also preorders_, to demand that \\(\otimes : X \times X \to X\\) be monotone. This makes \\(X\\) into a **monoid in the category of preorders**. It's very similar to how an "associative algebra" is a monoid in the category of vector spaces, or a topological group is a group in the category of topological spaces. If these examples are unfamiliar, I apologize: they don't really matter, they just indicate that in math we're often faced with the task of hybridizing two structures, say A's and B's — and a good approach is often to define an "A in the category of B's". This can be done systematically; it's called **internalization**, and we're seeing an example when we're discussing monoidal preorders. There is a lot more to say about it: * nLab, [Internalization](https://ncatlab.org/nlab/show/internalization). When you know internalization, you can just say: **Definition.** A monoidal preorder is a monoid in the category of preorders. and this _implies_ the condition \[ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .\] This is very nice. However, that nLab page may be difficult to understand without a lot of experience in category theory! That's why I'm teaching this course. Ask questions....`

John wrote:

Thanks for the links, I was planning to look at the Riehl's book and a few others after the course and the Seven Sketches, closer to winter, at the moment have time only for the latter two.

`John wrote: >Any introduction to category theory contains these insights; two of my favorites are these free ones Thanks for the links, I was planning to look at the Riehl's book and a few others after the course and the Seven Sketches, closer to winter, at the moment have time only for the latter two.`

John, continuing the discussion from Lecture 21, I became interested in the following, maybe you'll be able to help me here. Let's say we have a monotone function \(f: X \times X \to X\) and the condition \(C^\times: x \le x' \textrm{ and } y \le y' \Rightarrow f(x, y) \le f(x', y') .\)

As we learned, the condition implies that the function is monotone: \(C^\times \Rightarrow f \in M^\times\), where \(M^\times\) is the set of monotone functions \(X \times X \to X\). The question is whether converse \(f \in M^\times \Rightarrow C^\times\) is also true, that is the function \(f\) being monotonic implies that it supports the condition \(C^\times\)?

The easiest way to show that converse is not true, is to find a monotone function \(g \in M^\times\) which doesn't support \(C^\times\). The lexicographic order function looks like a good candidate. If it is monotonic (it looks like so, but I'm not sure: \(l(x, y) = x\)) and doesn't obey \(C^\times\), then the conclusion is that the condition \(C^\times\) is supported only by a subset \(F \subset M^\times\).

So the question is whether any monotone will do to automatically transform \((X \times X)\) into preorder, or the condition brings something new to the table? Still figuring it out.

`John, continuing the discussion from Lecture 21, I became interested in the following, maybe you'll be able to help me here. Let's say we have a monotone function \\(f: X \times X \to X\\) and the condition \\(C^\times: x \le x' \textrm{ and } y \le y' \Rightarrow f(x, y) \le f(x', y') .\\) As we learned, the condition implies that the function is monotone: \\(C^\times \Rightarrow f \in M^\times\\), where \\(M^\times\\) is the set of monotone functions \\(X \times X \to X\\). The question is whether converse \\(f \in M^\times \Rightarrow C^\times\\) is also true, that is the function \\(f\\) being monotonic implies that it supports the condition \\(C^\times\\)? The easiest way to show that converse is not true, is to find a monotone function \\(g \in M^\times\\) which doesn't support \\(C^\times\\). The lexicographic order function looks like a good candidate. If it is monotonic (it looks like so, but I'm not sure: \\(l(x, y) = x\\)) and doesn't obey \\(C^\times\\), then the conclusion is that the condition \\(C^\times\\) is supported only by a subset \\(F \subset M^\times\\). So the question is whether any monotone will do to automatically transform \\((X \times X)\\) into preorder, or the condition brings something new to the table? Still figuring it out.`

Keith wrote:

Keith, I do think that there are ways to make the road to understanding either an enjoyable journey, or a painful agony.

Sketchy, visual, or "intuitive" overviews of the size of a blog post or a paper strive to make the first scenario a reality. They serve as a map while you are exploring further. But it seems that the Seven Sketches + the course is the way to go, indeed :)

`Keith wrote: >Igor, I suspect the only way to learn how to 'convert "magic" to "method"' is a lot of practice. Or to put it simply, I think there are no shortcuts to learning. Keith, I do think that there are ways to make the road to understanding either an enjoyable journey, or a painful agony. Sketchy, visual, or "intuitive" overviews of the size of a blog post or a paper strive to make the first scenario a reality. They serve as a map while you are exploring further. But it seems that the Seven Sketches + the course is the way to go, indeed :)`

Igor, I think conventionally, the "default" order on \(X \times X\) is the product (component-wise) order. When we write a monotone function \(f : X \times X \to X\), we're leaving the orders implicit for both \(X \times X\) and \(X\), but there's still a

fixedorder for both, which all functions in \(M^\times\) must respect. In that sense, \(C^\times\) is indeed the defining characteristic of \(M^\times\).Put another way, a function \(f : X \times X \to X\) may be monotone with respect to the product order, but not with respect to the lexicographical order -- or vice versa. Thus, \(M^\times\)

can'tbe defined independent of any particular order.`Igor, I think conventionally, the "default" order on \\(X \times X\\) is the product (component-wise) order. When we write a monotone function \\(f : X \times X \to X\\), we're leaving the orders implicit for both \\(X \times X\\) and \\(X\\), but there's still a _fixed_ order for both, which all functions in \\(M^\times\\) must respect. In that sense, \\(C^\times\\) is indeed the defining characteristic of \\(M^\times\\). Put another way, a function \\(f : X \times X \to X\\) may be monotone with respect to the product order, but not with respect to the lexicographical order -- or vice versa. Thus, \\(M^\times\\) _can't_ be defined independent of any particular order.`

Puzzle 66@DanOneata Where did the definition of the relation \(\le_{X \times X}\) in the product preorder come from?

$$ x \le_X x' \text{ and } y \le_X y' = (x, y) \le_{X \times X} (x', y') $$ Is it just an alternate formulation of the "pixie dust"?

`**Puzzle 66** @DanOneata Where did the definition of the relation \\(\le_{X \times X}\\) in the product preorder come from? $$ x \le_X x' \text{ and } y \le_X y' = (x, y) \le_{X \times X} (x', y') $$ Is it just an alternate formulation of the "pixie dust"?`

Jonathan, thanks for

I got lost among 3 trees, and all these is tightly bound to what comes next in Lecture 23 and Lecture 24.

Indeed

any\(\rho : X \times X \to X\), where we assume that \(X\) is already equipped with order relation \(\leq_X\): \((X, \leq_X)\),automatically inducesa natural preorder on \(X \times X \) by requiring $$ \rho(x_1, x_2) \leq_X \rho(x'_1, x'_2) \Rightarrow (x_1, x_2) \leq_\rho (x'_1, x'_2) $$ where \(\leq_\rho = \leq_{X \times X}\) is an induced order relation on \(X \times X \), making it into preorder: \((X \times X, \leq_\rho)\). Since this relation is induced, implication also goes backwards: $$ (x_1, x_2) \leq_\rho (x'_1, x'_2) \Rightarrow \rho(x_1, x_2) \leq_X \rho(x'_1, x'_2) $$ which is exactly amonotonicitycondition! So things are starting to fall into their places, at last.And now we can say that among all possible \(\rho\) there indeed exist some functions which additionally support $$ C^\times: x_1 \le_X x'_1 \textrm{ and } x_2 \le_X x'_2 \Rightarrow \rho(x_1, x_2) \le_\rho \rho(x'_1, x'_2) $$ Okay, now only what I need is to figure out how this condition structures the \( (X \times X, \leq_\rho) \) preorder, and how preorders supporting it differ from others.

`Jonathan, thanks for >Thus, M× can't be defined independent of any particular order. I got lost among 3 trees, and all these is tightly bound to what comes next in Lecture 23 and Lecture 24. Indeed **any** \\(\rho : X \times X \to X\\), where we assume that \\(X\\) is already equipped with order relation \\(\leq_X\\): \\((X, \leq_X)\\), **automatically induces** a natural preorder on \\(X \times X \\) by requiring \[ \rho(x_1, x_2) \leq_X \rho(x'_1, x'_2) \Rightarrow (x_1, x_2) \leq_\rho (x'_1, x'_2) \] where \\(\leq_\rho = \leq_{X \times X}\\) is an induced order relation on \\(X \times X \\), making it into preorder: \\((X \times X, \leq_\rho)\\). Since this relation is induced, implication also goes backwards: \[ (x_1, x_2) \leq_\rho (x'_1, x'_2) \Rightarrow \rho(x_1, x_2) \leq_X \rho(x'_1, x'_2) \] which is exactly a **monotonicity** condition! So things are starting to fall into their places, at last. And now we can say that among all possible \\(\rho\\) there indeed exist some functions which additionally support \[ C^\times: x_1 \le_X x'_1 \textrm{ and } x_2 \le_X x'_2 \Rightarrow \rho(x_1, x_2) \le_\rho \rho(x'_1, x'_2) \] Okay, now only what I need is to figure out how this condition structures the \\( (X \times X, \leq_\rho) \\) preorder, and how preorders supporting it differ from others.`

And if my last argument in 38 is somewhat valid, then

is somewhat redundant, since all \(\rho: X \times X \to X\) are automatically monotone, but only some of them additionally support product order condition.

Edit: it seems that my travel in the dark continues; in the set of all possible preorders, defined on the set \(X \times X\), there is the subset of preorders with "natural order" induced by \(\rho \), and the subset of preorders possesing \(C^\times\) property. And these 2 subsets actually may be in any relation with each other - containment, intersection, or even disjoint. So John's argument is valid, don't know why I decided that preorders with \(C^\times\) should be part of "naturally ordered" preorders, probably it was morning.`And if my last argument in 38 is somewhat valid, then >What's another way to state this last condition using ideas we've already discussed? is somewhat redundant, since all \\(\rho: X \times X \to X\\) are automatically monotone, but only some of them additionally support product order condition. **Edit**: it seems that my travel in the dark continues; in the set of all possible preorders, defined on the set \\(X \times X\\), there is the subset of preorders with "natural order" induced by \\(\rho \\), and the subset of preorders possesing \\(C^\times\\) property. And these 2 subsets actually may be in any relation with each other - containment, intersection, or even disjoint. So John's argument is valid, don't know why I decided that preorders with \\(C^\times\\) should be part of "naturally ordered" preorders, probably it was morning.`

Frederick Eisele, #37:

The product preorder is a way of

producinga new preorder given two available preorders. Example 1.42 in the text-book says:In our case, since \(X\) is a preorder, so is \(X \times X\); given this follows logically, I wouldn't dub it "pixie dust". If anything, the special ingredient in the definition of monoidal preorders is "monotonicity".

But John has already elaborated on these ideas in the second half of comment #32 – check it out! :-)

`[Frederick Eisele, #37](https://forum.azimuthproject.org/discussion/comment/18375/#Comment_18375): > Where did the definition of the relation \\(\le X \times X\\) in the product preorder come from? > > Is it just an alternate formulation of the "pixie dust"? The product preorder is a way of _producing_ a new preorder given two available preorders. Example 1.42 in the text-book says: > Given preorders \\((P, \le_P)\\) and \\((Q, \le_Q)\\), we may define a preorder structure on the product set \\(P \times Q\\) by setting \\((p, q) \le_{P \times Q} (p', q')\\) if and only if \\(p \le_P p'\\) and \\(q \le_Q q'\\). In our case, since \\(X\\) is a preorder, so is \\(X \times X\\); given this follows logically, I wouldn't dub it "pixie dust". If anything, the special ingredient in the definition of monoidal preorders is "monotonicity". But John has already elaborated on these ideas in the second half of [comment #32](https://forum.azimuthproject.org/discussion/comment/18302/#Comment_18302) – check it out! :-)`