2
$\begingroup$

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.

$\endgroup$
4
  • 9
    $\begingroup$ $2^{\aleph_0}$ is strictly greater than $\aleph_0$, but it is not necessarily equal to $\aleph_1.$ This is the continuum hypothesis. $\endgroup$ Jul 4, 2021 at 21:34
  • 3
    $\begingroup$ 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$. $\endgroup$ Jul 4, 2021 at 21:38
  • 8
    $\begingroup$ Why do you think they should be the same? Why is $2^{100}$ so much bigger than $100^2$? $\endgroup$
    – bof
    Jul 4, 2021 at 21:50
  • $\begingroup$ Yep, I'm assuming CH, I figured that was implied. $\endgroup$
    – Trevor
    Jul 5, 2021 at 11:25

3 Answers 3

6
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Rob Arthan
    Jul 4, 2021 at 22:57
  • $\begingroup$ 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. $\endgroup$
    – Trevor
    Jul 5, 2021 at 3:20
  • $\begingroup$ 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. $\endgroup$
    – Trevor
    Jul 5, 2021 at 3:27
  • $\begingroup$ @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. $\endgroup$ Jul 5, 2021 at 4:48
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 5, 2021 at 4:53
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.