> \[ \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

\]

>

> 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

\]