# Proof that c = 2^aleph-naught **URL:** \ **Category:** Factual Questions\ **Created:** [September 12, 2014, 1:56am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253 "2014-09-12T01:56:51Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![Saint\_Cad](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/saint_cad/32/18907_2.png) [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)\ **Post date:** [September 12, 2014, 1:56am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/1 "2014-09-12T01:56:51Z")
I was reading up on the continuum hypothesis and was thinking of the proof that c is the same cardinality of the power set of the natural numbers. It seems to me that assuming the axiom of choice that every real number between [0, 1) can be put into a 1-1 correspondence with the power set of the naturals pretty easily. First, think of categorizing the naturals into 1 digit, 2 digit, 3 digit, etc numbers. If you think of a real as the first digit, next two digits, next three digits and so on this clearly would correspond to the element of the power set. For example: 0.2834692270… \<=\> {2, 83, 469, 2270, …} It should not be too hard to show this is a bijection and therefore equal cardinality. It seems too simple so what am I missing? ---
**Author:** ![j\_sum1](https://avatars.discourse-cdn.com/v4/letter/j/8baadc/32.png) [@j\_sum1](https://boards.straightdope.com/u/j_sum1)\ **Post date:** [September 12, 2014, 2:14am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/2 "2014-09-12T02:14:38Z")
I am no expert here. I am mostly commenting from what I have learned on these boards. However, my understanding is that you are correct. c = 2^aleph-naught if the axiom of choice is assumed. c ≠ 2^aleph-naught if the axiom of choice is not assumed. The details of the proof are beyond me. I also believe (and stand to be corrected) that if the AOC is not assumed then it is not possible to determine whether c is greater than or less than 2^alephnaught. No wonder Cantor went mad. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [September 12, 2014, 2:38am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/3 "2014-09-12T02:38:55Z")
Your proof doesn’t work, since it doesn’t hit all subsets, only those with a single one-digit number, a single two-digit number, a single three-digit number, and so on. The proof is, however, still fairly simple, and does not depend on the Axiom of Choice. Express your real number in binary, and let a 1 in the nth place mean that you include n in your subset. So, for instance, the real number 0.101010101… corresponds with the set of all odd numbers, and 0.0110101000101000101… corresponds with the set of prime numbers, and so on. There are still a few details dealing with the fact that 0.01111111… = 0.1000000… and so on, but that’s the gist of it. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [September 12, 2014, 2:40am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/4 "2014-09-12T02:40:10Z")
> [@Saint\_Cad](#): > > For example: 0.2834692270… \<=\> {2, 83, 469, 2270, …} Nitpick: Leading zeros will prevent a true bijection in this scheme: 0.102003000 =\> {1, 2, 3, 0} = {1, 3, 2, 0} =\> .103002000 This can be avoided by prefixing a ‘1’: 0.2834692270… \<=\> {12, 183, 1469, 12270, … } But that gives you an injection. A surjection is also easy, and together thay are good enough by Cantor-Bernstein. For a pure bijection I _think_ one of the simplest maps is shown by the following example, using binary representation: 0.110011000… \<==\> {1, 2, 5, 6, … } where the subset contains the places with ‘1’. ETA: Ninja’ed by Chronos while I was removing typos from my post. ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [September 12, 2014, 7:41am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/5 "2014-09-12T07:41:19Z")
> [@j\_sum1](#): > > I am no expert here. I am mostly commenting from what I have learned on these boards. > However, my understanding is that you are correct. c = 2^aleph-naught if the axiom of choice is assumed. c ≠ 2^aleph-naught if the axiom of choice is not assumed. Here, c is the cardinality of the continuum, i.e., of the real numbers. By definition, \aleph[SUB]0[/SUB] is the first infinite cardinal (viz., the cardinality of the integers), and \aleph[SUB]n+1[/SUB] is the smallest cardinal greater than \aleph[SUB]n[/SUB]. (The definition can also be applied to arbitrary cardinals, but requires some technical details I’m avoiding here.) Cantor’s argument shows that c = 2[SUP]\aleph[SUB]0[/SUB][/SUP]. The continuum hypothesis is about whether 2[SUP]\aleph[SUB]0[/SUB][/SUP] = \aleph[SUB]1[/SUB]. which is a different matter entirely. Also, the axiom of choice is not the same as the continuum hypothesis. The latter is still undecidable within ZFC (Zermelo-Fraenkel set theory + the axiom of choice): There are models in which it does and does not hold. ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [September 12, 2014, 7:47am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/6 "2014-09-12T07:47:37Z")
> [@Itself](#): > > (The definition can also be applied to arbitrary cardinals, but requires some technical details I’m avoiding here.) Arbitrary _ordinals_, rather. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [September 12, 2014, 7:51am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/7 "2014-09-12T07:51:23Z")
> [@Chronos](#): > > Your proof doesn’t work, since it doesn’t hit all subsets, only those with a single one-digit number, a single two-digit number, a single three-digit number, and so on. > > The proof is, however, still fairly simple, and does not depend on the Axiom of Choice. Express your real number in binary, and let a 1 in the nth place mean that you include n in your subset. So, for instance, the real number 0.101010101… corresponds with the set of all odd numbers, and 0.0110101000101000101… corresponds with the set of prime numbers, and so on. > > There are still a few details dealing with the fact that 0.01111111… = 0.1000000… and so on, but that’s the gist of it. Yup. You don’t need the Axiom of Choice at all. One point of note is that you DO need classical Boolean logic, in that the reals (defined in various natural ways) needn’t be isomorphic to 2^N or P(N) or any such thing in the framework of intuitionistic logic, tripping precisely upon the inability to carry out (in this context) the patching-up dealing with this 0.0111… = 0.100… business. Put another way, as **septimus** noted, it all comes down to the Cantor-Schroeder-Bernstein theorem, and this holds classically without assuming choice, but does not hold intuitionistically. ---
**Author:** ![j\_sum1](https://avatars.discourse-cdn.com/v4/letter/j/8baadc/32.png) [@j\_sum1](https://boards.straightdope.com/u/j_sum1)\ **Post date:** [September 12, 2014, 9:26am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/8 "2014-09-12T09:26:41Z")
Thanks **Itself**. I’m misremembering and getting my wires crossed. Huge week and freakishly tired. I should never have posted. It was almost inevitable that I would stuff something up. J. ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [September 12, 2014, 9:36am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/9 "2014-09-12T09:36:56Z")
> [@j\_sum1](#): > > Thanks **Itself**. I’m misremembering and getting my wires crossed. Huge week and freakishly tired. I should never have posted. It was almost inevitable that I would stuff something up. > J. Oh, it’s no problem at all (and it’s totally fine that you posted; I wouldn’t be surprised if a number of other posters misremembered similarly). ---
**Author:** ![Hellestal](https://avatars.discourse-cdn.com/v4/letter/h/3ab097/32.png) [@Hellestal](https://boards.straightdope.com/u/Hellestal)\ **Post date:** [September 12, 2014, 1:26pm UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/10 "2014-09-12T13:26:53Z")
> [@Chronos](#): > > There are still a few details dealing with the fact that 0.01111111… = 0.1000000… and so on, but that’s the gist of it. I’m not sure I follow this step… Is there a 40-page thread you can cite to make sense of this? ---
**Author:** ![Learjeff](https://avatars.discourse-cdn.com/v4/letter/l/94ad74/32.png) [@Learjeff](https://boards.straightdope.com/u/Learjeff)\ **Post date:** [September 12, 2014, 3:23pm UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/11 "2014-09-12T15:23:37Z")
> [@Hellestal](#): > > I’m not sure I follow this step… > > Is there a 40-page thread you can cite to make sense of this? I think that’s the only bit I followed. The point being that with the above arguments, we have two different representations for the same number, but which would be counted twice using the counting algorithm. Since I really don’t understand at least half of what’s being said in this thread, I could be way off base, so please let me know! ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [September 12, 2014, 6:29pm UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/12 "2014-09-12T18:29:40Z")
> [@Hellestal](#): > > I’m not sure I follow this step… > > Is there a 40-page thread you can cite to make sense of this? The issue is whether when there is a 1-1 map from X to Y and a 1-1 map from Y to X, then there is a bijection between X and Y. That is the Cantor-Shroeder-Bendixson theorem mentioned upthread. It doesn’t require 40 pages either, but it does require that subsets have complements, essentially excluded middle and that is not valid intuitionistically. There are models of set theory in which that fails. However, the excluded middle does follow from AC (Diaconescu’s theorem), but is a good bit weaker. Okay, here is a sketch. Details left to the interested reader. Suppose f: X –\> Y and g: Y –\> X are 1-1 maps. To simplify the notation, let me denote by f\*, g\* the inverse image of functions of f and g, resp. E.g., for y in Y, f\*(y) is the unique (since f is 1-1) x such that f(x) = y and is undefined if there isn’t any such x. Now take a y. There are three possibilities: 1. The sequence …f_g_f\*(y) goes on forever. Let us call Y\_1 the set of such y. 2. The sequence terminates in X. That is some iterate f_g_…f\*(y) is defined, g\* of that element is undefined. Call that set Y\_2. 3. In the same way, the sequence terminates in Y. Call that set Y\_3. Similarly, define X\_1, X\_2, and X\_3 as the subsets for which the corresponding sequence fails to terminate or terminates in X or Y. Incidentally, an element y in Y for which f\*(y) does not exist terminates in Y. Now the following facts are true (assuming excluded middle: 1. X is the union of the three disjoint sets X\_1, X\_2, and X\_3 2. Similarly for Y. 3. Either f or g defines a bijection between X\_1 and Y\_1; f determines a bijection between X\_2 and Y\_2; g determines a bijection between Y\_3 and X\_3. There, that didn’t take 40 pages. ---
**Author:** ![RadicalPi](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/radicalpi/32/9806_2.png) [@RadicalPi](https://boards.straightdope.com/u/RadicalPi)\ **Post date:** [September 12, 2014, 6:36pm UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/13 "2014-09-12T18:36:36Z")
> [@Hellestal](#): > > I’m not sure I follow this step… > > Is there a 40-page thread you can cite to make sense of this? > [@Hari\_Seldon](#): > > The issue is whether […] didn’t take 40 pages. I’m pretty sure Hellestal is referring to the 0.9999… = 1 thread. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [September 13, 2014, 1:07am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/14 "2014-09-13T01:07:18Z")
> [@Chronos](#): > > There are still a few details dealing with the fact that 0.01111111… = 0.1000000… and so on, but that’s the gist of it. Just to dispose of this detail: For x which is a multiple of a negative power-of-two (the cases which have two representations), distinguish three cases: If x \< 0.5, substitute (2x), use the …000… form, and proceed as Chronos and I described. If x \> 0.5, substitute (2x-1), use the …111… form and proceed as Chronos and I described. If x = 0.5, substitute (1= .1111111…) It seems nifty that the “troublesome” x=.5 case is actually helpful: the complete set {1, 2, 3… } is otherwise missing. Voilà! A perfect bijection between the reals in [0,1) and the subsets of {1,2,3,…}, unless I am mistaken. > [@Indistinguishable](#): > > One point of note is that you DO need classical Boolean logic, in that the reals (defined in various natural ways) needn’t be isomorphic to 2^N or P(N) or any such thing in the framework of intuitionistic logic, tripping precisely upon the inability to carry out (in this context) the patching-up dealing with this 0.0111… = 0.100… business. I’m not sure what you’re saying. Is my approach too LOGICal? 😉 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [September 13, 2014, 1:35am UTC](https://boards.straightdope.com/t/proof-that-c-2-aleph-naught/698253/15 "2014-09-13T01:35:47Z")
I suspect that the problem with your approach is that you need, in principle, an infinite number of digits to distinguish between the x=0.5 and x\>0.5 cases. Some alternate formulations have a problem with that; I’m not certain if “intuitionist” math is one of them (I use the scare quotes because intuitionist math is in no way intuitive). Actually, come to think of it, you also need an infinite number of digits to determine whether x is a multiple of a negative power of 2 to begin with.