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

- All Categories 2.2K
- Programming with Categories Course 22
- Exercises - Programming with Categories Course 15
- Applied Category Theory Course 341
- Applied Category Theory Seminar 4
- Exercises - Applied Category Theory Course 149
- Discussion Groups 50
- How to Use MathJax 15
- Chat 487
- Azimuth Code Project 108
- News and Information 147
- 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 41

Options

Now let's look at a mathematical approach to resource theories. As I've mentioned, resource theories let us tackle questions like these:

- Given what I have,
*is it possible*to get what I want? - Given what I have,
*how much will it cost*to get what I want? - Given what I have,
*how long will it take*to get what I want? - Given what I have,
*what is the set of ways*to get what I want?

Our first approach will only tackle question 1. Given \(y\), we will only ask *is it possible* to get \(x\). This is a yes-or-no question, unlike questions 2-4, which are more complicated. If the answer is yes we will write \(x \le y\).

So, for now our resources will form a "preorder", as defined in Lecture 3.

**Definition.** A **preorder** is a set \(X\) equipped with a relation \(\le\) obeying:

**reflexivity**: \(x \le x\) for all \(x \in X\).**transitivity**\(x \le y\) and \(y \le z\) imply \(x \le z\) for all \(x,y,z \in X\).

All this makes sense. Given \(x\) you can get \(x\). And if you can get \(x\) from \(y\) and get \(y\) from \(z\) then you can get \(x\) from \(z\).

What's new is that we can also *combine* resources. In chemistry we denote this with a plus sign: if we have a molecule of \(\text{H}_2\text{O}\) and a molecule of \(\text{CO}_2\) we say we have \(\text{H}_2\text{O} + \text{CO}_2\). We can use almost any symbol we want; Fong and Spivak use \(\otimes\) so I'll often use that. We pronounce this symbol "tensor". Don't worry about why: it's a long story, but you can live a long and happy life without knowing it.

It turns out that when you have a way to combine things, you also want a special thing that acts like "nothing". When you combine \(x\) with nothing, you get \(x\). We'll call this special thing \(I\).

**Definition.** A **monoid** is a set \(X\) equipped with:

- a binary operation \(\otimes : X \times X \to X\)
- an element \( I \in X \)

such that these laws hold:

the

**associative law**: \( (x \otimes y) \otimes z = x \otimes (y \otimes z) \) for all \(x,y,z \in X\)the

**left and right unit laws**: \(I \otimes x = x = x \otimes I\) for all \(x \in X\).

You know lots of monoids. In mathematics, monoids rule the world! I could talk about them endlessly, but today we need to combine the monoids and preorders:

**Definition.** A **monoidal preorder** is a set \(X\) with a relation \(\le\) making it into a preorder, an operation \(\otimes : X \times X \to X\) and element \(I \in X\) making it into a monoid, and obeying:

$$ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .$$
This last condition should make sense: if you can turn an egg into a fried egg and turn a slice of bread into a piece of toast, you can turn an egg *and* a slice of bread into a fried egg *and* a piece of toast!

You know lots of monoidal preorders, too! Many of your favorite number systems are monoidal preorders:

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

*Money* is an important resource: outside of mathematics, *money* rules the world.
We combine money by addition, and we often use these different number systems to keep track of money. In fact it was bankers who invented negative numbers, to keep track of debts! The idea of a "negative resource" was very radical: it took mathematicians over a century to get used to it.

But sometimes we combine numbers by multiplication. Can we get monoidal preorders this way?

**Puzzle 60.** Is the set \(\mathbb{N}\) with the usual \(\le\), the binary operation \(\cdot : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) and the element \(1 \in \mathbb{N}\) a monoidal preorder?

**Puzzle 61.** Is the set \(\mathbb{R}\) with the usual \(\le\), the binary operation \(\cdot : \mathbb{R} \times \mathbb{R} \to \mathbb{R}\) and the element \(1 \in \mathbb{R}\) a monoidal preorder?

**Puzzle 62.** One of the questions above has the answer "no". What's the least destructive way to "fix" this example and get a monoidal preorder?

**Puzzle 63.** Find more examples of monoidal preorders.

**Puzzle 64.** Are there monoids that cannot be given a relation \(\le\) making them into monoidal preorders?

**Puzzle 65.** A **monoidal poset** is a monoidal preorder that is also a poset, meaning

$$ x \le y \textrm{ and } y \le x \textrm{ imply } x = y $$ for all \(x ,y \in X\). Are there monoids that cannot be given any relation \(\le\) making them into monoidal posets?

**Puzzle 66.** Are there posets that cannot be given any operation \(\otimes\) and element \(I\) making them into monoidal posets?

## Comments

I don't think so. Following the definition:

That law is always obeyed for the trivial preorder where \(\forall xy. x \leq y\), right?

Every monoid has a partial order that makes it a monoidal poset. It's the dual of the trivial preorder - the discrete partial order.

Assume \(x \le x'\) and \(y \le y'\). If \(\le\) is the discrete partial order, then \(x = x'\) and \(y = y'\). Hence \(x \otimes y = x' \otimes y'\) by substitution, and thus \(x \otimes y \leq x' \otimes y'\) by reflexivity and substitution.

`> **Puzzle 64**. Are there monoids that cannot be given a relation ≤ making them into monoidal preorders? I don't think so. Following the definition: > A **monoidal preorder** is a set \\(X\\) with a relation \\(\le\\) making it into a preorder, an operation \\(\otimes : X \times X \to X\\) and element \\(I \in X\\) making it into a monoid, and obeying: > $$ x \le x' \textrm{ and } y \le y' \textrm{ imply } x \otimes y \le x' \otimes y' .$$ That law is always obeyed for the trivial preorder where \\(\forall xy. x \leq y\\), right? > **Puzzle 65**. Are there monoids that cannot be given any relation ≤ making them into monoidal posets? Every monoid has a partial order that makes it a monoidal poset. It's the dual of the trivial preorder - the discrete partial order. Assume \\(x \le x'\\) and \\(y \le y'\\). If \\(\le\\) is the discrete partial order, then \\(x = x'\\) and \\(y = y'\\). Hence \\(x \otimes y = x' \otimes y'\\) by substitution, and thus \\(x \otimes y \leq x' \otimes y'\\) by reflexivity and substitution.`

Puzzle 60.Yes. Suppose we have \(x \le y\) and \(x' \le y'\). We know all of the variables are nonnegative, so we can freely multiply our variables into these inequalities to obtain \(x \cdot x' \le y \cdot x'\) and \(y \cdot x' \le y \cdot y'\); by transitivity, we have \(x \cdot x' \le y \cdot y'\).Puzzle 61.No, because Puzzle 62 says one of Puzzle 60 and Puzzle 61 must have "no" as its answer. ;) Without appealing to outside information, we can merely demonstrate that \(-1 \le 1\) and \(-2 \le 1\) but \(-1 \cdot -2 = 2 \not\le 1 = 1 \cdot 1\).Puzzle 62.Define \(x \preceq y\) by \(\lvert x \rvert \le \lvert y \rvert\). Then if \(x \preceq y\) and \(x' \preceq y'\), we know \(\lvert x \rvert \le \lvert y \rvert\) and \(\lvert x' \rvert \le \lvert y' \rvert\); these are all positive quantities as before, so by the same process we find \(\lvert x \cdot x' \rvert = \lvert x \rvert \cdot \lvert x' \rvert \le \lvert y \rvert \cdot \lvert y' \rvert = \lvert y \cdot y' \rvert\). Therefore, \(x \cdot x' \preceq y \cdot y'\), as desired.We do get two units out of this (\(-1\) and \(1\)), but I think that's okay as long as we pick one and stick to it. They're equivalent in the sense that \(-1 \preceq 1\) and \(1 \preceq -1\).

Puzzle 63.The structures \(\langle \mathcal{P}(X), \subseteq, \cup, \emptyset \rangle\) and \(\langle \mathcal{P}(X), \subseteq, \cap, X \rangle\) are monoidal preorders. More generally, any lattice possesses two (dual) monoidal structures.Puzzle 64.We can always apply either the discrete or codiscrete preorders to make a monoid into a monoidal preorder.Puzzle 65.We can always apply the discrete preorder to make a monoid into a monoidal poset.Puzzle 66.This is surprisingly hard to think through. I've got a weak hunch that the poset below cannot be made into a monoidal poset, but I'm still working through it. The poset can't be a lattice, per Puzzle 63, and this is the smallest non-semilattice non-trivial-order at my disposal.`**Puzzle 60.** Yes. Suppose we have \\(x \le y\\) and \\(x' \le y'\\). We know all of the variables are nonnegative, so we can freely multiply our variables into these inequalities to obtain \\(x \cdot x' \le y \cdot x'\\) and \\(y \cdot x' \le y \cdot y'\\); by transitivity, we have \\(x \cdot x' \le y \cdot y'\\). **Puzzle 61.** No, because Puzzle 62 says one of Puzzle 60 and Puzzle 61 must have "no" as its answer. ;) Without appealing to outside information, we can merely demonstrate that \\(-1 \le 1\\) and \\(-2 \le 1\\) but \\(-1 \cdot -2 = 2 \not\le 1 = 1 \cdot 1\\). **Puzzle 62.** Define \\(x \preceq y\\) by \\(\lvert x \rvert \le \lvert y \rvert\\). Then if \\(x \preceq y\\) and \\(x' \preceq y'\\), we know \\(\lvert x \rvert \le \lvert y \rvert\\) and \\(\lvert x' \rvert \le \lvert y' \rvert\\); these are all positive quantities as before, so by the same process we find \\(\lvert x \cdot x' \rvert = \lvert x \rvert \cdot \lvert x' \rvert \le \lvert y \rvert \cdot \lvert y' \rvert = \lvert y \cdot y' \rvert\\). Therefore, \\(x \cdot x' \preceq y \cdot y'\\), as desired. We do get two units out of this (\\(-1\\) and \\(1\\)), but I think that's okay as long as we pick one and stick to it. They're equivalent in the sense that \\(-1 \preceq 1\\) and \\(1 \preceq -1\\). **Puzzle 63.** The structures \\(\langle \mathcal{P}(X), \subseteq, \cup, \emptyset \rangle\\) and \\(\langle \mathcal{P}(X), \subseteq, \cap, X \rangle\\) are monoidal preorders. More generally, any lattice possesses two (dual) monoidal structures. **Puzzle 64.** We can always apply either the discrete or codiscrete preorders to make a monoid into a monoidal preorder. **Puzzle 65.** We can always apply the discrete preorder to make a monoid into a monoidal poset. **Puzzle 66.** This is surprisingly hard to think through. I've got a weak hunch that the poset below cannot be made into a monoidal poset, but I'm still working through it. The poset can't be a lattice, per Puzzle 63, and this is the smallest non-semilattice non-trivial-order at my disposal. ![](https://i.imgur.com/Km2PosD.png)`

Puzzle 66.Let us pick the unit, \(I\), to be any element of the preorder \(P\), and let the binary operation always return the unit, that is, \(x \otimes y = I\) for all \(x, y \in P\); then:So, it seems that any poset can be turned into a monoidal poset.

Edit:As pointed out below by Jonathan, my answer is flawed – this happened because I was sloppy and I skipped some parts of the proof.`**Puzzle 66.** Let us pick the unit, \\(I\\), to be any element of the preorder \\(P\\), and let the binary operation always return the unit, that is, \\(x \otimes y = I\\) for all \\(x, y \in P\\); then: 1. \\( (P, \otimes, I) \\) is a monoid. 2. \\(x \otimes y \le x' \otimes y'\\) holds for all \\(x, y, x', y' \in P\\), because of reflexivity on \\(I\\). So, it seems that any poset can be turned into a monoidal poset. **Edit:** As pointed out below by Jonathan, my answer is flawed – this happened because I was sloppy and I skipped some parts of the proof.`

Dan, I don't think that's actually a proper monoid, since \(x \otimes I = I\) for all \(x\). If \(x \neq I\), we want \(x \otimes I = x\) instead. So \(I\) isn't a unit.

`Dan, I don't think that's actually a proper monoid, since \\(x \otimes I = I\\) for all \\(x\\). If \\(x \neq I\\), we want \\(x \otimes I = x\\) instead. So \\(I\\) isn't a unit.`

Jonathan Yes, you are right. Sorry, for the silly mistake! :(

`[Jonathan](https://forum.azimuthproject.org/profile/2316/Jonathan%20Castello) Yes, you are right. Sorry, for the silly mistake! :(`

Hey, it's a perfectly good semigroup. :) Sometimes there are useful semigroups that aren't quite monoids, like yours (which I'm inclined to call Const) and First, where \(x \otimes y = x\).

`Hey, it's a perfectly good [semigroup](https://en.wikipedia.org/wiki/Semigroup). :) Sometimes there are useful semigroups that aren't quite monoids, like yours (which I'm inclined to call Const) and [First](https://hackage.haskell.org/package/semigroups-0.18.1/docs/Data-Semigroup.html#t:First), where \\(x \otimes y = x\\).`

Nice answers, folks! But I'm not satisfied with the answer to Puzzles 62 and 66.

You're not going to like my answer to Puzzle 62, but my answer involves a

usefulmonoidal preorder.`Nice answers, folks! But I'm not satisfied with the answer to Puzzles 62 and 66. You're not going to like my answer to Puzzle 62, but my answer involves a _useful_ monoidal preorder.`

I

thinkthat your poset can be made into a monoidal preorder by letting \(\forall x. a \otimes x = x = x \otimes a\) and \(\forall x \forall y. x \neq a \wedge y \neq a \implies x \otimes y = c\). Is that right?In addition to the solution not being a meet-semi-lattice bounded below or a join-semi-lattice bounded above as you mention, I suspect that countable unbounded dense linear orders don't work.

`> Puzzle 66. This is surprisingly hard to think through. I've got a weak hunch that the poset below cannot be made into a monoidal poset, but I'm still working through it. The poset can't be a lattice, per Puzzle 63, and this is the smallest non-semilattice non-trivial-order at my disposal. I *think* that your poset can be made into a monoidal preorder by letting \\(\forall x. a \otimes x = x = x \otimes a\\) and \\(\forall x \forall y. x \neq a \wedge y \neq a \implies x \otimes y = c\\). Is that right? In addition to the solution not being a meet-semi-lattice bounded below or a join-semi-lattice bounded above as you mention, I suspect that countable unbounded dense linear orders don't work.`

It's certainly a monoid, but I don't think it respects the partial order structure. Since \(c \le a\) and \(d \le d\), we expect \(c \otimes d \le a \otimes d\). But \(c \otimes d = c \not\le d = a \otimes d\).

Here's a multiplication table I built out of your rule:

`> Is that right? It's certainly a monoid, but I don't think it respects the partial order structure. Since \\(c \le a\\) and \\(d \le d\\), we expect \\(c \otimes d \le a \otimes d\\). But \\(c \otimes d = c \not\le d = a \otimes d\\). Here's a multiplication table I built out of your rule: <pre> |abcd -+---- a|abcd b|bccc c|cccc d|dccc </pre>`

there's a trivial answer to

Puzzle 66– the empty poset can't be given a monoidal structure since there is no element to be \(I\).`there's a trivial answer to **Puzzle 66** – the empty poset can't be given a monoidal structure since there is no element to be \\(I\\).`

You're not wrong! Somehow the empty case is somewhat dissatisfying, however. Shall we pose the natural follow-up question, then, about whether any non-empty posets exist that can't be given a monoidal structure?

`You're not wrong! Somehow the empty case is somewhat dissatisfying, however. Shall we pose the natural follow-up question, then, about whether any non-empty posets exist that can't be given a monoidal structure?`

Okay... I see how to adapt your refutation of my attempted counter example into a proof that you've found one!

TheoremJonathan Castello's "bowtie" poset

cannothave a monoidal preorder associated with it.Proof.We first observe that if the bowtie can have a monoid preorder associated with it, there must be

someelement that is the identity \(I\) for that monoid.There are two cases to consider: \(I \in \{a,b\}\) and \(I \in \{c,d\}\).

In order to prove the theorem, we must prove both are infeasible.

By symmetry we only have to consider where \(I = a\) or \(I = c\).

First case: Suppose \(I = a\).Since \(c \leq a\) and \(d \leq d\) then \(c \otimes d \leq a \otimes d\). But since \(a \otimes d = d\), then \(c \otimes d \leq d\). But by construction of the bowtie diagram:

$$\forall x. x \leq d \implies x = d$$ ...thus \(c \otimes d = d\).

However, since \(c \leq c\) and \(d \leq a \) we have \(c \otimes d \leq c \otimes a\). But we know \(c \otimes a = c\) and \(\forall x. x \leq c \implies x = c\), hence \(c \otimes d = c\).

But then \(c = d\) ⚡️

Second case: Suppose \(I = c\).Since \(c \leq a\) and \(b \leq b\) then \(c \otimes b \leq a \otimes b\), and hence \(b \leq a \otimes b\). But then \(a \otimes b = b\) by construction.

Moreover seince \(a \leq a\) and \(c \leq b\) then \(a \leq a \otimes b\), hence \(a = a \otimes b\).

And thus \(a = b\) ⚡️

\(\Box\)

`> Shall we pose the natural follow-up question, then, about whether any non-empty posets exist that can't be given a monoidal structure? Okay... I see how to adapt your refutation of my attempted counter example into a proof that you've found one! **Theorem** Jonathan Castello's "bowtie" poset *cannot* have a monoidal preorder associated with it. ![](https://i.imgur.com/Km2PosD.png) **Proof.** We first observe that if the bowtie can have a monoid preorder associated with it, there must be *some* element that is the identity \\(I\\) for that monoid. There are two cases to consider: \\(I \in \\{a,b\\}\\) and \\(I \in \\{c,d\\}\\). In order to prove the theorem, we must prove both are infeasible. By symmetry we only have to consider where \\(I = a\\) or \\(I = c\\). *First case*: Suppose \\(I = a\\). Since \\(c \leq a\\) and \\(d \leq d\\) then \\(c \otimes d \leq a \otimes d\\). But since \\(a \otimes d = d\\), then \\(c \otimes d \leq d\\). But by construction of the bowtie diagram: $$\forall x. x \leq d \implies x = d$$ ...thus \\(c \otimes d = d\\). However, since \\(c \leq c\\) and \\(d \leq a \\) we have \\(c \otimes d \leq c \otimes a\\). But we know \\(c \otimes a = c\\) and \\(\forall x. x \leq c \implies x = c\\), hence \\(c \otimes d = c\\). But then \\(c = d\\) ⚡️ *Second case*: Suppose \\(I = c\\). Since \\(c \leq a\\) and \\(b \leq b\\) then \\(c \otimes b \leq a \otimes b\\), and hence \\(b \leq a \otimes b\\). But then \\(a \otimes b = b\\) by construction. Moreover seince \\(a \leq a\\) and \\(c \leq b\\) then \\(a \leq a \otimes b\\), hence \\(a = a \otimes b\\). And thus \\(a = b\\) ⚡️ \\(\Box\\)`

@Jonathan – let's take a look at your minimal-poset-that-isn't-a-semilattice above.

suppose it has a monoidal structure that respects the order, with \(d\) as the unit \(I\).

then \(a\otimes b \ge a\otimes d = a\otimes I = a\)

and \(a\otimes b \ge d\otimes b = I\otimes b = b\)

this is a contradiction, since \(a\) and \(b\) do not have a common upper bound

similar arguments show the unit can't be \(a\), \(b\) or \(c\) either.

so there is no monoidal structure that respects the ordering – QED

`@Jonathan – let's take a look at your minimal-poset-that-isn't-a-semilattice above. suppose it has a monoidal structure that respects the order, with \\(d\\) as the unit \\(I\\). then \\(a\otimes b \ge a\otimes d = a\otimes I = a\\) and \\(a\otimes b \ge d\otimes b = I\otimes b = b\\) this is a contradiction, since \\(a\\) and \\(b\\) do not have a common upper bound similar arguments show the unit can't be \\(a\\), \\(b\\) or \\(c\\) either. so there is no monoidal structure that respects the ordering – QED`

@Matthew Doty, @Anindya Bhattacharyya: beautiful! One can make your argument even slightly more elegant by noting that it's enough to consider the case \(I=d\); the other cases are not only similar, but reduce to this one by symmetry! You've already noted this for \(I=c\), but it also applies to \(I=a\) and \(I=b\) if you turn the poset upside down: if the given poset had a monoidal structure with \(a\) as the unit, then the same monoidal structure would work for the upside-down poset. But now one of the two maximal elements would be the unit.

Here's one more nut to crack:

Puzzle TF1.Suppose that \(X\) is a monoid equipped with a preorder \(\leq\) obeying:$$ x\leq x' \textrm{ implies } x\otimes y\leq x'\otimes y.$$ Does this make \(X\) into a monoidal preorder?

`@Matthew Doty, @Anindya Bhattacharyya: beautiful! One can make your argument even slightly more elegant by noting that it's enough to consider the case \\(I=d\\); the other cases are not only similar, but reduce to this one by symmetry! You've already noted this for \\(I=c\\), but it also applies to \\(I=a\\) and \\(I=b\\) if you turn the poset upside down: if the given poset had a monoidal structure with \\(a\\) as the unit, then the same monoidal structure would work for the upside-down poset. But now one of the two maximal elements would be the unit. Here's one more nut to crack: **Puzzle TF1.** Suppose that \\(X\\) is a monoid equipped with a preorder \\(\leq\\) obeying: $$ x\leq x' \textrm{ implies } x\otimes y\leq x'\otimes y.$$ Does this make \\(X\\) into a monoidal preorder?`

Hi, Tobias! I've renamed your puzzle TF1. Only I get to create puzzles named solely by natural numbers. This is not because I'm dictatorial - it's because for a while people started creating puzzles that I didn't notice, and the numbering scheme became confused!

I am very happy you're here. I really think it's great that people are not only solving puzzles, but posing their own. People can learn a lot in a "teaching/learning ecosystem" like this.

`Hi, Tobias! I've renamed your puzzle TF1. Only I get to create puzzles named solely by natural numbers. This is not because I'm dictatorial - it's because for a while people started creating puzzles that I didn't notice, and the numbering scheme became confused! I am very happy you're here. I really think it's great that people are not only solving puzzles, but posing their own. People can learn a lot in a "teaching/learning ecosystem" like this.`

Okay, thanks! By the way, my puzzle TF1 is harder than it may seem.

`Okay, thanks! By the way, my puzzle TF1 is harder than it may seem.`

Beautiful proofs! I'm glad my hunch was on the right track :D

I don't think

Puzzle TF1has a positive answer in general. It works out if \(\otimes\) is commutative, in which case it progresses almost exactly as my answer to Puzzle 60. We could also make it work if we get both left-multiplication and right-multiplication, since we'd just pick the side to multiply on, exactly as in my answer to Puzzle 60. But not every monoid has to be commutative, so it seems unlikely that this would be a sufficient condition in general.`Beautiful proofs! I'm glad my hunch was on the right track :D I don't think **Puzzle TF1** has a positive answer in general. It works out if \\(\otimes\\) is commutative, in which case it progresses almost exactly as my answer to Puzzle 60. We could also make it work if we get both left-multiplication and right-multiplication, since we'd just pick the side to multiply on, exactly as in my answer to Puzzle 60. But not every monoid has to be commutative, so it seems unlikely that this would be a sufficient condition in general.`

Well, this didn't pan out, but perhaps it will help someone else thinking about

TF1. But I guess it counts forPuzzle 63!Consider the lexicographical order on the free monoid over a ordered alphabet \(\Sigma\). (This is the set of all words, or finite sequences, that can be put together using elements of the alphabet.) This is not a commutative monoid, as \(abc\) is a different word from \(cba\). Prefixes dominate in the lexicographical order, so appending a common suffix will not change how two words are ordered -- thus we have right-multiplication. We

alsohave left-multiplication, since prepending a common prefix also has no effect on the ordering. So we can clearly have a monoidal preorder without requiring commutativity.(It seems clear that requiring multiplication on both sides to preserve the order is equivalent to requiring \((x, x') \le (y, y') \implies x \otimes y \le x' \otimes y'\).) (

EDIT:Got this slightly backwards; fixed in #20.)`Well, this didn't pan out, but perhaps it will help someone else thinking about **TF1**. But I guess it counts for **Puzzle 63**! Consider the lexicographical order on the free monoid over a ordered alphabet \\(\Sigma\\). (This is the set of all words, or finite sequences, that can be put together using elements of the alphabet.) This is not a commutative monoid, as \\(abc\\) is a different word from \\(cba\\). Prefixes dominate in the lexicographical order, so appending a common suffix will not change how two words are ordered -- thus we have right-multiplication. We _also_ have left-multiplication, since prepending a common prefix also has no effect on the ordering. So we can clearly have a monoidal preorder without requiring commutativity. (It seems clear that requiring multiplication on both sides to preserve the order is equivalent to requiring \\((x, x') \le (y, y') \implies x \otimes y \le x' \otimes y'\\).) (**EDIT:** Got this slightly backwards; fixed in #20.)`

@Jonathan:

Right! If \(x\leq x'\) and \(y\leq y'\), then we get \(x\otimes y\leq x\otimes y'\leq x'\otimes y'\), which means that it's enough to postulate each one of these two inequalities separately. So indeed the answer to my puzzle is 'yes' in the commutative case for exactly this reason.

Concerning the noncommutative case, I also like your new hunch ;)

`@Jonathan: > (It seems clear that requiring multiplication on both sides to preserve the order is equivalent to requiring \\((x, x') \le (y, y') \implies x \otimes y \le x' \otimes y'\\). Right! If \\(x\leq x'\\) and \\(y\leq y'\\), then we get \\(x\otimes y\leq x\otimes y'\leq x'\otimes y'\\), which means that it's enough to postulate each one of these two inequalities separately. So indeed the answer to my puzzle is 'yes' in the commutative case for exactly this reason. Concerning the noncommutative case, I also like your new hunch ;)`

It looks like I got my product construction a bit backwards -- the proper relation should be \((x, y) \le (x', y') \implies x \otimes y \le x' \otimes y'\). This should have been obvious to me before I posted, since tensor product and cartesian product are closely related (e.g. in the theory of multilinear maps).

`It looks like I got my product construction a bit backwards -- the proper relation should be \\((x, y) \le (x', y') \implies x \otimes y \le x' \otimes y'\\). This should have been obvious to me before I posted, since tensor product and cartesian product are closely related (e.g. in the theory of [multilinear maps](https://en.wikipedia.org/wiki/Multilinear_map#Relation_to_tensor_products)).`

@Matthew and @Anindya

I follow that making one of the elements the identity of the monoid leads to a contradiction but having hard time thinking about it intuitively. It seems like if you make \(a=I\) then c=d and the poset collapses into a preorder with no monoidal product since \((c \otimes d) \leq (a \otimes I) = c \leq a\). Is this right?

What about the poset is making it so that it can't have a monodical product? Can we add or remove elements or arrows to make it possible?

Sorry for being slow...

`@Matthew and @Anindya I follow that making one of the elements the identity of the monoid leads to a contradiction but having hard time thinking about it intuitively. It seems like if you make \\(a=I\\) then c=d and the poset collapses into a preorder with no monoidal product since \\((c \otimes d) \leq (a \otimes I) = c \leq a\\). Is this right? What about the poset is making it so that it can't have a monodical product? Can we add or remove elements or arrows to make it possible? Sorry for being slow...`

I am not sure. If I really knew the theory well, I would have solved Tobias' puzzle by now.

In this particular case, if we added an element \(\top\) above \(a\) and \(b\), we would have a join-semi-lattice and we could use \(\langle \top, \vee \rangle\) for the monoid structure. In category theory, we call \(\top\) an

terminal object. In lattice theory it's called thetopormaximum.We could also add a bottom element \(\bot\), and get a

meet-semi-latticefor Jonathon's bowtie. Bottom elements are also called minimal elements. Category theory calls bottom elementsinitial objects.Furthermore, if we make \(b\leq a\), then \(a\) would be an end and the structure would be a join-semi-lattice. We could then use \(\langle a, \vee\rangle\) as the monoid.

`> What about the poset is making it so that it can't have a monodical product? I am not sure. If I really knew the theory well, I would have solved Tobias' puzzle by now. > Can we add or remove elements or arrows to make it possible? In this particular case, if we added an element \\(\top\\) above \\(a\\) and \\(b\\), we would have a [join-semi-lattice](https://en.wikipedia.org/wiki/Semilattice) and we could use \\(\langle \top, \vee \rangle\\) for the monoid structure. In category theory, we call \\(\top\\) an *terminal object*. In lattice theory it's called the *top* or *maximum*. We could also add a bottom element \\(\bot\\), and get a *meet-semi-lattice* for Jonathon's bowtie. Bottom elements are also called minimal elements. Category theory calls bottom elements *initial objects*. Furthermore, if we make \\(b\leq a\\), then \\(a\\) would be an end and the structure would be a join-semi-lattice. We could then use \\(\langle a, \vee\rangle\\) as the monoid.`

@Matthew: it's true that an

endin category theory is a terminal object, but it's a very very special type of terminal object in a very particular category! Generally,'end' is not a synonym of 'terminal object'. Likewise, 'coend' is not a synonym of 'initial object'. So in the case of your poset, you should sayterminal objectortop element. Probably John can explain all of this better.`@Matthew: it's true that an *end* in category theory is a terminal object, but it's a very very special type of terminal object in a very particular category! Generally, **'end' is not a synonym of 'terminal object'**. Likewise, 'coend' is not a synonym of 'initial object'. So in the case of your poset, you should say *terminal object* or *top element*. Probably John can explain all of this better.`

@Michael – re "what about the poset is making it so that it can't have a monodical product?"...

• if a finite non-empty poset is

discrete, we can make it monoidal by slapping any old monoid structure on it (eg turn it into a cyclic group) – since \(x\leq y \iff x = y\) this monoid automatically respects the partial order• if a poset has

all finite joins, we can make it monoidal by choosing the bottom element (ie the join of nothing!) to be the unit and the binary join \(x\vee y\) to be the monoidal product• if a poset has

all finite meets, we can make it monoidal by choosing the top element (ie the meet of nothing!) to be the unit and the binary meet \(x\wedge y\) to be the monoidal productSo if a finite non-empty poset

can'tbe monoidal, then we know it can't be discrete, or have all finite joins, or have all finite meets.Jonathan's "bow tie" poset is just the smallest poset abiding by all three of these conditions.

`@Michael – re "what about the poset is making it so that it can't have a monodical product?"... • if a finite non-empty poset is *discrete*, we can make it monoidal by slapping any old monoid structure on it (eg turn it into a cyclic group) – since \\(x\leq y \iff x = y\\) this monoid automatically respects the partial order • if a poset has *all finite joins*, we can make it monoidal by choosing the bottom element (ie the join of nothing!) to be the unit and the binary join \\(x\vee y\\) to be the monoidal product • if a poset has *all finite meets*, we can make it monoidal by choosing the top element (ie the meet of nothing!) to be the unit and the binary meet \\(x\wedge y\\) to be the monoidal product So if a finite non-empty poset *can't* be monoidal, then we know it can't be discrete, or have all finite joins, or have all finite meets. Jonathan's "bow tie" poset is just the smallest poset abiding by all three of these conditions.`

@Michael – re your first question, we're assuming here that \(a, b, c, d\) are all mutually distinct (there's no "collapsing" going on).

If you set \(a = I\) then you can prove that \(c\otimes d \leq c\) and \(c\otimes d \leq d\).

But that means \(c\otimes d\) is a common lower bound of \(c\) and \(d\) – and no such lower bound exists.

Intuitively I think the best way of looking at this is that the partial order is too irregular to admit a monoidal structure: \(a\) and \(b\) don't have a join, \(c\) and \(d\) don't have a meet, there is no top element, nor is there a bottom one... basically \(\leq\) is too badly behaved for any \(\otimes\) operation to respect it.

`@Michael – re your first question, we're assuming here that \\(a, b, c, d\\) are all mutually distinct (there's no "collapsing" going on). If you set \\(a = I\\) then you can prove that \\(c\otimes d \leq c\\) and \\(c\otimes d \leq d\\). But that means \\(c\otimes d\\) is a common lower bound of \\(c\\) and \\(d\\) – and no such lower bound exists. Intuitively I think the best way of looking at this is that the partial order is too irregular to admit a monoidal structure: \\(a\\) and \\(b\\) don't have a join, \\(c\\) and \\(d\\) don't have a meet, there is no top element, nor is there a bottom one... basically \\(\leq\\) is too badly behaved for any \\(\otimes\\) operation to respect it.`

@Tobias – I think I might have an answer to your

Puzzle TF1... (it's an adaptation of @Jonathan's attempt at #18)Let's consider the set of words on an alphabet (including the empty word). This is a monoid by string concatenation.

We will define an A-word to be any word beginning with the letter A.

Consider the following rather ungainly preorder. Every word is \(\leq\) itself. But we also have the rule that any A-word is \(\geq\) any other word (whether it is an A-word or not). So the preorder is mostly discrete, except with all the A-words lumped together and sitting on top, so to speak.

Now we can check that \(x\leq x' \Rightarrow x\otimes y\leq x'\otimes y\) – the only non-trivial case is when \(x'\) is an A-word, in which case \(x'\otimes y\) is an A-word too.

But we do

nothave \(y\leq y' \Rightarrow x\otimes y\leq x\otimes y'\) – consider the case when \(y'\) is an A-word, but \(x\) is not (eg B \(\leq\) A but CB \(\nleq\) CA).So your "one-sided" condition is

notenough to obtain a monoidal preorder in general.`@Tobias – I think I might have an answer to your **Puzzle TF1**... (it's an adaptation of @Jonathan's attempt at #18) Let's consider the set of words on an alphabet (including the empty word). This is a monoid by string concatenation. We will define an A-word to be any word beginning with the letter A. Consider the following rather ungainly preorder. Every word is \\(\leq\\) itself. But we also have the rule that any A-word is \\(\geq\\) any other word (whether it is an A-word or not). So the preorder is mostly discrete, except with all the A-words lumped together and sitting on top, so to speak. Now we can check that \\(x\leq x' \Rightarrow x\otimes y\leq x'\otimes y\\) – the only non-trivial case is when \\(x'\\) is an A-word, in which case \\(x'\otimes y\\) is an A-word too. But we do *not* have \\(y\leq y' \Rightarrow x\otimes y\leq x\otimes y'\\) – consider the case when \\(y'\\) is an A-word, but \\(x\\) is not (eg B \\(\leq\\) A but CB \\(\nleq\\) CA). So your "one-sided" condition is *not* enough to obtain a monoidal preorder in general.`

@Tobias - I have edited my post. Thank you for the correction!

`@Tobias - I have edited my post. Thank you for the correction!`

I'm imagining @Anindya's counterexample like a stubby jellyfish -- a big blob at the top with some bits hanging down that are incomparable with everything except the blob.

Left-multiplication fails incredibly easily in this order. If \(x\) is not an A-word, and \(y \le y'\) are distinct in any way, then prepending \(x\) necessarily makes \(x \otimes y\) and \(x \otimes y'\) incomparable. For the same reason, right-multiplication easily preserves the order: it doesn't touch the first letter, so there's no chance of it disturbing the order.

`I'm imagining [@Anindya](https://forum.azimuthproject.org/profile/1950/Anindya%20Bhattacharyya)'s counterexample like a stubby jellyfish -- a big blob at the top with some bits hanging down that are incomparable with everything except the blob. Left-multiplication fails incredibly easily in this order. If \\(x\\) is not an A-word, and \\(y \le y'\\) are distinct in any way, then prepending \\(x\\) necessarily makes \\(x \otimes y\\) and \\(x \otimes y'\\) incomparable. For the same reason, right-multiplication easily preserves the order: it doesn't touch the first letter, so there's no chance of it disturbing the order.`

@Anindya: that's awesome! (To use an A-word, as they're the best of all words.)

I like that your example is really simple at the core, since it's enough to work with only four of those words, let's say \(A\), \(B\), \(C\) and the empty word; since you only care about the first letter anyway, we can define multiplication by just keeping the first letter, so that e.g. \(C\otimes A = C\). This is much simpler than my own solution!

Here's my own solution. Take any poset \(P\) with a nontrivial order; for example, \(P = \{0,1\}\) with \( 0\leq 1\) will do just fine. Now consider the set of all maps \( P \to P\). It's a monoid under composition: a function \(f : P \to P\) and a function \( g : P \to P \) multiply to \( g\circ f : P \to P\), which is the function given by \( (g\circ f)(x) := g(f(x))\). We can also equip this monoid with the pointwise order, which means that we write \( f\leq g\) whenever \( f(x) \leq g(x) \) in \(P\) for all \(x\). It's easy to see that if \( f\leq f'\), then also \( f\circ g \leq f'\circ g\) for any \( g\). However, in general we cannot expect \(g\leq g'\) to imply \( f\circ g\leq f\circ g'\), since \(f\) may even reverse some of the order relations! Concretely, choose some \(y,y'\in P\) with \(y\leq y'\) and \(y'\not\leq y\), and take \(g\) to be the constant function that maps every element to \(y\), and let likewise \(g'\) take everything to \(y'\). And now choose any \(f\) with \(f(y) = y'\) and \(f(y') = y\). Voilà!

`@Anindya: that's awesome! (To use an A-word, as they're the best of all words.) I like that your example is really simple at the core, since it's enough to work with only four of those words, let's say \\(A\\), \\(B\\), \\(C\\) and the empty word; since you only care about the first letter anyway, we can define multiplication by just keeping the first letter, so that e.g. \\(C\otimes A = C\\). This is much simpler than my own solution! Here's my own solution. Take any poset \\(P\\) with a nontrivial order; for example, \\(P = \\{0,1\\}\\) with \\( 0\leq 1\\) will do just fine. Now consider the set of all maps \\( P \to P\\). It's a monoid under composition: a function \\(f : P \to P\\) and a function \\( g : P \to P \\) multiply to \\( g\circ f : P \to P\\), which is the function given by \\( (g\circ f)(x) := g(f(x))\\). We can also equip this monoid with the pointwise order, which means that we write \\( f\leq g\\) whenever \\( f(x) \leq g(x) \\) in \\(P\\) for all \\(x\\). It's easy to see that if \\( f\leq f'\\), then also \\( f\circ g \leq f'\circ g\\) for any \\( g\\). However, in general we cannot expect \\(g\leq g'\\) to imply \\( f\circ g\leq f\circ g'\\), since \\(f\\) may even reverse some of the order relations! Concretely, choose some \\(y,y'\in P\\) with \\(y\leq y'\\) and \\(y'\not\leq y\\), and take \\(g\\) to be the constant function that maps every element to \\(y\\), and let likewise \\(g'\\) take everything to \\(y'\\). And now choose any \\(f\\) with \\(f(y) = y'\\) and \\(f(y') = y\\). Voilà!`

One interesting thing about the bowtie is that it seems to have a lot of internal symmetry. We can swap \(a\) and \(b\), swap \(c\) and \(d\), or even take the opposite of the relation while simultaneously swapping \(a\) with \(c\) and \(b\) with \(d\). I wonder if there's a connection between the number/kind of automoprphisms and isomorphisms a poset has, and whether or not it can support a monoidal structure. I suspect there might be, if only because each isomorphism should restrict any monoidal structure. (I wish I knew some Galois theory!)

`One interesting thing about the bowtie is that it seems to have a lot of internal symmetry. We can swap \\(a\\) and \\(b\\), swap \\(c\\) and \\(d\\), or even take the opposite of the relation while simultaneously swapping \\(a\\) with \\(c\\) and \\(b\\) with \\(d\\). I wonder if there's a connection between the number/kind of automoprphisms and isomorphisms a poset has, and whether or not it can support a monoidal structure. I suspect there might be, if only because each isomorphism should restrict any monoidal structure. (I wish I knew some Galois theory!)`

@Tobias, I also attempted to quotient Anindya's counterexample to that three-element monoid, but I think it loses something. Here's a picture of what we're dealing with, and a multiplication table:

Here, we have that \(b \le a\), as well as \(b = b \otimes b = b \otimes a = b\), so the counterexample fails. This is because we've identified all of the non-A words into a single class, thereby making them comparable when they weren't before. We might be able to get away with this if we added another element, \(b'\), so that \(b \otimes a = b'\).

`[@Tobias](https://forum.azimuthproject.org/profile/2235/Tobias%20Fritz), I also attempted to quotient Anindya's counterexample to that three-element monoid, but I think it loses something. Here's a picture of what we're dealing with, and a multiplication table: ![](https://i.imgur.com/VzVPhYj.png) <pre> |Iab -+--- I|Iab a|aaa b|bbb </pre> Here, we have that \\(b \le a\\), as well as \\(b = b \otimes b = b \otimes a = b\\), so the counterexample fails. This is because we've identified all of the non-A words into a single class, thereby making them comparable when they weren't before. We might be able to get away with this if we added another element, \\(b'\\), so that \\(b \otimes a = b'\\).`

@Jonathan: you're too fast ;) You're right, I was being sloppy, but I've fixed my comment now. It can be reduced to a four-element monoid.

`@Jonathan: you're too fast ;) You're right, I was being sloppy, but I've fixed my comment now. It can be reduced to a four-element monoid.`

Hah, I'm only fast because I was so convinced myself that the 3-element monoid sufficed that I put together a diagram and everything, only to convince myself at the last second that I was wrong. I only had to copy back the stuff I had already written. ;)

I just looked at your own counterexample, and it's quite nice! It's interesting to consider that the four-element monoid we've been alluding to is just a particular instance of your function-based construction, since we can model \(\{A, B, C, \varepsilon\}\) as a

left actionon itself. We get that \(A\), \(B\) and \(C\) are just constant functions; their corresponding right actions are just the identity function, which trivially preserves the order.`Hah, I'm only fast because I was so convinced myself that the 3-element monoid sufficed that I put together a diagram and everything, only to convince myself at the last second that I was wrong. I only had to copy back the stuff I had already written. ;) I just looked at your own counterexample, and it's quite nice! It's interesting to consider that the four-element monoid we've been alluding to is just a particular instance of your function-based construction, since we can model \\(\\{A, B, C, \varepsilon\\}\\) as a _[left action](https://en.wikipedia.org/wiki/Semigroup_action)_ on itself. We get that \\(A\\), \\(B\\) and \\(C\\) are just constant functions; their corresponding right actions are just the identity function, which trivially preserves the order.`

Anindya wrote:

There's probably something to this, but let's not fool anyone into thinking every monoidal preorder needs to have \(\otimes\) be the join or meet! Think of six counterexamples.

`Anindya wrote: > Intuitively I think the best way of looking at this is that the partial order is too irregular to admit a monoidal structure: \\(a\\) and \\(b\\) don't have a join, \\(c\\) and \\(d\\) don't have a meet, there is no top element, nor is there a bottom one... basically \\(\leq\\) is too badly behaved for any \\(\otimes\\) operation to respect it. There's probably something to this, but let's not fool anyone into thinking every monoidal preorder needs to have \\(\otimes\\) be the join or meet! Think of six counterexamples.`

So, I suspect you already know this, but you have just illustrated the Cayley embedding for monoids!

Rivas talks about this in his

Notions of Computation as Monoids(2014).That paper is awesome. Did you know you can use Cayley embedding to reduce the complexity of

`foldl (<>) mempty`

from \(\mathcal{O}(n^2)\) for`[[a]]`

to \(\mathcal{O}(n)\) (for isomorphic input)?`> I just looked at your own counterexample, and it's quite nice! It's interesting to consider that the four-element monoid we've been alluding to is just a particular instance of your function-based construction, since we can model \\(\\{A, B, C, \varepsilon\\}\\) as a _[left action](https://en.wikipedia.org/wiki/Semigroup_action)_ on itself. We get that \\(A\\), \\(B\\) and \\(C\\) are just constant functions; their corresponding right actions are just the identity function, which trivially preserves the order. So, I suspect you already know this, but you have just illustrated the [Cayley embedding](https://en.wikipedia.org/wiki/Cayley%27s_theorem) for monoids! Rivas talks about this in his [*Notions of Computation as Monoids* (2014)](https://arxiv.org/pdf/1406.4823.pdf). That paper is awesome. Did you know you can use Cayley embedding to reduce the complexity of `foldl (<>) mempty` from \\(\mathcal{O}(n^2)\\) for `[[a]]` to \\(\mathcal{O}(n)\\) (for isomorphic input)?`

I've not seen Rivas' paper -- I'll have to read it! But yes, I'm familiar with the Cayley embedding from my undergraduate abstract algebra class ^_^

I suspect the monoidal preorder compatibility condition can be rephrased in terms of the left and right actions of the monoid. Something like, \(x \le y \implies L_z(x) \le L_z(y)\) and \(x \le y \implies R_z(x) \le R_z(y)\) for all \(z\). So the left and right actions for all elements have to be monotone maps.

Does that complexity reduction have anything to do with difference lists?

`I've not seen Rivas' paper -- I'll have to read it! But yes, I'm familiar with the Cayley embedding from my undergraduate abstract algebra class ^_^ I suspect the monoidal preorder compatibility condition can be rephrased in terms of the left and right actions of the monoid. Something like, \\(x \le y \implies L_z(x) \le L_z(y)\\) and \\(x \le y \implies R_z(x) \le R_z(y)\\) for all \\(z\\). So the left and right actions for all elements have to be monotone maps. Does that complexity reduction have anything to do with [difference lists](https://stackoverflow.com/questions/13879260/why-are-difference-lists-more-efficient-than-regular-concatenation)?`

I agree. It appears we can say \(\langle \leq, \otimes, I \rangle\) is a monoidal preorder if and only if

$$ x \leq y \Longleftrightarrow \forall z. L_z(x) \leq L_z(y) \text{ and } R_z(x) \leq R_z(y) $$

Exactly!

Difference lists are precisely

left actionson lists.Here's a little implementation:

But it's not a complete implementation ;-)

Puzzle MD1: Give the instance of`Monoid`

for`DList a`

, ie replace the`undefined`

s below:Remember that we want to obey the laws:

$$ \begin{align} (\texttt{toDList}\, a)\ ⬦\ (\texttt{toDList}\, b) & \equiv \texttt{toDList}\, (a ⧺ b) \\ (\texttt{fromDList}\, a) ⧺ (\texttt{fromDList}\, b) & \equiv \texttt{fromDList}\, (a\ ⬦\ b) \\ \\ \texttt{fromDList}\, \texttt{mempty} & \equiv [] \\ \texttt{mempty} & \equiv \texttt{toDList}\, [] \\ \end{align} $$

`> I suspect the monoidal preorder compatibility condition can be rephrased in terms of the left and right actions of the monoid. Something like, \\(x \le y \implies L_z(x) \le L_z(y)\\) and \\(x \le y \implies R_z(x) \le R_z(y)\\) for all \\(z\\). So the left and right actions for all elements have to be monotone maps. I agree. It appears we can say \\(\langle \leq, \otimes, I \rangle\\) is a monoidal preorder if and only if $$ x \leq y \Longleftrightarrow \forall z. L_z(x) \leq L_z(y) \text{ and } R_z(x) \leq R_z(y) $$ > Does that complexity reduction have anything to do with difference lists? Exactly! Difference lists are precisely *left actions* on lists. Here's a little implementation: <pre> newtype DList a = DList ([a] -> [a]) toDList :: [a] -> DList a toDList xs = DList (xs ++) fromDList :: DList a -> [a] fromDList (DList leftAction) = leftAction [] </pre> But it's not a complete implementation ;-) **Puzzle MD1**: Give the instance of `Monoid` for `DList a`, ie replace the `undefined`s below: <pre> instance Monoid (DList a) where (<>) = undefined mempty = undefined </pre> Remember that we want to obey the laws: $$ \begin{align} (\texttt{toDList}\, a)\ ⬦\ (\texttt{toDList}\, b) & \equiv \texttt{toDList}\, (a ⧺ b) \\\\ (\texttt{fromDList}\, a) ⧺ (\texttt{fromDList}\, b) & \equiv \texttt{fromDList}\, (a\ ⬦\ b) \\\\ \\\\ \texttt{fromDList}\, \texttt{mempty} & \equiv [] \\\\ \texttt{mempty} & \equiv \texttt{toDList}\, [] \\\\ \end{align} $$`

For us non-Haskellers (I'm a Schemer), what's a difference list?

`For us non-Haskellers (I'm a Schemer), what's a difference list?`

I already know the answer to

MD1, so I'll let it sit for a while :)@Keith, a difference list is what you get when you partially apply

`append`

to one argument. Essentially:Defining

`append`

and`empty`

for difference lists, as inPuzzle MD1, is what makes difference lists interesting.`I already know the answer to **MD1**, so I'll let it sit for a while :) [@Keith](https://forum.azimuthproject.org/profile/2009/Keith%20E.%20Peterson), a difference list is what you get when you partially apply `append` to one argument. Essentially: <pre> (define (dlist xs) (lambda (ys) (append xs ys))) </pre> <pre> > ((dlist '(1 2 3)) '(4 5)) '(1 2 3 4 5) </pre> Defining `append` and `empty` for difference lists, as in **Puzzle MD1**, is what makes difference lists interesting.`

@Keith - The reason for doing the unevaluated function indirection in difference lists is that

`(reduce append lol)`

takes \(\mathcal{O}(n^2)\) time. Joel Spolsky dubbed thisShlemiel the painter’s algorithminBack to the Basics(2001).It's a minor optimization - Jeff Atwood wrote a reply of sorts to Joel in

The Sad Tragedy of Micro-Optimization Theater(2009) where he observed for real world applications worrying about difference lists never matters. Despite Jeff's protests, however, I feel like this sort of thing is still fodder for Google interviews.`@Keith - The reason for doing the unevaluated function indirection in difference lists is that `(reduce append lol)` takes \\(\mathcal{O}(n^2)\\) time. Joel Spolsky dubbed this *Shlemiel the painter’s algorithm* in [*Back to the Basics* (2001)](https://www.joelonsoftware.com/2001/12/11/back-to-basics/). It's a minor optimization - Jeff Atwood wrote a reply of sorts to Joel in [*The Sad Tragedy of Micro-Optimization Theater* (2009)](https://blog.codinghorror.com/the-sad-tragedy-of-micro-optimization-theater/) where he observed for real world applications worrying about difference lists never matters. Despite Jeff's protests, however, I feel like this sort of thing is still fodder for Google interviews.`

Oho. Recall the symmetries I mentioned in #30 -- these are just automorphisms on the given preorder.

Say we have a monoidal preorder \(\langle P, \le, \otimes, 1 \rangle\) and an automorphism \(A\) on the underlying preorder \(P'\) of \(P\), and define \(x \otimes_A y\) by \(A(A^{-1}(x) \otimes A^{-1}(y))\). Then \(\otimes_A\) also makes \(P'\) a monoidal preorder. It is clear that \(A(1)\) is the new unit, so we just have to show associativity.

Consider \((x \otimes_A y) \otimes_A z\). This expands to the wild mess of \(A(A^{-1}(A(A^{-1}(x) \otimes A^{-1}(y))) \otimes A^{-1}(z))\), which simplifies to \(A(A^{-1}(x)\otimes A^{-1}(y) \otimes A^{-1}(z))\). Similarly for \(x \otimes_A (y \otimes_A z)\). Thus, \(\otimes_A\) is associative.

This is awesome: for every

automorphismon the underlying preorder we get anisomorphismbetween monoidal preorders. This also helps to formalize my hunch from #30: the symmetries of the preorderdohelp to constrain the possible monoidal structures, because if you can findonemonoid, then every of the monoids induced by the automorphisms must also be valid for the preorder.It seems just possible that an automorphism of preorders may also give an automorphism of monoidal preorders, meaning that particular automorphism might not actually give a useful constraint, but I haven't been able to show or deny this. I also haven't considered whether mere isomorphisms between preorders give the same construction; it would be nice, since it would let us use the fact that the bowtie is isomorphic to its dual.

`Oho. Recall the symmetries I mentioned in #30 -- these are just automorphisms on the given preorder. Say we have a monoidal preorder \\(\langle P, \le, \otimes, 1 \rangle\\) and an automorphism \\(A\\) on the underlying preorder \\(P'\\) of \\(P\\), and define \\(x \otimes_A y\\) by \\(A(A^{-1}(x) \otimes A^{-1}(y))\\). Then \\(\otimes_A\\) also makes \\(P'\\) a monoidal preorder. It is clear that \\(A(1)\\) is the new unit, so we just have to show associativity. Consider \\((x \otimes_A y) \otimes_A z\\). This expands to the wild mess of \\(A(A^{-1}(A(A^{-1}(x) \otimes A^{-1}(y))) \otimes A^{-1}(z))\\), which simplifies to \\(A(A^{-1}(x)\otimes A^{-1}(y) \otimes A^{-1}(z))\\). Similarly for \\(x \otimes_A (y \otimes_A z)\\). Thus, \\(\otimes_A\\) is associative. This is awesome: for every _automorphism_ on the underlying preorder we get an _isomorphism_ between monoidal preorders. This also helps to formalize my hunch from #30: the symmetries of the preorder _do_ help to constrain the possible monoidal structures, because if you can find _one_ monoid, then every of the monoids induced by the automorphisms must also be valid for the preorder. It seems just possible that an automorphism of preorders may also give an automorphism of monoidal preorders, meaning that particular automorphism might not actually give a useful constraint, but I haven't been able to show or deny this. I also haven't considered whether mere isomorphisms between preorders give the same construction; it would be nice, since it would let us use the fact that the bowtie is isomorphic to its dual.`

@Tobias – your counterexample is a good deal more natural than mine – I think what's going on here is that given any sets \(Q\) and \(P\), we can "lift" any partial order on \(P\) to a partial order on \(\mathrm{Hom}(Q, P)\) using the pointwise construction. We don't need any kind of order on \(Q\) to do this.

Now the order you're putting on \(\mathrm{Hom}(P, P)\) is just a special case of this. It depends on the order on \(P\)-as-codomain but doesn't care about any order on \(P\)-as-domain. Consequently composition is well-behaved on the left, but not on the right.

Re "since you only care about the first letter anyway, we can define multiplication by just keeping the first letter" – unfortunately I don't think this works. If we throw away the tail of the juxtaposition we no longer have \(B \leq A\) but \(C \otimes B \nleq C \otimes A\), because the latter expression is just \(C\) on both sides. So we do have a monoidal preorder after all, and we don't get the "one-sided" counterexample we're after.

`@Tobias – your counterexample is a good deal more natural than mine – I think what's going on here is that given any sets \\(Q\\) and \\(P\\), we can "lift" any partial order on \\(P\\) to a partial order on \\(\mathrm{Hom}(Q, P)\\) using the pointwise construction. We don't need any kind of order on \\(Q\\) to do this. Now the order you're putting on \\(\mathrm{Hom}(P, P)\\) is just a special case of this. It depends on the order on \\(P\\)-as-codomain but doesn't care about any order on \\(P\\)-as-domain. Consequently composition is well-behaved on the left, but not on the right. Re "since you only care about the first letter anyway, we can define multiplication by just keeping the first letter" – unfortunately I don't think this works. If we throw away the tail of the juxtaposition we no longer have \\(B \leq A\\) but \\(C \otimes B \nleq C \otimes A\\), because the latter expression is just \\(C\\) on both sides. So we do have a monoidal preorder after all, and we don't get the "one-sided" counterexample we're after.`

@Jonathan – I think isomorphisms are enough – if \(Q\) is a preorder isomorphic to \(P\), then we can transplant the monoidal structure on \(P\) onto \(Q\) using the same trick (convert the \(Q\)-elements into \(P\)-elements, multiply them in \(P\), convert back again). The automorphism version (with \(Q = P\)) is just a special case of this.

`@Jonathan – I think isomorphisms are enough – if \\(Q\\) is a preorder isomorphic to \\(P\\), then we can transplant the monoidal structure on \\(P\\) onto \\(Q\\) using the same trick (convert the \\(Q\\)-elements into \\(P\\)-elements, multiply them in \\(P\\), convert back again). The automorphism version (with \\(Q = P\\)) is just a special case of this.`

@John – point taken re "let's not fool anyone into thinking every monoidal preorder needs to have \(\otimes\) be the join or meet" – one of the difficulties I have with monoidal categories is in grasping how we only care about the formal combinatory properties of the monoidal product, and not what it "actually is". So I tend to "reach" for familiar products, eg meet or cartesian or tensor, which can be misleading.

As for some counterexamples...

• Take any monoid (with at least 2 elements) – put the discrete partial order on the underlying set – we now have a (trivial) monoidal preorder where \(\otimes\) is not join or meet (since these operations don't exist).

• Take any non-commutative monoidal preorder, eg words on an alphabet ordered by length, or monotone endomaps on a poset ordered pointwise – the \(\otimes\) cannot be join or meet since it isn't commutative.

• Take the natural numbers and addition with the usual ordering – if \(n, m\) are non-zero then \(n + m\) is neither \(\mathrm{min}(n, m)\) nor \(\mathrm{max}(n, m)\), so here we have a commutative monoidal product where \(\otimes\) is neither join nor meet.

I'm working on a couple more where the \(\otimes\) operation is commutative and idempotent, but isn't join or meet. How "lattice-like" can \(\otimes\) get before it is forced to be a join or meet wrt the underlying preorder?

`@John – point taken re "let's not fool anyone into thinking every monoidal preorder needs to have \\(\otimes\\) be the join or meet" – one of the difficulties I have with monoidal categories is in grasping how we only care about the formal combinatory properties of the monoidal product, and not what it "actually is". So I tend to "reach" for familiar products, eg meet or cartesian or tensor, which can be misleading. As for some counterexamples... • Take any monoid (with at least 2 elements) – put the discrete partial order on the underlying set – we now have a (trivial) monoidal preorder where \\(\otimes\\) is not join or meet (since these operations don't exist). • Take any non-commutative monoidal preorder, eg words on an alphabet ordered by length, or monotone endomaps on a poset ordered pointwise – the \\(\otimes\\) cannot be join or meet since it isn't commutative. • Take the natural numbers and addition with the usual ordering – if \\(n, m\\) are non-zero then \\(n + m\\) is neither \\(\mathrm{min}(n, m)\\) nor \\(\mathrm{max}(n, m)\\), so here we have a commutative monoidal product where \\(\otimes\\) is neither join nor meet. I'm working on a couple more where the \\(\otimes\\) operation is commutative and idempotent, but isn't join or meet. How "lattice-like" can \\(\otimes\\) get before it is forced to be a join or meet wrt the underlying preorder?`

@Anindya wrote:

Here's another one! Let \(X\) be any set with at least two elements, and endow it with the

codiscreteorder where \(x \le y\) for all \(x, y\). Then every monoid on \(X\) gives a monoidal preorder. But certainly,noneof these monoids give a (unique) join or meet. (I'm solidly in the camp that thinks that if there's no unique [least upper / greatest lower] bound, then the join/meet operation shouldn't be considered defined at all.)If we do this same trick with the discrete order, we get your first counterexample, but from a slightly different starting point.

One thing we require of lattices that we don't of arbitrary monoidal preorders is that \(x \le x \vee y\) and \(y \le x \vee y\). Using a monoid where the product is incomparable with at least one of the operands should be sufficient to dodge being a meet or join. (Or heck, try something weird where \(x \le x \otimes y \le y\).)

`[@Anindya](https://forum.azimuthproject.org/profile/1950/Anindya%20Bhattacharyya) wrote: > As for some counterexamples... Here's another one! Let \\(X\\) be any set with at least two elements, and endow it with the _codiscrete_ order where \\(x \le y\\) for all \\(x, y\\). Then every monoid on \\(X\\) gives a monoidal preorder. But certainly, _none_ of these monoids give a (unique) join or meet. (I'm solidly in the camp that thinks that if there's no unique [least upper / greatest lower] bound, then the join/meet operation shouldn't be considered defined at all.) If we do this same trick with the discrete order, we get your first counterexample, but from a slightly different starting point. > How "lattice-like" can ⊗ get before it is forced to be a join or meet wrt the underlying preorder? One thing we require of lattices that we don't of arbitrary monoidal preorders is that \\(x \le x \vee y\\) and \\(y \le x \vee y\\). Using a monoid where the product is incomparable with at least one of the operands should be sufficient to dodge being a meet or join. (Or heck, try something weird where \\(x \le x \otimes y \le y\\).)`

I'm in the opposite camp there, @Jonathan – I'd say joins/meets in preorders are just coproducts/products, and we'd only ever expect them to be defined "up to isomorphism". So I'd draw the opposite conclusion – any monoidal operation on a codiscrete preorder is automatically a join and a meet!

Re your other point, I'm thinking about a monoidal preorder where we can "throw things away", ie \(x \otimes y \leq x\), or equivalently \(y \leq I\) for all \(y\). In this case \(x \otimes y\) is a lower bound of \(x\) and \(y\). And if we can "duplicate things", ie \(z \leq z \otimes z\), then we can prove \(\otimes\) is the meet operation (since any lower bound \(z \leq z \otimes z \leq x \otimes y\)).

But what if we can "dispose" but not "duplicate"? Then \(\otimes\) cannot be meet since it isn't idempotent. My hunch is that the "manufacturing" monoidal preorders would be an example of this, because we can chuck stuff away but not turn one girder into two.

`I'm in the opposite camp there, @Jonathan – I'd say joins/meets in preorders are just coproducts/products, and we'd only ever expect them to be defined "up to isomorphism". So I'd draw the opposite conclusion – any monoidal operation on a codiscrete preorder is automatically a join and a meet! Re your other point, I'm thinking about a monoidal preorder where we can "throw things away", ie \\(x \otimes y \leq x\\), or equivalently \\(y \leq I\\) for all \\(y\\). In this case \\(x \otimes y\\) is a lower bound of \\(x\\) and \\(y\\). And if we can "duplicate things", ie \\(z \leq z \otimes z\\), then we can prove \\(\otimes\\) is the meet operation (since any lower bound \\(z \leq z \otimes z \leq x \otimes y\\)). But what if we can "dispose" but not "duplicate"? Then \\(\otimes\\) cannot be meet since it isn't idempotent. My hunch is that the "manufacturing" monoidal preorders would be an example of this, because we can chuck stuff away but not turn one girder into two.`

@Anindya

From #46:

I don't know if you are a Haskell programmer, but

`Data.Monoid`

has a lot of canonical monoids. It has instances for`[a]`

, endomorphisms,`First a`

and`Last a`

.`First a`

obeys \(\forall x. x \neq I \implies x \otimes y = x\), like you sketch above (but it doesn't have the order you prescribe).There are also some truly awesome machine learning examples in Izbicki's

Algebraic classifiers(2013). Not only does Izbicki demonstrate how to model various popular machine learning algorithms as monoids, but he shows how to leverage monoidal (and group) structure for speeding up \(k\)-fold cross-validation from \(\mathcal{O}(kn)\) to \(\mathcal{O}(k + n)\) (given sufficient cloud computing resources).From #43:

I agree.

This is enough to prove an early hunch of mine in this thread which I later doubted.

Every dense unbounded linear order can be equipped with a monoidal poset.(This is a sort of model theoretic answer to

Puzzle 63.)Proof.In the case of \(\aleph_0\) this is easy enough to see, since it's order-isomorphic by Cantor's theorem to \(\mathbb{Q}\) so we can transfer the monoidal pre-order \(\langle \mathbb{Q}, \leq, +, 0\rangle\) to it.

But by upward Löwenheim-Skolem, for any cardinality \(\kappa\) there is a dense unbounded linear monoidal poset \(\langle D, \leq, +_D, 0\rangle\) which is an elementary extension of \(\langle \mathbb{Q}, \leq, +, 0\rangle\) where \(|D| = \kappa\).

Since the theory of dense linear orders is complete, then that means for any other dense linear poset with \(\kappa\) many elements it must be order isomorphic to \(\langle D, \leq, +_D, 0\rangle\) by some isomorphism \(\phi\). Then we can use Jonathan's idea in #41 along with \(\phi\) to embed \(+_D\).

\(\Box\)

`@Anindya From [#46](https://forum.azimuthproject.org/discussion/comment/18027/#Comment_18027): > point taken re "let's not fool anyone into thinking every monoidal preorder needs to have \\(\otimes\\) be the join or meet" – one of the difficulties I have with monoidal categories is in grasping how we only care about the formal combinatory properties of the monoidal product, and not what it "actually is". So I tend to "reach" for familiar products, eg meet or cartesian or tensor, which can be misleading. I don't know if you are a Haskell programmer, but [`Data.Monoid`](https://hackage.haskell.org/package/base-4.11.1.0/docs/Data-Monoid.html) has a lot of canonical monoids. It has instances for `[a]`, endomorphisms, `First a` and `Last a`. `First a` obeys \\(\forall x. x \neq I \implies x \otimes y = x\\), like you sketch above (but it doesn't have the order you prescribe). There are also some truly awesome machine learning examples in Izbicki's [*Algebraic classifiers* (2013)](http://proceedings.mlr.press/v28/izbicki13.pdf). Not only does Izbicki demonstrate how to model various popular machine learning algorithms as monoids, but he shows how to leverage monoidal (and group) structure for speeding up \\(k\\)-fold cross-validation from \\(\mathcal{O}(kn)\\) to \\(\mathcal{O}(k + n)\\) (given sufficient cloud computing resources). From [#43](https://forum.azimuthproject.org/discussion/comment/18023/#Comment_18023): > @Jonathan – I think isomorphisms are enough – if \\(Q\\) is a preorder isomorphic to \\(P\\), then we can transplant the monoidal structure on \\(P\\) onto \\(Q\\) using the same trick (convert the \\(Q\\)-elements into \\(P\\)-elements, multiply them in \\(P\\), convert back again). The automorphism version (with \\(Q = P\\)) is just a special case of this. I agree. This is enough to prove an early hunch of mine in this thread which I later doubted. *Every dense unbounded linear order can be equipped with a monoidal poset.* (This is a sort of model theoretic answer to **Puzzle 63**.) **Proof**. In the case of \\(\aleph_0\\) this is easy enough to see, since it's order-isomorphic by Cantor's theorem to \\(\mathbb{Q}\\) so we can transfer the monoidal pre-order \\(\langle \mathbb{Q}, \leq, +, 0\rangle\\) to it. But by upward Löwenheim-Skolem, for any cardinality \\(\kappa\\) there is a dense unbounded linear monoidal poset \\(\langle D, \leq, +_D, 0\rangle\\) which is an [elementary extension](https://en.wikipedia.org/wiki/Elementary_equivalence#Elementary_substructures_and_elementary_extensions) of \\(\langle \mathbb{Q}, \leq, +, 0\rangle\\) where \\(|D| = \kappa\\). Since the theory of dense linear orders is complete, then that means for any other dense linear poset with \\(\kappa\\) many elements it must be order isomorphic to \\(\langle D, \leq, +_D, 0\rangle\\) by some isomorphism \\(\phi\\). Then we can use Jonathan's idea in [#41](https://forum.azimuthproject.org/discussion/comment/17997/#Comment_17997) along with \\(\phi\\) to embed \\(+_D\\). \\(\Box\\)`

Anindhya wrote :

Thank you! This made it clearer in my head. So pretty much the preorder needs to have a top or bottom element in order to define a well behaved identity for the monoid.

You also wrote:

What I meant by collapse was this observation which may or may not be valid. Since \(c\otimes d \leq c\) and \(c\otimes d \leq d\), the only way this can be true is if c and d are both identities. Therefore, If you set \(a = I\), then for the bowtie, \(c = d = I\) and the set \(a, b, c, d\) collapses down to \(b, I\). So the contradiction is that a,c,d are not distinct.

Either way thanks for the great explanation.

Edit: Oops I said something completely different when I said collapse in comment 21. I think I got confused trying to understand both Matthew and Anindya's answers at once...

`Anindhya wrote : >• if a finite non-empty poset is *discrete*, we can make it monoidal by slapping any old monoid structure on it (eg turn it into a cyclic group) – since \\(x\leq y \iff x = y\\) this monoid automatically respects the partial order >• if a poset has *all finite joins*, we can make it monoidal by choosing the bottom element (ie the join of nothing!) to be the unit and the binary join \\(x\vee y\\) to be the monoidal product >• if a poset has *all finite meets*, we can make it monoidal by choosing the top element (ie the meet of nothing!) to be the unit and the binary meet \\(x\wedge y\\) to be the monoidal product >Intuitively I think the best way of looking at this is that the partial order is too irregular to admit a monoidal structure: \\(a\\) and \\(b\\) don't have a join, \\(c\\) and \\(d\\) don't have a meet, there is no top element, nor is there a bottom one... basically \\(\leq\\) is too badly behaved for any \\(\otimes\\) operation to respect it. Thank you! This made it clearer in my head. So pretty much the preorder needs to have a top or bottom element in order to define a well behaved identity for the monoid. You also wrote: >we're assuming here that \\(a, b, c, d\\) are all mutually distinct (there's no "collapsing" going on). >If you set \\(a = I\\) then you can prove that \\(c\otimes d \leq c\\) and \\(c\otimes d \leq d\\). What I meant by collapse was this observation which may or may not be valid. Since \\(c\otimes d \leq c\\) and \\(c\otimes d \leq d\\), the only way this can be true is if c and d are both identities. Therefore, If you set \\(a = I\\), then for the bowtie, \\(c = d = I\\) and the set \\(a, b, c, d\\) collapses down to \\(b, I\\). So the contradiction is that a,c,d are not distinct. Either way thanks for the great explanation. Edit: Oops I said something completely different when I said collapse in comment 21. I think I got confused trying to understand both Matthew and Anindya's answers at once...`

Michael wrote:

Hm. I'm not convinced that this is true in general, but my attempted counterexample foundered on associativity. The multiplication on the preorder below is not associative, since

$$c = Ic = (ab)c \ne a(bc) = ab = a.$$

`Michael wrote: > So pretty much the preorder needs to have a top or bottom element in order to define a well behaved identity for the monoid. Hm. I'm not convinced that this is true in general, but my attempted counterexample foundered on associativity. The multiplication on the preorder below is not associative, since $$c = Ic = (ab)c \ne a(bc) = ab = a.$$ <pre> a b \ / I / \ c d |Iabcd -+----- I|Iabcd a|aaIaa b|bIbbb c|ccccI d|dddId </pre>`

Michael Hong:

That's not true. The real numbers form a perfectly fine monoid with addition as the monoid operation. The identity element is 0. The real numbers has no top or bottom element!

Same for the integers, or the rational numbers, or many other examples we'll be interested in.

This is just the confusion I was warning about in Comment 34. If the monoid operation \(\otimes\) in our monoidal preorder is the join, the identity has to be the bottom element... so our preorder needs to have a bottom element. If the monoid operation is the meet, the identity has to be be the top element... so our preorder needs to have a top element. But there's no reason on God's green earth why the monoid operation needs to be the join or meet! And there's no reason a monoidal preorder needs to have a top or bottom element.

`Michael Hong: > So pretty much the preorder needs to have a top or bottom element in order to define a well behaved identity for the monoid. That's not true. The real numbers form a perfectly fine monoid with addition as the monoid operation. The identity element is 0. The real numbers has no top or bottom element! Same for the integers, or the rational numbers, or many other examples we'll be interested in. This is just the confusion I was warning about in [Comment 34](https://forum.azimuthproject.org/discussion/comment/17987/#Comment_17987). If the monoid operation \\(\otimes\\) in our monoidal preorder is the join, the identity has to be the bottom element... so our preorder needs to have a bottom element. If the monoid operation is the meet, the identity has to be be the top element... so our preorder needs to have a top element. But there's no reason on God's green earth why the monoid operation needs to be the join or meet! And there's no reason a monoidal preorder needs to have a top or bottom element.`