Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

${ \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?

share|cite|improve this question
The notation $X^Y$ is commonly used for the set of all functions from $Y$ to $X$. – André Nicolas Apr 8 '12 at 13:24
up vote 14 down vote accepted

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

share|cite|improve this answer
And conversely, of course, we can identify the Cartesian product $X \times X$ with $X^2$, the set of functions from $2$ to $X$, by associating a function $f \in X^2$ with the pair $(f(0), f(1))$. – Rahul Apr 8 '12 at 13:47
@RahulNarain of course, thanks—I had to dash off before answering the second part, but I'll edit my answer with it. – Benedict Eastaugh Apr 8 '12 at 15:23
10x for the responses I just have one more question, how can I prove that $\{0,1\}^N$ and ${N}^{\{0,1\}}$ are infinite by showing a countable set in each one of them? – JanosAudron Apr 8 '12 at 16:14
It won't be true for any arbitrary set $N$. Did you want to show that it holds for a specific set? – Benedict Eastaugh Apr 8 '12 at 16:19
N stands for The Natural numbers – JanosAudron Apr 8 '12 at 16:31

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.

share|cite|improve this answer
Hey anon thanks for the help just, if you don't you mind, can you check the LaTeX syntax plz... – JanosAudron Apr 8 '12 at 17:36
@Janos: Check what syntax specifically? – anon Apr 8 '12 at 17:45
never mind its ok now :) – JanosAudron Apr 8 '12 at 17:48

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.