Are there any known examples of sets that are definitely infinite, but where we don't know whether or not they're countable? I haven't heard of anything like this before, but it seems that there should be some example of a set like this.

As mentioned in the comments, it's possible to construct examples of the form

$$ S = \left\{ \begin{array}{ll} \mathbb{N} & \quad \mbox{if } P \mbox{ holds} \\ \mathbb{R} & \quad \mbox{otherwise} \end{array} \right. $$

where $P$ is some unresolved conjecture in mathematics. Certainly these sets work, but I was hoping for an example that arose "naturally" in the course of mathematics.


  • $\begingroup$ All the examples that come to mind are examples of sets which are consistently countable, and consistently uncountable. But I can't recall a case where we "didn't know whether or not it is countable or not". $\endgroup$ – Asaf Karagila May 29 '14 at 18:52
  • $\begingroup$ the things that we do not know ... $\endgroup$ – mesel May 29 '14 at 18:52
  • 3
    $\begingroup$ There is always "$X=\mathbb N$ if $\mathsf{CH}$ holds, and $X=\mathbb R$ otherwise". The point of this silly example is that it seems rather difficult to make the question precise in a way that avoids examples of this kind. $\endgroup$ – Andrés E. Caicedo May 29 '14 at 18:53
  • 1
    $\begingroup$ @Andres: In the meantime, I've proposed one problem which might fit the description. $\endgroup$ – Asaf Karagila May 29 '14 at 19:12
  • 1
    $\begingroup$ @AsafKaragila Yes, nice example. I'm hoping for something in analysis. (The supremum of the sizes of strong measure zero sets is an example, but we know the answer is consistently $\aleph_0$ and consistently larger, and the ideal --as in your answer-- is something for which we do not yet know this.) $\endgroup$ – Andrés E. Caicedo May 29 '14 at 19:20

Here's a wonderful open problem in set theory, which can be translated to a statement which you might be looking for.

Suppose that $\aleph_\omega$ is a strong limit cardinal. Is $2^{\aleph_\omega}<\aleph_{\omega_1}$?

We can prove that under the assumption that $\aleph_\omega$ is a strong limit cardinal, it is necessarily the case that $2^{\aleph_\omega}<\aleph_{\omega_4}$. This is one of Shelah's most celebrated results from PCF theory. And we can arrange for every countable successor ordinal $\alpha>\omega$, that is the case that $2^{\aleph_\omega}=\aleph_\alpha$ (well, under certain additional assumptions anyway).

So we can rephrase the question as follows:

Assuming that $\aleph_\omega$ is a strong limit cardinal. Is the set $\{\alpha\mid\aleph_\alpha<2^{\aleph_\omega}\}$ provably countable?

This set is always infinite, since every finite ordinal is necessarily in this set. But as the aforementioned problem shows, we do not know if it is always countable (even if we don't know exactly what is this set), or if it is possible for it to be uncountable.

| cite | improve this answer | |
  • $\begingroup$ I deleted my comment because I realized that if we just look at a fixed universe, then we would have a particular set, if we start with just a formula defining a set with cardinality independent of ZFC. Thanks for the response. $\endgroup$ – Carl Mummert May 30 '14 at 0:17
  • $\begingroup$ Sure, and sorry for deleting my comment as well. I decided to get some sleep after all. :-) $\endgroup$ – Asaf Karagila May 30 '14 at 0:18

A simple example that occurs naturally in set theory (although it is not as mysterious as the one in Asaf's answer and there are probably no more open problems about it) is the set $\mathbb{R} \cap L$ of all constructible reals. If $V = L$ then of course this set is uncountable, but the statement "$\mathbb{R} \cap L$ is countable" can be proved consistent relative to $\mathsf{ZFC}$ by forcing, and it also follows from large cardinal axioms (for example, from the existence of a measurable cardinal, or just from the existence of $0^\sharp$.)

The statement "$\mathbb{R} \cap L$ is countable" is equivalent to the statement "every $\Sigma^1_2$ set of reals with a $\Sigma^1_2$ well-ordering is countable," where $\Sigma^1_2$ denotes the pointclass of projections of co-analytic sets. There is an open problem along these lines about a pointclass much bigger then $\Sigma^1_2$:

Does any large cardinal axiom imply that every $(\Sigma^2_1)^{\text{uB}}$ set of reals with a $(\Sigma^2_1)^{\text{uB}}$ well-ordering is countable?

Here $\text{uB}$ denotes the pointclass of all universally Baire sets of reals, and a set of reals $A$ is called $(\Sigma^2_1)^{\text{uB}}$ if there is a formula $\varphi$ such that $x \in A \iff \exists B \in \text{uB}\,(\text{HC};\in , B) \models \varphi[x]$ for every real $x$. Essentially the question asks whether there is a large cardinal axiom that transcends the pointclass $(\Sigma^2_1)^{\text{uB}}$ in the way that $0^\sharp$ transcends the pointclass $\Sigma^1_2$.

For technical reasons, let's strengthen the notion of "$(\Sigma^2_1)^{\text{uB}}$ well-ordering of a $(\Sigma^2_1)^{\text{uB}}$ set of reals" to "$(\Sigma^2_1)^{\text{uB}}$-good well-ordering," by which we mean that the well-ordering has length $\le \omega_1$ and the set of reals coding its proper initial segments is a $(\Sigma^2_1)^{\text{uB}}$ set. It is consistent (as shown using forcing) that all such well-orderings are countable.

If there is a proper class of Woodin cardinals (a fairly mild large cardinal assumption,) then there is a canonical $(\Sigma^2_1)^{\text{uB}}$ set of reals that is maximal under inclusion among $(\Sigma^2_1)^{\text{uB}}$ sets of reals admitting $(\Sigma^2_1)^{\text{uB}}$-good well-orderings. This canonical $(\Sigma^2_1)^{\text{uB}}$ set of reals can be thought of as a higher-order analogue of $\mathbb{R} \cap L$, and the question asks whether any large cardinal axiom implies that it is countable. A "yes" answer would be a very important development for the field of inner model theory.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.