# Continuum Hypothesis - Why does my “proof” fail?

While thinking about the Continuum Hypothesis, I stumbled across a way of thinking about it that seems to intuitively make sense to me. But, being that I'm not a mathematician and Gödel/Cohen together have shown that the $$\sf{CH}$$ is independent of the $$\sf{ZFC}$$ axioms, I understand that this is $$99.999999999999\%$$ likely to be wrong. Anyway, here is my thinking, and if possible, I'd like to know where it is that I went awry:

Idea:

The assumption underlying my "proof" is that the number of natural numbers you need to "index" a set corresponds to its cardinality. Therefore, if you have a set $$A$$ with a cardinality $$a$$, and a set $$B$$ with a cardinality $$b$$, and you need $$i$$ indices to index $$A$$, and $$j$$ indices to index $$B$$, and you can show that there exists no number of indices between $$i$$ and $$j$$ that would generate a different cardinality than either $$a$$ or $$b$$, then there must be no cardinalities between $$a$$ or $$b$$.

So, let me show you what I mean by indices. The members of the set of natural numbers need only $$1$$ natural number to index them. Duh. $$1$$ gets labeled by $$1$$, $$2$$ by $$2$$, etc. So, a set with cardinality $$\aleph_0$$ only needs $$1$$ index. We also know that ordered $$n$$-tuples (with finite $$n$$) also are countable, requiring only $$1$$ index to label them. What is the next possible number of indices you could require? $$\aleph_0$$. The very next possible number of indices that would generate a different cardinality is $$\aleph_0$$. If you have $$\aleph_0$$ indices, each index being a natural number, the set of all such objects would basically be an ordered $$\aleph_0$$-Tuple. The cardinality of such a set is that of the continuum. Therefore, since there is no possible number of indices to label members of sets between finite natural numbers and $$\aleph_0$$, there are no cardinalities between $$\aleph_0$$ and the cardinality of the continuum.

Why wouldn't something like this work? It seems like either something outside my assumption is wrong, or my assumption is independent of $$\sf{ZFC}$$, and it's just one of many possible axioms that $$\sf{ZFC}$$ could be extended with...

• It is not likely to be wrong. It is wrong. :) – Pedro Tamaroff Aug 29 '16 at 22:52
• I like this question – mick Aug 29 '16 at 22:57

Your underlying assumption that "everything can be indexed nicely" basically translates to the following:

For every infinite set $X$, there is some set $Y$ such that $X\equiv (\aleph_0)^Y$, that is, the set of "$Y$-tuples" of natural numbers.

This, however, is provably false in ZFC! It turns out that we can show in ZFC using Koenig's Theorem that $(\aleph_0)^Y$ can never have size exactly $\aleph_\omega$.

In general, when reasoning about infinities, you need to be very careful and precise. Informal arguments like what you've written above - which hinge on appeals to intuition (how do you justify that every set can be "indexed" nicely?) - are more likely to confuse you than to help, until you have learned enough set theory to know when to trust them.

Incidentally, it's worth pointing out that we know that ZFC (assuming it's consistent!) can't prove the Continuum Hypothesis: if you give me a model of ZFC, I can produce (via forcing) a model of ZFC in which the Continuum Hypothesis is false (and another in which it is true).

• 1. Thanks for the answer. I appreciate it :) 2. Point to me an example of a way in which you could explicitly construct a set of cardinality $\aleph_\omega$? Or could you show that it's even in principle possible to imagine a set of such objects? It's my hunch that while infinite ordinals are valid, it's really wonky to just declare that an arbitrary class of ordered things automatically must have an omega'th item, simply because there are Aleph Null of them. For example, we know there isn't an Aleph Null'th integer, unless we make one up. Which is what I think about $\aleph_\omega$. – SSD Aug 29 '16 at 23:17
• @SSD Here's an explicit set of cardinality $\aleph_\omega$: the set of ordinals which have cardinality $\aleph_n$ for some $n<\omega$. – Noah Schweber Aug 29 '16 at 23:37
• Thanks, this is a direct answer to my concern, and I think that you've hit the nail on the head as to what the flaw was in my reasoning. – SSD Aug 30 '16 at 0:36
• @SSD Yes. There is no set at all - of any cardinality - such that $(\aleph_0)^Y\equiv \aleph_\omega$. – Noah Schweber Aug 30 '16 at 1:02
• @mick it has NOT been proven that $\vert \mathbb{R} \vert$ is less than $\aleph_\omega$. You are simply wrong. It is consistent with ZFC that the continuum is $\aleph_{\omega+1}$, for instance. This is a consequence of Solovay result, which you can Google (I gave you citations above). – Noah Schweber Sep 4 '16 at 0:27

You are right that for any uncountable set, if you try to index it with tuples of natural numbers, you will need at least $\aleph_0$ indices, so your set of all possible tuples you can create has cardinality $\aleph_0^{\aleph_0}=\mathfrak{c}$. But what if you don't actually need every possible tuple to index the elements of your set? That is, maybe if you try to label all the elements of your set with $\aleph_0$-tuples of natural numbers, you can do so, but no matter how you do it, you will have some $\aleph_0$-tuples left over at the end which you haven't used. This would mean that your set actually has cardinality smaller than $\mathfrak{c}$. And yet the set still might be uncountable: just because you can't label all the elements with finite tuples, doesn't necessarily mean that if you use infinite tuples, you will need to use all of the possible tuples.

• Hey, sorry to grave dig this, but looking back... is it not the case that even if you didn't need all tuples, as long as you needed infinite tuples, and less than or equal to $\aleph_0$, since there is no infinity less than $\aleph_0$, it follows that your cardinality is still that of the continuum? – SSD Jul 17 '18 at 2:55
• No. Why would that follow? The cardinality of the continuum is the cardinality you would get by using $\aleph_0$-tuples with no tuples left over. – Eric Wofsey Jul 17 '18 at 3:13
• Because if you have finitely fewer tuples, then you've still got $\aleph_0$ tuples. And if you have infinitely fewer tuples, since there is no infinity less than $\aleph_0$, you must be left with finitely many tuples. – SSD Jul 17 '18 at 3:15
• Perhaps a finite example would be more helpful. Let's say you have some set of things, and you want to label it with $n$-tuples of $0$s and $1$s. For instance, if your set has $4$ elements, you can use $n=2$, using the labels $(0,0)$, $(0,1)$, $(1,0)$ and $(1,1)$. Now suppose that you need tuples of at least length $3$ to label all the elements of your set. Does that mean that your set has to have $2^3=8$ elements? No, it might have fewer--specifically, it could have only $5,6,$ or $7$. – Eric Wofsey Jul 17 '18 at 3:16
• Right, but that infinite set of tuples needed must have no fewer than $\aleph_0$ members, since there is no infinity less than $\aleph_0$. And it can't have anymore either obviously. So by a sort of squeeze theorem logic, it must have $\aleph_0$ members. So this set of tuples must result in a set of cardinality continuum, since any set that requires $\aleph_0$ labels will have such a cardinality. – SSD Jul 17 '18 at 3:19

The core reason your argument doesn't work is that the set of all 'Aleph-Null-Tuples' is itself countable (the proof of this is essentially the same as the proof of the countability of the rationals), and so 'going up to Aleph-Null' in indexing doesn't actually get you to a larger size.

• Do you believe the set of real numbers is countable? Via decimal expansion, for example, they can be indexed by $\aleph_0$ tuples. – quid Aug 30 '16 at 11:21
• @quid No, I just got my wires crossed a bit. Sorry about that. [I really ought to remember to shut up sometimes :-( ] – PMar Aug 30 '16 at 12:24
• @PMar Happens to the best of us! – Noah Schweber Aug 30 '16 at 14:42