Why should $|2^\mathbb{N}|>|\mathbb{N}^2|$ be true?

Question

I've been thinking a bit about infinite things lately, and this question I had wondered about came back to me.

One of the classic expository demonstrations of Cantor's work is the two equally surprising facts that there are as many rationals as natural numbers, but there are more reals than natural numbers. This can be reduced to a statement in cardinal arithmetic, namely that $$|2^\mathbb{N}|>|\mathbb{N}^2|$$

Now, we can think of these sets as two collections of functions, $2^\mathbb{N}=\{f:\mathbb{N}\to \{0,1\}\}$ and $\mathbb{N}^2=\{f:\{0,1\}\to\mathbb{N}\}$. So it seems that what this statement (and others like it) is saying, is that if you want more functions, you're better off having a large domain than a large codomain.

Is there an intuitive explanation for why this should be true?

Answer 1

The inequality is made somewhat plausible by the observation that $|\mathbb N^2|$ is almost counting the number of $1$-element and $2$-element sets of natural numbers, while $|2^{\mathbb N}|$ counts all the sets of natural numbers. ("Almost" refers to the facts that each $2$-element set $\{a,b\}$ is counted twice, as $(a,b)$ and as $(b,a)$.)

Answer 2

This answer that I wrote explains why $\mathbb N^2$ is countably infinite.

One way to prove that $2^{\mathbb N}$ is uncountably infinite is by Cantor's diagonal argument, which I think has been iterated in stackexchange many times.

Answer 3

For a set $X$, the set $2^X$, its power set, should be much bigger than $X$. Cantor's diagonal argument gives a proof of this and I suggest that the contradiction in Cantor's argument gives some sort of indication as to why this is the case.

If you accept this, then we only need intuition as to why $\mathbb{N}, \mathbb{N}^2$ are the same size. Somehow this isn't that surprising. For instance, there are $| \mathbb{N}|$ many prime numbers, and we can associate each $n \in \mathbb{N}$ with its prime factorization which we can take to be a tuple such that each entry is a prime number and the $i$th entry is $\leq$ the $i+1$th. Then we already have an injective map $f: \mathbb{N}^2 \to \mathbb{Z}$ given by $(a, b)$ corresponds to $p_a \cdot p_b$ if $ a \leq b$ and $-p_a \cdot p_b$ otherwise.

The point of this is that $\mathbb{N}$ is the set of $1$-tuples of naturals and $\mathbb{N}^2$ is just the set of $2$-tuples and it shouldn't seem that surprising that we can re-index things to transform one into the other.

Answer 4

Continuing with Andreas answer is that for any $n \in \mathbb{N}$ we have that $\left \vert \mathbb{N}^n \right \vert = \left\vert \mathbb{N} \right\vert$ and even that $\left\vert \mathbb{N}^{<\omega} \right\vert = \left\vert \bigcup \{ \mathbb{N}^{n} \mid n \in \mathbb{N} \} \right\vert = \left\vert \mathbb{N} \right\vert$.

You can think of the functions from $n \to \mathbb{N}$ as sequences of length $n$ with values in $\mathbb{N}$, so what that is saying is that the union of all finite sequences of natural numbers is still countable!

In one sense, this may be clear if you recall the oft-quoted statement that "a countable union of countable sets is countable." But as you point out it is still very confusing. Infinities take time to get used to, but one thing you can always hold on to is that the powerset operation will always give you a larger cardinality, but in general exponentiation will not (unless you are raising it to a big enough size e.g. $\left| \mathbb{N}^{\mathbb{N}} \right| = \left| 2^{\mathbb{N}} \right|$).

Answer 5

Intuitively, it's because while functions have to be well-defined, they're allowed to be non-injective, so if you're placing arrows between the elements of two objects, you have a lot more freedom in choosing where to make your arrows point than where you can choose where to make them point from.

To put it more succinctly, you can find more ways to send things into an object than you can find ways to send things out of an object; for example, groups and rings generally have more subobjects than quotient objects.

Answer 6

There is an interesting paper about this theme that claims that the inequality $|2^\mathbb{N}|>|\mathbb{N}^2|$ need not be strict! So in stead of $|2^\mathbb{N}|>|\mathbb{N}^2|$ we have $|2^\mathbb{N}|\geq|\mathbb{N}^2|$.

Here is the link: http://www.gauge-institute.org/cantorset/CantorSetP.pdf.