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

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.

• $2^{\aleph_0}$ is strictly greater than $\aleph_0$, but it is not necessarily equal to $\aleph_1.$ This is the continuum hypothesis. Jul 4, 2021 at 21:34
• Also $\aleph_0^x$ is not equal to $\aleph_0$ unless $x$ is finite. In fact, ${\aleph_0}^{\kappa}=2^{\kappa}$ for any $\kappa\ge \aleph_0$. Jul 4, 2021 at 21:38
• Why do you think they should be the same? Why is $2^{100}$ so much bigger than $100^2$?
– bof
Jul 4, 2021 at 21:50
• Yep, I'm assuming CH, I figured that was implied. Jul 5, 2021 at 11:25

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?

• Your second paragraph is not correct: $\Bbb{R}$ is equipollent with $\Bbb{R}^\Bbb{N}$, i.e., $\Bbb{R} \times \Bbb{R} \times \Bbb{R}\times \ldots$ with a countably infinite number of $\Bbb{R}$s. Jul 4, 2021 at 22:57
• Thanks, this is exactly the sort of answer I was looking for; in order to reach a higher cardinality, an infinity must be applied to itself, and you don't find that in the lesser expressions I gave. Jul 5, 2021 at 3:20
• Actually, wait -- it's a good explanation as to why ${\aleph_0}^{\aleph_0}=\aleph_1$, but what about $2^{\aleph_0}=\aleph_1$? That's still just "doing something with something finite" (multiplying 2s) infinity times, just as $2\aleph_0$ is adding 2s infinity times, but clearly with different results between the two. Jul 5, 2021 at 3:27
• @RobArthan Oh yes! What I 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. Jul 5, 2021 at 4:48
• @Trevor Yes, but I think of it in a different way. 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. Jul 5, 2021 at 4:53

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.

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.