28
$\begingroup$

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

$\endgroup$
1
  • 14
    $\begingroup$ The notation $X^Y$ is commonly used for the set of all functions from $Y$ to $X$. $\endgroup$ Commented Apr 8, 2012 at 13:24

2 Answers 2

30
$\begingroup$

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

$\endgroup$
10
  • 5
    $\begingroup$ 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))$. $\endgroup$
    – user856
    Commented Apr 8, 2012 at 13:47
  • $\begingroup$ @RahulNarain of course, thanks—I had to dash off before answering the second part, but I'll edit my answer with it. $\endgroup$ Commented Apr 8, 2012 at 15:23
  • $\begingroup$ 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? $\endgroup$ Commented Apr 8, 2012 at 16:14
  • $\begingroup$ It won't be true for any arbitrary set $N$. Did you want to show that it holds for a specific set? $\endgroup$ Commented Apr 8, 2012 at 16:19
  • $\begingroup$ N stands for The Natural numbers $\endgroup$ Commented Apr 8, 2012 at 16:31
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Hey anon thanks for the help just, if you don't you mind, can you check the LaTeX syntax plz... $\endgroup$ Commented Apr 8, 2012 at 17:36
  • $\begingroup$ @Janos: Check what syntax specifically? $\endgroup$
    – anon
    Commented Apr 8, 2012 at 17:45
  • $\begingroup$ never mind its ok now :) $\endgroup$ Commented Apr 8, 2012 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .