#### Howdy, Stranger!

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

Options

# Lecture 59 - Chapter 4: Cost-Enriched Profunctors

edited July 2018

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

and

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.

To read other lectures go here.

• Options
1.
edited July 2018

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.$

Comment Source:>**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. \$ 
• Options
2.

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$$.

Comment Source: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\$$.
• Options
3.
edited July 2018

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?

Comment Source:>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? 
• Options
4.

No one has got Puzzle 184 correct yet!

Comment Source:No one has got Puzzle 184 correct yet!
• Options
5.

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

Comment Source:huh...? oh! there's a route \$$E\rightarrow S\rightarrow W\rightarrow N\dashrightarrow c\$$ with cost 9.1
• Options
6.
edited July 2018

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}}$$.

Comment Source: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}}\$$.
• Options
7.
edited July 2018

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$$.

Comment Source: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\$$. 
• Options
8.
edited July 2018

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.

Comment Source: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.
• Options
9.

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

Comment Source:Ah yes, I see. I was thinking of \$$\Phi\$$ as a matrix of flight costs, but that doesn't quite sit with the analogy.
• Options
10.

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

Comment Source:Isn't puzzle 185 asking for an algorithm that computes shortest possible paths over the profunctor \$$\Phi\$$?
• Options
11.

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.

Comment Source: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.
• Options
12.
edited July 2018

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$$.

Comment Source:>**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\$$.
• Options
13.
edited July 2018

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?

Comment Source: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?
• Options
14.
edited July 2018

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

$$\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?

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$$?

Comment Source: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\$$? 
• Options
15.

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.

Comment Source: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.
• Options
16.
edited July 2018

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$$.

Comment Source: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\$$.
• Options
17.

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.

Comment Source: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.
• Options
18.

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.

Comment Source: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. 
• Options
19.

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}$$

Comment Source: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}\$$ 
• Options
20.
edited July 2018

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?

Comment Source: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? 
• Options
21.

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 $$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. Comment Source: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"> 
• Options
22.
edited July 2018

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

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

Comment Source:I see. Absorbers can be used to create cancellation properties. Edit: Er, no. I might be thinking of something else.
• Options
23.
edited July 2018

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:

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 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: 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 :-).

Comment Source: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 :-). 
• Options
24.
edited July 2018

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:

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.

Comment Source:> 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**.
• Options
25.
edited July 2018

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.

Comment Source: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. 
• Options
26.

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!

Comment Source:> 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!