What's the meaning of a set to the power of another set?

${ \mathbb{N} }^{ \left\{ 0,1 \right\} }$ and ${ \left\{ 0,1 \right\} }^{ \mathbb{N} }$ to be more specific, and is there a countable subset in each one of them? How do I find them?

Solution 1:

The syntax $X^Y$ where $X$ and $Y$ are sets means the set of functions from $Y$ to $X$.

Recall for the following that the von Neumann ordinal $2 = \left\{0,1\right\}$.

We often identify the powerset $\mathcal{P}(X)$ with the set of functions $2^X$, since we can think of the latter set as the set of characteristic functions of subsets of $X$. Let $f \in 2^X$ be a function and let $Z \subseteq X$. We can stipulate that if $f(x) = 1$ then $x \in Z$, and if $f(x) = 0$ then $x \not\in Z$.

The exponent notation makes sense because of the following identity from cardinal arithmetic:

$$|X|^{|Y|} = |X^Y|.$$

That is, the cardinality of one cardinal raised to the power of another is just the cardinality of the functions from the latter to the former. The name 'powerset' also makes sense once thought of in these terms, since we can easily construct a bijection between $\mathcal{P}(X)$ and $2^X$ by identifying subsets with their characteristic functions from $X$.

As Rahul Narain points out, the set $X^2$ is naturally identified with the cartesian product $X \times X$. Each function $f \in X^2$ will be of the form $\left\{(0, x), (1, y)\right\}$ for $x, y \in X$. By taking $f(0)$ as the first component and $f(1)$ as the second, we can construct a pair $(f(0) = x, f(1) = y)$. The collection of all such pairs will just be the cartesian product of $X$ with itself.

Let $X$ be an infinite set. We seek to show that $X^2$ and $2^X$ are infinite, by showing that they both have infinite subsets. This is most easily done by constructing a bijection between those subsets and $X$. Firstly, suppose that

$$Y = \left\{ f : f(0) = f(1), f \in X^2 \right\}.$$

Clearly $Y \subseteq X$. Now let $G : Y \rightarrow X$, $G(f) = f(0)$. This is an injection since the uniqueness of $f(0)$ is guaranteed by the construction of $Y$. The inverse function $G^{-1} : X \rightarrow Y$ is easily defined as

$$G^{-1}(x) = \left\{ (0, x), (1, x) \right\}$$

which again must be an injection. Note that the identity relation $1_X = \left\{ (x, x) : x \in X \right\}$ bears the same relation to $Y$ as the full cartesian product does to $X^2$.

The proof that $2^X$ is infinite proceeds by the same basic method. Let

$$Z = \left\{ f : \exists{x} ( f(x) = 1 \wedge \forall{y} ( y \in X \wedge y \neq x \rightarrow f(y) = 0 ) ), f \in 2^X \right\}.$$

We will construct a bijection between $Z$ and $X$. Let $H : Z \rightarrow X$, $H(f) = x$ where $f(x) = 1$. Then let $H^{-1} : X \rightarrow Z$, $H^{-1}(x) = f$ for the unique $f$ such that $f(x) = 1$ and $\forall{y} ( y \neq x \rightarrow f(y) = 0)$.

Note that what we've essentially done here is set up a bijection between $X$ and all its subsets which are singletons. More precisely, the bijection is between $X$ and the characteristic functions of those singletons. Since $X$ is infinite, $Z$ must be infinite and thus so is $2^X$.

However, something much stronger also holds: the cardinality of $2^X$ is strictly greater than the cardinality of $X$. This is Cantor's theorem.

Lastly, since $\mathbb{N}$ is infinite, so are $\mathbb{N}^2$ and $2^\mathbb{N}$: just take $X = \mathbb{N}$ in the above proof. $Y$ and $Z$ will be countable since the proof constructs bijections between them and $X$, so they will have the same cardinality as $\mathbb{N}$, namely $\aleph_0$.

Solution 2:

Indeed, we can identify a function $f:Y\to X$ with an element of $\prod_Y X$ (a direct product of copies of $X$ indexed by $Y$) by considering the component with index $y$ the image of $y$ under $f$. This lends to what I feel is an intuitive way to remember the meaning of $X^Y$ with very little effort.

For whole numbers $n$, we have $a^n=\underbrace{a\times a\times\cdots\times a}_n$. Similarly for sets we may choose to write

$$X^Y\cong \underbrace{X\times X\times \cdots \times X}_Y.$$

All the better if one is already used to thinking of indexed tuples as functions of the index set.