2.2: Symmetric Monoidal Preorders

In Section 1.2.2 we introduced preorders. The notation for a preorder, namely (X, ≤), refers to two pieces of structure: a set called X and a relation called ≤ that is reflexive and transitive. We want to add to the concept of preorders a way of combining elements in X, an operation taking two elements and adding or multiplying them together. However, the operation does not have to literally be addition or multiplication; it only needs to satisfy some of the properties one expects from them.

Definition and first examples

We begin with a formal definition of symmetric monoidal preorders.

Definition 2.2: Symmetric Monoidal Structure

A symmetric monoidal structure on a preorder (X, ≤) consists of two constituents:

1. an element I \(\in\) X, called the monoidal unit, and
2. a function ⊗ : X × X → X, called the monoidal product.

These constituents must satisfy the following properties, where we write ⊗(\(x_{1}\), \(x_{2}\)) = \(x_{1}\) ⊗ \(x_{2}\):

1. for all \(x_{1}\), \(x_{2}\), \(y_{1}\), \(y_{2}\) \(\in\) X, if \(x_{1}\) ≤ \(y_{1}\) and \(x_{2}\) ≤ \(y_{2}\), then \(x_{1}\) ⊗ \(x_{2}\) ≤ \(y_{1}\) ⊗ \(y_{2}\),
2. for all x \(\in\) X, the equations I ⊗ x = x and x ⊗ I = x hold,
3. for all x, y, z \(\in\) X, the equation (x ⊗ y) ⊗ z = x ⊗ (y ⊗ z) holds, and
4. for all x, y \(\in\) X, the equation x ⊗ y = y ⊗ x holds.

We call these conditions monotonicity, unitality, associativity, and symmetry respectively.

A preorder equipped with a symmetric monoidal structure, (X, ≤, I, ⊗), is called a symmetric monoidal preorder.

Anyone can propose a set X, an order ≤ on X, an element I in X, and a binary operation ⊗ on X and ask whether (X, ≤, I, ⊗) is a symmetric monoidal preorder. And it will indeed be one, as long as it satisfies rules a, b, c, and d of Definition 2.2.

Remark 2.3. It is often useful to replace = with \(\cong\) throughout Definition 2.2. The result is a perfectly good notion, called a weak monoidal structure. The reason we chose equality is that it makes equations look simpler, which we hope aids first-time readers.

The notation for the monoidal unit and the monoidal product may vary: monoidal units we have seen include I (as in the definition), 0, 1, true, false, {∗}, and more. Monoidal products we have seen include ⊗ (as in the definition), +, ∗, \(\land\), \(\lor\), and ×. The preferred notation in a given setting is whatever best helps our brains remember what we’re trying to do; the names I and ⊗ are just defaults.

Example 2.4.

There is a well-known preorder structure, denoted ≤, on the set \(\mathbb{R}\) of real numbers; e.g. -5 \(\leq\) \(\sqrt{2}\).

We propose 0 as a monoidal unit and +: \(\mathbb{R}\) × \(\mathbb{R}\) → \(\mathbb{R}\) as a monoidal product. Does ( \(\mathbb{R}\), ≤, 0, +) satisfy the conditions of Definition 2.2?

If \(x_{1}\) ≤ \(y_{1}\) and \(x_{2}\) ≤ \(y_{2}\), it is true that \(x_{1}\) + \(x_{2}\) ≤ \(y_{1}\) + \(y_{2}\).

It is also true that 0 + x = x and x + 0 x, that (x + y) + z = x + (y + z), and that x + y = y + x. Thus ( \(\mathbb{R}\), ≤, 0, +) satisfies the conditions of being a symmetric monoidal preorder.

Exercise 2.5.

Consider again the preorder (\(\mathbb{R}\), ≤) from Example 2.4. Someone proposes 1 as a monoidal unit and ∗ (usual multiplication) as a monoidal product. But an expert walks by and says “that won’t work.” Figure out why, or prove the expert wrong!

Example 2.6

A monoid consists of a set M, a function ∗: M × M → M called the monoid multiplication, and an element e \(\in\) M called the monoid unit, such that, when you write ∗(m, n) as m ∗ n, i.e. using infix notation, the equations

m ∗ e = m, e ∗ m = m, (m ∗ n) ∗ p = m ∗ (n ∗ p) (2.7)

hold for all m, n, p ∈ M. It is called commutative if also m ∗ n = n ∗ m.
Every set S determines a discrete preorder \(Disc_{S} \)(where m ≤ n iff m = n; see Example 1.32), and it is easy to check that if (M, e , ∗) is a commutative monoid then (\(Disc_{M}\), =, e , ∗) is a symmetric monoidal preorder.

Exercise 2.8.

We said it was easy to check that if (M, ∗, e) is a commutative monoid then (\(Disc_{M}\) , =, ∗, e) is a symmetric monoidal preorder. Are we telling the truth? ♦

Example 2.9.

Here is a non-example for people who know the game “standard poker.” Let H be the set of all poker hands, where a hand means a choice of five cards from the standard 52-card deck. As an order, put h ≤ h′ if h′ beats or equals h in poker.

One could propose a monoidal product ⊗ : H × H → H by assigning \(h_{1}\) ⊗ \(h_{2}\) to be “the best hand one can form out of the ten cards in \(h_{1}\) and \(h_{2}\).” If some cards are in both \(h_{1}\) and \(h_{2}\), just throw the duplicates away. So for example {2♥, 3♥, 4♥, 6♠, 7♠} ⊗ {2♥, 5♥, 6♥, 6♠, 7♠} = {2♥, 3♥, 4♥, 5♥, 6♥}, because the latter is the best hand you can make with the former two.

This proposal for a monoidal structure will fail the condition (a) of Definition 2.2: it could be the case that \(h_{1}\) ≤ \(i_{1}\) and \(h_{2}\) ≤ \(i_{2}\), and yet not be the case that \(h_{1}\) ⊗ \(h_{2}\) ≤ \(i_{1}\) ⊗ \(i_{2}\). For example, consider this case:

\(h_{1}\) := {2♥, 3♥, 10♠, J♠, Q♠} \(i_{1}\) := {4♣, 4♠, 6♥, 6♦, 10♦}

\(h_{2}\) := {2♦, 3♦, 4♦, K♠, A♠} \(h_{2}\) := {5♠, 5♥, 7♥, J♦, Q♦}.

Here, \(h_{1}\) ≤ \(i_{1}\) and \(h_{2}\) ≤ \(i_{2}\), but \(h_{1}\) ⊗ \(h_{2}\) = {10♠, J♠, Q♠, K♠, A♠} is the best possible hand and beats \(i_{1}\) ⊗ \(i_{2}\) = {5♠, 5♥, 6♥, 6♦, Q♦}.

Subsections 2.2.3 and 2.2.4 are dedicated to examples of symmetric monoidal preorders. Some are aligned with the notion of resource theories, others come from pure math. When discussing the former, we will use wiring diagrams, so here is a quick primer.

Introducing wiring diagrams

Wiring diagrams are visual representations for building new relationships from old. In a preorder without a monoidal structure, the only sort of relationship between objects is ≤, and the only way you build a new ≤ relationship from old ones is by chaining them together. We denote the relationship x ≤ y by

We can chain some number of these ≤ relationships say 0, 1, 2, or 3 of them together in series as shown here

If we add a symmetric monoidal structure, we can combine relationships not only in series but also in parallel. Here is an example:

Different styles of wiring diagrams In fact, we will see later that there are many styles of wiring diagrams. When we are dealing with preorders, the sort of wiring diagram we can draw is that with single-input, single-output boxes connected in series. When we are dealing with symmetric monoidal preorders, we can have more complex boxes and more complex wiring diagrams, including parallel composition. Later we will see that for other sorts of categorical structures, there are other styles of wiring diagrams:

Wiring diagrams for symmetric monoidal preorders The style of wiring diagram that makes sense in any symmetric monoidal preorder is that shown in Eq. (2.12): boxes can have multiple inputs and outputs, and they may be arranged in series and parallel. Symmetric monoidal preorders and their wiring diagrams are tightly coupled with each other. How so?

The answer is that a monoidal preorder (X, ≤, I, ⊗) has some notion of element (x \(\in\) X), relationship (≤), and combination (using transitivity and ⊗), and so do wiring diagrams: the wires represent elements, the boxes represent relationships, and the wiring diagrams themselves show how relationships can be combined. We call boxes and wires icons; we will encounter several more icons in this chapter, and throughout the book.

To get a bit more rigorous about the connection, let’s start with a monoidal preorder (X, ≤, I, ⊗) as in Definition 2.2. Wiring diagrams have wires on the left and the right. Each element x \(\in\) X can be made the label of a wire. Note that given two objects x, y, we can either draw two wires in parallel one labeled x and one labeled y or we can draw one wire labeled x ⊗ y.

We consider wires in parallel to represent the monoidal product of their labels, so we consider both cases above to represent the element x ⊗ y. Note also that a wire labeled I or an absence of wires:

both represent the monoidal unit I; another way of thinking of this is that the unit is the empty monoidal product.

A wiring diagram runs between a set of parallel wires on the left and a set of parallel wires on the right. We say that a wiring diagram is valid if the monoidal product of the elements on the left is less than the monoidal product of those on the right. For example, if we have the inequality x ≤ y, the the diagram that is a box with a wire labeled x on the left and a wire labeled y on the right is valid; see the first box below:

The validity of the second box corresponds to the inequality \(x_{1}\) ⊗ \(x_{2}\) ≤ \(y_{1}\) ⊗ \(y_{2}\) ⊗ \(y_{3}\). Before going on to the properties from Definition 2.2, let us pause for an example of what we’ve discussed so far.

Example 2.14.

Recall the symmetric monoidal preorder (\(\mathbb{R}\), ≤, 0, +) from Example 2.4. The wiring diagrams for it allow wires labeled by real numbers. Drawing wires in parallel corresponds to adding their labels, and the wire labeled 0 is equivalent to no wires at all.

And here we express a couple facts about (\(\mathbb{R}\), ≤, 0, +) in this language: 4 ≤ 7 and 2+5 ≤ −1+5+3.

We now return to how the properties of symmetric monoidal preorders correspond to properties of this sort of wiring diagram. Let’s first talk about the order structure: conditions (a)reflexivity and (b)transitivity from Definition 1.30. Reflexivity says that x ≤ x, this means the diagram just consisting of a wire

is always valid. Transitivity allows us to connect facts together: it says that if x ≤ y and y ≤ z, then x ≤ z. This means that if the diagrams

are valid, we can put them together and obtain the valid diagram

Next let’s talk about the properties (a)–(d) from the definition of symmetric monoidal structure (Definition 2.2). Property (a) says that if \(x_{1}\) ≤ \(y_{1}\) and \(x_{2}\) ≤ \(y_{2}\) then \(x_{1}\) ⊗ \(x_{2}\) ≤ \(y_{1}\) ⊗ \(y_{2}\). This corresponds to the idea that stacking any two valid boxes in parallel is still valid:

Condition (b), that I ⊗ x = x and x ⊗ I = x, says we don’t need to worry about I or blank space; in particular diagrams such as the following are valid:

Condition (c), that (x ⊗ y) ⊗ z = x ⊗ (y ⊗ z) says that we don’t have to worry about whether we build up diagrams from the top or from the bottom

But this looks much harder than it is: the associative property should be thought of as saying that there is no distinction between the stuff on the very left above and the stuff on the very right, i.e.

and indeed a diagram that moves from one to the other is valid.
Finally, the symmetry condition (d), that x ⊗ y = y ⊗ x, says that a diagram is valid even if its wires cross:

One may regard the pair of crossing wires as another icon in our iconography, in addition to the boxes and wires we already have.

Wiring diagrams as graphical proofs Given a monoidal preorder X = (X, ≤, I, ⊗), a wiring diagram is a graphical proof of something about X. Each box in the diagram has a left side and a right side, say x and y, and represents the assertion that x ≤ y.

A wiring diagram is a bunch of interior boxes connected together inside an exterior box. It represents a graphical proof that says: if all of the interior assertions are correct, then so is the exterior assertion.

The inner boxes in Eq. (2.15) translate into the assertions:

and the outer box translates into the assertion:

The whole wiring diagram 2.15 says “if you know that the assertions in 2.16 are true, then I am a proof that the assertion in 2.17 is also true.” What exactly is the proof that diagram 2.15 represents? It is the proof

Indeed, each inequality here is a vertical slice of the diagram 2.15, and the transitivity of these inequalities is expressed by connecting these vertical slices together.

Example 2.19.

Recall the lemon meringue pie wiring diagram from Eq. (2.1). It has five interior boxes, such as “separate egg” and “fill crust,” and it has one exterior box called “prepare lemon meringue pie.” Each box is the assertion that, given the collection of resources on the left, say an egg, you can transform it into the collection of resources on the right, say an egg white and an egg yolk. The whole string diagram is a proof that if each of the interior assertions is true i.e. you really do know how to separate eggs, make lemon filling, make meringue, fill crust, and add meringue then the exterior assertion is true: you can prepare a lemon meringue pie.

Exercise 2.20.

The string of inequalities in Eq. (2.18) is not quite a proof, because technically there is no such thing as v + w + u, for example. Instead, there is (v + w) + u and v + (w + u), and so on.

1. Formally prove, using only the rules of symmetric monoidal preorders (Definition 2.2), that given the assertions in Eq. (2.16), the conclusion in Eq. (2.17) follows.
2. Reflexivity and transitivity should show up in your proof. Make sure you are explicit about where they do.
3. How can you look at the wiring diagram Eq. (2.12) and know that the symmetry axiom (Definition 2.2(d)) does not need to be invoked? ♦

We next discuss some examples of symmetric monoidal preorders. We begin in Section 2.2.3 with some more concrete examples, from science, commerce, and infor- matics. Then in Section 2.2.4 we discuss some examples arising from pure math, some of which will get a good deal of use later on, e.g. in Chapter 4.

Applied examples

Resource theories are studies of how resources are exchanged in a given arena. For example, in social resource theory one studies a marketplace where combinations of goods can be traded for as well as converted into other combinations of goods.

Whereas marketplaces are very dynamic, and an apple might be tradable for an orange on Sunday but not on Monday, what we mean by resource theory in this chapter is a static notion: deciding “what buys what,” once and for all.1 This sort of static notion of conversion might occur in chemistry: the chemical reactions that are possible one day will quite likely be possible on a different day as well. Manufacturing may be somewhere in between: the set of production techniques—whereby a company can convert one set of resources into another do not change much from day to day.

We learned about resource theories from [CFS16; Fri17], who go much further than we will; see Section 2.6 for more information. In this section we will focus only on the main idea. While there are many beautiful mathematical examples of symmetric monoidal preorders, as we will see in Section 2.2.4, there are also ad hoc examples coming from life experience. In the next chapter, on databases, we will see the same theme: while there are some beautiful mathematical categories out there, database schemas are ad hoc organizational patterns of information. Describing something as “ad hoc” is often considered derogatory, but it just means “formed, arranged, or done for a particular purpose only.” There is nothing wrong with doing things for a particular purpose; it’s common outside of pure math and pure art. Let’s get to it.

Chemistry In high school chemistry, we work with chemical equations, where mate- rial collections such as

are put together in the form of reaction equations, such as

The collection on the left, 2H2O + 2Na is called the reactant, and the collection on the right, 2NaOH + H2 is called the product.

We can consider reaction equations such as the one above as taking place inside a single symmetric monoidal preorder (Mat, →, 0, +). Here Mat is the set of all collections of atoms and molecules, sometimes called materials. So we have NaCl \(\in\) Mat and 4H2O + 6Ne \(\in\) Mat.

The set Mat has a preorder structure denoted by the → symbol, which is the preferred symbol in the setting of chemistry.

To be clear, → is taking the place of the order relation ≤ from Definition 2.2. The + symbol is the preferred notation for the monoidal product in the chemistry setting, taking the place of ⊗. While it does not come up in practice, we use 0 to denote the monoidal unit.

Exercise 2.21.

Here is an exercise for people familiar with reaction equations: check that conditions (a), (b), (c), and (d) of Definition 2.2 hold.

An important notion in chemistry is that of catalysis: one compound catalyzes a certain reaction. For example, one might have the following set of reactions:

Using the laws of monoidal preorders, we obtain the composed reaction

Here k is the catalyst because it is found both in the reactant and the product of the reaction. It is said to catalyze the reaction x + y → z.

The idea is that the reaction x + y → z cannot take place given the reactions in Eq. (2.22). But if k is present, meaning if we add k to both sides, the resulting reaction can take place.

The wiring diagram for the reaction in Eq. (2.23) is shown in Eq. (2.24). The three interior boxes correspond to the three reactions given in Eq. (2.22), and the exterior box corresponds to the composite reaction x + y + k → z + k.

Manufacturing we are talking about baking pies, building smart phones, or following pharmaceutical recipes, manufacturing firms need to store basic recipes, and build new recipes by combining simpler recipes in schemes like the one shown in Eq. (2.1) or Eq. (2.24).

The basic idea in manufacturing is exactly the same as that for chemistry, except there is an important assumption we can make in manufacturing that does not hold for chemical reactions:

You can trash anything you want, and it disappears from view.

This simple assumption has caused the world some significant problems, but it is still in effect. In our meringue pie example, we can ask: “what happened to the egg shell, or the paper wrapping the stick of butter”? The answer is they were trashed, i.e. thrown in the garbage bin. It would certainly clutter our diagram and our thinking if we had to carry these resources through the diagram:

Instead, in our daily lives and in manufacturing, we do not have to hold on to something if we don’t need it; we can just discard it. In terms of wiring diagrams, this can be shown using a new icon , as follows:

To model this concept of waste using monoidal categories, one just adds an addi- tional axiom to (a), (b), (c), and (d) from Definition 2.2: (e) x ≤ I for all x \(\in\) X. (discard axiom) It says that every x can be converted into the monoidal unit I. In the notation of the chemistry section, we would write instead x → 0: any x yields nothing. But this is certainly not accepted in the chemistry setting. For example,

is certainly not a legal chemical equation. It is easy to throw things away in manufacturing, because we assume that we have access to—the ability to grab onto and directly manipulate each item produced. In chemistry, when you have 1023 of substance A dissolved in something else, you cannot just simply discard A. So axiom (e) is valid in manufacturing but not in chemistry.

Recall that in Section 2.2.2 we said that there were many different styles of wiring diagrams. Now we’re saying that adding the discard axiom changes the wiring diagram style, in that it adds this new discard icon that allows wires to terminate, as shown in Eq. (2.25). In informatics, we will change the wiring diagram style yet again.

Informatics A major difference between information and a physical object is that information can be copied. Whereas one cup of butter never becomes two, it is easy for a single email to be sent to two different people. It is much easier to copy a music file than it is to copy a CD. Here we do not mean “copy the information from one compact disc onto another” of course that’s easy instead, we mean that it’s quite difficult to copy the physical disc, thereby forming a second physical disc! In diagrams, the distinction is between the relation

and the relation

The former is possible, the latter is magic.
Of course material objects can sometimes be copied; cell mitosis is a case in point.

But this is a remarkable biological process, certainly not something that is expected for ordinary material objects. In the physical world, we would make mitosis a box transforming one cell into two. But in (classical, not quantum) information, everything can be copied, so we add a new icon to our repertoire.

Namely, in wiring diagram notation, copying information appears as a new icon, \(\begin{equation}-x\end{equation}\), allowing us to split wires:

Now with two copies of the email, we can send one to Alice and one to Bob.

Information can also be discarded, at least in the conventional way of thinking, so in addition to axioms (a) to (d) from Definition 2.2, we can keep axiom (e) from page 50 and add a new copy axiom:

(f) x ≤ x + x for all x \(\in\) X. (copy axiom)

allowing us to make mathematical sense of diagrams like Eq. (2.26). Now that we have examples of monoidal preorders under our belts, let’s discuss some nice mathematical examples.

Abstract examples

In this section we discuss several mathematical examples of symmetric monoidal structures on preorders.

The Booleans The simplest nontrivial preorder is the booleans: \(\mathbb{B}\) = {true, false} with false ≤ true. There are two different symmetric monoidal structures on it.

Example 2.27 (Booleans with AND).

We can define a monoidal structure on \(\mathbb{B}\) by letting the monoidal unit be true and the monoidal product be \(\wedge\) (AND). If one thinks of false = 0 and true = 1, then \(\wedge\) corresponds to the usual multiplication operation ∗. That is, with this correspondence, the two tables below match up:

One can check that all the properties in Definition 2.2 hold, so we have a monoidal preorder which we denote Bool := (\(\mathbb{B}\), ≤, true, \(\wedge\)).

Bool will be important when we get to the notion of enrichment. Enriching in a monoidal preorder V = (V, ≤, I, ⊗) means “letting V structure the question of getting from a to b.” All of the structures of a monoidal preorder i.e. the set V, the ordering relation ≤, the monoidal unit I, and the monoidal product ⊗ play a role in how enrichment works.

For example, let’s look at the case of Bool = (\(\mathbb{B}\), ≤, true, \(\wedge\)). The fact that its underlying set is \(\mathbb{B}\) = {false, true} will translate into saying that “getting from a to b is a true/false question.” The fact that true is the monoidal unit will translate into saying “you can always get from a to a.” The fact that \(\cap\) is the monoidal product will translate into saying “if you can get from a to b AND you can get from b to c then you can get from a to c.” Finally, the “if-then” form of the previous sentence is coming from the order relation ≤. We will make this more precise in Section 2.3.

We will be able to play the same game with other monoidal preorders, as we will see after we define a monoidal preorder called Cost in Example 2.37.

Some other monoidal preorders It is a bit imprecise to call Bool “the” boolean monoidal preorder, because there is another monoidal structure on (\(\mathbb{B}\), ≤), which we describe in Exercise 2.29. The first structure, however, seems to be more useful in practice than the second.

Exercise 2.29.

Let (\(\mathbb{B}\), ≤) be as above, but now consider the monoidal product to be \(\vee\) (OR).

What must the monoidal unit be in order to satisfy the conditions of Definition 2.2? Does it satisfy the rest of the conditions? ♦

In Example 2.30 and Exercise 2.31 we give two different monoidal structures on the preorder (\(\mathbb{N}\), ≤) of natural numbers, where ≤ is the usual ordering (0 ≤ 1 and 5 ≤ 16).

Example 2.30 (Natural numbers with addition).

There is a monoidal structure on (\(\mathbb{N}\), ≤) where the monoidal unit is 0 and the monoidal product is +, i.e. 6 + 4 = 10. It is easy to check that \(x_{1}\) ≤\(y_{1}\) and \(x_{2}\) ≤ \(y_{2}\) implies \(x_{1}\) + \(x_{2}\) ≤ \(y_{1}\) + \(y_{2}\), as well as all the other conditions of Definition 2.2.

Exercise 2.31.

Show there is a monoidal structure on (\(\mathbb{N}\), ≤) where the monoidal product is ∗, i.e. 6 ∗ 4 = 24. What should the monoidal unit be?

Example 2.32 (Divisibility and multiplication)

Recall from Example 1.45 that there is a “divisibility” order on \(\mathbb{N}\): we write m|n to mean that m divides into n without remainder. So 1|m for all m and 4|12.

There is a monoidal structure on (\(\mathbb{N}\), | ), where the monoidal unit is 1 and the monoidal product is ∗, i.e. 6 ∗ 4 = 24. Then if \(x_{1}\)| \(y_{1}\) and \(x_{2}\)| \(y_{2}\), then (\(x_{1}\) ∗ \(x_{2}\))|( \(y_{1}\) ∗ \(y_{2}\)).

Indeed, if there is some \(p_{1}\), \(p_{1}\) \(\in\) \(\mathbb{N}\) such that \(x_{1}\)∗\(p_{1}\) = \(y_{1}\) and \(x_{2}\)∗\(p_{2}\) = \(y_{2}\), then (\(p_{1}\) ∗ \(p_{2}\)) ∗ (\(x_{1}\) ∗ \(x_{2}\)) = \(y_{1}\) ∗ \(y_{2}\).

Exercise 2.33.

Again taking the divisibility order (\(\mathbb{N}\), | ). Someone proposes 0 as the monoidal unit and + as the monoidal product. Does that proposal satisfy the conditions of Definition 2.2? Why or why not?

Exercise 2.34.

Consider the preorder (P, ≤) with Hasse diagram no → maybe → yes . We propose a monoidal structure with yes as the monoidal unit and “min” as the monoidal product.

1. Make sense of “min” by filling in the multiplication table with elements of P.

2. Check the axioms of Definition 2.2 hold for NMY := (P, ≤, yes, min), given your definition of min. If not, change your definition of min.

Exercise 2.35.

Let S be a set and let P(S) be its power set, the set of all subsets of S, including the empty subset, Ø \(\subseteq\) S, and the “everything” subset, S \(\subseteq\) S. We can give P(S) an order: A ≤ B is given by the subset relation A \(\subseteq\) B, as discussed in Example 1.50. We propose a symmetric monoidal structure on P(S) with monoidal unit S and monoidal product given by intersection A \(\land\) B.

Does it satisfy the conditions of Definition 2.2? ♦

Exercise 2.36.

Let \(Prop^{N}\) denote the set of all mathematical statements one can make about a natural number, where we consider two statements to be the same if one is true if and only if the other is true. For example “n is prime” is an element of \(Prop^{N}\), and so are “n = 2” and “n ≥ 11.” The statements “n + 2 = 5” and “n is the least odd prime” are considered the same. Given P, Q \(\in\) \(Prop^{N}\), we say P ≤ Q if for all n \(\in\) N, whenever P(n) is true, so is Q(n).

Define a monoidal unit and a monoidal product on PropN that satisfy the conditions of Definition 2.2. ♦

The monoidal preorder Cost As we said above, when we enrich in monoidal preorders we see them as different ways to structure the question of “getting from here to there.” We will explain this in more detail in Section 2.3. The following monoidal preorder will eventually structure a notion of distance or cost for getting from here to there.

Example 2.37 (Lawvere's monodial preorder, COST).

Let [0, ∞] denote the set of non- negative real numbers such as 0, 1, 15.333, and 2π together with ∞. Consider the preorder ([0, ∞], ≥), with the usual notion of ≥, where of course ∞ ≥ x for all x \(\in\) [0, ∞].

There is a monoidal structure on this preorder, where the monoidal unit is 0 and the monoidal product is +. In particular, x + ∞ = ∞ for any x \(\in\) [0, ∞]. Let’s call this monoidal preorder

Cost := ([0, ∞], ≥, 0, +),

because we can think of the elements of [0, ∞] as costs. In terms of structuring “getting from here to there,” Cost seems to say “getting from a to b is a question of cost.” The monoidal unit being 0 will translate into saying that you can always get from a to a at no cost. The monoidal product being + will translate into saying that the cost of getting from a to c is at most the cost of getting from a to b plus the cost of getting from b to c. Finally, the “at most” in the previous sentence is coming from the ≥.

The opposite of a monoidal preorder One can take the opposite of any preorder, just flip the order: ((X, ≤)\(^{op}\) := (X, ≥); see Example 1.58. Proposition 2.38 says that if the preorder had a symmetric monoidal structure, so does its opposite.

Proposition 2.38.

Suppose X = (X, ≤) is a preorder and \(X^{op}\) = (X, ≥) is its opposite. If (X, ≤, I, ⊗) is a symmetric monoidal preorder then so is its opposite, (X, ≥, I, ⊗).

Proof. Let’s first check monotonicity. Suppose \(x_{1}\) ≥ \(y_{1}\) and \(x_{2}\) ≥ \(y_{2}\) in \(X^{op}\); we need to show that \(x_{1}\) ⊗ \(x_{2}\) ≥ \(y_{1}\) ⊗ \(y_{2}\). But by definition of opposite order, we have \(y_{1}\) ≤ \(x_{1}\) and \(y_{2}\) ≤ \(x_{2}\) in X, and thus \(y_{1}\) ⊗ \(y_{2}\) ≤ \(x_{1}\) ⊗ \(x_{2}\) in X. Thus indeed \(x_{1}\) ⊗ \(x_{2}\) ≥ \(y_{1}\) ⊗ \(y_{2}\) in \(X^{op}\).

The other three conditions are even easier; see Exercise 2.39. □

Exercise 2.39.

Complete the proof of Proposition 2.38 by proving that the three remaining conditions of Definition 2.2 are satisfied.

Exercise 2.40.

Since Cost is a symmetric monoidal preorder, Proposition 2.38 says that \(Cost^{op}\) is too.

1. What is \(Cost^{op}\) as a preorder?
2. What is its monoidal unit?
3. What is its monoidal product

Monoidal monotone maps

Recall from Example 1.49 that for any preorder (X, ≤), there is an induced equivalence relation \(\cong\) on X, where x \(\cong\) x′ iff both x ≤ x′andx′ ≤ x.

Definition: 2.41.

Let P = (P, \(≤_{P}\), \(I_{P}\), \(⊗_{P}\)) and Q = (Q, \(≤_{Q}\) ,\(I_{Q}\),\(⊗_{Q}\)) be monoidal preorders. A monoidal monotone from P to Q is a monotone map f : (P, \(≤_{P}\) ) → (Q , \(≤_{Q}\)), satisfying two conditions:

(a) \(I_{Q}\) \(≤_{Q}\) f(\(I_{P}\)), and

(b) f(\(p_{1}\)) \(⊗_{Q}\) f(\(p_{2}\)) \(≤_{Q}\) f(\(p_{1}\) \(⊗_{P}\) \(p_{2}\))

for all \(p_{1}\), \(p_{2}\) \(\in\) P.

There are strengthenings of these conditions that are also important. If f satisfies the following conditions, it is called a strong monoidal monotone:

(a’) \(I_{Q}\) \(\cong\) f(\(I_{P}\)), and

(b’) f(\(p_{1}\)) \(⊗_{Q}\) f(\(p_{2}\)) f(\(p_{1}\) \(⊗_{P}\) \(p_{2}\));

and if it satisfies the following conditions it is called a strict monoidal monotone:

(a”) \(I_{Q}\) = f(\(I_{P}\)), and

(b”) f(\(p_{1}\)) \(⊗_{Q}\) f(\(p_{2}\)) = f(\(p_{1}\) \(⊗_{P}\) \(p_{2}\)).

Monoidal monotones are examples of monoidal functors, which we will see various incarnations of throughout the book; see Definition 6.68. What we call monoidal monotones could also be called lax monoidal monotones, and there is a dual notion ofoplax monoidal monotones, where the inequalities in (a) and (b) are reversed; we will not use oplaxity in this book.

Example 2.42.

There is a monoidal monotone i : (\(\mathbb{N}\), ≤, 0, +) → (\(\mathbb{R}\), ≤, 0, +), where i(n) = n for all n \(\in\) \(\mathbb{N}\). It is clearly monotonic, m ≤ n implies i(m) ≤ i(n). It is even strict monoidal because i(0) = 0 and i(m + n) = i(m) + i(n). There is also a monoidal monotone f : (\(\mathbb{R}\), ≤, 0, +) → (\(\mathbb{N}\), ≤, 0, +) going the other way. Here f (x) := ⌊x⌋ is the floor function, e.g. f (3.14) = 3. It is monotonic because x ≤ y implies f(x) ≤ f(y). Also f(0) = 0 and f(x) + f(y) ≤ f(x+y), so it is a monoidal monotone. But it is not strict or even strong because f (0.5) + f (0.5) \(\neq\) f (0.5 + 0.5).

Recall Bool = (\(\mathbb{B}\), ≤, true, \(\wedge\)) from Example 2.27 and Cost := ([0, ∞], ≥, 0, +) from Example 2.37. There is a monoidal monotone g : Bool → Cost, given by g(false) := ∞ and g(true) := 0.

Exercise 2.43.

1. Check that the map g : (\(\mathbb{B}\), ≤, true, \(\wedge\)) → ([0, ∞], ≥, 0, +) presented above indeed

• is monotonic,
• satisfies condition (a) of Definition 2.41, and
• satisfies condition (b) of Definition 2.41.

2. Is g strict? ♦

Exercise 2.44.

Let Bool and Cost be as above, and consider the following quasi-inverse functions d, u : [0, ∞] → B defined as follows:

1. Is d monotonic?
2. Does d satisfy conditions (a) and (b) of Definition 2.41?
3. Is d strict?
4. Is u monotonic?
5. Does u satisfy conditions (a) and (b) of Definition 2.41?
6. Is u strict? ♦

Exercise 2.45.

1. Is (\(\mathbb{N}\), ≤, 1, ∗) a monoidal preorder, where ∗ is the usual multiplication of natural numbers?

2. If not, why not? If so, does there exist a monoidal monotone (\(\mathbb{N}\), ≤, 0, +) → (\(\mathbb{N}\), ≤ , 1, ∗)? If not; why not? If so, find it.

3. Is (\(\mathbb{Z}\), ≤, ∗, 1) a monoidal preorder? ♦