0
$\begingroup$

The above definition was given to me by a friend of mine who introduced me to $\aleph$, and infinite sets. The argument he gave me was (paraphrased how I understand it).

While the set of natural numbers is infinite, each number has only a finite number of digits.
Each real number as an infinite number of digits. (The rest is filled up with 0s).
We can represent each real number using binary numbers.
Map each bit of the real numbers to an element of $\mathbb N$.
The cardinality of $\mathbb N$ is $\aleph_0$.
There are $2^{\aleph_0}$ possible combinations of the bits.
There are $2^{\aleph_0}$ real numbers.

He then sort of defined $2^{\aleph_0}$ as $\aleph_1$. I'm guessing the cardinality of the real numbers is taken to be $\aleph_1$?

Said friend also said he has a proof that $\aleph_0^k = \aleph_0$. I haven't yet read his proof as at the time of writing, and may update this question with it when I do. I've been told here that

you can't claim $2^{\aleph_0} = \aleph_1$

which surprised me, but I can't be so sure of the definition myself, so.  
My question is:

Is $\aleph_1 = 2^{\aleph_0}$?

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Continuum_hypothesis $\endgroup$ – i707107 Jun 6 '17 at 17:39
  • $\begingroup$ what do you ask? $\endgroup$ – Mirko Jun 6 '17 at 17:48
  • $\begingroup$ Is k a cardinal or just a natural number? If it is a natural number then the result is obvious. $\endgroup$ – Jacob Wakem Jun 6 '17 at 17:50
  • 1
    $\begingroup$ There were many questions about this before. $\endgroup$ – Asaf Karagila Jun 6 '17 at 17:52
  • $\begingroup$ Coincidentally, the question proof of $2^{\aleph_{0}} = \mathfrak{c}$ was posted just yesterday (and spun off some discussion about the distinction between $\aleph_{1}$ and $\mathfrak{c}$). $\endgroup$ – Andrew D. Hwang Jun 6 '17 at 17:53
6
$\begingroup$

Your friend was incorrect when he defined $\aleph_1$ to be $2^{\aleph_0}$. It is possible that $\aleph_1=2^{\aleph_0}$ (this statement is called the "continuum hypothesis"), but it is also possible that $\aleph_1<2^{\aleph_0}$. Indeed, it is known that the usual axioms of set theory (ZFC) cannot decide this question: it is consistent with ZFC that CH holds, and consistent with ZFC that CH fails. In fact, essentially the only thing that ZFC can prove about $2^{\aleph_0}$ is that it has uncountable cofinality; for instance, it is consistent with ZFC that $2^{\aleph_0}=\aleph_{\omega^2\cdot 3+17}$, which is pretty wild!

So what are the right definitions?

  • $2^{\aleph_0}$ is defined to be the cardinality of the set of functions from $\mathbb{N}$ (or, any set of size $\aleph_0$) to $\{0,1\}$ (or, any set of size $2$). It turns out that this is also the cardinality of $\mathbb{R}$; this isn't hard to show, but also isn't trivial (an important issue is the fact that a real number can have multiple decimal expansions). By Cantor's diagonal argument, $2^{\aleph_0}$ is uncountable.

  • Meanwhile, $\aleph_1$ is defined to be the cardinality of the smallest uncountable ordinal; equivalently, it is the number of distinct ordertypes of countable ordinals. By an argument similar to that of the Burali-Forti paradox, $\aleph_1$ is uncountable, and (assuming a very mild version of the axiom of choice) $\aleph_1$ is the least uncountable cardinality.

Note that these two objects have very different definitions, so it shouldn't be surprising that they are not perfectly related. They are often conflated, possibly due to the fact that $2^{\aleph_0}$ is often assumed to be the next "nicely definable" cardinality after $\aleph_0$ (which is an interesting claim which is studied extensively in descriptive set theory); however, this conflation is indeed incorrect unless the author explicitly assumes CH (or some additional axiom implying CH).


Incidentally, it is quite easy to show that $\aleph_0^k=\aleph_0$ for finite $k$, so your friend was correct there.

$\endgroup$
  • $\begingroup$ Can you not show that $2^{\aleph_0}\geq\aleph_1$ using Cantor's theorem? I.e., the powers set of $\aleph_0$ should be at least as great as the next infinite cardinal. Thanks. With regards, $\endgroup$ – user12802 Oct 21 '17 at 12:40
  • 2
    $\begingroup$ @Andrew Yes, of course. And one can do more: by Konig's theorem, $2^{\aleph_0}$ has uncountable cofinality, so we can't have e.g. $2^{\aleph_0}=\aleph_\omega$. And Solovay showed that that is all we can prove, in ZFC. $\endgroup$ – Noah Schweber Oct 21 '17 at 14:54
  • $\begingroup$ Thanks for your insight. $\endgroup$ – user12802 Oct 21 '17 at 17:37

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.