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

- All Categories 2.3K
- Chat 493
- ACT Study Group 5
- Azimuth Math Review 6
- MIT 2020: Programming with Categories 53
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 138
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 64
- Azimuth Code Project 110
- Drafts 1
- Math Syntax Demos 15
- Wiki - Latest Changes 1
- Strategy 110
- Azimuth Project 1.1K

Options

We've been looking at feasibility relations, as our first example of enriched profunctors. Now let's look at another example. This combines many ideas we've discussed - but don't worry, I'll review them, and if you forget some definitions just click on the links to earlier lectures!

Remember, \(\mathbf{Bool} = \lbrace \text{true}, \text{false} \rbrace \) is the preorder that we use to answer true-or-false questions like

*can we*get from here to there?

while \(\mathbf{Cost} = [0,\infty] \) is the preorder that we use to answer quantitative questions like

*how much does it cost*to get from here to there?

or

*how far is it*from here to there?

In \(\textbf{Cost}\) we use \(\infty\) to mean it's impossible to get from here to there: it plays the same role that \(\text{false}\) does in \(\textbf{Bool}\). And remember, the ordering in \(\textbf{Cost}\) is the *opposite* of the usual order of numbers! This is good, because it means we have

$$ \infty \le x \text{ for all } x \in \mathbf{Cost} $$ just as we have

$$ \text{false} \le x \text{ for all } x \in \mathbf{Bool} .$$ Now, \(\mathbf{Bool}\) and \(\mathbf{Cost}\) are monoidal preorders, which are just what we've been using to define enriched categories! This let us define

- \(\mathbf{Bool}\)-enriched categories, which are just
**preorders**

and

- \(\mathbf{Cost}\)-enriched categories, which are
**Lawvere metric spaces**.

We can draw preorders using graphs, like these:

An edge from \(x\) to \(y\) means \(x \le y\), and we can derive other inequalities from these. Similarly, we can draw Lawvere metric spaces using \(\mathbf{Cost}\)-weighted graphs, like these:

The distance from \(x\) to \(y\) is the length of the shortest directed path from \(x\) to \(y\), or \(\infty\) if no path exists.

All this is old stuff; now we're thinking about enriched profunctors between enriched categories.

A \(\mathbf{Bool}\)-enriched profunctor between \(\mathbf{Bool}\)-enriched categories also called a feasibility relation between preorders, and we can draw one like this:

What's a \(\mathbf{Cost}\)-enriched profunctor between \(\mathbf{Cost}\)-enriched categories? It should be no surprise that we can draw one like this:

You can think of \(C\) and \(D\) as countries with toll roads between the different cities; then an enriched profunctor \(\Phi : C \nrightarrow D\) gives us the cost of getting from any city \(c \in C\) to any city \(d \in D\). This cost is \(\Phi(c,d) \in \mathbf{Cost}\).

But to specify \(\Phi\), it's enough to specify costs of flights from *some* cities in \(C\) to *some* cities in \(D\). That's why we just need to draw a *few* blue dashed edges labelled with costs. We can use this to work out the cost of going from any city \(c \in C\) to any city \(d \in D\). I hope you can guess how!

**Puzzle 182.** What's \(\Phi(E,a)\)?

**Puzzle 183.** What's \(\Phi(W,c)\)?

**Puzzle 184.** What's \(\Phi(E,c)\)?

Here's a much more challenging puzzle:

**Puzzle 185.** In general, a \(\mathbf{Cost}\)-enriched profunctor \(\Phi : C \nrightarrow D\) is defined to be a \(\mathbf{Cost}\)-enriched functor

$$ \Phi : C^{\text{op}} \times D \to \mathbf{Cost} $$ This is a function that assigns to any \(c \in C\) and \(d \in D\) a cost \(\Phi(c,d)\). However, for this to be a \(\mathbf{Cost}\)-enriched functor we need to make \(\mathbf{Cost}\) into a \(\mathbf{Cost}\)-enriched category! We do this by saying that \(\mathbf{Cost}(x,y)\) equals \( y - x\) if \(y \ge x \), and \(0\) otherwise. We must also make \(C^{\text{op}} \times D\) into a \(\mathbf{Cost}\)-enriched category, which I'll let you figure out to do. Then \(\Phi\) must obey some rules to be a \(\mathbf{Cost}\)-enriched functor. What are these rules? What do they mean concretely in terms of trips between cities?

And here are some easier ones:

**Puzzle 186.** Are the graphs we used above to describe the preorders \(A\) and \(B\) Hasse diagrams? Why or why not?

**Puzzle 187.** I said that \(\infty\) plays the same role in \(\textbf{Cost}\) that \(\text{false}\) does in \(\textbf{Bool}\). What exactly is this role?

By the way, people often say **\(\mathcal{V}\)-category** to mean \(\mathcal{V}\)-enriched category, and **\(\mathcal{V}\)-functor** to mean \(\mathcal{V}\)-enriched functor, and **\(\mathcal{V}\)-profunctor** to mean \(\mathcal{V}\)-enriched profunctor. This helps you talk faster and do more math per hour.

## Comments

There is a way to get from \(E\) to \(a\) using \(S\) then,

\[ \Phi(E,a)= 9.4. \]

There is a way to get from \(W\) to \(c\) using \(N\) then,

\[ \Phi(W,c) = 5.7. \]

There is a way to get from \(E\) to \(c\) using \(S\) and \(a\) then,

\[ \Phi(E,c) = 9.4. \]

`>**Puzzle 182.** What's \\(\Phi(E,a)\\)? There is a way to get from \\(E\\) to \\(a\\) using \\(S\\) then, \\[ \Phi(E,a)= 9.4. \\] >**Puzzle 183.** What's \\(\Phi(W,c)\\)? There is a way to get from \\(W\\) to \\(c\\) using \\(N\\) then, \\[ \Phi(W,c) = 5.7. \\] >**Puzzle 184.** What's \\(\Phi(E,c)\\)? There is a way to get from \\(E\\) to \\(c\\) using \\(S\\) and \\(a\\) then, \\[ \Phi(E,c) = 9.4. \\]`

Answer to

Puzzle 182: There are infinitely many paths from \(E\) to \(a\), with costs of the form 9+0.4+n*(2+0.4) for \(n\in\mathbb{N}\), \(\Phi(E,a)\) should be the infimum of of the possible costs, so \(\Phi(E,a)=9.4\).Similarly,

Answer to

Puzzle 183: \(\Phi(W,c)=5.7\)Answer to

Puzzle 184: \(\Phi(E,c)=9.4\).`Answer to **Puzzle 182**: There are infinitely many paths from \\(E\\) to \\(a\\), with costs of the form 9+0.4+n*(2+0.4) for \\(n\in\mathbb{N}\\), \\(\Phi(E,a)\\) should be the infimum of of the possible costs, so \\(\Phi(E,a)=9.4\\). Similarly, Answer to **Puzzle 183**: \\(\Phi(W,c)=5.7\\) Answer to **Puzzle 184**: \\(\Phi(E,c)=9.4\\).`

I am having a hard time seeing how \(\Phi\) is a \(\mathbf{Cost}\)-enriched functor. From my understanding, a \(\mathbf{Cost}\)-enriched functor, would be a functor going between two \(\mathbf{Cost}\)-enriched categories \(C\) and \(D\). But according to the definition this would require the functor to be a monotone function. But these profunctors don't seem to be monotone nor are they functions (at least the example in the lecture is not)...

So looking at the second definition, \(\Phi : C^{\text{op}} \times D \to \mathbf{Cost} \), we are taking the product of two \(\mathbf{Cost}\)-enriched categories and sending them to \(\mathbf{Cost}\), the base of enrichment itself. Can the base of enrichment be an enriched category?

`>In general, a \\(\mathbf{Cost}\\)-enriched profunctor \\(\Phi : C \nrightarrow D\\) is defined to be a \\(\mathbf{Cost}\\)-enriched functor >\[ \Phi : C^{\text{op}} \times D \to \mathbf{Cost} \] I am having a hard time seeing how \\(\Phi\\) is a \\(\mathbf{Cost}\\)-enriched functor. From my understanding, a \\(\mathbf{Cost}\\)-enriched functor, would be a functor going between two \\(\mathbf{Cost}\\)-enriched categories \\(C\\) and \\(D\\). But according to the definition this would require the functor to be a monotone function. But these profunctors don't seem to be monotone nor are they functions (at least the example in the lecture is not)... So looking at the second definition, \\(\Phi : C^{\text{op}} \times D \to \mathbf{Cost} \\), we are taking the product of two \\(\mathbf{Cost}\\)-enriched categories and sending them to \\(\mathbf{Cost}\\), the base of enrichment itself. Can the base of enrichment be an enriched category?`

No one has got Puzzle 184 correct yet!

`No one has got Puzzle 184 correct yet!`

huh...? oh! there's a route \(E\rightarrow S\rightarrow W\rightarrow N\dashrightarrow c\) with cost 9.1

`huh...? oh! there's a route \\(E\rightarrow S\rightarrow W\rightarrow N\dashrightarrow c\\) with cost 9.1`

Michael said

That's a very good question, one that causes much confusion and one that I'm not sure that John has answered, yet. I'm sure John will have plenty to say about this, but, at the risk of adding to the confusion, let me say some things here.

You've identified the following problem.

So asking for a \(\mathcal{V}\)-functor \(\Phi : C^{\text{op}} \times D \to \mathcal{V}\) gives a type error. The codomain is a monoidal preorder not a \(\mathcal{V}\)-category.

However, in many cases of interest one can 'turn \(\mathcal{V}\) into a \(\mathcal{V}\)-category'. Many authors will use the same symbol for both the monoidal preorder and the enriched category, which as I said, can lead to confusion. People talk of \(\mathcal{V}\) being 'enriched over itself', which has a fundamental type error built into it! This is okay for experts who understand the subtleties here, but I've seen experienced mathematicians from other areas getting tangled up over these things. (I could add that a lot of the terminology around enriched categories goes back to the days of 'concrete enrichment', but I shouldn't get sidetracked.)

[In case you come across these terms, other ways of describing this process which are perhaps less confusing, include making \(\mathcal{V}\) into a 'closed monoidal category', or definining 'internal homs'.]

In the case of a commutative monoidal

posetthere is only one sensible way to do this. [I'm going to use \(\rtimes\) for the order on \(\mathcal{V}\) to avoid the confusion of switching between \(\ge\) and \(\le\) when going to \(\textbf{Cost}\).] I'm going to write \(\overline{\mathcal{V}}\) for the \(\mathcal{V}\)-enriched version of \(\mathcal{V}\). This will be a \(\mathcal{V}\)-category with the same objects as \(\mathcal{V}\). So I want a function$$\text{ob}\mathcal{V}\times\text{ob}\mathcal{V}\to \text{ob}\mathcal{V} ; \qquad x,y\mapsto \overline{\mathcal{V}}(x,y).$$ You take

$$ \overline{\mathcal{V}}(x,y)=\bigvee\{z\mid z\otimes x \rtimes y\}. $$ This will work provided that the poset has the requisite joins, and that \(\otimes\) distributes over joins. And because it is a

posetrather than a preorder, the join will be unique.In the case of \(\textbf{Cost}\) you get the following.

$$ \overline{\textbf{Cost}}(x,y) =\inf\{z\mid z + x \ge y\} =\max(y-x, 0). $$ So this is a very asymmetric version of the usual metric on the half interval \([0,\infty]\). But you can check that this is a \(\textbf{Cost}\)-category, \(\overline{\textbf{Cost}}\).

`Michael said > Can the base of enrichment be an enriched category? That's a very good question, one that causes much confusion and one that I'm not sure that John has answered, yet. I'm sure John will have plenty to say about this, but, at the risk of adding to the confusion, let me say some things here. You've identified the following problem. - The base of enrichment, \\(\mathcal{V}\\), needs to be a monoidal preorder (at least in the generality we're in here). - There is no canonical way to make a preorder into a \\(\mathcal{V}\\)-category. - A \\(\mathcal{V}\\)-functor goes between \\(\mathcal{V}\\)-categories. So asking for a \\(\mathcal{V}\\)-functor \\(\Phi : C^{\text{op}} \times D \to \mathcal{V}\\) gives a type error. The codomain is a monoidal preorder not a \\(\mathcal{V}\\)-category. However, in many cases of interest one can 'turn \\(\mathcal{V}\\) into a \\(\mathcal{V}\\)-category'. Many authors will use the same symbol for both the monoidal preorder and the enriched category, which as I said, can lead to confusion. People talk of \\(\mathcal{V}\\) being 'enriched over itself', which has a fundamental type error built into it! This is okay for experts who understand the subtleties here, but I've seen experienced mathematicians from other areas getting tangled up over these things. (I could add that a lot of the terminology around enriched categories goes back to the days of 'concrete enrichment', but I shouldn't get sidetracked.) [In case you come across these terms, other ways of describing this process which are perhaps less confusing, include making \\(\mathcal{V}\\) into a 'closed monoidal category', or definining 'internal homs'.] In the case of a commutative monoidal *poset* there is only one sensible way to do this. [I'm going to use \\(\rtimes\\) for the order on \\(\mathcal{V}\\) to avoid the confusion of switching between \\(\ge\\) and \\(\le\\) when going to \\(\textbf{Cost}\\).] I'm going to write \\(\overline{\mathcal{V}}\\) for the \\(\mathcal{V}\\)-enriched version of \\(\mathcal{V}\\). This will be a \\(\mathcal{V}\\)-category with the same objects as \\(\mathcal{V}\\). So I want a function \[\\text{ob}\mathcal{V}\times\text{ob}\mathcal{V}\to \text{ob}\mathcal{V} ; \qquad x,y\mapsto \overline{\mathcal{V}}(x,y).\] You take \[ \overline{\mathcal{V}}(x,y)=\bigvee\\{z\mid z\otimes x \rtimes y\\}. \] This will work provided that the poset has the requisite joins, and that \\(\otimes\\) distributes over joins. And because it is a *poset* rather than a preorder, the join will be unique. In the case of \\(\textbf{Cost}\\) you get the following. \[ \overline{\textbf{Cost}}(x,y) =\inf\\{z\mid z + x \ge y\\} =\max(y-x, 0). \] So this is a very asymmetric version of the usual metric on the half interval \\([0,\infty]\\). But you can check that this is a \\(\textbf{Cost}\\)-category, \\(\overline{\textbf{Cost}}\\).`

re

Puzzle 185...According to the definition a \(\mathcal{V}\)-functor \(F : \mathcal{X}\rightarrow \mathcal{Y}\) is a function from objects of \(\mathcal{X}\) to objects of \(\mathcal{Y}\) such that \(\mathcal{X}(x_0, x_1) \leq \mathcal{Y}(F(x_0), F(x_1))\) for all \(\mathcal{X}\)-objects \(x_0, x_1\).

Applying this in the case \(\mathcal{V} = \textbf{Cost}\), and bearing in mind the reverse ordering on \(\textbf{Cost}\), this says that a \(\textbf{Cost}\)-functor is a function between Lawvere metric spaces that "shrinks all journeys", in that the cost of getting from \(x_0\) to \(x_1\) in \(\mathcal{X}\) is always \(\geq\) the cost of getting from \(F(x_0)\) to \(F(x_1)\) in \(\mathcal{Y}\).

OK, what does this mean when \(\mathcal{X} = C^\text{op}\times D\) and \(\mathcal{Y} = \textbf{Cost}\)?

It says the cost of getting from \((c_0, d_0)\) to \((c_1, d_1)\) is \(\geq\) the cost of getting from \(\Phi(c_0, d_0)\) to \(\Phi(c_1, d_1)\).

ie the cost of getting from \(c_1\) to \(c_0\) plus the cost of getting from \(d_0\) to \(d_1\) is \(\geq\) the maximum of \(\Phi(c_1, d_1) - \Phi(c_0, d_0)\) and zero – thanks @Simon for explaining how \(\textbf{Cost}\) is a \(\textbf{Cost}\)-enriched category!

ie \(C(c_1, c_0) + D(d_0, d_1) \geq \text{max}(\Phi(c_1, d_1) - \Phi(c_0, d_0), 0)\)

ie \(\Phi(c_1, d_1) \leq C(c_1, c_0) + \Phi(c_0, d_0) + D(d_0, d_1)\)

ie flying directly from \(c_1\) to \(d_1\) never costs more than driving from \(c_1\) to \(c_0\), flying from \(c_0\) to \(d_0\), then driving from \(d_0\) to \(d_1\).

`re **Puzzle 185**... According to the [definition](https://forum.azimuthproject.org/discussion/2169/lecture-32-chapter-2-enriched-functors/p1) a \\(\mathcal{V}\\)-functor \\(F : \mathcal{X}\rightarrow \mathcal{Y}\\) is a function from objects of \\(\mathcal{X}\\) to objects of \\(\mathcal{Y}\\) such that \\(\mathcal{X}(x_0, x_1) \leq \mathcal{Y}(F(x_0), F(x_1))\\) for all \\(\mathcal{X}\\)-objects \\(x_0, x_1\\). Applying this in the case \\(\mathcal{V} = \textbf{Cost}\\), and bearing in mind the reverse ordering on \\(\textbf{Cost}\\), this says that a \\(\textbf{Cost}\\)-functor is a function between Lawvere metric spaces that "shrinks all journeys", in that the cost of getting from \\(x_0\\) to \\(x_1\\) in \\(\mathcal{X}\\) is always \\(\geq\\) the cost of getting from \\(F(x_0)\\) to \\(F(x_1)\\) in \\(\mathcal{Y}\\). OK, what does this mean when \\(\mathcal{X} = C^\text{op}\times D\\) and \\(\mathcal{Y} = \textbf{Cost}\\)? It says the cost of getting from \\((c_0, d_0)\\) to \\((c_1, d_1)\\) is \\(\geq\\) the cost of getting from \\(\Phi(c_0, d_0)\\) to \\(\Phi(c_1, d_1)\\). ie the cost of getting from \\(c_1\\) to \\(c_0\\) plus the cost of getting from \\(d_0\\) to \\(d_1\\) is \\(\geq\\) the maximum of \\(\Phi(c_1, d_1) - \Phi(c_0, d_0)\\) and zero – thanks @Simon for explaining how \\(\textbf{Cost}\\) is a \\(\textbf{Cost}\\)-enriched category! ie \\(C(c_1, c_0) + D(d_0, d_1) \geq \text{max}(\Phi(c_1, d_1) - \Phi(c_0, d_0), 0)\\) ie \\(\Phi(c_1, d_1) \leq C(c_1, c_0) + \Phi(c_0, d_0) + D(d_0, d_1)\\) ie flying directly from \\(c_1\\) to \\(d_1\\) never costs more than driving from \\(c_1\\) to \\(c_0\\), flying from \\(c_0\\) to \\(d_0\\), then driving from \\(d_0\\) to \\(d_1\\).`

Bat, your conclusion is not quite right, as \(\Phi(c_1, d_1) \) is not necessarily the cost of

flying directlyfrom \(c_1 \) to \(d_1\), but is rather the (cheapest) cost oftravellingfrom \(c_1 \) to \(d_1\), this travelling might involve some driving.`Bat, your conclusion is not quite right, as \\(\Phi(c_1, d_1) \\) is not necessarily the cost of *flying directly* from \\(c_1 \\) to \\(d_1\\), but is rather the (cheapest) cost of *travelling* from \\(c_1 \\) to \\(d_1\\), this travelling might involve some driving.`

Ah yes, I see. I was thinking of \(\Phi\) as a matrix of flight costs, but that doesn't quite sit with the analogy.

`Ah yes, I see. I was thinking of \\(\Phi\\) as a matrix of flight costs, but that doesn't quite sit with the analogy.`

Isn't puzzle 185 asking for an algorithm that computes shortest possible paths over the profunctor \(\Phi\)?

`Isn't puzzle 185 asking for an algorithm that computes shortest possible paths over the profunctor \\(\Phi\\)?`

Also, the puzzles are missed numbered after puzzle 185.

No. A Hasse diagram must be acyclic, and the graph for A has a cycle.

`Also, the puzzles are missed numbered after puzzle 185. >*Puzzle 186*. Are the graphs we used above to describe the preorders A and B Hasse diagrams? Why or why not? No. A Hasse diagram must be acyclic, and the graph for A has a cycle.`

Both play the role of showing that two objects are disconnected.

In the case of \(\textbf{Bool}\), \(\Phi(x,y) = \text{false}\) means \(x \not\leq y\).

In the case of \(\textbf{Cost}\), \(\Phi(x,y) = \infty\) means \(x \overset{\infty}\rightarrow y\) that is to say, that you'll never have enough of the required resource to get from \(x\) to \(y\), regardless of how must you try to acquire.

Both describe the situation, \(x \not\rightarrow y\).

`>**Puzzle 186.** I said that \\(\infty\\) plays the same role in \\(\textbf{Cost}\\) that \\(\text{false}\\) does in \\(\textbf{Bool}\\). What exactly is this role? Both play the role of showing that two objects are disconnected. In the case of \\(\textbf{Bool}\\), \\(\Phi(x,y) = \text{false}\\) means \\(x \not\leq y\\). In the case of \\(\textbf{Cost}\\), \\(\Phi(x,y) = \infty\\) means \\(x \overset{\infty}\rightarrow y\\) that is to say, that you'll never have enough of the required resource to get from \\(x\\) to \\(y\\), regardless of how must you try to acquire. Both describe the situation, \\(x \not\rightarrow y\\).`

Keith wrote:

Thanks, I've fixed that now.

Right!

Why must a Hasse diagram be acyclic, and why are we using a graph with a cycle here?

`Keith wrote: > Also, the puzzles are missed numbered after puzzle 185. Thanks, I've fixed that now. > >*Puzzle 186*. Are the graphs we used above to describe the preorders A and B Hasse diagrams? Why or why not? > No. A Hasse diagram must be acyclic, and the graph for A has a cycle. Right! Why must a Hasse diagram be acyclic, and why are we using a graph with a cycle here?`

Keith wrote:

No, I'm a mathematician: if I ever want an algorithm, I'll ask for it loud and clear!

I'm asking:

A) What properties must a function \(\Phi : C^{\text{op}} \times D \to \mathbf{Cost}\) obey for it to be a \(\mathbf{Cost}\)-enriched functor?

Simon has pointed out a problem here, which is that I may never have come out and said how \(\mathbf{Cost}\) becomes a \(\mathbf{Cost}\)-enriched category! Without knowing this my question is not really well-posed.

So, how does \(\mathbf{Cost}\) becomes a \(\mathbf{Cost}\)-enriched category?

A \(\mathbf{Cost}\)-enriched category \( \mathcal{C}\) has a cost \(\mathcal{C}(x,y)\) for any two objects \(x,y\), so here we need a cost for any two costs \(x,y\). And here's what it is: it's \(y-x\), or zero if this is less than zero.

Simon has explained how we get this from general principles. I will say more about this later - I was always planning to explain it; I just forget I needed to explain it for this puzzle!

And given the answer to part A), I'm asking

B) What does this answer mean in terms of our favorite example, where

$$ \Phi : C^{\text{op}} \times D \to \mathbf{Cost} $$ describes the cost of travelling from a city \(c \in C\) to a city \(d \in D\)?

`Keith wrote: > Isn't puzzle 185 asking for an algorithm that computes shortest possible paths over the profunctor \\(\Phi\\)? No, I'm a mathematician: if I ever want an algorithm, I'll ask for it loud and clear! > **Puzzle 185.** In general, a \\(\mathbf{Cost}\\)-enriched profunctor \\(\Phi : C \nrightarrow D\\) is defined to be a [\\(\mathbf{Cost}\\)-enriched functor](https://forum.azimuthproject.org/discussion/2169/lecture-32-chapter-2-enriched-functors/p1) > \[ \Phi : C^{\text{op}} \times D \to \mathbf{Cost} \] > This is a function that assigns to any \\(c \in C\\) and \\(d \in D\\) a cost \\(\Phi(c,d)\\). However, to be a \\(\mathbf{Cost}\\)-enriched functor it needs to obey some properties! What are these properties? What do they mean in terms of trips between cities? I'm asking: A) What properties must a function \\(\Phi : C^{\text{op}} \times D \to \mathbf{Cost}\\) obey for it to be a \\(\mathbf{Cost}\\)-enriched functor? Simon has pointed out a problem here, which is that I may never have come out and said how \\(\mathbf{Cost}\\) becomes a \\(\mathbf{Cost}\\)-enriched category! Without knowing this my question is not really well-posed. So, how does \\(\mathbf{Cost}\\) becomes a \\(\mathbf{Cost}\\)-enriched category? A \\(\mathbf{Cost}\\)-enriched category \\( \mathcal{C}\\) has a cost \\(\mathcal{C}(x,y)\\) for any two objects \\(x,y\\), so here we need a cost for any two costs \\(x,y\\). And here's what it is: it's \\(y-x\\), or zero if this is less than zero. Simon has explained how we get this from general principles. I will say more about this later - I was always planning to explain it; I just forget I needed to explain it for this puzzle! And given the answer to part A), I'm asking B) What does this answer mean in terms of our favorite example, where \[ \Phi : C^{\text{op}} \times D \to \mathbf{Cost} \] describes the cost of travelling from a city \\(c \in C\\) to a city \\(d \in D\\)?`

Well \( C^{\text{op}} \times D \) is a cost enriched category if we use some operator to turn the two costs into one. We want a product so I think that means plus on costs, and using min would produce the co product? Maybe? Hmm.

`Well \\( C^{\text{op}} \times D \\) is a cost enriched category if we use some operator to turn the two costs into one. We want a product so I think that means plus on costs, and using min would produce the co product? Maybe? Hmm.`

Christopher wrote:

Right! I guess that's another thing I didn't explain: how to make the product of two \(\mathcal{V}\)-enriched categories into another \(\mathcal{V}\)-enriched category! Ugh, I was getting way ahead of myself. In general the answer is just what you guessed: if \(\mathcal{A}\) and \(\mathcal{B}\) are \(\mathcal{V}\)-enriched categories, there's a \(\mathcal{V}\)-enriched category whose objects are pairs consisting of an object in \(\mathcal{A}\) and one in \(\mathcal{B}\), and where we define

$$ (\mathcal{A}\times \mathcal{B})( (a,b), (a',b') ) = \mathcal{A}(a,a') \otimes \mathcal{B}(b,b') $$ where \(\otimes\) is the multiplication (or 'tensor product') in \(\mathcal{V}\). Remember, \(\mathcal{V}\) is a monoidal preorder with multiplication \(\otimes\) and unit object \(I\).

`Christopher wrote: > Well \\( C^{\text{op}} \times D \\) is a cost enriched category if we use some operator to turn the two costs into one. Right! I guess that's another thing I didn't explain: how to make the product of two \\(\mathcal{V}\\)-enriched categories into another \\(\mathcal{V}\\)-enriched category! Ugh, I was getting way ahead of myself. In general the answer is just what you guessed: if \\(\mathcal{A}\\) and \\(\mathcal{B}\\) are \\(\mathcal{V}\\)-enriched categories, there's a \\(\mathcal{V}\\)-enriched category whose objects are pairs consisting of an object in \\(\mathcal{A}\\) and one in \\(\mathcal{B}\\), and where we define \[ (\mathcal{A}\times \mathcal{B})( (a,b), (a',b') ) = \mathcal{A}(a,a') \otimes \mathcal{B}(b,b') \] where \\(\otimes\\) is the multiplication (or 'tensor product') in \\(\mathcal{V}\\). Remember, \\(\mathcal{V}\\) is a monoidal preorder with multiplication \\(\otimes\\) and unit object \\(I\\).`

Simon wrote:

Wasn't that sneaky? Getting cheap travel arrangements often is!

But then Anindya figured out the cheapest deal.

`Simon wrote: > No one has got Puzzle 184 correct yet! Wasn't that sneaky? Getting cheap travel arrangements often is! But then Anindya figured out the cheapest deal.`

Keith wrote:

That's true; this is kind of 'conceptual' answer where you use words to explain what things really mean. But there's also a 'purely mathematical' answer.

`Keith wrote: > >**Puzzle 186.** I said that \\(\infty\\) plays the same role in \\(\textbf{Cost}\\) that \\(\text{false}\\) does in \\(\textbf{Bool}\\). What exactly is this role? > Both play the role of showing that two objects are disconnected. That's true; this is kind of 'conceptual' answer where you use words to explain what things really mean. But there's also a 'purely mathematical' answer.`

I can see two ways in which they "play the same role":

• \(\text{false}\in\textbf{Bool}\) and \(\infty\in\textbf{Cost}\) are both bottom elements with respect to the partial order.

ie \(\text{false}\leq x\) for all \(x\in\textbf{Bool}\) and \(\infty\leq x\) for all \(x\in\textbf{Cost}\)

• they are both zero elements with respect to the monoidal product:

ie \(\text{false}\wedge x = \text{false}\) for all \(x\in\textbf{Bool}\) and \(\infty + x = \infty\) for all \(x\in\textbf{Cost}\)

`I can see two ways in which they "play the same role": • \\(\text{false}\in\textbf{Bool}\\) and \\(\infty\in\textbf{Cost}\\) are both bottom elements with respect to the partial order. ie \\(\text{false}\leq x\\) for all \\(x\in\textbf{Bool}\\) and \\(\infty\leq x\\) for all \\(x\in\textbf{Cost}\\) • they are both zero elements with respect to the monoidal product: ie \\(\text{false}\wedge x = \text{false}\\) for all \\(x\in\textbf{Bool}\\) and \\(\infty + x = \infty\\) for all \\(x\in\textbf{Cost}\\)`

I think I am not understanding something correctly about \(\mathbf{Cost}\)-categories. Isn't the composition rule for \(\mathbf{Cost}\)-categories like this: If we have objects \(N,W,S\), then the composition rule is \(\mathcal{C}(S,W) + \mathcal{C}(W,N) \ge \mathcal{C}(S,N)\) so \(4 \ge \mathcal{C}(S,N)\). There's another path between \(S\) and \(N\) via \(E\), but it gives \(7 \ge \mathcal{C}(S,N)\). Does this mean that \(\mathcal{C}(S,N) = 4\) since it's the meet of compositions that give \(\mathcal{C}(S,N)\)?

Also, it seems to me that \(\mathcal{V}\)-profunctors are a way of gluing together two \(\mathcal{V}\)-categories such that the result is a \(\mathcal{V}\)-category. Like for two \(\mathbf{Bool}\)-categories (say \(\mathcal{X}\) and \(\mathcal{Y}\)) and a feasibility relation \(\Psi\), we have a \(\mathbf{Bool}\)-category \(\mathcal{Z}\) where \(\mathrm{ob}(\mathcal{Z}) = \mathrm{ob}(\mathcal{X}) \sqcup \mathrm{ob}(\mathcal{Y}) \) and \(\mathcal{Z}(a,b)\) is true when either \(\mathcal{X}(a,b)\) or \(\mathcal{Y}(a,b)\) or \(\Psi(a,b)\) is true (basically when there's a path \(a\) to \(b\)). Is that intuition right?

`I think I am not understanding something correctly about \\(\mathbf{Cost}\\)-categories. Isn't the composition rule for \\(\mathbf{Cost}\\)-categories like this: If we have objects \\(N,W,S\\), then the composition rule is \\(\mathcal{C}(S,W) + \mathcal{C}(W,N) \ge \mathcal{C}(S,N)\\) so \\(4 \ge \mathcal{C}(S,N)\\). There's another path between \\(S\\) and \\(N\\) via \\(E\\), but it gives \\(7 \ge \mathcal{C}(S,N)\\). Does this mean that \\(\mathcal{C}(S,N) = 4\\) since it's the meet of compositions that give \\(\mathcal{C}(S,N)\\)? Also, it seems to me that \\(\mathcal{V}\\)-profunctors are a way of gluing together two \\(\mathcal{V}\\)-categories such that the result is a \\(\mathcal{V}\\)-category. Like for two \\(\mathbf{Bool}\\)-categories (say \\(\mathcal{X}\\) and \\(\mathcal{Y}\\)) and a feasibility relation \\(\Psi\\), we have a \\(\mathbf{Bool}\\)-category \\(\mathcal{Z}\\) where \\(\mathrm{ob}(\mathcal{Z}) = \mathrm{ob}(\mathcal{X}) \sqcup \mathrm{ob}(\mathcal{Y}) \\) and \\(\mathcal{Z}(a,b)\\) is true when either \\(\mathcal{X}(a,b)\\) or \\(\mathcal{Y}(a,b)\\) or \\(\Psi(a,b)\\) is true (basically when there's a path \\(a\\) to \\(b\\)). Is that intuition right?`

Anindya wrote:

Great! I think the first one is more fundamental in what we're doing, but they're somehow connected.

By the way, instead of 'zero element' I prefer to say 'absorbing element': an

absorbing element\(x\) for a binary operation \(\cdot\) is one with \(x\cdot a = x = a \cdot x\) for all \(a\).For example, zero is not an absorbing element for addition in \(\mathbb{R}\) or \( [0,\infty] \), but it makes me uncomfortable to say zero is not a zero element.

`Anindya wrote: > I can see two ways in which they "play the same role": >• \\(\text{false}\in\textbf{Bool}\\) and \\(\infty\in\textbf{Cost}\\) are both bottom elements with respect to the partial order. > i.e. \\(\text{false}\leq x\\) for all \\(x\in\textbf{Bool}\\) and \\(\infty\leq x\\) for all \\(x\in\textbf{Cost}\\) >• they are both zero elements with respect to the monoidal product: > i.e. \\(\text{false}\wedge x = \text{false}\\) for all \\(x\in\textbf{Bool}\\) and \\(\infty + x = \infty\\) for all \\(x\in\textbf{Cost}\\) Great! I think the first one is more fundamental in what we're doing, but they're somehow connected. By the way, instead of 'zero element' I prefer to say 'absorbing element': an [**absorbing element**](https://en.wikipedia.org/wiki/Absorbing_element) \\(x\\) for a binary operation \\(\cdot\\) is one with \\(x\cdot a = x = a \cdot x\\) for all \\(a\\). For example, zero is not an absorbing element for addition in \\(\mathbb{R}\\) or \\( [0,\infty] \\), but it makes me uncomfortable to say zero is not a zero element. <img src = "http://math.ucr.edu/home/baez/emoticons/tongue2.gif">`

I see. Absorbers can be used to create cancellation properties.

Edit: Er, no. I might be thinking of something else.

`I see. Absorbers can be used to create cancellation properties. Edit: Er, no. I might be thinking of something else.`

Scott Oswald wrote:

I explained this stuff a bit here:

so if you don't remember that it might help to look at it.

You're definitely on the right track! Perhaps what's confusing you is this. These pictures:

are not technically pictures of \(\mathbf{Cost}\)-categories; they are pictures of \(\mathbf{Cost}\)-weighted graphs, a concept I explained in Lecture 33. But we can

constructa \(\mathbf{Cost}\)-category from a \(\mathbf{Cost}\)-weighted graph, bydefining\(\mathcal{C}(x,y)\) to be the price of the least expensive route from \(x\) to \(y\), i.e. the infimum over all edge paths from \(x\) to \(y\) of the sum of the costs labelling these edges.So, my objection to what you said is only a technical one: we are not using the rules for composition in a \(\mathbf{Cost}\)-category to deduce \(\mathcal{C}(S,N) = 4\); rather, we are using a specific recipe to construct a \(\mathbf{Cost}\)-category from a \(\mathbf{Cost}\)-weighted graph, and this recipe gives us \(\mathcal{C}(S,N) = 4\).

This is certainly one thing one can do with a \(\mathcal{V}\)-profunctor! Given a \(\mathcal{V}\)-profunctor \(\Psi : \mathcal{X} \nrightarrow \mathcal{Y}\), we can glue \(\mathcal{X}\) and \(\mathcal{Y}\) together as you're imagining and get a new \(\mathcal{V}\)-category called their

collage.Simon Willerton explained this in the case \(\mathcal{V} = \textbf{Bool}\) back in comment #7 to Lecture 57:

`Scott Oswald wrote: > I think I am not understanding something correctly about \\(\mathbf{Cost}\\)-categories. Isn't the composition rule for \\(\mathbf{Cost}\\)-categories like this: If we have objects \\(N,W,S\\), then the composition rule is \\(\mathcal{C}(S,W) + \mathcal{C}(W,N) \ge \mathcal{C}(S,N)\\) so \\(4 \ge \mathcal{C}(S,N)\\). There's another path between \\(S\\) and \\(N\\) via \\(E\\), but it gives \\(7 \ge \mathcal{C}(S,N)\\). Does this mean that \\(\mathcal{C}(S,N) = 4\\) since it's the meet of compositions that give \\(\mathcal{C}(S,N)\\)? I explained this stuff a bit here: * [Lecture 33 - Chapter 2: Tying up loose ends](https://forum.azimuthproject.org/discussion/2192/lecture-33-chapter-2-tying-up-loose-ends/p1). so if you don't remember that it might help to look at it. You're definitely on the right track! Perhaps what's confusing you is this. These pictures: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/lawvere_metric_spaces.png"></center> are not technically pictures of \\(\mathbf{Cost}\\)-categories; they are pictures of \\(\mathbf{Cost}\\)-weighted graphs, a concept I explained in Lecture 33. But we can _construct_ a \\(\mathbf{Cost}\\)-category from a \\(\mathbf{Cost}\\)-weighted graph, by _defining_ \\(\mathcal{C}(x,y)\\) to be the price of the least expensive route from \\(x\\) to \\(y\\), i.e. the infimum over all edge paths from \\(x\\) to \\(y\\) of the sum of the costs labelling these edges. So, my objection to what you said is only a technical one: we are not using the rules for composition in a \\(\mathbf{Cost}\\)-category to deduce \\(\mathcal{C}(S,N) = 4\\); rather, we are using a specific recipe to construct a \\(\mathbf{Cost}\\)-category from a \\(\mathbf{Cost}\\)-weighted graph, and this recipe gives us \\(\mathcal{C}(S,N) = 4\\). > Also, it seems to me that \\(\mathcal{V}\\)-profunctors are a way of gluing together two \\(\mathcal{V}\\)-categories such that the result is a \\(\mathcal{V}\\)-category. This is certainly one thing one can do with a \\(\mathcal{V}\\)-profunctor! Given a \\(\mathcal{V}\\)-profunctor \\(\Psi : \mathcal{X} \nrightarrow \mathcal{Y}\\), we can glue \\(\mathcal{X}\\) and \\(\mathcal{Y}\\) together as you're imagining and get a new \\(\mathcal{V}\\)-category called their **collage.** Simon Willerton explained this in the case \\(\mathcal{V} = \textbf{Bool}\\) back in [comment #7 to Lecture 57](https://forum.azimuthproject.org/discussion/comment/19971/#Comment_19971): > <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/feasibility_relation.png"></center> > In some sense, in the pictures it would be more sensible to put \\(Y\\) *on top of* \\(X\\). One can think (sometimes usefully, sometimes less usefully) of a feasability relation (or profunctor) between preorders as giving rise to a new preorder, known as the **collage**. The underlying set of the collage is the disjoint union \\(X \sqcup Y\\) and on both \\(X\\) and \\(Y\\) the new preorder restricts to the preorders you started with, but for all \\(x \in X\\) and \\(y \in Y\\) you have \\(y\not\le x\\) whilst \\(x\le y\, \iff\ \Phi(x,y)\\). > The pictures drawn with the blue arrows are the Hasse diagrams of these collages. Nothing in \\(Y\\) ever comes before anything in \\(X\\) in this preorder, so that's why it would make sense to draw \\(Y\\) on top of \\(X\\). I'll leave it for someone to produce such a version of the examples above :-).`

Of course, I think I forgot about that.

First, I like the word "collage", it means "gluing" in French.

I am trying to see if there's a way to take that intuition and turn it into a general formula for combining \(\mathcal{V}\)-categories given a \(\mathcal{V}\)-profunctor. But when \(\mathcal{V} = \mathbf{Cost}\), we are only required to have \( \mathcal{C}(x,y) + \mathcal{C}(y,z) \ge \mathcal{C}(x,z)\) meaning that for \(a \in \mathrm{ob}\left(\mathcal{X}\right)\) and \(b \in \mathrm{ob}\left(\mathcal{Y}\right)\), the morphism (am I allowed to say morphism for enriched categories?) \(\mathcal{Z}(a,b)\) is only required to be less than the least expensive route from \(a\) to \(b\). We can choose that the least expensive route defines \(\mathcal{Z}(a,b)\) (like we do for building \(\mathbf{Cost}\)-categories from weighted graphs).

I don't know, maybe it depends on the answer to

Puzzle 185.`> But we can _construct_ a \\(\mathbf{Cost}\\)-category from a \\(\mathbf{Cost}\\)-weighted graph, by _defining_ \\(\mathcal{C}(x,y)\\) to be the price of the least expensive route from \\(x\\) to \\(y\\), i.e. the infimum over all edge paths from \\(x\\) to \\(y\\) of the sum of the costs labelling these edges. > So, my objection to what you said is only a technical one: we are not using the rules for composition in a \\(\mathbf{Cost}\\)-category to deduce \\(\mathcal{C}(S,N) = 4\\); rather, we are using a specific recipe to construct a \\(\mathbf{Cost}\\)-category from a \\(\mathbf{Cost}\\)-weighted graph, and this recipe gives us \\(\mathcal{C}(S,N) = 4\\) Of course, I think I forgot about that. > This is certainly one thing one can do with a \\(\mathcal{V}\\)-profunctor! Given a \\(\mathcal{V}\\)-profunctor \\(\Psi : \mathcal{X} \nrightarrow \mathcal{Y}\\), we can glue \\(\mathcal{X}\\) and \\(\mathcal{Y}\\) together as you're imagining and get a new \\(\mathcal{V}\\)-category called their **collage.** > Simon Willerton explained this in the case \\(\mathcal{V} = \textbf{Bool}\\) back in [comment #7 to Lecture 57](https://forum.azimuthproject.org/discussion/comment/19971/#Comment_19971): First, I like the word "collage", it means "gluing" in French. I am trying to see if there's a way to take that intuition and turn it into a general formula for combining \\(\mathcal{V}\\)-categories given a \\(\mathcal{V}\\)-profunctor. But when \\(\mathcal{V} = \mathbf{Cost}\\), we are only required to have \\( \mathcal{C}(x,y) + \mathcal{C}(y,z) \ge \mathcal{C}(x,z)\\) meaning that for \\(a \in \mathrm{ob}\left(\mathcal{X}\right)\\) and \\(b \in \mathrm{ob}\left(\mathcal{Y}\right)\\), the morphism (am I allowed to say morphism for enriched categories?) \\(\mathcal{Z}(a,b)\\) is only required to be less than the least expensive route from \\(a\\) to \\(b\\). We can choose that the least expensive route defines \\(\mathcal{Z}(a,b)\\) (like we do for building \\(\mathbf{Cost}\\)-categories from weighted graphs). I don't know, maybe it depends on the answer to **Puzzle 185**.`

Hi -

Yes; we can actually reduce the problem of constructing the collage of a \(\mathcal{V}\)-profunctor to the problem of getting a \(\mathcal{V}\)-category from a \(\mathcal{V}\)-weighted graph, which I'll assume you know how to solve.

Notice that any \(\mathcal{V}\)-category \(\mathcal{C}\) gives a \(\mathcal{V}\)-weighted graph with an edge from any object \(c\) to any object \(c'\), weighted by \(\mathcal{C}(c,c')\). If we take this \(\mathcal{V}\)-weighted graph and use our recipe for turning it into a \(\mathcal{V}\)-category, we get \(\mathcal{C}\) back!

Next notice that any \(\mathcal{V}\)-profunctor \(\Phi : \mathcal{C} \nrightarrow \mathcal{D}\) gives a \(\mathcal{V}\)-weighted graph! This has:

an edge from any object \(c\) to any object \(c'\) of \(\mathcal{C}\), weighted by \(\mathcal{C}(c,c')\).

an edge from any object \(d\) to any object \(d'\) of \(\mathcal{D}\), weighted by \(\mathcal{D}(d,d')\).

an edge from any object \(c\) of \(\mathcal{C}\) to any object \(d\) of \(\mathcal{D}\), weighted by \(\Phi(c,d)\).

If we take this \(\mathcal{V}\)-weighted graph and use our recipe for turning it into a \(\mathcal{V}\)-category, we get the

collageof \(\Phi\).By the way, when you have a \(\mathcal{V}\)-enriched category \(\mathcal{Z}\) and two objects \(a\) and \(b\) in it, we call \(\mathcal{Z}(a,b) \in \mathcal{V}\) the

hom-objectfrom \(a\) to \(b\). This is like when we have an ordinary category \(\mathcal{Z}\): then \(\mathcal{Z}(a,b)\) is a set, called thehom-setfrom \(a\) to \(b\) and often written \(\text{hom}(a,b)\). In the enriched case \(\mathcal{Z}(a,b) \in \mathcal{V}\) is not analogous to a morphism; it's analogous to a set of morphisms.`Hi - > I am trying to see if there's a way to take that intuition and turn it into a general formula for combining \\(\mathcal{V}\\)-categories given a \\(\mathcal{V}\\)-profunctor. But when \\(\mathcal{V} = \mathbf{Cost}\\), we are only required to have \\( \mathcal{C}(x,y) + \mathcal{C}(y,z) \ge \mathcal{C}(x,z)\\) meaning that for \\(a \in \mathrm{ob}\left(\mathcal{X}\right)\\) and \\(b \in \mathrm{ob}\left(\mathcal{Y}\right)\\), the morphism (am I allowed to say morphism for enriched categories?) \\(\mathcal{Z}(a,b)\\) is only required to be less than the least expensive route from \\(a\\) to \\(b\\). We can choose that the least expensive route defines \\(\mathcal{Z}(a,b)\\) (like we do for building \\(\mathbf{Cost}\\)-categories from weighted graphs). Yes; we can actually reduce the problem of constructing the collage of a \\(\mathcal{V}\\)-profunctor to the problem of getting a \\(\mathcal{V}\\)-category from a \\(\mathcal{V}\\)-weighted graph, which I'll assume you know how to solve. Notice that any \\(\mathcal{V}\\)-category \\(\mathcal{C}\\) gives a \\(\mathcal{V}\\)-weighted graph with an edge from any object \\(c\\) to any object \\(c'\\), weighted by \\(\mathcal{C}(c,c')\\). If we take this \\(\mathcal{V}\\)-weighted graph and use our recipe for turning it into a \\(\mathcal{V}\\)-category, we get \\(\mathcal{C}\\) back! Next notice that any \\(\mathcal{V}\\)-profunctor \\(\Phi : \mathcal{C} \nrightarrow \mathcal{D}\\) gives a \\(\mathcal{V}\\)-weighted graph! This has: * an edge from any object \\(c\\) to any object \\(c'\\) of \\(\mathcal{C}\\), weighted by \\(\mathcal{C}(c,c')\\). * an edge from any object \\(d\\) to any object \\(d'\\) of \\(\mathcal{D}\\), weighted by \\(\mathcal{D}(d,d')\\). * an edge from any object \\(c\\) of \\(\mathcal{C}\\) to any object \\(d\\) of \\(\mathcal{D}\\), weighted by \\(\Phi(c,d)\\). If we take this \\(\mathcal{V}\\)-weighted graph and use our recipe for turning it into a \\(\mathcal{V}\\)-category, we get the **collage** of \\(\Phi\\). By the way, when you have a \\(\mathcal{V}\\)-enriched category \\(\mathcal{Z}\\) and two objects \\(a\\) and \\(b\\) in it, we call \\(\mathcal{Z}(a,b) \in \mathcal{V}\\) the **hom-object** from \\(a\\) to \\(b\\). This is like when we have an ordinary category \\(\mathcal{Z}\\): then \\(\mathcal{Z}(a,b)\\) is a set, called the **hom-set** from \\(a\\) to \\(b\\) and often written \\(\text{hom}(a,b)\\). In the enriched case \\(\mathcal{Z}(a,b) \in \mathcal{V}\\) is not analogous to a morphism; it's analogous to a set of morphisms.`

Okay, that makes sense. Thanks for the clarification!

`> By the way, when you have a \\(\mathcal{V}\\)-enriched category \\(\mathcal{Z}\\) and two objects \\(a\\) and \\(b\\) in it, we call \\(\mathcal{Z}(a,b) \in \mathcal{V}\\) the **hom-object** from \\(a\\) to \\(b\\). This is like when we have an ordinary category \\(\mathcal{Z}\\): then \\(\mathcal{Z}(a,b)\\) is a set, called the **hom-set** from \\(a\\) to \\(b\\) and often written \\(\text{hom}(a,b)\\). In the enriched case \\(\mathcal{Z}(a,b) \in \mathcal{V}\\) is not analogous to a morphism; it's analogous to a set of morphisms. Okay, that makes sense. Thanks for the clarification!`