Lecture 30 - Chapter 2: Preorders as Enriched Categories

John Baez · May 2018

Okay, last time I dumped the definition of "enriched category" on you. Now let's figure out what it does! To get going we need to pick a monoidal preorder $\mathcal{V}$. Then:

Definition. A $\mathcal{V}$-enriched category, say $\mathcal{X}$, consists of:

a set of objects, $\mathrm{Ob}(\mathcal{X})$, and
an element $\mathcal{X}(x,y) \in \mathcal{V}$ for any pair of objects $x,y$.

such that:

a) $ I\leq\mathcal{X}(x,x) $ for any object $x$, and

b) $ \mathcal{X}(x,y)\otimes\mathcal{X}(y,z)\leq\mathcal{X}(x,z) $ for any objects $x,y,z$.

We often say "$\mathcal{V}$-category" instead of $\mathcal{V}$-enriched category, just to save time. Life is short.

To understand this definition, we need examples! The simplest interesting example is $\mathcal{V} = \mathbf{Bool}$. This is the set of Booleans, or "truth values":

$$ \mathbf{Bool} = \{ \texttt{true}, \texttt{false} \} . $$ It's a poset where $x \le y$ means "$x$ implies $y$". Namely, $ \texttt{false} \le \texttt{true} $ and everything is less than or equal to itself, and that's all. We make it monoidal by taking $x \otimes y$ to mean "$x$ and $y$", so the unit $I$ is $\texttt{true}$. Let's see what this gives.

Theorem. A $\mathbf{Bool}$-category is a preorder.

Proof. Let's start with a $\mathbf{Bool}$-category and see what it actually amounts to. A $\mathbf{Bool}$-enriched category, say $\mathcal{X}$, consists of:

a set of objects, $\mathrm{Ob}(\mathcal{X})$ and
an element $\mathcal{X}(x,y) \in \mathbf{Bool} $ for any two objects $x,y$

So, we get a truth value for each pair $x,y$. Let's make up a relation $\le$ on $ \mathrm{Ob}(\mathcal{X})$ such that $x \le y$ is true when $ \mathcal{X}(x,y) = \texttt{true}$, and false when $ \mathcal{X}(x,y) = \texttt{false}$.

In our example this means

$$ \texttt{true} \textrm{ implies that } x \le x . $$ In other words, $x \le x$ is true. So this is just the reflexive law for $\le$!

b) $ \mathcal{X}(x,y)\otimes\mathcal{X}(y,z)\leq\mathcal{X}(x,z) $ for any objects $x,y,z$.

In our example this means

$$ x \le y \textrm{ and } y \le z \textrm{ implies } x \le z .$$ So this is just the transitive law for $\le$!

It's easy to turn this argument around and get the converse: any preorder gives a $\mathbf{Bool}$-category $\mathcal{X}$ if we define $ \mathcal{X}(x,y) = \texttt{true}$ when $x \le y$ and $ \mathcal{X}(x,y) = \texttt{false}$ otherwise. $ \qquad \blacksquare $

Yee-hah! We've managed to define preorders in a new, more abstract, more confusing way!

But of course that's not our goal. That was just a warmup. A much cooler example occurs when we take $\mathcal{V} = \mathbf{Cost}$. This is the set of costs, or non-negative real numbers including infinity:

$$ \mathbf{Cost} = [0,\infty] . $$ It's a poset where the order is defined in the opposite of the usual way: we use $\ge$ instead of $\le$. It becomes a monoidal using addition, with $0$ as the unit. In case you're nervous about infinity, this means that $x + \infty = \infty = \infty + x$ and $x \le \infty$ for all $x$.

Puzzle 88. Show that these choices actually makes $ \mathbf{Cost}$ into a symmetric monoidal poset.

Puzzle 89. Figure out exactly what a $\mathbf{Cost}$-category is, starting with the definition above. Again, what matters is not your final answer so much as your process of deducing it!

Hint: given a $\mathbf{Cost}$-category $\mathcal{X}$, write $\mathcal{X}(x,y)$ as $d(x,y)$ and call it the distance between the objects $x,y \in \mathrm{Ob}(\mathcal{X})$. The axioms of an enriched category then say interesting things about "distance".

To read other lectures go here.

Keith E. Peterson · May 2018

Puzzle 89. Figure out exactly what a $\mathbf{Cost}$-category is, starting with the definition above. Again, what matters is not your final answer so much as your process of deducing it!

Hint: given a $\mathbf{Cost}$-category $\mathcal{X}$, write $\mathcal{X}(x,y)$ as $d(x,y)$ and call it the distance between the objects $x,y \in \mathrm{Ob}(\mathcal{X})$. The axioms of an enriched category then say interesting things about "distance".

Both the book (on page 53) and Simon Willerton, on his Catester videos on enriched categories, spill the beans that such a $\mathbf{Cost}$- or $ \mathbb{R}_+ $-category is a metric space.

Now I'm not sure if proof by book or proof by Catster will count, but you did want us to get creative with the proving process.

Anyways, joking aside... For those wanting to give a proof, I would recommend reading 'Seven Sketches' and watching that video playlist.

John Baez · May 2018

Keith wrote:

such a $\mathbf{Cost}$-category is a metric space.

Not true. Work it out and see! It's quicker to work it out than to watch a video. It's also much better for your brain: ultimately, learning math is about learning to think, not watching other people do it. You can watch exercise videos all day and not be any stronger.

Keith E. Peterson · May 2018

Oh, wait. You're right. It isn't a proper metric space.

John Baez · May 2018

There you go. Just follow the definition and see where it leads.

Note: in comments #5 and #6, Keith and Jonathan were figuring out what a $\mathbf{Cost}$-category was based on my original wrong definition of this preorder! In fact you have to deliberately turn around the definition of $\le$ to get something good here. I've subsequently fixed my lecture.

Keith E. Peterson · May 2018

Definition. A $\mathbf{Cost}$- or $ \mathbb{R}_+ $-category, say $\mathcal{d}$, consists of:

a set of objects, $\mathrm{Ob}(\mathcal{d})$, and
an element $\mathcal{d}(x,y) \in \mathbb{R}_+$ for any pair of objects $x,y$.

such that:

a) $ 0\leq\mathcal{d}(x,x) $ for any object $x$, and

b) $ \mathcal{d}(x,y) + \mathcal{d}(y,z)\leq\mathcal{d}(x,z) $ for any objects $x,y,z$.

(Here I'm calling my $\mathbf{Cost}$- or $ \mathbb{R}_+ $-category, $\mathcal{d}$, to make it easier.)

Edit: Why does my answer feel like it's backwards?

Jonathan Castello · May 2018

Puzzle 89: Recall that $\mathbf{Cost} = \langle [0, \infty], \le, +, 0 \rangle$ is a symmetric monoidal poset (a total order, even). Consider a $\mathbf{Cost}$-category $\mathcal{X}$. This is effectively a function $\mathcal{X} : \mathrm{Ob}(\mathcal{X}) \times \mathrm{Ob}(\mathcal{X}) \to \mathbf{Cost}$ for some choice of object set $\mathrm{Ob}(\mathcal{X})$ obeying the following properties:

$0 \le \mathcal{X}(x, x)$ for all $x \in \mathrm{Ob}(\mathcal{X})$
$\mathcal{X}(x, y) + \mathcal{X}(y, z) \le \mathcal{X}(x, z)$ for all $x, y, z \in \mathrm{Ob}(\mathcal{X})$.

Taking John's hint into consideration, property #2 is suggestive of the triangle inequality -- but the inequality goes the wrong way! If we started with $\mathbf{Cost}^{op}$, we would get the triangle inequality, and $\mathcal{X}(x, x) = 0$ -- but we didn't, so we don't. (No Lawvere metric spaces for us!)

So what does this $\mathbf{Cost}$-enriched category tell us? First, going nowhere might actually cost you. Maybe you're renting. Second, it pays to take the scenic route! Even if you end up back where you started, you won't be worse off than if you'd stayed put. Shop around!

(I feel like there's a contraction mapping lurking here, but I'm not sure I can tease it out.)

John Baez · May 2018

Hmm, someone got something backwards somewhere! We want to make the inequalities point the right way: we want

$$ \mathcal{X}(x,x) \le 0 $$ so that $ \mathcal{X}(x,x) = 0$ and

$$ \mathcal{X}(x, z) \le \mathcal{X}(x, y) + \mathcal{X}(y, z) $$ Normally it's me who gets things backward, but I thought I just copied the definitions from Fong and Spivak. I'll straighten it out somehow...

John Baez · May 2018

Okay, if you look at Example 2.19 of Seven Sketches you'll see Fong and Spivak deliberately turn around the definition of inequality in the preorder $ \mathbf{Cost} $... just what we need to save the day! I had forgotten to do this!

I'll turn it around in my lecture. Sorry, folks. See, it really is good to work things out starting with the definitions, and see what happens.

Keith E. Peterson · May 2018

I just realized something... In narratology, the smallest 'units' or objects are mythemes/narreme, which are relationships between characters, objects, events, places, themes, etc. Mythemes should compose if the first's output matches the second's input. This, in my mind, has a very enriched feeling.

Jonathan Castello · May 2018

John, in the lecture notes, you have:

$x \le \infty$ for all $x$

Given the $\textbf{Cost}^{op}$ issue, should that be changed as well to $x \ge \infty$?

(Also, the title should say "Chapter 2", not "Chapter 1"!)

John Baez · May 2018

Jonathan wrote:

should that be changed as well to $x \ge \infty$?

No, if we did that we'd also have to say $2 \ge 1$, etc. What Fong and Spivak are doing instead is saying that the ordering on $ \textbf{Cost} $ is the usual $ \ge $ on the set $[0,\infty]$, not the usual $ \le $.

Yeah, I know it's confusing! It would be probably less confusing if Fong and Spivak had defined $ \textbf{Cost} $ to be the monoidal poset $ ([0,\infty],\le,0) $ and then studied $ \textbf{Cost}^{\text{op}}$-categories. But they are instead defining $ \textbf{Cost} $ to be $ ([0,\infty],\ge,0) $.

As I've said before:

Category theory reduces all of mathematics to the study of arrows. The only mistake you can make with an arrow is to get it pointing the wrong way. Thus, in category theory, this is the mistake you will always make.

nad · May 2018

Category theory reduces all of mathematics to the study of arrows. The only mistake you can make with an arrow is to get it pointing the wrong way. Thus, in category theory, this is the mistake you will make.

So for example if one would define an implication by $ A \rightarrow B :\iff A \land B $ instead of $ A \rightarrow B \iff \neg (A \land \neg B) $ then it seems that one can't define an order by $ false \leq true $.

Simon Willerton · May 2018

One way to try to avoid the confusion over $ \le $ and $ \ge $ is to define your general poset with a more ambiguous symbol such as $\rtimes$ so you have $ (\mathcal{V}, \rtimes, I ) $. Then you're not preferencing $\le$ over $\ge$.

Jonathan Castello · May 2018

John wrote:

What Fong and Spivak are doing instead is saying that the ordering on $ \textbf{Cost} $ is the usual $ \ge $ on the set $[0,\infty]$, not the usual $ \le $.

Oh. Oh.

My head hurts now.

Alex Varga · May 2018

I was messing around with computing the "cost" of running functional programs a while back. For example, an expression like $5$ would have a cost of $0$, an expression like $2 + 3$ would have a cost of $1$, and a non-terminating expression would have a cost of $\infty$. It seems that this is related to a $\mathbf{Cost}$-enriched category where $\mathrm{Ob}(\mathcal{X})$ is the set of terms and $\mathcal{X}(x,y)$ is the minimum possible number of steps to reduce x to y under all possible reduction strategies, which might be $\infty$. Is this an accurate example?

Christopher Upshaw · May 2018

Hey John, I know fairly little about physics, in physics when considering how much energy is released/lost on a path, you can (often?) split it into a anti-symmetric "potential" and an symmetric ?friction? Can you do the same thing to $\mathbf{Cost}-categories$ in general?

Fredrick Eisele · May 2018

Back to the metric space comment .

A metric space consists of

1) a set $X$ the elements of which are called points and

2) a metric function $ d : X \times X \rightarrow \mathbb{R}_{\ge 0} $, where $ d(x,y) $ is the metric, a distance between x and y

and the rules

a) $ \forall x | x \in X $, we have $ d(x,x) = 0 $

b) $ \forall x, y | x, y \in X $, if $ d(x,y) = 0 $ then $ x = y $

c) $ \forall x, y | x, y \in X $, we have $ d(x,y) = d(y,x) $

d) $ \forall x, y, z | x, y, z \in X $, we have $ d(x,y) + d(y,z) \ge d(x,z) $

Is Cost-category [I want to call it a Cost-set] a metric space?

We have a symmetric monoidal preorder with which to embelish. $$ \tag{cost} \textbf{Cost} := ( [0,\infty], \ge, 0, +) $$ And a $ \textbf{Cost} $-category $$ \tag{cost-set} \mathcal{X} := (\textbf{X}, \textbf{Cost}) $$ With the rules attendant on monoidal categories and $ \mathcal{V}\text{-category} $.

i) $ 0 \ge d(x,x) $

j) $ d(x,y) + d(y,z) \ge d(x,z) $

We have

1) a set $ \textbf{X} := Ob(\mathcal{X}) $ and

2) a metric function $ + := d $ from $ \textbf{Cost} $.

$$ \forall x,y \in \textbf{X} , d(x,y) := x + y $$ a) from (i) we have $ 0 \ge d(x,x) $ and from cost-set we have $d \in [0,\infty] $ giving $d(x,x) = 0 $

b) It is possible to have two objects in $ \textbf{X} $ having the same "cost" so $\mathcal{X}$ is not a metric space.

c) The only rule restricting opposite costs was symmetry, now that we are working not working with symmetric monoidal posets but monoidal preorders that is off the table. In other words they are certainly not required to be equivalent.

d) this is exactly (j)

So $\mathcal{X}$ is almost a metric space if we drop property (b) and (c).

Q: Would (c) be satisfied if $ \mathcal{V} $ were symmetric?

Q: Would (b) be satisfied if $ \mathcal{V} $ were a poset? A: No, I can see no reason as the mapping $ \mathcal{X}(x,y) \rightarrow \mathcal{V} $ is not required to be 1-to-1.

Edit I am going to stop fiddling with this as the next lecture addresses it better.

Marius Furter · May 2018

Jonathan wrote:

First, going nowhere might actually cost you. Maybe you're renting. Second, it pays to take the scenic route! Even if you end up back where you started, you won't be worse off than if you'd stayed put. Shop around!

I really dig this version of reality! Seems like good life advice.

Puzzle 88. Show that these choices actually makes $ \mathbf{Cost}$ into a symmetric monoidal poset.

We have $ ([0,\infty],\ge,+,0) $. Note the unintuitive opposite ordering of $ \mathbf{Cost}$. E.g $1 \ge 3 $. Because of the $\infty $ we need to consider the special cases it creates.

Poset Conditions: $ x \ge x$ clearly holds, also for $\infty $. $x \ge y $ and $y \ge z $ implies $x \ge z $ also holds since we have a linear order. E.g $0 \ge 2 $ and $2 \ge \infty $ and indeed $0 \ge \infty $. Finally, $x \ge y $ and $y \ge x $ implies $x = y $ holds again because we have a linear order without equivalent elements.

Monoid Conditions: $ I \otimes x = x = x \otimes I $ holds since $ 0 + x = x = x + 0$ for all x including $\infty $. $ (x \otimes y) \otimes y = x \otimes (y \otimes z)$ since addition is associative.

Symmetric Monoidal Poset Conditions: $ x \ge x' $ and $y \ge y' $ implies $x \otimes y \ge x' \otimes y' $ holds for all $x,x',y,y'$ including $\infty $. E.g $ 0 \ge \infty $ and $\infty \ge \infty $ and indeed $0 + \infty \ge \infty + \infty $. Finally, $x \otimes y \ge y \otimes x$ and $y \otimes x \ge x \otimes y$ both hold since $x+y = y+x$ since addition is commutative.

Question: John called this thing a symmetric monoidal poset, but since it's a poset and $x \ge y $ and $y \ge x $ implies $x = y $, shouldn't $x \otimes y \ge y \otimes x$ and $y \otimes x \ge x \otimes y$ imply $x \otimes y = y \otimes x$, meaning it's the same as a commutative monoidal poset. I guess the question boils down to whether the product of a poset with itself is also a poset. If we define the product as: $ (x,y) \le_{X \times X} (y,y') \text{ iff } x \le_X y \text{ and } x' \le_X y' $ this seems to be the case.

MatthewDoty · May 2018

Puzzle 89. Figure out exactly what a Cost-category is, starting with the definition above. Again, what matters is not your final answer so much as your process of deducing it!

There is an excellent article by Simon Willteron which lays out what Cost-enriched categories are nicely. Simon mentions Lawvere's Metric spaces, generalized logic, and closed categories (2002) where these ideas originated.

Here is my observation: Cost-enriched categories are a generalization of Bool-enriched categories.

To start, consider the following monoidal poset which I am calling Prod:

$$\langle [0,1], \leq, 1, (\cdot) \rangle$$ ...where $(\cdot)$ is just ordinary multiplication over $\mathbb{R}$.

Consider the map $- \mathrm{ln} : [0,1] \to [0,\infty]$. This inverse of this map is $x \mapsto e^{-x}$. Moreover, we have the following monoid homomorphisms:

$$ \begin{align} - \mathrm{ln} (a \cdot b) & = - (\mathrm{ln} (a) + \mathrm{ln} (b)) \\ & = - \mathrm{ln} (a) + -\mathrm{ln} (b) \end{align} $$ and

$$ \begin{align} e^{- (a + b)} & = e^{(- a)\, +\, (-b)} \\ & = e^{-a} \cdot e^{-b} \end{align} $$ Since $- \mathrm{ln} $ and $\lambda x. e^{-x}$ are strictly decreasing, we have

$$\begin{align} \mathbf{Prod} & \cong \langle [0,1], \leq, 1, (\cdot) \rangle\\ & \cong \langle [0,\infty], \geq, 0, + \rangle \\ &\cong \mathbf{Cost} \end{align}$$ We can see that every Bool-enriched category is a Prod-enriched category, using the following mappings:

$$ \begin{align} \mathtt{false} & \mapsto 0 \\ \mathtt{true} & \mapsto 1 \\ (\wedge) & \mapsto (\cdot) \\ \end{align} $$ Morever, say a Prod-enriched category $\mathcal{X}$ is bivalent if:

$$ \forall x, y. \mathcal{X}(x,y) = 0 \text{ or } \mathcal{X}(x,y) = 1 $$ Then $\mathcal{X}$ is equivalent to a Bool-enriched category.

This is because Prod (hence Cost) is the fuzzy logic generalization of Bool logic called Product Logic.

Prod has inequality in the right direction and feels a lot like Bool. But it doesn't have the nice interpretation that Cost has.

John Baez · May 2018

Just so everyone knows: I've edited this lecture slightly so that it defines $\mathcal{V}$-categories whenever $\mathcal{V}$ is a monoidal preorder, not just a symmetric monoidal poset. The definition doesn't change at all: we just don't need those extra bells and whistles to define a $\mathcal{V}$-category!

Keith E. Peterson · May 2018

Matthew Doty, I'll give you one better. Iverson Bracketing gives a homeomorphism (in fact, various) from Cost-categories to Bool-categories.

I used the ideas behind Iverson Brackets to create my Just for Fun, err I mean ignore that. ;)

Christopher Upshaw · May 2018

@FredrickEisele

The metric function and the monoid function are different things, they have distinct domains.

The metric function takes two points (objects) in the almost metric space, and produces a element of $ [0,\inf]$.

The monoid takes two distances (elements of $ [0,\inf]$) and produces a third.

This and the order on Cost determines what the "enriched" transivity means.

JimStuttard · May 2018

@Frederick #17 has d(x,y) = d(x,y)?

Christopher Upshaw · May 2018

If we interpret distance as negative log odds.

$(-({\log}_2 (p \over 1-p)$

Michael Hong · May 2018

From this lecture:

So, we get a truth value for each pair $x,y$. Let's make up a relation $\le$ on $ \mathrm{Ob}(\mathcal{X})$ such that $x \le y$ is true when $ \mathcal{X}(x,y) = \texttt{true}$, and false when $ \mathcal{X}(x,y) = \texttt{false}$.

I think not knowing that we have to define another relation $\le$ on $ \mathrm{Ob}(\mathcal{X})$ is what confused me the most when I first attempted to understand the past few lectures. Because there was nothing in the definition of enriched categories on this new relation, the relation $\le$ from the monoidal preorder $\mathcal{V}$ just seemed to "spill over" into $\mathrm{Ob}(\mathcal{X})$ which made it unclear for the beginner which set was enriching what and which elements from the preorder was doing the enriching.

So from the definition of Bool-categories, you get a set of objects and a truth value in between them. My question is wouldn't you need to define a new relation like the statement above to make Bool-category into a preorder? Or is there some unspoken thing going on where you don't need this?

Christopher Upshaw · May 2018

There's a very straight forward isomorphism between a set and it's indicator function. A relation $\triangle$ is defined to be a subset of $ S \times S$. It's indicator function is then a function ($\chi)$ from a pair of elements of S to a Boolean value (True or False) where \[\chi (a,b) = True \iff a \triangle b \]

So technically what we get is the indicator function of a relation. But the distinction is entirely unimportant in normal mathematical reasoning.

Michael Hong · May 2018

Christopher

Cool thanks! I will keep that in mind in the future.

Jonathan Castello · May 2018

Michael Hong wrote:

I think not knowing that we have to define another relation $\le$ on $ \mathrm{Ob}(\mathcal{X})$ is what confused me the most when I first attempted to understand the past few lectures.

But we don't have to define another relation on $\mathrm{Ob}(\mathcal{X})$. Not in general, anyway. The theorem you're referencing is taking any given Bool-enriched category and constructing a preorder out of the information it contains. This is a theorem about Bool-enriched categories, not a requirement of their definition. It wouldn't work this way for, say, Cost-categories. That's why we say that Bool-categories "are" preorders, and Cost-categories "are" Lawvere metric spaces -- each has a "straightforward" way to convert between the two concepts.

As John says in this lecture:

We've managed to define preorders in a new, more abstract, more confusing way!

At present, $\mathcal{V}$-enriched categories are just sets $S$ with an associated map $\mathcal{X} : S \times S \to \mathcal{V}$ into a monoidal preorder. We require $\mathcal{X}$ to satisfy some additional properties, so it can't be just any such map, but it is a map. And for whatever reason, we tend to prioritize the map instead of the set in our notation, denoting $S$ by $\mathrm{Ob}(\mathcal{X})$.

When $\mathcal{V}$ is Bool, $\mathcal{X}$ has the form $S \times S \to \mathbf{Bool}$, which as Christopher notes is the form of the characteristic function for a binary relation on $S$. This gives a convenient stepping stone in the interconvertability between Bool-enriched categories and preorders (which are just particularly nice binary relations).

Azimuth Forum

Howdy, Stranger!

Categories

Lecture 30 - Chapter 2: Preorders as Enriched Categories

Comments