2.2. Symmetric monoidal preorders
Contents
2.2. Symmetric monoidal preorders#
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 likely 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.
Exercise 2.5.#
This won’t work, because the monoidal product doesn’t satisfy requirement (a). Consider the
example:
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\).
2.2.2. Introducing wiring diagrams#
For more background, see String diagram.
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:
Similarly for the second equation:
And the third equation:
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.
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.
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.
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:
We have, multiplying both sides of the first premise by \(y_2\):
Multiplying both sides of the second premise by \(x_1\):
And combining \(\eqref{eq:31a}\) and \(\eqref{eq:31b}\) with transitivity:
Exercise 2.33.#
No, because \(0 | n = \infty \neq 0\).
Exercise 2.34.#
In the following table we use 0 for no, 1 for maybe, and 2 for yes:
import pandas as pd
preorder = [0, 1, 2]
min = pd.DataFrame(index=preorder, columns=preorder, data=[[0,0,0], [0,1,1], [0,1,2]])
display(min)
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 2 | 0 | 1 | 2 |
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:
Applying \(min(\_, y_2)\) to the first premise:
Applying \(min(x_1, \_)\) to the second premise:
And combining \(\eqref{eq:34a}\) and \(\eqref{eq:34b}\) with transitivity:
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:
Applying \(\_ \cap y_2\) to the first premise:
Applying \(x_1 \cap \_\) to the second premise:
And combining \(\eqref{eq:35a}\) and \(\eqref{eq:35b}\) with transitivity:
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:
\(R\) = “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):
Exercise 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.
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:
Looking ahead, you can see this graph as describing morphisms in Set where the sets are singletons (see Singleton (mathematics)).
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:
Checking condition (a) of Definition 2.41:
Checking condition (b) of Definition 2.41:
Yes, \(g\) is a strict monoidal monotone.
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:
Checking condition (a) of Definition 2.41:
Checking condition (b) of Definition 2.41:
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:
Checking condition (a) of Definition 2.41:
Checking condition (b) of Definition 2.41:
Yes, \(u\) is a strict monoidal monotone.
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.