Correspondences $f: X \to 2^Y$ I am reading some notes on correspondences and have a question. (The notes are here.)
I have a question about something on page 1.
Basically, the notes provide some motivation for why we might want to define correspondences. It then says, 

We would like to have a notion of a set-valued function. The seemingly obvious idea a function $f : X \to 2^Y$ from a set $X$ in to the set of subsets of $Y$ may not be the best choice.

I have looked at this several times but have no idea where the $2^Y$ comes from. Any help would be appreciated!
P.S. This actually is not homework but I am not sure what tag to use, I tried correspondences and looked through the first 5 pages of common tags without any luck.
 A: The usage of $2^Y$ can be used to denote the power set of $Y$, that is:
$$P(Y)=\{A \mid A\subseteq Y\}$$
In fact the notation itself means $\{f\colon Y\to\{0,1\}\mid f\text{ a function}\}$, however there is a bijection between $P(Y)$ and this set, given by:
$$A\subseteq Y\mapsto\chi_A(x) = \begin{cases} 1 & x\in A\\ 0 & x\notin A\end{cases}$$
So when speaking about a set valued function, it means that the values are subsets of $Y$, therefore elements of $P(Y)$ or elements of $2^Y$ accordingly.
It is actually hidden in the quoted text. "from a set $X$ in to the set of subsets of $Y$" in fact giving away that $2^Y$ is the notation used by the author for the power set of a set $Y$.
A: If $A$ is a set with $m$ elements and $B$ is a set with $n$ elements, then the set of all functions from $A$ into $B$ has $n^m$ elements.
Consequently it became conventional to denote the set of all functions from $A$ into $B$ by $B^A$.
If we let $2$ denote the set $\{0,1\}$ with two elements, then $2^A$ is the set of all functions from $A$ into $\{0,1\}$, and that's essentially the set of all subsets of $A$.  I.e. any subset of $A$ corresponds to the function that maps members of that subset to $1$ and non-members to $0$.
