2.2. Symmetric monoidal preorders#

\[ \newcommand{\Cat}[1]{\mathbf{#1}} \]

2.2.1. Definition and first examples#

Definition 2.2.#

See also Monoidal category - Monoidal preorders for an alternative definition of non-symmetric monoidal preorders. The full definition of a Monoidal category is not introduced (even roughly) until section 4.4.3.

You can remember the term “monoidal product” for the ⊗ operator because in general the “most important” example of a monoid in this context is going to be the real numbers with multiplication as the ⊗ operator. The usual formula for matrix multiplication (and by extension, for dot products) is based on this monoid; see Section 2.5.3. However, the symbol ⊗ (\otimes or “circled times”) is primarily associated with the Tensor product (see The Tensor Product, Demystified) and is the original source of this word. A final option is to associate this word to the “Cartesian product” when you are working with Set-categories (regular categories) (see Example 4.49).

In the short term we’re going to have to accept “+” as a “monoidal product” however. The article Monoid tries to avoid anything but the language “binary operator” in its definition.

Example 2.4.#

Exercise 2.5.#

This won’t work, because the monoidal product doesn’t satisfy requirement (a). Consider the example:

\[\begin{split} \begin{align} \\ x_1 & = -2 \\ x_2 & = -2 \\ y_1 & = 1 \\ y_2 & = 1 \\ x_1 \leq y_1 & = true \\ x_2 \leq y_2 & = true \\ x_1 \otimes x_2 & = 4 \not\leq 1 = y_1 \otimes y_2 \\ \end{align} \end{split}\]

Reveal 7S answer

Exercise 2.8.#

The element $e$ in the monoid $(M, \ast, e)$ serves as $I$ in the discrete preorder $(\Cat{Disc}_M, =, \ast, e)_{}$. The monoid multiplication $\ast$ serves as the monoidal product $\otimes$ and satisfies properties (b), (c), and (d) by definition of being a monoid. By virtue of being a discrete preorder, it satisfies (a) because $x_1$ will always equal $y_1$ and therefore with “=” as the order operator this condition comes down to $x_1 \otimes x_2 = x_1 \otimes x_2$.

Reveal 7S answer

Example 2.9.#

2.2.2. Introducing wiring diagrams#

Compare to String diagram and string diagram in nLab.

Exercise 2.20.#

Using reflexivity, we have that $u \leq u$. Add this to the first of the equations in (2.16), using (a) in the definition of a symmetrical monoidal preorder:

\[\begin{split} \begin{align} \\ t & \leq v + w \\ u & \leq u \\ t + u & \leq u + v + w \\ \end{align} \end{split}\]

Similarly for the second equation:

\[\begin{split} \begin{align} \\ w + u & \leq x + z \\ v & \leq v \\ v + w + u & \leq v + x + z \\ \end{align} \end{split}\]

And the third equation:

\[\begin{split} \begin{align} \\ v + x & \leq y \\ z & \leq z \\ v + x + z & \leq y + z \\ \end{align} \end{split}\]

Using transitivity, we can combine all three of these equations to get Equation (2.18) in the text.

To answer 3., the symmetry axiom does not need to be invoked because wires do not cross.

Reveal 7S answer

2.2.3. Applied examples#

Exercise 2.21.#

The condition (a) holds by the conservation of matter. The condition (b) holds because adding nothing to a reactant leaves you with the reactant as the product. The condition (d) holds because it shouldn’t matter what order reactants are added together in a reaction.

It’s not clear that (c) would hold in all circumstances; adding two reactants may produce a product that no longer reacts with another reactant that the original reactants may have reacted with.

Reveal 7S answer

2.2.4. Abstract examples#

Exercise 2.29.#

The monoidal unit must be $false$ (satisfying the unitality condition (a)).

It’s not clear that the author is presenting these tables to show they are symmetric (as in “symmetric” monoidal preorder), but they show that symmetric condition (d) is satisfied.

The associative condition (c) is satisfied because booleans over $\vee$ are associative.

The monotonicity requirement (a) is satisfied because the booleans over $\vee$ are also already monotone, and this is apparent in the tables as well. See also Boolean algebra - Monotone laws and Monotonic function - In Boolean functions.

Reveal 7S answer

Exercise 2.31.#

Notice this question only asks for a monoidal structure, not a symmetric monoidal preorder structure. Since it seems to have both, we’ll show both here.

The monoidal unit should be 1 (satisfies unitality). The natural numbers under addition satisfy the associativity condition, so this symmetric monoidal preorder will as well. See Natural number - Algebraic properties satisfied by the natural numbers. The natural numbers also satisfy the commutativity condition (symmetry condition in the text).

The following is based (roughly) on Propositional calculus - Natural deduction system and Propositional calculus - Proofs in propositional calculus. To see the monotonicity condition is satisfied we’ll use the normal rules of algebra on the natural (positive) numbers, with these two premises:

\[\begin{split} \begin{align} \\ x_1 & \leq y_1 \\ x_2 & \leq y_2 \\ \end{align} \end{split}\]

We have, multiplying both sides of the first premise by $y_2$:

\[\begin{split} \begin{equation} \\ x_1 \ast y_2 \leq y_1 \ast y_2 \\ \label{eq:31a} \tag{a} \end{equation} \end{split}\]

Multiplying both sides of the second premise by $x_1$:

\[\begin{split} \begin{equation} \\ x_1 \ast x_2 \leq x_1 \ast y_2 \\ \label{eq:31b} \tag{b} \end{equation} \end{split}\]

And combining $\eqref{eq:31a}$ and $\eqref{eq:31b}$ with transitivity:

\[ x_1 \ast x_2 \leq x_1 \ast y_2 \leq y_1 \ast y_2 \]

Reveal 7S answer

Exercise 2.33.#

No, because $0 | n = \infty \neq 0$.

Reveal 7S answer

Exercise 2.34.#

In the following table we use 0 for no, 0.5 for maybe, and 1 for yes:

import pandas as pd

preorder = [0, 0.5, 1]
min = pd.DataFrame(index=preorder, columns=preorder, data=[[0,0,0], [0,0.5,0.5], [0,0.5,1]])
display(min)

	0.5	1.0
0.0	0.0	0.0
0.5	0.5	0.5
1.0	0.5	1.0

The min function is associative; see Associative property - Examples. The yes element can be used as a monoidal unit. It’s easy to see the symmetry/commutativity property is satisfied in the truth table.

To see the monotonicity condition is satisfied we’ll use as an inference rule that a partially-applied min function is order-preserving. That is, if we have that $a_1 \leq a_2$, it follows that $min(a_1, b) \leq min(a_2, b)$. Then, starting from these two premises: $$ \begin{align} \\ x_1 & \leq y_1 \\ x_2 & \leq y_2 \\ \end{align} $$

Applying $min(\_, y_2)$ to the first premise:

\[\begin{split} \begin{equation} \\ min(x_1, y_2) \leq min(y_1, y_2) \\ \label{eq:34a} \tag{a} \end{equation} \end{split}\]

Applying $min(x_1, \_)$ to the second premise:

\[\begin{split} \begin{equation} \\ min(x_1, x_2) \leq min(x_1, y_2) \\ \label{eq:34b} \tag{b} \end{equation} \end{split}\]

And combining $\eqref{eq:34a}$ and $\eqref{eq:34b}$ with transitivity:

\[ min(x_1, x_2) \leq min(x_1, y_2) \leq min(y_1, y_2) \]

Reveal 7S answer

See also Exercise 2.29; we could have constructed a NMY preorder from the max operation as well.

Exercise 2.35.#

It should satisfy the identity/unitality condition because $S \cap X$ for any $X$ that is a subset of $S$ should be $X$. See also Intersection (set theory); the intersection operation is associative, and commutative.

To see the monotonicity condition is satisfied we’ll use as an inference rule that a partially-applied $\cap$ is order-preserving. That is, if we have that $a_1 \leq a_2$ (that is, $a_1 \subset a_2$), it follows that $a_1 \cap b \leq a_2 \cap b$. Then, starting from these two premises:

\[\begin{split} \begin{align} \\ x_1 & \leq y_1 \\ x_2 & \leq y_2 \\ \end{align} \end{split}\]

Applying $\_ \cap y_2$ to the first premise:

\[\begin{split} \begin{equation} \\ x_1 \cap y_2 \leq y_1 \cap y_2 \\ \label{eq:35a} \tag{a} \end{equation} \end{split}\]

Applying $x_1 \cap \_$ to the second premise:

\[\begin{split} \begin{equation} \\ x_1 \cap x_2 \leq x_1 \cap y_2 \\ \label{eq:35b} \tag{b} \end{equation} \end{split}\]

And combining $\eqref{eq:35a}$ and $\eqref{eq:35b}$ with transitivity:

\[ x_1 \cap x_2 \leq x_1 \cap y_2 \leq y_1 \cap y_2 \]

Reveal 7S answer

Exercise 2.36.#

$\def\NN{{\bf N}}\def\bold#1{{\bf #1}}$A list of example statements (including those that were already made) that may be made in this language:

$Q$ = “n is prime”
$R$ = “n is even”
$S$ = $0 \leq n$
$T$ = $n = 15$

Clearly $S \leq P$ for all $P$ in $n \in \NN$, but $T$ is only true for a single $P$. If we use “and” as our monoidal product, we must pick something that is always true (like $S$) as our monoidal unit. If we had chosen “or” then we’d have to come up with a statement that is always false.

An “and” operation is clearly already associative and commutative. It’s also order-preserving, which we can use in the following proof (in a style suggested by Example 1.123):

Reveal 7S answer

Example 2.37#

See also Extended real number line, referenced in Pointed set.

Exercise 2.39.#

The $I$ remains the identity because in the original symmetric monoidal preorder we had $I \otimes x = x$ and $x \otimes I = x$ and nothing about $\otimes$ has changed. Similarly, if $\otimes$ was associative and commutative it should remain so.

Reveal 7S answer

Exercise 2.40.#

As a preorder $\bold{Cost}^{op}$ is $([0, ∞], \leq)$. In this preorder smaller numbers are “better” (greater) as in golf.

The monoidal unit remains 0, and the monoidal product remains +.

Note that (confusingly) we use the symbol $≤_{X^{op}}$ to mean the same as ≥ (where ≥ has its normal meaning in a linear order); see the first example in Opposite category. See also “is parent of” as discussed in Relation (mathematics). Given an arrow, the source is the first argument to the operator (e.g. ≤) and the target is the second argument. Visually:

It’s not enough to draw a diagram with arrows to communicate (by definition non-commutative) relationships. Let’s say you were planning a gift exchange with family members, and you sent out this list:

George → Mary
Mary → Sandeep
Sandeep → George

Does George buy a gift for Mary, or Mary buy a gift for George? Without the giver and receiver labeled, there’s no way to know which is correct. If you send out this list, someone may end up without a gift while someone else gets two! Only one arrow needs to be labeled, in the style of a legend:

\[ Giver \; \underrightarrow{buys for} \; Receiver \]

Looking ahead, you can see this graph as describing morphisms in Set where the sets are singletons (see Singleton (mathematics)).

Reveal 7S answer

2.2.5. Monoidal monotone maps#

Exercise 2.43#

To show this is indeed a monotone map, we must show $x ≤_B y$ implies $f(x) ≥_{Cost} f(y)$ for all $x,y \in B$. There are only four cases to check:

\[\begin{split} \begin{align} \\ false \leq false & \to \infty \geq \infty \\ false \leq true & \to \infty \geq 0 \\ true \leq false & \to 0 \geq \infty \\ true \leq true & \to 0 \geq 0 \\ \end{align} \end{split}\]

Checking condition (a) of Definition 2.41:

\[ 0 \leq g(true) = 0 \]

Checking condition (b) of Definition 2.41:

\[\begin{split} \begin{align} \\ \infty + \infty \leq g(false) = \infty \\ \infty + 0 \leq g(false) = \infty \\ 0 + \infty \leq g(false) = \infty \\ 0 + 0 \leq g(true) = 0 \\ \end{align} \end{split}\]

Yes, $g$ is a strict monoidal monotone.

Reveal 7S answer

Exercise 2.44#

To show $d$ is a monotone map, we must show $x ≥_{Cost} y$ implies $d(x) ≤_B d(y)$ for all $x,y \in B$. There are only nine cases to check, if we treat all numbers between 0 and $\infty$ as one of three options for each variable:

\[\begin{split} \begin{align} \\ 0 \geq 0 & \to T \leq T \\ 0 \geq 7 & \to T \leq F \\ 0 \geq ∞ & \to T \leq F \\ 7 \geq 0 & \to F \leq T \\ 7 \geq 7 & \to F \leq F \\ 7 \geq ∞ & \to F \leq F \\ ∞ \geq 0 & \to F \leq T \\ ∞ \geq 7 & \to F \leq F \\ ∞ \geq ∞ & \to F \leq F \\ \end{align} \end{split}\]

Checking condition (a) of Definition 2.41:

\[ T \leq d(0) = T \]

Checking condition (b) of Definition 2.41:

\[\begin{split} \begin{align} \\ d(0) \wedge d(0) = T & \to d(0 + 0) = T \\ d(0) \wedge d(7) = F & \to d(0 + 7) = F \\ d(0) \wedge d(∞) = F & \to d(0 + ∞) = F \\ d(7) \wedge d(0) = F & \to d(7 + 0) = F \\ d(7) \wedge d(7) = F & \to d(7 + 7) = F \\ d(7) \wedge d(∞) = F & \to d(7 + ∞) = F \\ d(∞) \wedge d(0) = F & \to d(∞ + 0) = F \\ d(∞) \wedge d(7) = F & \to d(∞ + 7) = F \\ d(∞) \wedge d(∞) = F & \to d(∞ + ∞) = F \\ \end{align} \end{split}\]

Yes, $d$ is a strict monoidal monotone.

To show $u$ is a monotone map, we must show $x ≥_{Cost} y$ implies $u(x) ≤_B u(y)$ for all $x,y \in B$. There are only nine cases to check, if we treat all numbers between 0 and $\infty$ as one of three options for each variable:

\[\begin{split} \begin{align} \\ 0 \geq 0 & \to T \leq T \\ 0 \geq 7 & \to T \leq T \\ 0 \geq ∞ & \to T \leq F \\ 7 \geq 0 & \to T \leq T \\ 7 \geq 7 & \to T \leq T \\ 7 \geq ∞ & \to T \leq T \\ ∞ \geq 0 & \to F \leq T \\ ∞ \geq 7 & \to F \leq T \\ ∞ \geq ∞ & \to F \leq F \\ \end{align} \end{split}\]

Checking condition (a) of Definition 2.41:

\[ T \leq u(0) = T \]

Checking condition (b) of Definition 2.41:

\[\begin{split} \begin{align} \\ u(0) \wedge u(0) = T & \to u(0 + 0) = T \\ u(0) \wedge u(7) = T & \to u(0 + 7) = T \\ u(0) \wedge u(∞) = F & \to u(0 + ∞) = F \\ u(7) \wedge u(0) = T & \to u(7 + 0) = T \\ u(7) \wedge u(7) = T & \to u(7 + 7) = T \\ u(7) \wedge u(∞) = F & \to u(7 + ∞) = F \\ u(∞) \wedge u(0) = F & \to u(∞ + 0) = F \\ u(∞) \wedge u(7) = F & \to u(∞ + 7) = F \\ u(∞) \wedge u(∞) = F & \to u(∞ + ∞) = F \\ \end{align} \end{split}\]

Yes, $u$ is a strict monoidal monotone.

Reveal 7S answer

Exercise 2.45#

To answer 1., see the same question in Exercise 2.31.

To answer 2., we simply need to guess and check different kinds of functions for the monoidal monotone. An answer that works is $f(p) := n^p$ where $n$ is any integer (e.g. 2).

To answer 3., see nearly the same question in Exercise 2.5.

Reveal 7S answer

Executable Notes

2.2. Symmetric monoidal preorders

Contents

2.2. Symmetric monoidal preorders#

2.2.1. Definition and first examples#

Definition 2.2.#

Example 2.4.#

Exercise 2.5.#

Exercise 2.8.#

Example 2.9.#

2.2.2. Introducing wiring diagrams#

Exercise 2.20.#

2.2.3. Applied examples#

Exercise 2.21.#

2.2.4. Abstract examples#

Exercise 2.29.#

Exercise 2.31.#

Exercise 2.33.#

Exercise 2.34.#

Exercise 2.35.#

Exercise 2.36.#

Example 2.37#

Exercise 2.39.#

Exercise 2.40.#

2.2.5. Monoidal monotone maps#

Exercise 2.43#

Exercise 2.44#

Exercise 2.45#