# Set notation and functions into sets

Let $\mathbf 2 = \{0, 1\}$ and $X , Y$ be sets.

(i) Describe the elements of $\mathbf 2^{X\times Y}$ and $\left({\mathbf 2^X}\right)^Y$.

(ii) Find a bijective function from $\mathbf 2^{X\times Y}$ to $\left({\mathbf 2^X}\right)^Y$.

(iii) Let $\mathbb N$ and $\mathbb R$ be, respectively, the sets of natural numbers and real numbers. Describe and compare the cardinalities of: $\mathbb N$, $\mathbb N \times \mathbb N$, $\mathbf 2^{\mathbb N}$ , $\mathbb R$ and $\mathbf 2^{\mathbb R}$.

First of all, apologies for being incompetent with Latex (^) indicates "to the power of" so in the case of 2 ^ (X x Y) - this is the set of all functions from the cartesian product of (X x Y) into 2, 2 being defined as {0, 1}. Also; N and R are the naturals and reals respectively.

-
In your apology, you already solved half of (i). What else did you find by yourself? –  Hagen von Eitzen Jan 12 '13 at 14:11
Please add parenthesis to clarify, $2^{X^Y}$ means $2^{(X^Y)}$ or $(2^X)^Y$? –  Asaf Karagila Jan 12 '13 at 14:59
@AsafKaragila Note that LaTeX already makes a tiny distinction between $\mathbf 2^{X^Y}$ and ${\mathbf 2^X}^Y$, so just spending an hour with a magnifying glass would have told you ;) –  Hagen von Eitzen Jan 13 '13 at 17:37
@Hagen: Yes. I am well aware of that. I still think it's best to have explicit parenthesis rather than half-point difference in the font. –  Asaf Karagila Jan 13 '13 at 18:00
@AsafKaragila After checking the histoy, I noticed that it was in fact my fault: The OP had no LaTeX dollars in it, hence made the parentheses clear and this got lost after my adding LaTeX markup ... –  Hagen von Eitzen Jan 13 '13 at 18:29

(i) As $A^B$ is the set of functions $B\to A$, we see that $$\mathbf2^{X\times Y}$$ is the set of functions from $X\times Y$ to $\mathbf 2$, whereas the elements of $$\left(\mathbf2^X\right)^Y$$ are functions from $Y$ to the set of functions from $X$ to $\mathbf 2$. One may also note that one can biject $\mathbf 2^A$ with the powerset $P(A)$ via $f\mapsto f^{-1}(\{1\})$, so via this identification the first set "is" $P(X\times Y)$ and the second "is" the set of maps $Y\to P(X)$.

(ii) The only map $X\to \mathbf 2$ that comes to mind if you are given a map $f\colon X\times Y\to \mathbf 2$ and and element $y\in Y$, is $x\mapsto f(x,y)$. Showing that this map $f\mapsto (y\mapsto(x\mapsto f(x,y)))$ is a bijection, is straightforward.

(iii) You probably have already shown statements (Cantor diagonal arguments) essentially equivalent to $|\mathbb N|=|\mathbb N\times \mathbb N|<\left |\mathbf 2^{\mathbb N}\right|=|\mathbb R|<\left |\mathbf 2^{\mathbb R}\right |$.

-