Keith wrote in comment #1:

> \$$\texttt{false}\$$ maps to everything less than $500 I wrote: > [...] please clarify what you mean by saying > > \$$\texttt{false}\$$ maps to everything less than$500

> You're making it sound like a feasibility relation is a 'multi-valued function' where \$$\texttt{false}\$$ can map to lots of different things. That's a really cool way of talking, which we may be able to make sense of if we work a little - but that's not what we defined a feasibility relation to be.

Christopher wrote approximately:

> a relation is the same thing as a multivalued function (where 'multi' includes zero).

Right: that's the clarification I was wanting from Keith. We can think of relations in at least 3 ways:

1. A relation \$$R: X \nrightarrow Y \$$ between sets is a subset \$$R \subseteq X \times Y \$$.

2. A relation \$$R: X \nrightarrow Y \$$ between sets is a function
\$$R \colon X \times Y \to \textbf{Bool} \$$.

3. A relation \$$R: X \nrightarrow Y \$$ between sets is a function
\$$R \colon X \to P(Y) \$$ where \$$P(Y)\$$ is the power set of \$$Y\$$.

We've been using the first two outlooks a lot, but the third lets us think of a relation as a multivalued function from \$$X\$$ to \$$Y\$$, i.e. a function that maps each element of \$$X\$$ to a _subset_ of \$$Y \$$. This is the outlook that Keith was taking!

We can get from outlook 2 to outlook 3 as follows.

Functions \$$f: A \times B \to C\$$ correspond in a one-to-one way with functions \$$\hat{f} : A \to C^B\$$, where \$$C^B\$$ is the set of functions from \$$B\$$ to \$$C\$$. Computer scientists call this correspondence **currying**. It goes like this:

$\hat{f}(a)(b) = f(a,b) .$

So, functions

$f: X \times Y \to \textbf{Bool}$

correspond in a one-to-one way with functions

$\hat{f} : X \to \textbf{Bool}^Y .$

But \$$\textbf{Bool}^Y\$$ is just the power set of \$$Y \$$!

It's interesting to see how this plays out when we think about _feasibility_ relations.

**Puzzle.** Suppose \$$X\$$ and \$$Y\$$ are preorders. Can we reinterpret a feasibility relation, namely a monotone function

$\Phi : X^{\text{op}} \times Y \to \textbf{Bool} ,$

as a monotone function

$\hat{\Phi} : X^{\text{op}} \to \textbf{Bool}^{\textbf{X}}$

or perhaps slightly better

$\tilde{\Phi} : Y \to \textbf{Bool}^{\textbf{X}^{\text{op}}} ?$

The first problem here is figuring out what's an exponential of preorders!