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

Assume that \$$(\Psi \Phi)(x,z)\$$. We need to show:

1. If \$$x' \leq x\$$ then \$$(\Psi \Phi)(x',z)\$$ and
2. If \$$z \leq z'\$$ then \$$(\Psi \Phi)(x,z')\$$

Let's start with (1) and assume \$$x' \leq x\$$. From the hypothesis that \$$(\Psi \Phi)(x,z)\$$ then there exists a \$$y\$$ such that \$$\Phi(x,y) = \text{true} \text{ and } \Psi(y,z) = \text{true}\$$. From this we know that since \$$\Phi\$$ is a feasibility relation and \$$x' \leq x\$$ we know \$$\Phi(x',y) = \text{true}\$$. Hence
$\Phi(x',y) = \text{true} \text{ and } \Psi(y,z) = \text{true}$
which means

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

The proof of (2) is similar.

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

**Puzzle 176** gives a composition rule. We have two things left to show:

1. \$$(\Phi (\Psi \Upsilon))(a,d) = \text{true} \text{ if and only if } ((\Phi \Psi) \Upsilon)(a,d) = \text{true}\$$
2. Every poset has an identity feasibility relationship \$$\mathbf{1}_X: X \nrightarrow X \$$ such that \$$(\mathbf{1} \Phi (x,y)) = \text{true} \text{ if and only if } (\Phi \mathbf{1})(x,y) = \text{true} \text{ if and only if } \Phi(x,y) = \text{true} \$$

(1) follows from the following tautology in first order logic:

$\exists b. \phi(a,b) \wedge (\exists c. \psi(b,c) \wedge \upsilon(c,d)) \Longleftrightarrow \exists c. (\exists b. \phi(a,b) \wedge \psi(b,c)) \wedge \upsilon(c,d)$

To see (2), all we need is an identity feasibility relation. This appears to be given by:

$\mathbf{1}_X(x,y) = \text{true} \Longleftrightarrow x \leq_X y$