# 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...

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, 2016 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$. Aug 29, 2016 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, 2016 at 0:36
• @SSD Yes. There is no set at all - of any cardinality - such that $(\aleph_0)^Y\equiv \aleph_\omega$. Aug 30, 2016 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). Sep 4, 2016 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, 2018 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. Jul 17, 2018 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, 2018 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$. Jul 17, 2018 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, 2018 at 3:19