4
$\begingroup$

If we add 'continuum hypothesis is false' as an axiom, then we are postulating the existence of sets whose cardinality is greater than that of naturals but less than that of reals.

But then, would this theory provide us any algorithm to produce the elements such a set? Can we give examples of such a set using this theory? Or do we just say 'Let $X$ be one such set', without giving any description of the elements of $X$.

$\endgroup$
2
  • $\begingroup$ forcing${}{}{}$? $\endgroup$ Commented May 14, 2020 at 6:31
  • $\begingroup$ @AnginaSeng Much simpler than that. See my answer below. $\endgroup$ Commented May 14, 2020 at 6:37

2 Answers 2

8
$\begingroup$

Yes.

In the context of $\sf ZFC$ we know that there is a smallest uncountable cardinal, $\aleph_1$, and by definition this is the cardinality of possible order types (that is, equivalence classes up to isomorphism) of well-orders which are finite or countable.

Cantor himself revised the Continuum Hypothesis after developing the notation of $\aleph$ cardinals in his 1891 paper, where CH is now recast as $\aleph_1=2^{\aleph_0}$.

Since we know that $2^{\aleph_0}$ is uncountable, and $\aleph_1$ is by definition the smallest uncountable cardinal, we have that $\aleph_1\leq 2^{\aleph_0}$. So if CH is false, we know that this inequality is sharp. This gives us an explicit example of a set which is of intermediate cardinality. And maybe that's enough for you, and you can stop reading here.

Not Quite.

But you might be more interested in a set of real numbers which has an intermediate cardinality. The answer to that is much more complicated. Again, using the axiom of choice, we can prove that there is a set of real numbers of size $\aleph_1$, it is even "semi-explicit":

  1. Note that every real numbers can be seen as encoding a sequence of real numbers (for example, the $n$th real in the sequence is given by the $p_n^k$ digits of your real, where $p_n$ is the $n$th prime number).

  2. Note that every finite or countable well-ordered set can be realised as a subset of the rational numbers, and thus of the real numbers, with their usual order.

  3. For every real we can assign an ordinal, then, either $0$ if it does not code a set that is well-ordered, or the order type, in case it does. Note that every order type will have $2^{\aleph_0}$ different codes, and that's okay. We're not done yet.

  4. Using the axiom of choice, choose a single real coding each well-ordered set. This set has size $\aleph_1$, pretty much by definition.

But the use of the axiom of choice is essential, and that means that we don't really have a proper algorithm, or a proper definition, or a set of real numbers which has size $\aleph_1$. In particular, that means that if CH fails, while we have a "rough notion of a counterexample within the real numbers", it is not exactly that.

So what can we do to improve this? Unfortunately, not a lot. We can ask about sets of real numbers that are definable in the context of analysis, rather than the set-theoretic context (which is what most people think of when they think of "an algorithm"), Andrés Caicedo's answer here has a lot of information as to why this is not quite possible. Namely, it is possible that CH fails, but any such failure must be somehow "exotic" or "pathological" and that every "reasonably defined set" is either countable or has the cardinality of the continuum.

Not at all.

Okay, so all of the above is in the context of $\sf ZFC$. But what happens if we want to omit the axiom of choice? Because it's not particularly "algorithmic" when we have to rely on it.

In that case, you have it even worse. It is no longer provable that $\aleph_1$ is the smallest uncountable cardinality. It is still true that there are no $\aleph_{0.5}$ cardinals, but it just might be the case that there are cardinals which are simply incomparable with $\aleph_1$. And it might just be that $2^{\aleph_0}$ is one of them.

In this case finding an intermediate cardinality is no longer easy. It might be, given a specific universe of set theory, with specific properties. But in general, there's no reason to expect any kind of uniform approach to this problem.

For example, it is quite easy (once the basic techniques have been covered) to arrange a model of $\sf ZF$ in which $\aleph_1\nleq2^{\aleph_0}$ (which immediately implies the two cardinals are incomparable), and not only that there are intermediate cardinals, but there are a lot of incomparable cardinals which are intermediate themselves.

Of course, you can argue that the "correct formulation" of the Continuum Hypothesis is $\aleph_1<2^{\aleph_0}$, in which case we fallback to the case of just finding a set of size $\aleph_1$, which requires no use of the axiom of choice. But it is arguable that Cantor's original formulation, about intermediate cardinals, is the correct one when not assuming the axiom of choice.


Conclusion.

To sum up the whole thing, this depends on how exactly you formulate CH, or rather its negation, and whether or not you want to rely on the axiom of choice. In the case where you end up with the negation phrased as $\aleph_1<2^{\aleph_0}$, finding a set is easy, but finding a set of real numbers might be hard.

And if you want to have a truly algorithmic way, then you may argue that rejecting the axiom of choice should yield the same answer, which can cause even more problems.

$\endgroup$
7
$\begingroup$

The set of equivalence classes of well-orderings of $\omega$, where two well-orders are equivalent if they have the same order type, is in $1$-$1$ correspondence with the countable infinite ordinals, so that set has size $\aleph_1$. If the continuum hypothesis is false, then $\vert \mathbb N \vert \lt \aleph_1 \lt \vert \mathbb R \vert$.

$\endgroup$
1
  • 1
    $\begingroup$ Just a stylistic comment, $-$ is a minus, it has the spacing of an operator because it is an operator. As such $1-1$ is just $0$. The correct way to typeset would be $1$-$1$, which is cumbersome, but has a correct output of $1$-$1$. $\endgroup$
    – Asaf Karagila
    Commented May 14, 2020 at 10:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .