7
$\begingroup$

Does anyone here know of a reference to an analysis on a proposed relationship between The Continuum Hypothesis and The Axiom of Choice?

$\endgroup$
  • $\begingroup$ What do you mean by "proposed relationship"? AC and CH are independent over ZF. $\endgroup$ – user61527 Aug 21 '13 at 17:24
  • 3
    $\begingroup$ It’s known that $\mathsf{CH}$ is consistent with and independent of $\mathsf{ZFC}$, and that $\mathsf{AC}$ is consistent with and independent of $\mathsf{ZF}+\mathsf{CH}$, so there simply is no relationship. $\endgroup$ – Brian M. Scott Aug 21 '13 at 17:36
  • 1
    $\begingroup$ $\mathsf{AC}(\Bbb R)$--the Axiom of Choice for subsets of the real numbers--does follow from $\mathsf{ZF}+\mathsf{CH},$ since it readily implies that $\Bbb R$ is well-orderable. That's about as much of a relationship as you're going to get, though. $\endgroup$ – Cameron Buie Aug 21 '13 at 17:39
  • 6
    $\begingroup$ There’s nowhere to progress: the facts are fully understood. You’re asking for something that can’t exist. $\endgroup$ – Brian M. Scott Aug 21 '13 at 17:54
  • 3
    $\begingroup$ @Cameron: That really depends on your formulation of $\sf CH$ without the axiom of choice. $\endgroup$ – Asaf Karagila Aug 21 '13 at 22:59
22
+100
$\begingroup$

I will focus mostly in the follow-up question of whether there is progress on the continuum problem, but along the way I mention some of the results relating $\mathsf{AC}$ and $\mathsf{CH}$.


First of all, in the context of first order $\mathsf{ZF}$, neither statement implies the other, and each of the four possible combinations is relatively consistent with $\mathsf{ZF}$: Both $\mathsf{CH}$ and $\mathsf{AC}$ holding, both failing, or one holding and the other not. Cohen's method of forcing can be used to establish this.

There is a connection, though: The generalized continuum hypothesis $\mathsf{GCH}$ is the statement that for any infinite set $X$, any subset of $\mathcal P(X)$ either has the same size as $\mathcal P(X)$, or else can be injected into $X$. (One can state $\mathsf{GCH}$ in a variety of ways, some books choose slightly different formulations than the one I stated.) In $\mathsf{ZF}$ one can prove that if $\mathsf{GCH}$ holds, then $\mathsf{AC}$ holds, see for example this question.

(This leads to an interesting open question, due to Specker: Assume $\mathsf{ZF}$. Suppose that $X$ is infinite, and the instance of $\mathsf{GCH}$ that applies to $X$ holds, that is, any subset of $\mathcal P(X)$ either has the same size as $\mathcal P(X)$, or else can be injected into $X$. Does it follow that $X$ is well-orderable?)

As the first paragraph suggests, if there are models of $\mathsf{ZF}$ at all, there are many models, and nothing much can be said about $\mathsf{AC}$ and $\mathsf{CH}$ in this generality. But we usually do not simply look at all possible models, there are some that are "special" and we pay particular attention to them. The first example of such a model is $L$, Gödel's constructible universe. In this model $\mathsf{GCH}$ holds and, naturally, so does $\mathsf{AC}$. In fact, in $L$ there is a canonical well-ordering of the whole universe, which is something stronger than what we can abstractly deduce from $\mathsf{GCH}$. Also, it is not just $\mathsf{GCH}$ that holds, but a strong "local" version that sometimes is stated by saying that $\emptyset$ is acceptable at all $\alpha$. What this strong version gives us is that $L$ is described as the limit of an increasing hierarchy $(J_\alpha\mid \alpha\in\mathsf{ORD})$ of "initial segments", and each $J_\alpha$ satisfies that, for any $\kappa$ infinite, if there is a subset of $\kappa$ in $J_{\alpha+1}\setminus J_\alpha$, then, in $J_{\alpha+1}$, there is a surjection from $\kappa$ onto $J_\alpha$. This gives that each $J_\alpha$ satisfies $\mathsf{GCH}$, and more.

In set theory, we pay particular attention to "$L$-like" models. These are models of $\mathsf{ZF}$ that share many of the nice properties that make $L$ special, and moreover, allow the presence of large cardinals. That $L$ is not very accommodating in this sense is the main objection to assuming $V=L$ ("every set is in $L$") as an additional axiom of set theory. In these $L$-like models, we have $\mathsf{GCH}$ and $\mathsf{AC}$ in the strong forms mentioned above. The point here is that, even if formally neither statement implies the other, we have identified natural models where both statements hold, essentially as a consequence of the same abstract property.

Several natural questions appear at this point. One is whether it makes sense to assume as an additional axiom of set theory that the universe is an $L$-like model. This would be a nice state of affairs, as these models come equipped with a rich combinatorial structure, allowing us to decide many statements that $\mathsf{ZFC}$ is not strong enough to settle. Also, we would have that $\mathsf{GCH}$ holds. There is significant work on studying this possibility, the most recent instance of which is the "ultimate $L$" hypothesis studied by Woodin. See here and here.

Another natural question is why we care about large cardinals to the point that they become central to our study of models of set theory (not just $L$-like models). There are many good reasons for this. Some have been discussed extensively in MO. See here, and here, for example. (These are technical discussions, though. For a nice introduction to large cardinals, the best suggestion is Kanamori's book, The higher infinite.)

Gödel's program aims at studying "well-motivated" extensions of $\mathsf{ZFC}$ based on large cardinals. It started in his influential paper What is Cantor's continuum problem? A key feature that has been identified as a consequence of this program is that the large cardinal hierarchy serves as a natural measure of consistency strength. What is remarkable about this is that the arithmetic consequences of large cardinals are compatible. In fact, as the large cardinals become stronger (as we climb through the hierarchy), this holds not just their arithmetic consequences, but also for their consequences in the first order theory of the reals. A natural goal of Gödel's program is to see how far we can go this way. The continuum hypothesis is a second order statement about the reals (or, if you wish, a third order statement about the natural numbers). It would have been great if the compatibility we see at the first order level held at higher levels once we climb high enough in the hierarchy. Unfortunately, this appears not to be the case. The reason is usually described as the Levy-Solovay theorem, though it is not a single result but really a family of statements, some of them established by other authors. What these theorems say is that, given a large cardinal property $P(\kappa)$, if $\mathbb P$ is a small forcing, meaning $|\mathbb P|<\kappa$, then after forcing with $\mathbb P$, in the new universe, we have that $P(\kappa)$ still holds. Since $\mathsf{CH}$ can be made true or false, as one wishes, with such a small forcing $\mathbb P$, it follows that the large cardinal property $P(\kappa)$ cannot imply (or refute) the continuum hypothesis. Instances of properties $P(\kappa)$ for which this has been proved are "$\kappa$ is measurable", "$\kappa$ is strong", $\kappa$ is Woodin", "$\kappa$ is supercompact", etc. See here.

If large cardinals are not enough to settle $\mathsf{CH}$, are there any reasonable extensions of $\mathsf{ZFC}$ beyond large cardinals that do the job? As mentioned above, assuming that the universe is $L$-like is one such extension, which gives us $\mathsf{GCH}$. Another is to assume that the universe satisfies appropriate strong reflection principles. Sometimes this is states as saying that the universe satisfies a strong forcing axiom such as $\mathsf{MM}$, Martin's maximum). These statements imply that $\mathsf{CH}$ is false. Personally, I find their consequences very appealing, but I agree that the picture is not yet as well-developed as with large cardinals to accept these principles as being "true".

I must say here that the study of reflection principles is not arbitrary among the many other principles that could have been considered instead. A natural motivation behind the study of large cardinals is that they formalize the intuition that the universe is "tall". Similarly, reflection principles formalize the intuition that the universe is "wide". This wideness is incompatible with $L$-like structures, so it is no wonder that the two approaches I've mentioned lead to incompatible answers for the continuum problem. There is actually an interesting dichotomy here: In quite a few occasions we have seen that problems in set theory have different answer if we assume $\mathsf{CH}$ and if we assume, say, Martin's maximum. But the difference is striking: Under $\mathsf{CH}$, we tend to have a wild variety of objects, and trying to classify them is impossible. Under $\mathsf{MM}$, we have very few objects, with much structure, and a simple classification is possible. Examples occur in the study of uncountable linear orders, in the study of automatic continuity of homomorphisms between Banach algebras, and in many other situations. For more on this, see here.

A few years ago, Woodin identified $\Omega$-logic, a natural strengthening of first order logic, and formulated the $\Omega$-conjecture. Large cardinals settle the first order theory of the reals, in the sense that it cannot be modified by forcing. In fact, projective determinacy, a single consequence of the existence of large cardinals, suffices for this. One of Woodin's goals was to show that if we want a similar "axiomatization" of the second order theory of the reals, then, whatever axiomatization we ended up choosing, it would imply that $\mathsf{CH}$ is false. This would have given a nice way of solving the continuum problem, since he also showed that such axiomatizations exist, so the implication is not vacuous.

Unfortunately, his proposed argument for this (via Tarski's undefinability of truth theorem) depended on some conjectured properties of models in the presence of the axiom of determinacy, and this conjecture has since been refuted by work of Grigor Sargsyan.

The most current development in the quest for extensions of $\mathsf{ZFC}$ that may settle $\mathsf{CH}$ is actually of a radically different nature. The view has been advanced that we should, rather than conceive of a single universe, think in terms of a multiverse of sets. Joel Hamkins has suggested one such approach, but the one I have in mind is more restrictive. The idea is that it makes no sense to distinguish between conflicting theories as long as they are mutually interpretable. Any choice between the two would be based on aesthetic rather than mathematical considerations. The standard approach to interpretability in the context of set theory is via forcing (this is more than a heuristic, if the $\Omega$-conjecture actually holds). The multiverse view thus proposes to study the partial order of models that can be accessed by forcing (we may or may not have a ground model to begin with). See these slides for more details. Under this view, statements such as $\mathsf{CH}$ are not so interesting, as they do not hold in all the models in the multiverse. (It is not quite that $\mathsf{CH}$ becomes meaningless, we can always ask of a specific model whether it satisfies $\mathsf{CH}$ or not. But the question of whether $\mathsf{CH}$ holds in the multiverse makes no sense, and the question of whether it is true of all models in the multiverse has an easy answer: No.)

Note that reflection principles are fragile in this context, just as $\mathsf{CH}$, they hold in some models and fail in others. On the other hand, if we are interested in this view, studying ultimate $L$ or $L$-like models still makes sense, as they can serve as the ground model for the multiverse. (The fact that there is such a ground model wold be an additional axiom.)


Let me close by inviting you to look at a very interesting series of answers on a similar question asked a while ago on MO (I linked above to one of these answers, by Justin Moore). Also, you may want to read a short essay I wrote on similar matters a while ago as a result of some exchanges via (of all things) Twitter.

A few weeks after writing the above, I posted a closely related essay that may also be of interest.

$\endgroup$
  • 1
    $\begingroup$ Well written, although from the looks of the other questions asked by the OP -- well beyond their level. I enjoyed it, though! $\endgroup$ – Asaf Karagila Aug 22 '13 at 1:17
  • $\begingroup$ (One possible typo is that with Specker's question, I believe you may wanted to say $\sf CH$ holds for $X$, and not $\sf GCH$.) $\endgroup$ – Asaf Karagila Aug 22 '13 at 1:18
  • $\begingroup$ @AsafKaragila Thanks. And thank you for spotting the typo; I meant to say: The instance of $\mathsf{GCH}$ that applies to $X$. I rephrased. $\endgroup$ – Andrés E. Caicedo Aug 22 '13 at 1:40
  • 1
    $\begingroup$ (Maybe it's about time to write a book! ;-) Or at least a reasonably long review paper of the continuum hypothesis...) $\endgroup$ – Asaf Karagila Sep 22 '13 at 16:17
  • 1
    $\begingroup$ If nothing else, I agree that I need to collect these essays somewhere. Thanks for the suggestion. $\endgroup$ – Andrés E. Caicedo Sep 22 '13 at 16:20
11
$\begingroup$

There isn't much relationship between the axiom of choice and the continuum hypothesis. The following theories are equiconsistent (so from a model of one, we know how to generate a model of another):

  1. $\sf ZFC$.
  2. $\sf ZFC+CH$.
  3. $\sf ZFC+\lnot CH$.
  4. $\sf ZF+\lnot AC+CH$.
  5. $\sf ZF+\lnot AC+\lnot CH$.

This means that (1) we cannot prove the continuum hypothesis (or its negation) from either $\sf ZFC$ or $\sf ZF+\lnot AC$; (2) we cannot prove the axiom of choice (or its negation) from either $\sf ZF+CH$ or $\sf ZF+\lnot CH$.

Of course it is possible to prove or disprove either statement from less familiar axioms. Axioms like the axiom of determinacy contradict the axiom of choice, but it proves that there are no intermediate cardinals between $\aleph_0$ and $2^{\aleph_0}$ (but it proves that $2^{\aleph_0}\neq\aleph_1$ too, see the next part of the answer for more on this); in $\sf ZFC$ there are several set theoretical axioms which prove that $2^{\aleph_0}=\aleph_2$; and there are other axioms which in $\sf ZF$ can prove both $\sf AC$ and $\sf CH$. All these axioms may be considered "unusual" for someone unfamiliar with modern set theory.

But despite all this, there is one interesting relation between the two. Assuming $\sf AC$, all the formulations of $\sf CH$ are equivalent to $2^{\aleph_0}=\aleph_1$. However without the axiom of choice there are many non-equivalent formulations. Do note that the equiconsistency of the above theories does not depend on the choice of formulation of $\sf CH$.

For more one that last part, How to formulate continuum hypothesis without the axiom of choice?.

$\endgroup$
  • 1
    $\begingroup$ I wasn't even aware of any $\mathsf{CH}$ formulation other than $\aleph_1=2^{\aleph_0}.$ Good to know! $\endgroup$ – Cameron Buie Aug 21 '13 at 23:49
  • $\begingroup$ @Cameron: See my answer on mathoverflow.net/questions/135912/…, originally the definition of the continuum hypothesis was "there are no intermediate cardinals", but when Cantor defined the $\aleph$ numbers he pointed the simpler equation definition known to you. But Cantor has used the axiom of choice thoroughly (his first proof of the Cantor-Bernstein theorem was a quick corollary to the fact that every two cardinals are comparable). $\endgroup$ – Asaf Karagila Aug 22 '13 at 0:01

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.