Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
Sorry, couldn't resist replacing the pipe with a \mid. – Rasmus Oct 24 '11 at 9:22
@Rasmus: Strange I usually keep my pipes \mid... Thanks :-) – Asaf Karagila Oct 24 '11 at 9:40

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

share|cite|improve this answer
Though some of us prefer the notation $^AB$ for the set of functions from $A$ into $B$. (I suspect that this usage started with set theorists wanting to distinguish the set $^\lambda\kappa$ of functions from the cardinal $\kappa^\lambda$.) – Brian M. Scott Oct 25 '11 at 18:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.