# Undecidable cardinality

Let $$S$$ be an infinite subset of $$\mathbb{R}$$ with the property that the existence of $$S$$ can be proved within ZFC (and in particular the definition of $$S$$ does not invoke the negation of the continuum hypothesis), but the cardinality of $$S$$ is undecidable within ZFC.

Are there some concrete examples of such sets?

I.e. something more constructive than $$S:=$$ some subset of cardinality $$\aleph_1$$?

This question results from musing about intuitively obvious equivalents of $$\neg CH$$ in order to find evidence against the validity of $$CH$$. My (undoubtedly too optimistic) thinking was that if some such example of $$S$$ is concrete enough, it would be perhaps intuitively obvious whether it should be countable or continuum, despite this being undecidable formally.

My best guess for the moment is something along the lines of

$$S=\left\{\sum_n\frac{1}{a_n}:\; (a_n)\;\text{is a strictly increasing sequence of primes}\right\}$$

but surely the cardinality can be determined (though not quite sure how).

• The existence of $\{x\in\Bbb R\mid\sf CH\}$ is provable in ZFC, but if CH fails, the set is empty and if CH holds it's the entire real line. Jun 5, 2019 at 22:10
• Yes, I just realised precisely that and edited to make clear what I mean. Jun 5, 2019 at 22:11
• Your set has cardinality continuum. In fact, $S=\mathbb R^+$. Jun 5, 2019 at 22:16
• @Wojowu: how do you prove that? I only see that $S$ is unbounded. Jun 5, 2019 at 22:19
• Briefly, fix $x>0$. Pick $a_n$ inductively so that it's the smallest prime above $a_{n-1}$ such that the sum $1/a_1+\dots+1/a_n<x$. You can show that the sum of this series is $x$ because the sum of prime reciprocals diverges. Jun 5, 2019 at 22:21

There are several problems with your question.

1. Invoking undecidable statements does not mean that the existence of the set is not provable. We can define $$S=\{x\in\Bbb R\mid\sf CH\}$$ which is empty if $$\sf CH$$ fails, and is the whole set of real numbers if it holds.

2. What does it mean to decide the cardinality of a set? Surely saying that the cardinality is the same as that of the real numbers is something decisive. Indeed, $$S$$ that you suggestion satisfies that, even though it is not a set of real numbers, as some of these sums do not converge.

What you mean want to argue is that the index of the $$\aleph$$ cardinal is decidable. That is something more concrete, but then $$\Bbb R$$ itself is an example for a set which provably exist and we cannot say much more than that.

3. If you do accept $$2^{\aleph_0}$$ as "a good answer for cardinality", then it seems to me that you're actually asking whether or not we can define a set of real numbers whose cardinality is $$\aleph_1$$. To that the answer is "depends on what you mean by that". Define in what sense? In the set theoretic universe? With parameters? With real numbers and ordinals as parameters? Define with a predicative definition?

These answers tend to end up with different answers. But it is consistent with $$\sf ZFC$$ that every projective set is either countable or of size $$2^{\aleph_0}$$, which may or may not be larger than $$\aleph_1$$. Since projective sets are what we might "normally think of" when we think about definable sets of real numbers, this shows that the answer to your question is more or less "no, we cannot explicitly construct a projective set of reals of cardinality $$\aleph_1$$ in $$\sf ZFC$$".

The proof is not at all trivial, and it does require some large cardinal assumptions. If you move away from projective sets, you start getting a bit messier answers (e.g. it can be trivial in the sense that every set is definable from itself as a parameter).

• @Damian: You can't. That's the point. Jun 5, 2019 at 22:35
• @Damian: Almost anything "down-to-earth" that you'd write is Borel, and probably $\Sigma^0_4$ or less. Jun 5, 2019 at 22:42
• @Damian: If it were clear, it wouldn't have taken decades of research by very smart people, would it? Jun 5, 2019 at 22:55
• @Damian: Well, go ahead. Study this. It will take you a couple of years, and by the end you'd be a set theorist. Join us, it's great. We have very nice conferences! Jun 5, 2019 at 23:04
• @DamianReding You might want to look at a proof of "every Borel (even analytic) set is countable or has the size of the continuum". This should not take too long to understand. Jun 5, 2019 at 23:13