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

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

Options

Okay, now I've rather carefully discussed one example of \(\mathcal{V}\)-enriched profunctors, and rather sloppily discussed another. Now it's time to build the general framework that can handle both these examples.

We can define \(\mathcal{V}\)-enriched categories whenever \(\mathcal{V}\) is a monoidal preorder: we did that way back in Lecture 29. We can also define \(\mathcal{V}\)-enriched functors whenever \(\mathcal{V}\) is a monoidal preorder: we did that in Lecture 31. But to define \(\mathcal{V}\)-enriched profunctors, we need \(\mathcal{V}\) to be a bit better. We can see why by comparing our examples.

Our first example involved \(\mathcal{V} = \textbf{Bool}\). A **feasibility relation**

$$ \Phi : X \nrightarrow Y $$ between preorders is a monotone function

$$ \Phi: X^{\text{op}} \times Y\to \mathbf{Bool} . $$ We shall see that a feasibility relation is the same as a \( \textbf{Bool}\)-enriched profunctor.

Our second example involved \(\mathcal{V} = \textbf{Cost}\). I said that a \( \textbf{Cost}\)-enriched profunctor

$$ \Phi : X \nrightarrow Y $$ between \(\mathbf{Cost}\)-enriched categories is a \( \textbf{Cost}\)-enriched functor

$$ \Phi: X^{\text{op}} \times Y \to \mathbf{Cost} $$ obeying some conditions. But I let you struggle to guess those conditions... without enough clues to make it easy!

To fit both our examples in a general framework, we start by considering an arbitrary monoidal preorder \(\mathcal{V}\). \(\mathcal{V}\)-enriched profunctors will go between \(\mathcal{V}\)-enriched categories. So, let \(\mathcal{X}\) and \(\mathcal{Y}\) be \(\mathcal{V}\)-enriched categories. We want to make this definition:

**Tentative Definition.** A \(\mathcal{V}\)-enriched profunctor

$$ \Phi : \mathcal{X} \nrightarrow \mathcal{Y} $$ is a \(\mathcal{V}\)-enriched functor

$$ \Phi: \mathcal{X}^{\text{op}} \times \mathcal{Y} \to \mathcal{V} .$$ Notice that this handles our first example very well. But some questions appear in our second example - and indeed in general. For our tentative definition to make sense, we need three things:

We need \(\mathcal{V}\) to itself be a \(\mathcal{V}\)-enriched category.

We need any two \(\mathcal{V}\)-enriched category to have a 'product', which is again a \(\mathcal{V}\)-enriched category.

We need any \(\mathcal{V}\)-enriched category to have an 'opposite', which is again a \(\mathcal{V}\)-enriched category.

Items 2 and 3 work fine whenever \(\mathcal{V}\) is a commutative monoidal poset. We'll see why in Lecture 62.

Item 1 is trickier, and indeed it sounds rather scary. \(\mathcal{V}\) began life as a humble monoidal preorder. Now we're wanting it to be *enriched in itself!* Isn't that circular somehow?

Yes! But not in a bad way. Category theory often eats its own tail, like the mythical ourobous, and this is an example.

To get \(\mathcal{V}\) to become a \(\mathcal{V}\)-enriched category, we'll demand that it be 'closed'. For starters, let's assume it's a monoidal *poset*, just to avoid some technicalities.

**Definition.** A monoidal poset is **closed** if for all elements \(x,y \in \mathcal{V}\) there is an element \(x \multimap y \in \mathcal{V}\) such that

$$ x \otimes a \le y \text{ if and only if } a \le x \multimap y $$ for all \(a \in \mathcal{V}\).

This will let us make \(\mathcal{V}\) into a \(\mathcal{V}\)-enriched category by setting \(\mathcal{V}(x,y) = x \multimap y \). But first let's try to understand this concept a bit!

We can check that our friend \(\mathbf{Bool}\) is closed. Remember, we are making it into a monoidal poset using 'and' as its binary operation: its full name is \( \lbrace \text{true},\text{false}\rbrace, \wedge, \text{true})\). Then we can take \( x \multimap y \) to be 'implication'. More precisely, we say \( x \multimap y = \text{true}\) iff \(x\) implies \(y\). Even more precisely, we define:

$$ \text{true} \multimap \text{true} = \text{true} $$
$$ \text{true} \multimap \text{false} = \text{false} $$
$$ \text{false} \multimap \text{true} = \text{true} $$
$$ \text{false} \multimap \text{false} = \text{true} . $$
**Puzzle 188.** Show that with this definition of \(\multimap\) for \(\mathbf{Bool}\) we have

$$ a \wedge x \le y \text{ if and only if } a \le x \multimap y $$ for all \(a,x,y \in \mathbf{Bool}\).

We can also check that our friend \(\mathbf{Cost}\) is closed! Remember, we are making it into a monoidal poset using \(+\) as its binary operation: its full name is \( [0,\infty], \ge, +, 0)\). Then we can define \( x \multimap y \) to be 'subtraction'. More precisely, we define \(x \multimap y\) to be \(y - x\) if \(y \ge x\), and \(0\) otherwise.

**Puzzle 189.** Show that with this definition of \(\multimap\) for \(\mathbf{Cost}\) we have

$$ a + x \le y \text{ if and only if } a \le x \multimap y . $$
But beware. We have defined the ordering on \(\mathbf{Cost}\) to be the *opposite* of the usual ordering of numbers in \([0,\infty]\). So, \(\le\) above means the *opposite* of what you might expect!

Next, two more tricky puzzles. Next time I'll show you in general how a closed monoidal poset \(\mathcal{V}\) becomes a \(\mathcal{V}\)-enriched category. But to appreciate this, it may help to try some examples first:

**Puzzle 190.** What does it mean, exactly, to make \(\mathbf{Bool}\) into a \(\mathbf{Bool}\)-enriched category? Can you see how to do this by defining

$$ \mathbf{Bool}(x,y) = x \multimap y $$ for all \(x,y \in \mathbf{Bool}\), where \(\multimap\) is defined to be 'implication' as above?

**Puzzle 191.** What does it mean, exactly, to make \(\mathbf{Cost}\) into a \(\mathbf{Cost}\)-enriched category? Can you see how to do this by defining

$$ \mathbf{Cost}(x,y) = x \multimap y $$ for all \(x,y \in \mathbf{Cost}\), where \(\multimap\) is defined to be 'subtraction' as above?

Note: for Puzzle 190 you might be tempted to say "a \(\mathbf{Bool}\)-enriched category is just a preorder, so I'll use that fact here". However, you may learn more if you go back to the general definition of enriched category and use that! The reason is that we're trying to understand some general things by thinking about two examples.

**Puzzle 192.** The definition of 'closed' above is an example of a very important concept we keep seeing in this course. What is it? Restate the definition of closed monoidal poset in a more elegant, but equivalent, way using this concept.

## Comments

Puzzle 192: A monoidal preorder is

closediff there exists a operator: \(\multimap\) such that \[(\_\otimes x) \vdash (x\multimap \_)\]`Puzzle 192: A monoidal preorder is _closed_ iff there exists a operator: \\(\multimap\\) such that \\[(\\_\otimes x) \vdash (x\multimap \\_)\\]`

possible typo: in previous lectures we've defined profunctors as \(\mathcal{V}\)-enriched functors \(\mathcal{X}^\text{op}\times\mathcal{Y}\rightarrow\mathcal{V}\) but here we're using \(\mathcal{X}\times\mathcal{Y}^\text{op}\rightarrow\mathcal{V}\) – is this a mistake or are we swapping round for a reason?

`possible typo: in previous lectures we've defined profunctors as \\(\mathcal{V}\\)-enriched functors \\(\mathcal{X}^\text{op}\times\mathcal{Y}\rightarrow\mathcal{V}\\) but here we're using \\(\mathcal{X}\times\mathcal{Y}^\text{op}\rightarrow\mathcal{V}\\) – is this a mistake or are we swapping round for a reason?`

re

Puzzle 188:\(a\wedge x \leq y\) is false iff \(a\wedge x = \text{true}\) and \(y = \text{false}\) iff \(a = \text{true}\), \(x = \text{true}\), \(y = \text{false}\)

\(a \leq x\multimap y\) is false iff \(a = \text{true}\) and \(x\multimap y = \text{false}\) iff \(a = \text{true}\), \(x = \text{true}\), \(y = \text{false}\)

so \(a\wedge x \leq y\) iff \(a \leq x\multimap y\)

`re **Puzzle 188**: \\(a\wedge x \leq y\\) is false iff \\(a\wedge x = \text{true}\\) and \\(y = \text{false}\\) iff \\(a = \text{true}\\), \\(x = \text{true}\\), \\(y = \text{false}\\) \\(a \leq x\multimap y\\) is false iff \\(a = \text{true}\\) and \\(x\multimap y = \text{false}\\) iff \\(a = \text{true}\\), \\(x = \text{true}\\), \\(y = \text{false}\\) so \\(a\wedge x \leq y\\) iff \\(a \leq x\multimap y\\)`

Let's recall the definition John gave in Lecture 29:

We want

$$ \mathcal{X}(a,b) := a \multimap_{\mathbf{Bool}} b$$ Let's go through the parts of the definition.

truth tablebelow.$$ \begin{array}{|c|c|c|} \hline a & b &a \multimap b\\ \hline \text{true}&\text{true}&\text{true}\\ \hline \mathbf{true}&\mathbf{false} &\mathbf{false}\\ \hline \text{false}&\text{true} &\text{true}\\ \hline \text{false}&\text{false} &\text{true}\\ \hline \end{array} $$ Now we need to verify the two laws, (a) and (b), hold.

(a) We need \(I \le \mathcal{X}(x,x)\), ie \(\text{true} \leq x \multimap x\), for all x. But as we can see from the truth table, \(x \multimap x = \text{true}\) holds for \(x = \text{true}\) and \(x = \text{false}\).

(b) We need to check \(x \multimap y \wedge y \multimap z \leq x \multimap z\). We can show this using another truth table, enumerating all of the possible values. We just need to check that the last two columns, and verify that \(x \multimap y \wedge y \multimap z \leq x \multimap z\), remembering that \(\text{false} \le \text{true}\).

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline x & y & z & x \multimap y & y \multimap z & x \multimap y \wedge y \multimap z & x \multimap z \\ \hline \text{true}&\text{true}&\text{true} &\text{true} &\text{true} &\mathbf{true} & \mathbf{true} \\ \hline \text{true}&\text{true}&\text{false}&\text{true} &\text{false}&\mathbf{false}&\mathbf{false}\\ \hline \text{true}&\text{false}&\text{true}&\text{false} &\text{true}&\mathbf{false}&\mathbf{true}\\ \hline \text{true}&\text{false}&\text{false}&\text{false} &\text{true}&\mathbf{false}&\mathbf{false}\\ \hline \text{false}&\text{true}&\text{true} &\text{true} &\text{true} &\mathbf{true} & \mathbf{true} \\ \hline \text{false}&\text{true}&\text{false}&\text{true} &\text{false}&\mathbf{false}&\mathbf{true}\\ \hline \text{false}&\text{false}&\text{true}&\text{true} &\text{true}&\mathbf{true}&\mathbf{true}\\ \hline \text{false}&\text{false}&\text{false}&\text{true} &\text{true}&\mathbf{true}&\mathbf{true}\\ \hline \end{array} $$

`> **Puzzle 190.** What does it mean, exactly, to make \\(\mathbf{Bool}\\) into a \\(\mathbf{Bool}\\)-enriched category? Can you see how to do this by defining > > \[ \mathbf{Bool}(x,y) = x \multimap y \] > > for all \\(x,y \in \mathbf{Bool}\\), where \\(\multimap\\) is defined to be 'implication' as above? Let's recall the definition John gave in [Lecture 29](https://forum.azimuthproject.org/discussion/2121/lecture-29-chapter-2-enriched-categories): > **Definition.** A **\\(\mathcal{V}\\)-enriched category** \\(\mathcal{X}\\) consists of two parts, satisfying two properties. First: > > 1. one specifies a set \\(\mathrm{Ob}(\mathcal{X})\\), elements of which are called **objects**; > > 2. for every two objects \\(x,y\\), one specifies an element \\(\mathcal{X}(x,y)\\) of \\(\mathcal{V}\\). > > Then: > > a) for every object \\(x\in\text{Ob}(\mathcal{X})\\) we require that > > \[ I\leq\mathcal{X}(x,x) .\] > > b) for every three objects \\(x,y,z\in\mathrm{Ob}(\mathcal{X})\\), we require that > > \[ \mathcal{X}(x,y)\otimes\mathcal{X}(y,z)\leq\mathcal{X}(x,z). \] We want \[ \mathcal{X}(a,b) := a \multimap_{\mathbf{Bool}} b\] Let's go through the parts of the definition. 1. The objects are specified by \\(\mathrm{Ob}(\multimap_{\mathbf{Bool}}) = \\{ \text{true}, \text{false} \\} \\) 2. The behavior of \\(a \multimap_{\mathbf{Bool}} b\\) is specified by its [*truth table*](https://en.wikipedia.org/wiki/Material_conditional#Truth_table) below. \[ \begin{array}{|c|c|c|} \hline a & b &a \multimap b\\\\ \hline \text{true}&\text{true}&\text{true}\\\\ \hline \mathbf{true}&\mathbf{false} &\mathbf{false}\\\\ \hline \text{false}&\text{true} &\text{true}\\\\ \hline \text{false}&\text{false} &\text{true}\\\\ \hline \end{array} \] Now we need to verify the two laws, (a) and (b), hold. (a) We need \\(I \le \mathcal{X}(x,x)\\), ie \\(\text{true} \leq x \multimap x\\), for all x. But as we can see from the truth table, \\(x \multimap x = \text{true}\\) holds for \\(x = \text{true}\\) and \\(x = \text{false}\\). (b) We need to check \\(x \multimap y \wedge y \multimap z \leq x \multimap z\\). We can show this using another truth table, enumerating all of the possible values. We just need to check that the last two columns, and verify that \\(x \multimap y \wedge y \multimap z \leq x \multimap z\\), remembering that \\(\text{false} \le \text{true}\\). \[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline x & y & z & x \multimap y & y \multimap z & x \multimap y \wedge y \multimap z & x \multimap z \\\\ \hline \text{true}&\text{true}&\text{true} &\text{true} &\text{true} &\mathbf{true} & \mathbf{true} \\\\ \hline \text{true}&\text{true}&\text{false}&\text{true} &\text{false}&\mathbf{false}&\mathbf{false}\\\\ \hline \text{true}&\text{false}&\text{true}&\text{false} &\text{true}&\mathbf{false}&\mathbf{true}\\\\ \hline \text{true}&\text{false}&\text{false}&\text{false} &\text{true}&\mathbf{false}&\mathbf{false}\\\\ \hline \text{false}&\text{true}&\text{true} &\text{true} &\text{true} &\mathbf{true} & \mathbf{true} \\\\ \hline \text{false}&\text{true}&\text{false}&\text{true} &\text{false}&\mathbf{false}&\mathbf{true}\\\\ \hline \text{false}&\text{false}&\text{true}&\text{true} &\text{true}&\mathbf{true}&\mathbf{true}\\\\ \hline \text{false}&\text{false}&\text{false}&\text{true} &\text{true}&\mathbf{true}&\mathbf{true}\\\\ \hline \end{array} \]`

There is a general proof of (b) above.

For

anycommutative closed monoidal preorder we have$$ x \multimap y \otimes y \multimap z \le x \multimap z $$ We don't really care if we are in \(\mathbf{Bool}\) or \(\mathbf{Cost}\) or whatever.

First observe

$$ a \multimap b \le a \multimap b \text{ for all } a \text{ and } b$$ This follows from reflexivity of \(\le\). By the adjointness of \(\otimes \dashv\, \multimap\) we know

$$ a \multimap b \otimes a \le b \text{ for all } a \text{ and } b$$ In particular, we have

$$ \begin{align} x \multimap y \otimes x & \le y \tag{A}\\ y \multimap z \otimes y & \le z \tag{B} \end{align} $$ If we take \((A)\), we can

tensorboth sides by applying \(y \multimap z\, \otimes \) to get$$ y \multimap z \otimes x \multimap y \otimes x \le y \multimap z \otimes y $$ This follows since \(\otimes\) is monotone. Along with \((B)\) and transitivity of \(\le\) we have

$$ y \multimap z \otimes x \multimap y \otimes x \le z $$ applying \(\otimes \dashv\, \multimap\) once again to this gives

$$ y \multimap z \otimes x \multimap y \le x \multimap z \tag{★} $$ Finally, since we are assuming \(\otimes\) is commutative, we know

$$ y \multimap z \otimes x \multimap y = x \multimap y \otimes y \multimap z $$ taking this along with \((★)\) finally yields:

$$ x \multimap y \otimes y \multimap z \le x \multimap z $$

`There is a general proof of (b) above. For *any* commutative closed monoidal preorder we have \[ x \multimap y \otimes y \multimap z \le x \multimap z \] We don't really care if we are in \\(\mathbf{Bool}\\) or \\(\mathbf{Cost}\\) or whatever. First observe \[ a \multimap b \le a \multimap b \text{ for all } a \text{ and } b\] This follows from reflexivity of \\(\le\\). By the adjointness of \\(\otimes \dashv\, \multimap\\) we know \[ a \multimap b \otimes a \le b \text{ for all } a \text{ and } b\] In particular, we have \[ \begin{align} x \multimap y \otimes x & \le y \tag{A}\\\\ y \multimap z \otimes y & \le z \tag{B} \end{align} \] If we take \\((A)\\), we can *tensor* both sides by applying \\(y \multimap z\, \otimes \\) to get \[ y \multimap z \otimes x \multimap y \otimes x \le y \multimap z \otimes y \] This follows since \\(\otimes\\) is monotone. Along with \\((B)\\) and transitivity of \\(\le\\) we have \[ y \multimap z \otimes x \multimap y \otimes x \le z \] applying \\(\otimes \dashv\, \multimap\\) once again to this gives \[ y \multimap z \otimes x \multimap y \le x \multimap z \tag{★} \] Finally, since we are assuming \\(\otimes\\) is commutative, we know \[ y \multimap z \otimes x \multimap y = x \multimap y \otimes y \multimap z \] taking this along with \\((★)\\) finally yields: \[ x \multimap y \otimes y \multimap z \le x \multimap z \]`

I think we can simplify that slightly @Matthew

We have your (A) and (B), ie \(x\otimes (x\multimap y) \leq y\) and \(y \otimes (y\multimap z) \leq z\).

Therefore \(x\otimes (x\multimap y) \otimes (y\multimap z) \leq y \otimes (y\multimap z) \leq z\).

So by adjunction \((x\multimap y) \otimes (y\multimap z) \leq (x\multimap z)\).

(EDIT: Oh I see this is the same proof, but you spelled it out in a bit more detail!)

`I think we can simplify that slightly @Matthew We have your (A) and (B), ie \\(x\otimes (x\multimap y) \leq y\\) and \\(y \otimes (y\multimap z) \leq z\\). Therefore \\(x\otimes (x\multimap y) \otimes (y\multimap z) \leq y \otimes (y\multimap z) \leq z\\). So by adjunction \\((x\multimap y) \otimes (y\multimap z) \leq (x\multimap z)\\). (EDIT: Oh I see this is the same proof, but you spelled it out in a bit more detail!)`

Sure, but it's important to note that we are using commutativity to flip (B).

Again, you are using commutativity...

That's pedantry, I know. The proof is ugly and long if we don't just use commutativity implicitly.

However, I am not sure if this theorem is true in a closed non-commutative monoidal preorder.

`> I think we can simplify that slightly @Matthew > > We have your (A) and (B), ie \\(x\otimes (x\multimap y) \leq y\\) and \\(y \otimes (y\multimap z) \leq z\\). Sure, but it's important to note that we are using commutativity to flip (B). > Therefore \\(x\otimes (x\multimap y) \otimes (y\multimap z) \leq y \otimes (y\multimap z) \leq z\\). > > So by adjunction \\((x\multimap y) \otimes (y\multimap z) \leq (x\multimap z)\\). Again, you are using commutativity... That's pedantry, I know. The proof is ugly and long if we don't just use commutativity implicitly. However, I am not sure if this theorem is true in a closed non-commutative monoidal preorder.`

One detail that puzzles me about the adjunction: the maps \((x\otimes -)\) and \((x\multimap -)\) are monotone but they don't seem to (necessarily) be

monoidalmonotone. So this is an adjunction between preorders, not an adjunction between monoidal preorders. That seems a bit unexpected to me.`One detail that puzzles me about the adjunction: the maps \\((x\otimes -)\\) and \\((x\multimap -)\\) are monotone but they don't seem to (necessarily) be *monoidal* monotone. So this is an adjunction between preorders, not an adjunction between monoidal preorders. That seems a bit unexpected to me.`

Anindya wrote:

You know, there might be a typo in the lecture notes.

I usually see \((x\otimes -) \dashv (x\multimap -)\). For instance, this is how the Haskell adjunctions library defines them (see the hackage docs).

But in the lecture notes, John wrote

So technically \( (- \otimes x) \dashv (x\multimap -)\) if we don't assume commutativity.

If we go instead with

$$ x \otimes a \le y \text{ if and only if } a \le x \multimap y \tag{✴'} $$ Then your quick proof in #6 works, the theorem we proved holds without demanding commutativity, and \((x\otimes -) \dashv (x\multimap -)\) like you say.

`[Anindya](https://forum.azimuthproject.org/discussion/comment/20082/#Comment_20082) wrote: > One detail that puzzles me about the adjunction: the maps \\((x\otimes -)\\) and \\((x\multimap -)\\) are monotone but ... You know, there might be a typo in the lecture notes. I usually see \\((x\otimes -) \dashv (x\multimap -)\\). For instance, this is how the Haskell adjunctions library defines them (see [the hackage docs](https://hackage.haskell.org/package/adjunctions-4.0.2/docs/Data-Functor-Adjunction.html#t:Adjunction)). But in the lecture notes, John wrote > \[ a \otimes x \le y \text{ if and only if } a \le x \multimap y \tag{✴} \] So technically \\( (- \otimes x) \dashv (x\multimap -)\\) if we don't assume commutativity. If we go instead with \[ x \otimes a \le y \text{ if and only if } a \le x \multimap y \tag{✴'} \] Then your quick proof in [#6](https://forum.azimuthproject.org/discussion/comment/20080/#Comment_20080) works, the theorem we proved holds without demanding commutativity, and \\((x\otimes -) \dashv (x\multimap -)\\) like you say.`

I've been thinking about the case when \(\otimes\) is not symmetric.

As @Matthew says, we can turn \(\mathcal{V}\) into a \(\mathcal{V}\)-enriched preorder if \((x\otimes -)\) has a right adjoint.

If on the other hand it's \((-\otimes x)\) that has a right adjoint, the proof doesn't work. However in this case we could slightly vary the definition of a \(\mathcal{V}\)-enriched category to use right-to-left composition instead of left-to-right composition.

This amount to replacing the \(\mathcal{V}(x, y)\otimes\mathcal{V}(y, z)\leq\mathcal{V}(x, z)\) condition with \(\mathcal{V}(y, z)\otimes\mathcal{V}(x, y)\leq\mathcal{V}(x, z)\) – similarly to how we define \(\text{hom}\) in a \(\textbf{Set}\)-category. Then the proof would go through.

So whether to go with \((x\otimes -)\) or \((-\otimes x)\) depends on which way round we write composites.

A speculative interpretation of this: we could read the non-symmetric \(A \otimes B\) as "A and then B". In this case a right adjoint of \(A \otimes -\) would be like a permit to turn any A

that you've already gotinto a B, because \(A \otimes (A \multimap B) \leq B\), while a right adjoint of \(- \otimes A\) would be a permit to turn any Athat you get in the futureinto a B, because \((A \multimap B)\otimes A \leq B\). Maybe there's some "time-conscious" logic sitting in here that might be useful in some situations.`I've been thinking about the case when \\(\otimes\\) is not symmetric. As @Matthew says, we can turn \\(\mathcal{V}\\) into a \\(\mathcal{V}\\)-enriched preorder if \\((x\otimes -)\\) has a right adjoint. If on the other hand it's \\((-\otimes x)\\) that has a right adjoint, the proof doesn't work. However in this case we could slightly vary the definition of a \\(\mathcal{V}\\)-enriched category to use right-to-left composition instead of left-to-right composition. This amount to replacing the \\(\mathcal{V}(x, y)\otimes\mathcal{V}(y, z)\leq\mathcal{V}(x, z)\\) condition with \\(\mathcal{V}(y, z)\otimes\mathcal{V}(x, y)\leq\mathcal{V}(x, z)\\) – similarly to how we define \\(\text{hom}\\) in a \\(\textbf{Set}\\)-category. Then the proof would go through. So whether to go with \\((x\otimes -)\\) or \\((-\otimes x)\\) depends on which way round we write composites. A speculative interpretation of this: we could read the non-symmetric \\(A \otimes B\\) as "A and then B". In this case a right adjoint of \\(A \otimes -\\) would be like a permit to turn any A *that you've already got* into a B, because \\(A \otimes (A \multimap B) \leq B\\), while a right adjoint of \\(- \otimes A\\) would be a permit to turn any A *that you get in the future* into a B, because \\((A \multimap B)\otimes A \leq B\\). Maybe there's some "time-conscious" logic sitting in here that might be useful in some situations.`

Just thinking out loud here...

If we define a function called \(\mathrm{when}\),

\[ \mathrm{when}(b,x) :\mathbf{Bool}\otimes \mathcal{X} \to \mathcal{X} \\ := \text{if } b \text{ then } x \text{ else } \varnothing, \]

then \(\mathrm{when}\) is adjoint (in fact equivalent to) to taking the Cartesian product with a Boolean variable,

\[ (b \times -) \vdash \mathrm{when}(b,-). \]

So then a \(\mathbf{Cost}\)-morphism is something like \(\mathrm{when}(x\multimap y,r)\), ie are \(\mathbf{Bool}\)-morphisms that are labeled by a real number.

`Just thinking out loud here... If we define a function called \\(\mathrm{when}\\), \\[ \mathrm{when}(b,x) :\mathbf{Bool}\otimes \mathcal{X} \to \mathcal{X} \\\\ := \text{if } b \text{ then } x \text{ else } \varnothing, \\] then \\(\mathrm{when}\\) is adjoint (in fact equivalent to) to taking the Cartesian product with a Boolean variable, \\[ (b \times -) \vdash \mathrm{when}(b,-). \\] So then a \\(\mathbf{Cost}\\)-morphism is something like \\(\mathrm{when}(x\multimap y,r)\\), ie are \\(\mathbf{Bool}\\)-morphisms that are labeled by a real number.`

Anindya wrote:

This is just a mistake - I'll fix it, thanks!

I repeatedly amaze myself by my inability to stick to arbitrary conventions. In my defense I'll mention that there's a heated and pointless debate among category theorists about which convention is better. It doesn't really matter which you use as long as you stick with it, but people who get used to one find the other counterintuitive. I'm

tryingto use Fong and Spivak's convention \(\mathcal{X}^\text{op}\times\mathcal{Y}\rightarrow\mathcal{V}\), and this is actually my favorite convention, mainly because it makes the hom-functor$$ \text{hom} : \mathcal{C}^{\text{op}} \times \mathcal{C} \to \mathbf{Set} $$ into a profunctor.

(We are currently just studying

enrichedprofunctors betweenenrichedcategories, and for a \(\mathcal{V}\)-enriched category \(\mathcal{C}\) will have an enriched profunctor$$ \text{hom} : \mathcal{C}^{\text{op}} \times \mathcal{C} \to \mathcal{V}, $$ but the idea is just the same for ordinary categories and ordinary profunctors.)

`Anindya wrote: > possible typo: in previous lectures we've defined profunctors as \\(\mathcal{V}\\)-enriched functors \\(\mathcal{X}^\text{op}\times\mathcal{Y}\rightarrow\mathcal{V}\\) but here we're using \\(\mathcal{X}\times\mathcal{Y}^\text{op}\rightarrow\mathcal{V}\\) – is this a mistake or are we swapping round for a reason? This is just a mistake - I'll fix it, thanks! I repeatedly amaze myself by my inability to stick to arbitrary conventions. In my defense I'll mention that there's a heated and pointless debate among category theorists about which convention is better. It doesn't really matter which you use as long as you stick with it, but people who get used to one find the other counterintuitive. I'm _trying_ to use Fong and Spivak's convention \\(\mathcal{X}^\text{op}\times\mathcal{Y}\rightarrow\mathcal{V}\\), and this is actually my favorite convention, mainly because it makes the hom-functor \[ \text{hom} : \mathcal{C}^{\text{op}} \times \mathcal{C} \to \mathbf{Set} \] into a profunctor. (We are currently just studying _enriched_ profunctors between _enriched_ categories, and for a \\(\mathcal{V}\\)-enriched category \\(\mathcal{C}\\) will have an enriched profunctor \[ \text{hom} : \mathcal{C}^{\text{op}} \times \mathcal{C} \to \mathcal{V}, \] but the idea is just the same for ordinary categories and ordinary profunctors.)`

Matthew wrote:

This is an interesting issue. I was using the convention in Fong and Spivak's book (see Section 2.5.1), and I should stick with that to avoid confusion. It could be that in the noncommutative case the convention you mention here works better. I will avoid trouble by the simple expedient of assuming \(\mathcal{V}\) is commutative. But there's more to say...

The book mainly focuses on categories enriched over commutative monoidal posets - or symmetric monoidal preorders, which work more or less the same way. Things get more fussy if we drop the assumption of commutativity, or symmetry, and certain things just don't work at all.

For example, a \(\mathcal{V}\)-enriched category has an 'opposite' when \(\mathcal{V}\) is symmetric monoidal but not, I believe, when \(\mathcal{V}\) is merely monoidal! To define composition in the would-be opposite you need to switch two things in \(\mathcal{V}\past each other.

Similarly, we can take the product of two \(\mathcal{V}\)-enriched categories when \(\mathcal{V}\) is symmetric monoidal but not, I believe, when \(\mathcal{V}\) is merely monoidal. Again, to define composition we need to switch two things in \(\mathcal{V}\) past each other.

We will see these things soon.

For these two reasons it's hopeless (I believe) to develop the theory of enriched profunctors when \(\mathcal{V}\) is merely monoidal. Thus, I could have spared myself some grief by assuming \(\mathcal{V}\) is a commutative monoidal poset throughout this lecture. But in fact closed monoidal categories, and closed monoidal posets, are interesting even in the noncommutative case! So I couldn't resist getting into trouble.

I will rewrite the lecture to avoid this issue by assuming commutativity. The reason is that in the noncommutative case one must really distinguish between

left closedandright closedmonoidal posets. In one, the operation \(a \otimes -\) has a right adjoint for each \(a\). In the other, the operation \( - \otimes a\) has a right adjoint for each \(a\).(When we want to distinguish these two, we do it by turning around the lollipop in \(\multimap\). I don't know how to do that in this TeX installation!)

Puzzle.You can think of a monoid as a 'discrete' monoidal poset, meaning one where \(x \le y\) iff \(x = y\). Show that a monoid which isgroupgives a monoidal poset that is both left closed and right closed.A monoidal poset (or monoidal category) that's both left and right closed is called

biclosed.You're raising the issue of whether it's

left closedorright closedmonoidal posets that become enriched over themselves... or both... orneither. You may have already settled this, but my instinct is that if one works, the other must too! The reason is that I don't believe the concept of "enriched category" has a left/right asymmetry built into it: I don't think there are "left" and "right" enriched categories.`Matthew wrote: > If we go instead with > \[ x \otimes a \le y \text{ if and only if } a \le x \multimap y \tag{✴'} \] > Then your quick proof in [#6](https://forum.azimuthproject.org/discussion/comment/20080/#Comment_20080) works, the theorem we proved holds without demanding commutativity, and \\((x\otimes -) \dashv (x\multimap -)\\) like you say. This is an interesting issue. I was using the convention in Fong and Spivak's book (see Section 2.5.1), and I should stick with that to avoid confusion. It could be that in the noncommutative case the convention you mention here works better. I will avoid trouble by the simple expedient of assuming \\(\mathcal{V}\\) is commutative. But there's more to say... <img width = "100" src = "http://math.ucr.edu/home/baez/mathematical/warning_sign.jpg"> The book mainly focuses on categories enriched over commutative monoidal posets - or symmetric monoidal preorders, which work more or less the same way. Things get more fussy if we drop the assumption of commutativity, or symmetry, and certain things just don't work at all. For example, a \\(\mathcal{V}\\)-enriched category has an 'opposite' when \\(\mathcal{V}\\) is symmetric monoidal but not, I believe, when \\(\mathcal{V}\\) is merely monoidal! To define composition in the would-be opposite you need to switch two things in \\(\mathcal{V}\\past each other. Similarly, we can take the product of two \\(\mathcal{V}\\)-enriched categories when \\(\mathcal{V}\\) is symmetric monoidal but not, I believe, when \\(\mathcal{V}\\) is merely monoidal. Again, to define composition we need to switch two things in \\(\mathcal{V}\\) past each other. We will see these things soon. For these two reasons it's hopeless (I believe) to develop the theory of enriched profunctors when \\(\mathcal{V}\\) is merely monoidal. Thus, I could have spared myself some grief by assuming \\(\mathcal{V}\\) is a commutative monoidal poset throughout this lecture. But in fact closed monoidal categories, and closed monoidal posets, are interesting even in the noncommutative case! So I couldn't resist getting into trouble. I will rewrite the lecture to avoid this issue by assuming commutativity. The reason is that in the noncommutative case one must really distinguish between **left closed** and **right closed** monoidal posets. In one, the operation \\(a \otimes -\\) has a right adjoint for each \\(a\\). In the other, the operation \\( - \otimes a\\) has a right adjoint for each \\(a\\). (When we want to distinguish these two, we do it by turning around the lollipop in \\(\multimap\\). I don't know how to do that in this TeX installation!) **Puzzle.** You can think of a monoid as a 'discrete' monoidal poset, meaning one where \\(x \le y\\) iff \\(x = y\\). Show that a monoid which is _group_ gives a monoidal poset that is both left closed and right closed. A monoidal poset (or monoidal category) that's both left and right closed is called **biclosed**. You're raising the issue of whether it's _left closed_ or _right closed_ monoidal posets that become enriched over themselves... or both... or _neither_. You may have already settled this, but my instinct is that if one works, the other must too! The reason is that I don't believe the concept of "enriched category" has a left/right asymmetry built into it: I don't think there are "left" and "right" enriched categories.`

Anindya wrote:

Hmm, as mentioned in my previous comment I don't see a left/right asymmetry built into the definition of enriched category:

The interesting thing is that you can interpret \(\mathcal{X}(x,y)\) as 'morphisms from \(x\) to \(y\)' or 'morphisms from \(y\) to \(x\)' and the definition makes sense either way!

Are you suggesting that we could switch to using

$$ \mathcal{X}(y,z)\otimes \mathcal{X}(x,y) \leq\mathcal{X}(x,z)? $$ We could, but you'll notice this isn't just a left/right reflection of the usual definition: I could explain the difference to someone who can't tell the difference between left and right! In the usual definition, the two \(y\)'s here are next to each other:

$$ \mathcal{X}(x,y)\otimes\mathcal{X}(y,z) $$ while in the modified definition they aren't.

`<img width = "100" src = "http://math.ucr.edu/home/baez/mathematical/warning_sign.jpg"> Anindya wrote: > However in this case we could slightly vary the definition of a \\(\mathcal{V}\\)-enriched category to use right-to-left composition instead of left-to-right composition. Hmm, as mentioned in my previous comment I don't see a left/right asymmetry built into the definition of enriched category: > **Definition.** A **\\(\mathcal{V}\\)-enriched category** \\(\mathcal{X}\\) consists of two parts, satisfying two properties. First: > 1. one specifies a set \\(\mathrm{Ob}(\mathcal{X})\\), elements of which are called **objects**; > 2. for every two objects \\(x,y\\), one specifies an element \\(\mathcal{X}(x,y)\\) of \\(\mathcal{V}\\). > Then: > a) for every object \\(x\in\text{Ob}(\mathcal{X})\\) we require that > \[ I\leq\mathcal{X}(x,x) .\] > b) for every three objects \\(x,y,z\in\mathrm{Ob}(\mathcal{X})\\), we require that > \[ \mathcal{X}(x,y)\otimes\mathcal{X}(y,z)\leq\mathcal{X}(x,z). \] The interesting thing is that you can interpret \\(\mathcal{X}(x,y)\\) as 'morphisms from \\(x\\) to \\(y\\)' or 'morphisms from \\(y\\) to \\(x\\)' and the definition makes sense either way! Are you suggesting that we could switch to using \[ \mathcal{X}(y,z)\otimes \mathcal{X}(x,y) \leq\mathcal{X}(x,z)? \] We could, but you'll notice this isn't just a left/right reflection of the usual definition: I could explain the difference to someone who can't tell the difference between left and right! In the usual definition, the two \\(y\\)'s here are next to each other: \[ \mathcal{X}(x,y)\otimes\mathcal{X}(y,z) \] while in the modified definition they aren't.`

Okay, you actually are suggesting that:

Sorry, I'm not always good at reading what people write!

`Okay, you actually are suggesting that: > This amount to replacing the \\(\mathcal{V}(x, y)\otimes\mathcal{V}(y, z)\leq\mathcal{V}(x, z)\\) condition with \\(\mathcal{V}(y, z)\otimes\mathcal{V}(x, y)\leq\mathcal{V}(x, z)\\) – similarly to how we define \\(\text{hom}\\) in a \\(\textbf{Set}\\)-category. Then the proof would go through. Sorry, I'm not always good at reading what people write!`

Anindya wrote:

It's actually familiar. One fundamental example of a monoidal preorder is a

group, with \(x \le y\) iff \(x = y\), with \( x \otimes y\) defined to be the product \(xy\). This is closed if we define \(x \multimap y = yx^{-1} \), since the definition of 'closed'$$ a \otimes x \le y \text{ if and only if } a \le x \multimap y $$ turns into

$$ ax = y \text{ if and only if } a = yx^{-1} $$ The moral is:

But back to your point: multiplying by \(x\) is not a group homomorphism, nor is dividing by \(x\):

$$ (aa')x \ne (ax)(a'x) $$ and

$$ (yy')x^{-1} \ne (yx^{-1}) (y' {x}^{-1}) .$$ So, in the general case, we shouldn't want the maps \((x\otimes -)\) and \((x\multimap -)\) to be monoidal.

`Anindya wrote: > One detail that puzzles me about the adjunction: the maps \\((x\otimes -)\\) and \\((x\multimap -)\\) are monotone but they don't seem to (necessarily) be *monoidal* monotone. So this is an adjunction between preorders, not an adjunction between monoidal preorders. That seems a bit unexpected to me. It's actually familiar. One fundamental example of a monoidal preorder is a _group_, with \\(x \le y\\) iff \\(x = y\\), with \\( x \otimes y\\) defined to be the product \\(xy\\). This is closed if we define \\(x \multimap y = yx^{-1} \\), since the definition of 'closed' \[ a \otimes x \le y \text{ if and only if } a \le x \multimap y \] turns into \[ ax = y \text{ if and only if } a = yx^{-1} \] The moral is: > **The monoidal structure is to multiplication as the closed structure is to division.** But back to your point: multiplying by \\(x\\) is not a group homomorphism, nor is dividing by \\(x\\): \[ (aa')x \ne (ax)(a'x) \] and \[ (yy')x^{-1} \ne (yx^{-1}) (y' {x}^{-1}) .\] So, in the general case, we shouldn't want the maps \\((x\otimes -)\\) and \\((x\multimap -)\\) to be monoidal.`

John wrote:

Okay, that makes things clearer.

I think the usual symbol is

`\multimapinv`

, but it doesn't work here. However, if you don't mind copy-pasting unicode, you can use \(⟜\) which works fine.`John wrote: > For these two reasons it's hopeless (I believe) to develop the theory of enriched profunctors when \\(\mathcal{V}\\) is merely monoidal. Thus, I could have spared myself some grief by assuming \\(\mathcal{V}\\) is a commutative monoidal poset throughout this lecture. But in fact closed monoidal categories, and closed monoidal posets, are interesting even in the noncommutative case! So I couldn't resist getting into trouble. Okay, that makes things clearer. > The reason is that in the noncommutative case one must really distinguish between **left closed** and **right closed** monoidal posets. In one, the operation \\(a \otimes -\\) has a right adjoint for each \\(a\\). In the other, the operation \\( - \otimes a\\) has a right adjoint for each \\(a\\). > > (When we want to distinguish these two, we do it by turning around the lollipop in \\(\multimap\\). I don't know how to do that in this TeX installation!) I think the usual symbol is `\multimapinv`, but it doesn't work here. However, if you don't mind copy-pasting unicode, you can use \\(⟜\\) which works fine.`

I've decided to flip the definition of 'closed monoidal category' around a bit to make it nicer in the noncommutative case, following the suggestions of Anindya and Matthew. In the commutative case, which is the main case we care about, this doesn't change anything. But it will make Lecture 61 a bit smoother!

`I've decided to flip the definition of 'closed monoidal category' around a bit to make it nicer in the noncommutative case, following the suggestions of Anindya and Matthew. In the commutative case, which is the main case we care about, this doesn't change anything. But it will make Lecture 61 a bit smoother!`

Interesting, in a class on sub-structural type theory they used / and \ for ordered implication/closure.

`Interesting, in a class on sub-structural type theory they used / and \ for ordered implication/closure.`

A closed monoidal poset that happens to be lattice is called

residuated lattice.Some textbooks (and Wikipedia) denote \(x \multimap z\) with \(x / z\) and call it the

right residual of \(z\) by \(x\). Dually they denote \(z ⟜ y\) as theleft residual of \(z\) by \(y\)and it is denoted with \(z \backslash y\).The "lollipop" \(\multimap\) was, AFAIK, introduced by Jean-Yves Girard in

Linear Logic(1987). Just as fragments of intuitionistic logic can be given semantics inCartesian Closed Categories(CCC)s, the \(\otimes,\multimap\)-fragement of linear logic can be given semantics inSymmetric Monoidal Closed Categories(SMCCs). There is a nice discussion of this inIntroduction to Categories and Categorical Logic (2011)by Abramsky and Tzevelekos.`> Interesting, in a class on sub-structural they used / and \ for ordered implication/closure. A closed monoidal poset that happens to be lattice is called [*residuated lattice*](https://en.wikipedia.org/wiki/Residuated_lattice#Definition). Some textbooks (and Wikipedia) denote \\(x \multimap z\\) with \\(x / z\\) and call it the *right residual of \\(z\\) by \\(x\\)*. Dually they denote \\(z ⟜ y\\) as the *left residual of \\(z\\) by \\(y\\)* and it is denoted with \\(z \backslash y\\). The "lollipop" \\(\multimap\\) was, AFAIK, introduced by Jean-Yves Girard in [*Linear Logic* (1987)](https://www.sciencedirect.com/science/article/pii/0304397587900454). Just as fragments of intuitionistic logic can be given semantics in *Cartesian Closed Categories* (CCC)s, the \\(\otimes,\multimap\\)-fragement of linear logic can be given semantics in *Symmetric Monoidal Closed Categories* (SMCCs). There is a nice discussion of this in [*Introduction to Categories and Categorical Logic (2011)*](https://arxiv.org/pdf/1102.1313.pdf) by Abramsky and Tzevelekos.`

Yes, I think Girard introduced the lollipop along with some other strange symbols like the upside-down and.

In logic and physics we mainly use

braidedandsymmetricmonoidal closed categories, and I wrote an introduction to those here:New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-172.The first time I saw really interesting applications of closed monoidal categories that weren't symmetric or even braided was in Lambek's work on linguistics. When you don't have a braiding isomorphism \(x \otimes y \cong y \otimes x\) you need to distinguish between left and right closed monoidal categories, which have two operations x⊸y and y⟜x, or in other words x\y and y/x. Lambek uses these to describe grammatical operations! His

pregroupsare monoidal preorders that are both left and right closed. My student Jade and another student at ACT2018 wrote a pretty good introduction to this idea, which is pretty simple:The n-Category Café, 6 February 2018.`Yes, I think Girard introduced the lollipop along with some other strange symbols like the upside-down and. In logic and physics we mainly use _braided_ and _symmetric_ monoidal closed categories, and I wrote an introduction to those here: * John Baez and Mike Stay, [Physics, topology, logic and computation: a Rosetta Stone](http://arxiv.org/abs/0903.0340) in _New Structures for Physics_, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-172. The first time I saw really interesting applications of closed monoidal categories that weren't symmetric or even braided was in Lambek's work on linguistics. When you don't have a braiding isomorphism \\(x \otimes y \cong y \otimes x\\) you need to distinguish between left and right closed monoidal categories, which have two operations x⊸y and y⟜x, or in other words x\y and y/x. Lambek uses these to describe grammatical operations! His **pregroups** are monoidal preorders that are both left and right closed. My student Jade and another student at ACT2018 wrote a pretty good introduction to this idea, which is pretty simple: * Jade Master and Cory Griffith, [Linguistics using category theory](https://golem.ph.utexas.edu/category/2018/02/linguistics_using_category_the.html), _The n-Category Café_, 6 February 2018.`

I did not know about the application to linguistics. This is really cool John! Thanks for the reference!

`I did not know about the application to linguistics. This is really cool John! Thanks for the reference!`

Sure! Lambek's original papers are also very clear.

Do you know any other good applications of left and right residuated monoidal posets that aren't commutative?

`Sure! Lambek's original papers are also very clear. Do you know any other good applications of left and right residuated monoidal posets that aren't commutative?`

New Structures for Physics, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-172.I found the string diagram for lollipops from the paper above and redrew them showing \( a \otimes x \le y \text{ if and only if } a \le x \multimap y \). It's a pretty dynamic symbol propping up the string on the other side.

`* John Baez and Mike Stay, [Physics, topology, logic and computation: a Rosetta Stone](http://arxiv.org/abs/0903.0340) in _New Structures for Physics_, ed. Bob Coecke, Lecture Notes in Physics vol. 813, Springer, Berlin, 2011, pp. 95-172. I found the string diagram for lollipops from the paper above and redrew them showing \\( a \otimes x \le y \text{ if and only if } a \le x \multimap y \\). It's a pretty dynamic symbol propping up the string on the other side. ![lollipop string diagram](http:\\aether.co.kr/images/lollipop_string_diagram.svg)`

Hey John,

The ones I've encountered are

action algebras.These extend

regular expressions, which are insanely common in computer programming. For instance, if you try to sign up for a website, programmers do not want you to give an invalid email. The programmer will check that your email matches a pattern like`^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+.[a-zA-Z0-9-.]+$`

(I lifted that from this stack overflow)

Suppose I had three regular expression:

I can combine these to match a line of text where there's an email, a comma, and a phone number (lots of files are like this). This is done using a

monoidal tensor. I've seen this tensor denoted \(;\) in Propositional Dynamic Logic and programming language design courses so I'll use that notation.So we can make a new regular expression like this:

$$\mathtt{email} ; \mathtt{comma} ; \mathtt{phone}$$ Composition here is

notcommutative so this will not match a phone followed by a comma follows by an email.There's also a regular expression \(I\) that just matches an empty string, and plays the role of identity \(I ; R = R ; I = R\).

We can pre-order regular expressions too: \(A \leq B\) if any text \(A\) matches then \(B\) matches it.

Action algebras explore what programming is like if \((;)\) had left and right adjoints such that

$$(- \leftarrow A) \dashv (A ; -) \dashv (A \to -) $$ Real world regular expressions never implement this, but these residuals are still useful for understanding regular expressions. For instance, action algebras are finitely axiomatizable and form a variety. Regular expressions correspond to a fragment of this variety. Regular expressions are remarkably

notfinitely axiomatizable! One proof of this comes from none other than John Conway of surreal-numbers and game-of-life fame.`Hey John, > Do you know any other good applications of left and right residuated monoidal posets that aren't commutative? The ones I've encountered are [*action algebras*](https://en.wikipedia.org/wiki/Action_algebra). These extend [*regular expressions*](https://en.wikipedia.org/wiki/Regular_expression), which are insanely common in computer programming. For instance, if you try to sign up for a website, programmers do not want you to give an invalid email. The programmer will check that your email matches a pattern like <center><code>^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$</code></center> (I lifted that from this [stack overflow](https://stackoverflow.com/a/719543)) Suppose I had three regular expression: - one called \\(\mathtt{email}\\) for checking emails - one called \\(\mathtt{comma}\\) for checking there's a comma - one called \\(\mathtt{phone}\\) for checking phone numbers I can combine these to match a line of text where there's an email, a comma, and a phone number (lots of files are like this). This is done using a *monoidal tensor*. I've seen this tensor denoted \\(;\\) in [Propositional Dynamic Logic](https://plato.stanford.edu/entries/logic-dynamic/) and programming language design courses so I'll use that notation. So we can make a new regular expression like this: \[\mathtt{email} ; \mathtt{comma} ; \mathtt{phone}\] Composition here is *not* commutative so this will not match a phone followed by a comma follows by an email. There's also a regular expression \\(I\\) that just matches an empty string, and plays the role of identity \\(I ; R = R ; I = R\\). We can pre-order regular expressions too: \\(A \leq B\\) if any text \\(A\\) matches then \\(B\\) matches it. Action algebras explore what programming is like if \\((;)\\) had left and right adjoints such that \[(- \leftarrow A) \dashv (A ; -) \dashv (A \to -) \] Real world regular expressions never implement this, but these residuals are still useful for understanding regular expressions. For instance, action algebras are finitely axiomatizable and form a variety. Regular expressions correspond to a fragment of this variety. Regular expressions are remarkably *not* finitely axiomatizable! One proof of this comes from none other than [John Conway](https://en.wikipedia.org/wiki/Kleene_algebra#History) of surreal-numbers and game-of-life fame.`

Ordered types can be used to describe elements of a (possibly bi-directional) pipeline running asynchronously. (If its synchronous I think all you need is subsignleton types.) See notes for lectures 5-10 (sep 13-sep 29) of http://www.cs.cmu.edu/~fp/courses/15816-f16/schedule.html

`Ordered types can be used to describe elements of a (possibly bi-directional) pipeline running asynchronously. (If its synchronous I think all you need is subsignleton types.) See notes for lectures 5-10 (sep 13-sep 29) of http://www.cs.cmu.edu/~fp/courses/15816-f16/schedule.html`

I am confused, what does this have to do with residuated lattices over non-commutative monoids?

`> Ordered types can be used to describe elements of a (possibly bi-directional) pipeline running asynchronously. (If its synchronous I think all you need is subsignleton types.) See notes for lectures 5-10 (sep 13-sep 29) of http://www.cs.cmu.edu/~fp/courses/15816-f16/schedule.html I am confused, what does this have to do with residuated lattices over non-commutative monoids?`

Because \( (\bullet, /, \\ ) \) is one if I understand correctly.

`Because \\( (\bullet, /, \\\ ) \\) is one if I understand correctly.`

Okay, the Frank Pfenning lecture notes you linked do have a bunch of substructural logics with things that behave like residuals. These aren't exactly residuated lattices, since Prof. Pfenning holds on to proof terms and has multiple assumptions. This is because he's trying to give denotational semantics for programs given some background context.

If you drop the proof terms, and restrict yourself to the single-premise and single conclusion fragment of Prof. Pfenning's sequent calculi, you can recover a preorder using the turnstyle \(\vdash\) he defines. It looks like some work to show the meta-theorem \(X \bullet Y \vdash Z \iff Y \vdash X / Z\).

`Okay, the Frank Pfenning lecture notes you linked do have a bunch of substructural logics with things that behave like residuals. These aren't exactly residuated lattices, since Prof. Pfenning holds on to proof terms and has multiple assumptions. This is because he's trying to give denotational semantics for programs given some background context. If you drop the proof terms, and restrict yourself to the single-premise and single conclusion fragment of Prof. Pfenning's sequent calculi, you can recover a preorder using the turnstyle \\(\vdash\\) he defines. It looks like some work to show the meta-theorem \\(X \bullet Y \vdash Z \iff Y \vdash X / Z\\).`

Yeah, I kind of forgot about the

latticepart. Though I think if you are willing to work with preorders instead of posets you can lift the lattice on the types into a lattice-like-preorder on terms.`Yeah, I kind of forgot about the _lattice_ part. Though I think if you are willing to work with preorders instead of posets you can lift the lattice on the types into a lattice-like-preorder on terms.`