Why is $2^{\aleph_0}>\aleph_0$, but ${\aleph_0}^2=\aleph_0$?

Question

I understand the direct arguments as to why $2^{\aleph_0}=\aleph_1$. What I'm wondering about is if there is some straightforward/intuitive explanation as to why "infinity being in the exponent" is the magic line that bumps things up to the next cardinality, while $\aleph_0+\aleph_0=\aleph_0$ and $\aleph_0 \cdot \aleph_0=\aleph_0$, $(\aleph_0)^x=\aleph_0$, etc., or whether this is just a result that comes from the math that needs to be accepted.

Answer 1

I think, a possible not-so-good explanation may be that any infinity taken once or twice or any finite number of times doesn't change anything. We can extend our idea of constructing bijections from $\mathbb A\to \mathbb A\times \mathbb A$ to constructing bijections from $\mathbb A\to \mathbb A\times \mathbb A\times \dots \times \mathbb A$ where there are only finite number of $\mathbb A$'s in there.

But, when you take an infinity infinite number of times, that's when we add another dimension of infinity. It's intuitively similar to why there is no bijection from $\mathbb A \to \mathbb A\times \mathbb A\times \mathbb A\times\dots$ where there are infinite number of $\mathbb A$'s (this can be easily proved using Cantor's diagonalisation argument if $\mathbb A=\mathbb N$).

Rob Arthan pointed out that the second paragraph doesn't make sense for larger infinities than $\mathbb N$. While that's true, what I actually meant was this adding another dimension of infinity part. Since $\mathbb N$ is a smaller infinity than $\mathbb R$, taking $\mathbb R$, $\mathbb N$ times still doesn't change much. But when you take $\mathbb R$, $\mathbb R$ times, that's when the infinity changes.

And, about Trevor's question of $2^{\aleph_0}$, I would rather think of $2^{\mathbb A}$ as the collection of all subsets of $\mathbb A$. Now, if you take only the collection of one-element subsets of $\mathbb A$, that's the same infinity as that of $\mathbb A$. Same holds for a collection of $k$ element subsets of $\mathbb A$ where $k$ is finite or a strictly smaller infinity than that of $\mathbb A$. But, when you take all the subsets, that's when you are adding that dimension.

Does that make sense?

Answer 2

I had a thought; this is coming from a compsci perspective and offers another way to view the $2^x$ aspect of it.

Suppose you have magic RAM that can do the things I'm about to describe.

You store some data of length $\aleph_0$ on it. To reference specific individual elements (or bits) of your data, you can do it by providing an address, and that address will always be some finite sequence of bits, a binary number. Since the union of all possible addresses (all finite numbers) will suffice to let you access the entire object, and since all finite numbers jointly comprise $\mathbb N$, mapping to $\aleph_0$, this checks out as the size of the data.

You also store some data of length $\aleph_1$ on it. To reference specific bits of this object, each address will need to be a bit string of length $\aleph_0$. Since this much addressing information is sufficient to map an address to every bit in the object, it's also a measure of the size of the object itself, as we know that $2^{\aleph_0}$ describes every possible address for such an object, and therefore corresponds to its size. This is similar to how $32$ bits is exactly what you need to describe the location of a specific byte within $4$ GB, which is $2^{32}$ bytes.

Answer 3

We avoid using the OP's cardinality statements, casting them instead in terms of the objects $\Bbb N$ and $2^{\Bbb N}$.

We can also equivalently use the power set $\mathcal{P}(\Bbb N)$ to represent $2^{\Bbb N}$.

If you are presented with the (impossible) task of constructing a surjective mapping from $\Bbb N$ to $\mathcal{P}(\Bbb N)$ begin by contemplating the injective mapping

$\quad \kappa: \; n \mapsto \{n\}$

The function $\kappa$ is only hitting the singletons and has the following properties

$\quad \forall n \; n \in \kappa(n)$

$\quad \emptyset \notin \kappa(\Bbb N)$

If we could change $\kappa$ so that for some integer $b$, $\,\kappa(b) = \emptyset$, then $b \notin \kappa(b)$.

We now intuitively realize that if $\kappa$ were to become a surjection the set

$\tag 1 B = \{b \in \Bbb N \mid b \notin \kappa(b)\}$

would be of interest - $\kappa$ must disassociate from the initial integer atoms to get full coverage.

The set $B$ is a measure (in the imagination) of how much $\kappa$ is a disassociative mapping. And it would certainly be amusing if there was no way that $B$ itself could be in the range of $\kappa$.

But that is indeed the case; see the proof of Cantor's theroem.