In the puzzles [last time](https://forum.azimuthproject.org/discussion/2281/lecture-57-chapter-4-feasibility-relations/p1) we saw something nice: a [feasibility relation](https://forum.azimuthproject.org/discussion/2281/lecture-57-chapter-4-feasibility-relations#latest) between preorders is a generalization of something we learned about a long time ago: a [monotone function](https://forum.azimuthproject.org/discussion/1828/lecture-4-chapter-1-galois-connections/p1) between preorders.

But the really cool part is this: given preorders \\(X\\) and \\(Y\\), we can get a feasibility relation \\(\Phi : X \nrightarrow Y\\) either from a monotone function \\(f : X \to Y\\) or from a monotone function \\(g: Y \to X\\). So, feasibility relations put monotone functions going _forwards_ from \\(X\\) to \\(Y\\) and those going _backwards_ from \\(Y\\) to \\(X\\) into a common framework!

Even better, we saw that one of our favorite themes, namely _adjoints_, is deeply connected to this idea. Let me state this as a theorem:

**Theorem.** Let \\(f : X \to Y \\) and \\(g: Y \to X\\) be monotone functions between the preorders \\(X\\) and \\(Y\\). Define the feasibility relations \\(\Phi : X \nrightarrow Y\\) by

\[ \Phi(x,y) \text{ if and only if } f(x) \le y \]

and

\[ \Psi(x,y) \text{ if and only if } x \le g(y) .\]

Then \\(\Phi = \Psi\\) if and only if \\(f \\) is the left adjoint of \\(g\\).

**Proof.** We have \\(\Phi = \Psi\\) iff

\[ \Phi(x,y) \text{ if and only if } \Psi(x,y) \]

for all \\(x \in X, y \in Y\\), but by our definitions this is true iff

\[ f(x) \le y \text{ if and only if } x \le g(y) \]

which is true iff \\(f\\) is the left adjoint of \\(g\\). \\( \qquad \blacksquare \\)

Ah, if only all proofs were so easy!

Now, to make feasibility relations into a truly satisfactory generalization of monotone functions, we should figure out how to _compose_ them. Luckily this is easy, because we already know how to compose relations from [Lecture 40](https://forum.azimuthproject.org/discussion/2223/lecture-40-chapter-3-relations/p1). So, we should try to prove this:

**Theorem.** Suppose that \\(\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\\) are feasibility relations between preorders. Then there is a **composite** feasibility relation

\[ \Psi \Phi : X \nrightarrow Z \]

defined as follows:

\[ (\Psi \Phi)(x,z) = \text{true} \]

if and only if for some \\(y \in Y\\),

\[ \Phi(x,y) = \text{true} \text{ and } \Psi(y,z) = \text{true}. \]

**Puzzle 176.** Prove this! Show that \\(\Psi \Phi\\) really is a feasibility relation.

I hope you see how reasonable this form of composition is. Think of it in terms of our pictures from last time:

Here we have three preorders \\(X,Y,Z\\), which we can think of as cities with one-way roads. We can also take one-way airplane flights from \\(X\\) to \\(Y\\) and from \\(Y\\) to \\(Z\\): the flights in blue are a way of drawing a feasibility relation \\(\Phi: X \nrightarrow Y\\), and the flights in red are a way of drawing \\(\Psi: Y \nrightarrow Z\\).

**Puzzle 177.** Is \\( (\Psi\Phi)(N,y) = \text{true}\\)?

**Puzzle 178.** Is \\( (\Psi\Phi)(W,y) = \text{true}\\)?

**Puzzle 179.** Is \\(( \Psi\Phi)(E,y) = \text{true}\\)?

**Puzzle 180.** Prove that there is a category \\(\textbf{Feas}\\) whose objects are preorders and whose morphisms are feasibility relations, composed as above.

**Puzzle 181.** Suppose that \\(\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\\) are feasibility relations between preorders. Prove that

\[ (\Psi\Phi)(x,z) = \bigvee_{y \in Y} \Phi(x,y) \wedge \Psi(y,z) \]

where \\(\wedge\\) is the meet in the poset \\(\textbf{Bool}\\), and \\(\bigvee\\) is the join. How is this formula related to matrix multiplication?

You may remember that a feasibility relation is a \\(\mathcal{V}\\)-enriched profunctor in the special case where \\(\mathcal{V} = \textbf{Bool}\\). This formula will be the key to defining composition for more general \\(\mathcal{V}\\)-enriched profunctors. But we need to talk about that more.

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Chapter_4)**

But the really cool part is this: given preorders \\(X\\) and \\(Y\\), we can get a feasibility relation \\(\Phi : X \nrightarrow Y\\) either from a monotone function \\(f : X \to Y\\) or from a monotone function \\(g: Y \to X\\). So, feasibility relations put monotone functions going _forwards_ from \\(X\\) to \\(Y\\) and those going _backwards_ from \\(Y\\) to \\(X\\) into a common framework!

Even better, we saw that one of our favorite themes, namely _adjoints_, is deeply connected to this idea. Let me state this as a theorem:

**Theorem.** Let \\(f : X \to Y \\) and \\(g: Y \to X\\) be monotone functions between the preorders \\(X\\) and \\(Y\\). Define the feasibility relations \\(\Phi : X \nrightarrow Y\\) by

\[ \Phi(x,y) \text{ if and only if } f(x) \le y \]

and

\[ \Psi(x,y) \text{ if and only if } x \le g(y) .\]

Then \\(\Phi = \Psi\\) if and only if \\(f \\) is the left adjoint of \\(g\\).

**Proof.** We have \\(\Phi = \Psi\\) iff

\[ \Phi(x,y) \text{ if and only if } \Psi(x,y) \]

for all \\(x \in X, y \in Y\\), but by our definitions this is true iff

\[ f(x) \le y \text{ if and only if } x \le g(y) \]

which is true iff \\(f\\) is the left adjoint of \\(g\\). \\( \qquad \blacksquare \\)

Ah, if only all proofs were so easy!

Now, to make feasibility relations into a truly satisfactory generalization of monotone functions, we should figure out how to _compose_ them. Luckily this is easy, because we already know how to compose relations from [Lecture 40](https://forum.azimuthproject.org/discussion/2223/lecture-40-chapter-3-relations/p1). So, we should try to prove this:

**Theorem.** Suppose that \\(\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\\) are feasibility relations between preorders. Then there is a **composite** feasibility relation

\[ \Psi \Phi : X \nrightarrow Z \]

defined as follows:

\[ (\Psi \Phi)(x,z) = \text{true} \]

if and only if for some \\(y \in Y\\),

\[ \Phi(x,y) = \text{true} \text{ and } \Psi(y,z) = \text{true}. \]

**Puzzle 176.** Prove this! Show that \\(\Psi \Phi\\) really is a feasibility relation.

I hope you see how reasonable this form of composition is. Think of it in terms of our pictures from last time:

Here we have three preorders \\(X,Y,Z\\), which we can think of as cities with one-way roads. We can also take one-way airplane flights from \\(X\\) to \\(Y\\) and from \\(Y\\) to \\(Z\\): the flights in blue are a way of drawing a feasibility relation \\(\Phi: X \nrightarrow Y\\), and the flights in red are a way of drawing \\(\Psi: Y \nrightarrow Z\\).

**Puzzle 177.** Is \\( (\Psi\Phi)(N,y) = \text{true}\\)?

**Puzzle 178.** Is \\( (\Psi\Phi)(W,y) = \text{true}\\)?

**Puzzle 179.** Is \\(( \Psi\Phi)(E,y) = \text{true}\\)?

**Puzzle 180.** Prove that there is a category \\(\textbf{Feas}\\) whose objects are preorders and whose morphisms are feasibility relations, composed as above.

**Puzzle 181.** Suppose that \\(\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\\) are feasibility relations between preorders. Prove that

\[ (\Psi\Phi)(x,z) = \bigvee_{y \in Y} \Phi(x,y) \wedge \Psi(y,z) \]

where \\(\wedge\\) is the meet in the poset \\(\textbf{Bool}\\), and \\(\bigvee\\) is the join. How is this formula related to matrix multiplication?

You may remember that a feasibility relation is a \\(\mathcal{V}\\)-enriched profunctor in the special case where \\(\mathcal{V} = \textbf{Bool}\\). This formula will be the key to defining composition for more general \\(\mathcal{V}\\)-enriched profunctors. But we need to talk about that more.

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Chapter_4)**