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?
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.
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.
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.
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.
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.
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.
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!
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:
The sequence …fgf*(y) goes on forever. Let us call Y_1 the set of such y.
The sequence terminates in X. That is some iterate fg…f*(y) is defined, g* of that element is undefined. Call that set Y_2.
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:
X is the union of the three disjoint sets X_1, X_2, and X_3
Similarly for Y.
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.
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.
I’m not sure what you’re saying. Is my approach too LOGICal?
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.
