nLab continuum hypothesis

The Continuum Hypothesis

Context

Foundations

foundations

The basis of it all

 Set theory

set theory

Foundational axioms

foundational axioms

Removing axioms

The Continuum Hypothesis

Idea

Cantor’s continuum problem is simply the question: How many points are there on a straight line in Euclidean space? In other terms, the question is: How many different sets of integers do there exist? K. Gödel (1947, p.515)

The continuum hypothesis is a famous problem of set theory concerning the cardinality of the Dedekind real numbers (the “continuum”). The hypothesis in its classical form goes back to G. Cantor and was on top of Hilbert's list of open problems in mathematics in 1900.

In concise form the continuum hypothesis (CHCH) reads: 2 0= 1\quad 2^{\aleph_0}=\aleph _1\quad; which roughly says that every subset of the Dedekind real numbers is either countable or has the same cardinality as the set of all Dedekind real numbers.

The generalized continuum hypothesis (GCHGCH) states more generally: 2 k= k+1\quad 2^{\aleph_k}=\aleph _{k+1}\quad. (But see also Remark below.)

The independence of the continuum hypothesis from the ZFC axioms of set theory has been established in landmark papers by K. Gödel and P. J. Cohen, the former proving the consistency of ZFC+CHZFC+CH relative to ZFCZFC in 1938, and the latter proving the consistency of ZFC+¬CHZFC+\neg CH relative to ZFCZFC in 1963. For fully formal proof see Han 18.

The broader implications of the independence results for set theory in general and ZFCZFC in particular are somewhat controversial. They are widely taken as a pointer towards the deficiency of ZFCZFC and the need for new axioms of set theory. This position has been voiced famously in Gödel (1947) from a platonist perspective.

W. Lawvere in 2003 interpreted Cantor’s original point of view as saying that CHCH holds for ‘sufficiently structureless’ sets and, accordingly, viewed Gödel’s 1938 result as a proof of CHCH, whereas in P. Dehornoy‘s 2003 reinterpretation based on work of Woodin, CHCH is actually conjectured to be false. S. Feferman has argued more recently that CHCH is essentially mathematically indefinite and has made notions of ‘indefiniteness’ explicit that indeed enable to back this point of view with technical results (cf. Feferman (2011)). Similarly, Joel David Hamkins has argued (cf. Hamkins 2012) that under the multiverse view of set theory, CHCH is settled by our extensive knowledge of models of set theory satisfying both CHCH and ¬CH\neg CH which all seem fully set-theoretic, so that no principle implying either one can possibly be considered ‘obviously true’.

The attempt to give categorical accounts of the forcing methods introduced by Cohen provided a strong impetus in the development of (elementary) topos theory in the work of Freyd, Tierney, Lawvere and later Scedrov. The following exposition follows this categorical approach.

Statement

Definition

Let EE be an elementary topos with subobject classifier Ω\Omega and natural numbers object NN. The (external) continuum hypothesis in EE asserts that if there is a sequence of monomorphisms

NAΩ NN \hookrightarrow A\hookrightarrow \Omega^N

then either there exists a monomorphism ANA \hookrightarrow N or a monomorphism Ω NA\Omega^N \hookrightarrow A.

When the topos is Boolean, so the Cantor-Schroeder-Bernstein theorem holds, this implies the existence of an isomorphism ANA \simeq N or Ω NA\Omega^N \simeq A. Note, however, that neither of the original monomorphisms is necessarily an isomorphism (one of them could be the successor map on NN, for example).

In the classical case (that is, in the topos Set with the axiom of choice), this equivalently asserts that there is no strict inequality of cardinal numbers

||<α<|Ω |{|\mathbb{N}|} \lt \alpha\lt {|\Omega^\mathbb{N}|}

which it is more common to write as

0<α<2 0 \aleph_0 \lt \alpha \lt 2^{\aleph_0}

In the formal proof outlined in (Han–van Doorn 20), the statement is fomulated in Lean as:

x,Ord(x)xωP(Ω)x\forall x, Ord(x)\Rightarrow x \leq \omega \vee P(\Omega) \leq x

where xyx\leq y means xx is a subquotient of yy, and Ord(x)Ord(x) is a predicate that returns True if and only if xx is an ordinal. This says that no ordinal can be between ω\omega and P(ω)P(\omega) in size. In the presence of classical logic and the well-ordering principle, this then implies that no set can have cardinality between ω\omega and P(ω)P(\omega).

In weakly predicative mathematics

Predicatively, the power set Ω N\Omega^N does not exist, but if function sets exist, then the mathematics is only weakly predicative. Assuming EE is a Heyting ΠW-pretopos, one replaces the subset classifier Ω\Omega in the definition of the Dedekind real numbers with a Sierpinski space object Σ\Sigma in SetSet, defined as an initial σ \sigma -frame in SetSet. The continuum hypothesis then becomes that if there is a series of monomorphisms such that

NAΣ NN \hookrightarrow A\hookrightarrow \Sigma^N

then either there exists a monomorphism ANA \hookrightarrow N or a monomorphism Σ NA\Sigma^N \hookrightarrow A.

If the ΠW\Pi W-pretopos EE is Boolean, then it is an elementary topos, the principle of excluded middle is true, and SS has two elements and is isomorphic to Ω\Omega, so the pretopos is no longer predicative, and this definition reduces to the classical definition.

Since Σ\Sigma as defined above is a countable set, one could replace Σ\Sigma with NN itself, as NN is also countable. The continuum hypothesis then becomes that if there is a series of monomorphisms such that

NAN NN \hookrightarrow A\hookrightarrow N^N

then there exists a monomorphism ANA \hookrightarrow N or a monomorphism N NAN^N \hookrightarrow A.

The set N NN^N is typically called the Baire space of sequences, and sometimes called the Baire real numbers in descriptive set theory and denoted as BB. In constructive mathematics, there is an homeomorphism between N NN^N and the set of positive irrational numbers JJ through infinite continued fractions.

Finally, one could construct the unit interval continuum as the terminal coalgebra of the endofunctor F(X)=X×2+1F(X) = X \times 2 + 1 on Set, the stream 2 *2_*. Since the initial algebra of the endofunctor F(X)=X×2+1F(X) = X \times 2 + 1 is the free monoid 2 *2^* and has countable cardinality, the continuum hypothesis then be written as that if there is a series of monomorphisms such that

2 *A2 *2^* \hookrightarrow A\hookrightarrow 2_*

then there exists a monomorphism A2 *A \hookrightarrow 2^* or a monomorphism 2 *A2_* \hookrightarrow A. This last definition is important in situations where internal hom-objects? do not exist in the ambient category, such as in the pretopos Set of strongly predicative mathematics.

In strongly predicative mathematics

If neither power sets nor function sets exist, such as in a Boolean or Heyting W-pretopos, the mathematics is strongly predicative and the cardinality of the continuum is an inaccessible cardinal. Then, classically, the continuum hypothesis becomes the question of whether there is a cardinal between the inaccessible cardinal 0\aleph_0 and the inaccessible cardinal 𝔠\mathfrak{c}.

While the set of real numbers could be defined by fiat as the terminal archimedean field object RR in SetSet, its existence has to be included as an axiom of the set theory, after which the continuum hypothesis becomes if there is a series of monomorphisms such that

NARN \hookrightarrow A\hookrightarrow R

then either there exists a monomorphism ANA \hookrightarrow N or a monomorphism RAR \hookrightarrow A. One could likewise assert by fiat the existence of free monoids and streams on a finite set, whereby the continuum hypothesis follows from above.

Unprovability

Theorem

There exists a boolean topos in which the axiom of choice holds and the continuum hypothesis fails.

One topos for which the theorem holds is called the Cohen topos; it is the topos of sheaves with respect to the dense topology (also called the ¬¬\neg\neg-topology) on the Cohen poset. Thus, in this topos, there exist monomorphisms A2 \mathbb{N} \hookrightarrow A\hookrightarrow 2^{\mathbb{N}} but no monomorphism ANA \hookrightarrow N or Ω NA\Omega^N \hookrightarrow A.

The Cohen topos will be constructed from the topos Set of sets. For this, recall that the subobject classifier of SetSet is 2{0,1}2\coloneqq \{0,1\}. The technique of constructing such a topos is called forcing.

Definition

(Cohen poset)

Let \mathbb{N} be the set of natural numbers; i.e. the natural numbers object in SetSet. Let AA be a set with strictly larger cardinality |A|>|2 |{|A|}\gt {|2^\mathbb{N}|}; e.g. A2 2 A\coloneqq 2^{2^{\mathbb{N}}} will do because of the diagonal argument. Then the Cohen poset PP is defined to be the set of morphisms

p:F p2p:F_p\to 2

where F pA×F_p\subseteq A\times \mathbb{N} is any finite subset. The order relation on PP is defined by

qpiffF qF pandq| F p=pq\le p\; iff\; F_q\supseteq F_p\;and\;q|_{F_p}=p

where the right-hand condition means that qq restricted to F pF_p must coincide with pp.

We think of each element of PP as an approximation to the function F:A×2F:A\times\mathbb{N} \to 2 that is the transpose of the putative monomorphism

f:A2 f:A\to 2^\mathbb{N}

with “smaller” elements considered as better approximations. The very rough intuition is that pqp\to q\to \dots (if pqp\ge q \ge \dots) forms a codirected diagram of monomorphisms with domains of increasing size whose colimit is ff, and that by free cocompletion (i.e. forming (pre)sheaves) we obtain a topos in which this colimit exists.

Lemma

The dense Grothendieck topology on PP is subcanonical. In other words: For any pPp\in P we have y(p)=hom(,p)Sh(P,¬¬)y(p)=hom(-,p)\in\Sh(P,\neg\neg)

Lemma

Let k A×:{PSet pA×k_{A\times\mathbb{N}}:\begin{cases}P\to Set \\ p \mapsto A\times\mathbb{N}\end{cases} denote the functor constant on A×A\times\mathbb{N}. Let

C:{PSet p{(b,n)|p(b,n)=0}A×C:\begin{cases} P\to Set \\ p\mapsto \{(b,n)|p(b,n)=0\}\subseteq A\times \mathbb{N} \end{cases}

Then we have ¬¬C=C{\neg}{\neg} C=C in Sub(k A×)Sub(k_{A\times\mathbb{N}}); i.e. CC is a closed subobject with respect to the dense topology ¬¬{\neg}{\neg} in the algebra of subobjects of k A×k_{A\times\mathbb{N}}.

Let Ω\Omega denote the subobject classifier of Psh(P)Psh(P). Let Ω ¬¬\Omega_{{\neg}{\neg}} denote the subobject classifier of Sh(P,¬¬)Sh(P,\neg\neg). Recall that Ω ¬¬\Omega_{{\neg}{\neg}} is given by the equalizer Ω ¬¬=eq(id Ω,¬¬)\Omega_{{\neg}{\neg}}=eq(id_\Omega,{\neg}{\neg}).

By the preceding lemma, the characteristic morphism χ a\chi_a of the subobject a:Ck A×=k A×k a \colon C\hookrightarrow k_{A\times\mathbb{N}}=k_A\times\k_\mathbb{N} factors through some f:k A×Ω ¬¬f \colon k_{A\times\mathbb{N}}\to \Omega_{\neg\neg}.

Lemma

The adjoint g:k AΩ ¬¬ k g:k_A\to \Omega_{{\neg}{\neg}}^{k_{\mathbb{N}}} of ff is a monomorphism.

Corollary

The associated-sheaf functor sends gg to a monomorphism in the Cohen topos.

Unrefutability

If VV is a model of ZF, then the continuum hypothesis and the axiom of choice both hold in Gödel’s constructible universe LL built from VV. Actually, the GCH holds in LL as well.

Remark

Regarding the statement of the generalized continuum hypothesis in ZF (not ZFC), one should distinguish various possibilities. One might leave the statement 2 n= n+12^{\aleph_n} = \aleph_{n+1} unchanged, so that the GCH becomes a statement just about ordinals or well-ordered sets. But then one could argue such a generalized continuum hypothesis is not as general or strong as it might be, since not all sets can be well-ordered using ZF alone. The more general statement would say that if there are monomorphisms XYX \to Y and YP(X)Y \to P(X) for infinite sets XX and YY, then YY is bijective with one of X,P(X)X, P(X).

For example, Sierpiński proved that over ZF, the generalized continuum hypothesis implies AC. (See Hartogs number.) For this result, he certainly used the stronger formulation.

In weakly predicative mathematics, power sets do not exist, so the stronger version of the continuum hypothesis for Dedekind real numbers would have to be rephrased in terms of the Sierpinski space 𝕊\mathbb{S} and function sets: if there are monomorphisms XYX \to Y and Y𝕊 XY \to \mathbb{S}^X for infinite sets XX and YY, then YY is bijective with one of X,𝕊 XX, \mathbb{S}^X, or equivalently the version involving natural numbers and function sets: if there are monomorphisms XYX \to Y and Y XY \to \mathbb{N}^X for infinite sets XX and YY, then YY is bijective with one of X, XX, \mathbb{N}^X.

Generalization: Easton’s theorem

Just how flexible can the power operation κ2 κ\kappa \mapsto 2^\kappa be? There are of course some constraints. Obvious ones are that κ<2 κ\kappa \lt 2^\kappa and 2 κ2 λ2^\kappa \leq 2^\lambda whenever κλ\kappa \leq \lambda. A more refined one is a consequence of König's theorem, namely that

  • κ<cof(2 κ)\kappa \lt cof(2^\kappa)

where the right side is the cofinality of 2 κ2^\kappa.

A remarkable illustration of the power of the forcing method is Easton's theorem, which says that as far as regular cardinals go, these are really the only constraints.

Theorem

(Easton 70)

Suppose \mathcal{M} is a model of ZFC in which the generalized continuum hypothesis (GCH) holds. Let FF be a partial function from the class of infinite regular cardinals to the class of cardinals such that

  • FF is strictly increasing and preserves the order \leq;

  • κ\kappa is less than the cofinality of F(κ)F(\kappa) for all κdom(F)\kappa \in dom(F).

Then there is a generic extension [G]\mathcal{M}[G] of \mathcal{M} with the same cardinals and cofinalities, such that [G]2 κ=F(κ)\mathcal{M}[G] \models 2^\kappa = F(\kappa) for all κdom(F)\kappa \in dom(F).

On the other hand, the behavior of the power operation on singular cardinals is not so unconstrained. For example, in a model of ZFC, the smallest cardinal for which GCH fails can never be singular. The so-called “pcf theory?” (or “possible cofinalities theory”), due to Saharon Shelah, gives some information on possible bounds for the power operation on singular cardinals (among other things).

References

  • J. L. Bell, Set Theory - Boolean-Valued Models and Independence Proofs , Oxford Logic Guides 47 3rd ed. Oxford UP 2005.

  • A. Church, Paul J. Cohen and the Continuum Problem, pp.15-20 in Proceedings ICM Moscow 1966. (pdf)

  • P. J. Cohen, The independence of the continuum hypothesis I, Proc. Nat. Acad. Sci. 50 (1963) pp.1143-1148. (pdf)

  • P. J. Cohen, The independence of the continuum hypothesis II, Proc. Nat. Acad. Sci. 51 (1963) pp.105-110. (pdf)

  • P. J. Cohen, Set Theory and the Continuum Hypothesis , Benjamin New York 1966. (Dover reprint 2008)

  • P. Dehornoy, Progrès récents sur l’hypothèse du continu (d’après Woodin) , Séminaire Bourbaki exposé 915 (2003). (English version)

  • Solomon Feferman, The Continuum Hypothesis is neither a definite mathematical problem nor a definite logical problem , Harvard lectures 2011. (pdf)

  • Joel David Hamkins, The set-theoretic multiverse, Review of Symbolic Logic 5:416-449 (2012), arxiv

  • M.C. Fitting, Intuitionistic Logic, Model Theory and Forcing, North-Holland Amsterdam 1969.

  • K. Gödel, What is Cantor’s continuum problem? , Am. Math. Monthly 54 no. 9 (1947) pp.515-25. (pdf)

  • F. W. Lawvere, Foundations and Applications: Axiomatization and Education, Bulletin of Symbolic Logic 9 no.2 (2003) pp.213-224. (ps-preprint)

  • Saunders Mac Lane, Ieke Moerdijk, Sheaves in Geometry and Logic , Springer Heidelberg 1994. (sections VI.2, VI.3)

  • W. Hugh Woodin, The Continuum Hypothesis, Part I , Notices AMS 48 no.6 (2001) pp.567-576. (pdf)

  • W. Hugh Woodin, The Continuum Hypothesis, Part II , Notices AMS 48 no.7 (2001) pp.681-690. (pdf)

  • W. Easton, Powers of regular cardinals, Ann. Math. Logic, 1 (2): 139–178, (1970) doi:10.1016/0003-4843(70)90012-4

A formal proof of the independence of the continuum hypothesis from ZFC is in

published as

Last revised on February 20, 2023 at 13:06:47. See the history of this page for a list of all contributions to it.