Continuum Hypothesis

288_48aedb8880cab8c45637abc7493ecddd[1]Georg Cantor originally proposed that there is no infinite set with a cardinal number between that of the “small” infinite set of natural numbers (N) and the “large” infinite set of real numbers C (the “continuum”).  “There is no set whose cardinality is strictly between that of the integers and that of the real numbers.”  This means that N=Aleph0, C=Aleph1.

Gödel showed that no contradiction arises if the continuum hypothesis is added to conventional Zermelo-Fraenkel set theory. However, Paul Cohen proved in 1963 that no contradiction arises if the negation of the continuum hypothesis is added to set theory. Together, Gödel’s and Cohen’s results lead to the conclusion that the validity of the continuum hypothesis depends on the version of set theory being used, which makes it undecidable. This is a major problem.

The following outline of the Continuum hypothesis is quoted from Nancy McGough’s site Infinite Ink , which is a great website.

Overview

People have tried to understand space, time, motion, and the notion of “continuum” for thousands of years. This pursuit lead to the Pythagoreans discovery of irrational numbers, Zeno’s paradoxes, infinitesimal calculus, transfinite set theory, relativity theory, quantum physics, and many more intriguing ideas.

What do we mean when we say “continuum”? Here’s a description Albert Einstein gave on p. 83 of his Relativity: The Special and the General Theory:

The surface of a marble table is spread out in front of me. I can get from any one point on this table to any other point by passing continuously from one point to a “neighboring” one, and repeating this process a (large) number of times, or, in other words, by going from point to point without executing “jumps.” I am sure the reader will appreciate with sufficient clearness what I mean here by “neighbouring” and by “jumps” (if he is not too pedantic). We express this property of the surface by describing the latter as a continuum.

Hermann Weyl said “let us stick to time as the most fundamental continuum” and gave the following description on p. 92 of his The Continuum:

So we can gather the following concerning objectively presented time:

  1. an individual point in it is non-independent, i.e., is pure nothingness when taken by itself, and exists only as a “point of transition” (which, of course, can in no way be understood mathematically).
  2. it is due to the essence of time (and not to contingent imperfections of our medium) that a fixed time-point cannot be exhibited in any way, that always only an approximation, never an exact determination is possible.

Corresponding remarks apply to every intuitively given continuum; in particular, to the continuum of spatial extension.

What is the Continuum Hypothesis?

In 1874 Georg Cantor discovered that there is more than one level of infinity. The lowest level is called “countable infinity” and higher levels are called “uncountable infinities.” The natural numbers are an example of a countably infinite set and the real numbers are an example of an uncountably infinite set. In 1877 Cantor hypothesized that the number of real numbers is the nextlevel of infinity above countable infinity. Since the real numbers are used to represent a linear continuum, this hypothesis is called “the Continuum Hypothesis” or CH.

Let c be the cardinality of (i.e., number of points in) a continuum, aleph0 be the cardinality of any countably infinite set, and aleph1 be the next level of infinity above aleph0. Here are six ways to state CH:

Sets-of-Reals Versions of CH

  • Any set of real numbers is either finite, countably infinite, or has the same cardinality as the entire set of real numbers.
  • Any infinite set of real numbers is either countably infinite or has the same cardinality as the entire set of real numbers.
  • Any uncountable set of real numbers has the same cardinality as the entire set of reals numbers.

Cardinal-Number Versions of CH

  • There is no cardinal number between aleph0 and c.
  • c = aleph1
  • 2aleph0 = aleph1 (explained in section 3.1.1)

The Continuum Hypothesis has been, and continues to be, one of the most hotly pursued problems in mathematics. It was the first problem in Hilbert’s list of 23 important unsolved problems, ten of which he presented to the Second International Congress of Mathematicians at Paris in 1900. Pursuit of the Continuum Hypothesis has motivated a lot of useful and interesting mathematics in real analysis, topology, set theory, and logic.

Current Status of CH

Despite nearly 120 years of investigation, CH is still debated and continues to motivate a lot of mathematics, especially in set theory and logic. Like the Axiom of Choice (AC), Gödel showed that CH is consistent with standard set theory and Cohen showed that ~CH is consistent with standard set theory (and thus CH is independent of standard set theory). But, unlike AC, CH has not been adopted as an axiom of set theory. Instead, mathematicians either live with this incompleteness in set theory or try to find more intuitive axioms that will help to decide CH. In the “Introduction” of the Israel Mathematical Conference Proceedings, Vol. 6, 1993Haim Judah said:

We still think that the study of the size of the continuum should be our guiding light for further research in set theory.


Mathematics of the Continuum and CH

The existence of irrational numbers, the uncountability of the reals, and the self-repeating, fractal-nature of the continuum show us that our intuition can’t always be trusted. To avoid problems with intuition, we formalize our intuitive notions and try to rigorously prove or disprove statements about these notions. Notions related to the continuum and CH include measure, Baire category, density, separability, connectedness, continuity, completeness, compactness, and of course cardinality. We start with cardinality, the main concept related to CH.

Sizes of Sets: Cardinal Numbers

Before Cantor, collections were either finite or infinite and there was no notion of different levels of infinity. Only Wallis’s infinity symbol, oo, was needed to represent the notion of infinity. While investigating questions about singularities of Fourier series, Cantor made the revolutionary discovery that not all infinite sets are the same size.

Cantor showed that the natural numbers (N), the integers (Z), and the rational numbers (Q) are all the same size by constructing one-to-one correspondences between them (for details see Seton Hall University’s Interactive Real Analysis). Cantor described these as “countably infinite” or having “cardinality aleph0.” Cantor also showed that the real numbers can not be put into one-to-one correspondence with a countably infinite set and thus are not countably infinite. After this surprising discovery, Cantor proposed the Continuum Hypothesis and developed transfinite set theory, the “paradise of the infinite” from which Hilbert hoped we would never be driven!

aleph0 < c = 2aleph0

We now step through a sketch of the proof of the following, which will help us to define the continuum hypothesis (CH) and the generalized continuum hypothesis (GCH).

aleph0 < card(R) = c = card((0,1)) = card(P(N)) = 2aleph0

 aleph0 < card(R) = c

Cantor showed, using his famous diagonal argument, that the real numbers (R) cannot be put into one-to-one correspondence with the natural numbers. Since the reals are a superset of N, their cardinality must be larger than aleph0. He called the cardinality of the real numbers c for “continuum.”

card(R) = card((0,1))

When proving things about c it’s sometimes easier to work with a set other than R that has cardinality c. An example of such a set is the set of reals between 0 and 1, which is called “the open interval zero one” and denoted:

(0,1)

There are many ways to show that all the reals can be put into one-to-one correspondence with (0,1). One way to do this mapping is to use the great and powerful arctan function. You can use arctan with different multipliers and shifters to construct a one-to-one correspondence between R and any open interval of reals.

Exercise
f(x)=arctan(x) maps R continuously one-to-one and onto (-pi/2, pi/2). What function of arctan maps R continuously one-to-one and onto (0,1)?

Since this function of arctan maps R continuously one-to-one and onto (0,1) and its inverse — a function of tan — maps (0,1) continuously one-to-one and onto R, we see that R and (0,1), in addition to having the same cardinality, are homeomorphic.

card((0,1)) = card(P(N)) = 2aleph0

The set of reals between 0 and 1 can be represented by the set of all countably infinite sequences of 0’s and 1’s . Think of these as representing binary “decimals” between .000000… and .111111… . In this representation .1=1/2, .01=1/4, .11=3/4, etc.

The power set of the natural numbers, P(N), can also be represented by the set of all countably infinite sequences of 0’s and 1’s. Each sequence represents a subset of N by interpreting a 0 in position n to mean that the number n is not in the subset and a 1 in position n to mean the number n is in the subset. This way of specifying a set is called the “characteristic function” of the set.

One way to represent all countably infinite sequences of 0’s and 1’s is to use Cartesian product notation:

{0, 1} x {0, 1} x {0, 1} x … = {0, 1}aleph0

Since in set theory {0, 1} = 2, we can also write this as:

2aleph0

So we now have:

aleph0 < c = card(R) = card((0,1)) = card(P(N)) = 2aleph0

CH and GCH

Since CH is the proposal that c is the next level of infinity above aleph0, namely aleph1, and we have just shown that c = 2aleph0, another way to state CH is:

2aleph0 = aleph1

This is sometimes called the “arithmetic version of CH.” In 1908 Felix Hausdorff proposed the following generalization of CH:

For any cardinal alepha,   2alepha = alepha+1

This is the Generalized Continuum Hypothesis or GCH. Another way to state GCH is:

   {card(N), card(P(N)), card(P(P(N))), card(P(P(P(N)))), . . .} = {aleph0aleph1aleph2aleph3, . . .}

Obviously CH follows from GCH and we have:

ZF+GCH |- CH

Note that ZF+GCH |- AC so it would be redundant (and misleading) to put “ZFC+GCH” on the left side of the turnstile.

Sample Cardinalities

After Cantor showed that there are different levels of infinity, Cantor and others quickly discovered the cardinality of many sets, including the following.

Cardinality    Samples
aleph0
  • N = natural numbers
  • w = [N, <] = natural numbers in their natural order
  • Z = integers
  • Q = rational numbers
  • algebraic numbers
  • set of all finite sets of natural numbers
  • set of all cofinite sets of natural numbers (sets whose complements are finite)
  • <ww = <wN = set of all finite sequences of natural numbers
aleph1
  • w1 = set of all countable ordinals
c = 2aleph0
  • R = real numbers
  • C = complex numbers
  • irrational numbers
  • transcendental numbers
  • R2 = 2-dimensional Euclidean space
  • R3 = 3-dimensional Euclidean space
  • Rn = n-dimensional Euclidean space
  • any non-empty open set of reals
  • any perfect set of reals
  • any Cantor set
  • any uncountable closed set of reals
  • any uncountable Borel set of reals
  • any uncountable analytic set of reals
  • any set of reals with positive measure
  • any set of reals of second category (not meager)
  • P(N) = set of all subsets of the natural numbers
  • ww = wN = set of all countably infinite sequences of natural numbers
  • w2 = set of all countably infinite sequences of 0’s and 1’s
  • set of all coinfinite sets of natural numbers (sets whose complements are infinite)
  • set of all infinite coinfinite sets of natural numbers
  • set of all open sets of reals
  • set of all closed sets of reals
  • set of all Borel sets of reals
  • set of all analytic sets of reals
  • C(R) = set of all continuous functions from R to R
  • set of all analytic functions from R to R
2c = 22aleph0
  • P(R) = set of all subsets of the real numbers
  • RR = set of all functions from R to R
  • P(P(N)) = set of all subsets of the power set of N

In this hierarchy of cardinalities, CH is the claim that the aleph1 and c levels should be merged into one level. And GCH would mean that 2c = aleph2, 22c = aleph3, etc.

 


Metamathematics and CH

The results of Gödel and Cohen about the consistency and independence of CH are metamathematical theorems. Questions that are not within the framework of standard mathematics, but are rather about the framework of mathematics, are part of metamathematics. Today the standard framework for mathematics is first-order logic and ZFC.

Most interesting results in logic are about the interplay between formal theory and model theory. An example of this type of result is Gödel’s First Incompleteness Theorem, which tells us that if we have:

  • a formal theory, T, which contains arithmetic
  • a model of that theory, M

then there is a statement U that is true in the model but cannot be proved in the formal theory. This type of statement is consistent with T but “undecidable” in T. Gödel’s Completeness theorem tells us that if T is consistent then U is undecidable in T if and only if models exist for both T+U and T+~U. Since ZFC contains arithmetic, it has been known since 1938, when Gödel proved his incompleteness theorems, that it is incomplete. CH was suspected to be one of its undecidable statements but it wasn’t until 1963 that Cohen proved the independence of CH. He did this by constructing a model of ZFC in which CH is false (i.e., a model of ZFC+~CH). The technique he used to construct the model is called “forcing.” In 1966 Cohen received a Fields Medal for his work.

A good discussion of these topics is in What is Mathematical Logic by J.N. Crossley and others. The last chapter gives a nice description of forcing and the construction of a model of ZFC+~CH.

…………………

Alternate Mathematical Frameworks

Another path to resolving CH is to view all of mathematics through a framework other than the standard first-order logic and Zermelo Fraenkel set theory. Possibilities include using Second-Order Logic, Linear Logic, Intuitionist Logic, or the meta framework, Category Theory, which can be used to encompass all frameworks.

3. Mathematics of the Continuum and CH

The existence of irrational numbers, the uncountability of the reals, and the self-repeating, fractal-nature of the continuum show us that our intuition can’t always be trusted. To avoid problems with intuition, we formalize our intuitive notions and try to rigorously prove or disprove statements about these notions. Notions related to the continuum and CH include measure, Baire category, density, separability, connectedness, continuity, completeness, compactness, and of course cardinality. We start with cardinality, the main concept related to CH.

3.1 Sizes of Sets: Cardinal Numbers

Before Cantor, collections were either finite or infinite and there was no notion of different levels of infinity. Only Wallis’s infinity symbol, oo, was needed to represent the notion of infinity. While investigating questions about singularities of Fourier series, Cantor made the revolutionary discovery that not all infinite sets are the same size.Cantor showed that the natural numbers (N), the integers (Z), and the rational numbers (Q) are all the same size by constructing one-to-one correspondences between them (for details see Seton Hall University’s Interactive Real Analysis). Cantor described these as “countably infinite” or having “cardinality aleph0.” Cantor also showed that the real numbers can not be put into one-to-one correspondence with a countably infinite set and thus are not countably infinite. After this surprising discovery, Cantor proposed the Continuum Hypothesis and developed transfinite set theory, the “paradise of the infinite” from which Hilbert hoped we would never be driven!

3.1.1   aleph0 < c = 2aleph0

We now step through a sketchof the proof of the following, which will help us to define the continuum hypothesis (CH) and the generalized continuum hypothesis (GCH).

aleph0 < card(R) = c = card((0,1)) = card(P(N)) = 2aleph0

3.1.1.1   aleph0 < card(R) = c

Cantor showed, using his famous diagonal argument, that the real numbers (R) cannot be put into one-to-one correspondence with the natural numbers. Since the reals are a superset of N, their cardinality must be larger than aleph0. He called the cardinality of the real numbers cfor “continuum.”

3.1.1.2  card(R) = card((0,1))

When proving things about c it’s sometimes easier to work with a set other than R that has cardinality c. An example of such a set is the set of reals between 0 and 1, which is called “the open interval zero one” and denoted:

(0,1)

There are many ways to show that all the reals can be put into one-to-one correspondence with (0,1). One way to do this mapping is to use the great and powerful arctan function. You can use arctan with different multipliers and shifters to construct a one-to-one correspondence between R and anyopen interval of reals.

Exercise
f(x)=arctan(x) maps R continuously one-to-one and onto (-pi/2, pi/2). What function of arctan maps R continuously one-to-one and onto (0,1)?

Since this function of arctan maps R continuously one-to-one and onto (0,1) and its inverse — a function of tan — maps (0,1) continuously one-to-one and onto R, we see that R and (0,1), in addition to having the same cardinality, are homeomorphic.

3.1.1.3   card((0,1)) = card(P(N)) = 2aleph0

The set of reals between 0 and 1 can be represented by the set of all countably infinite sequences of 0’s and 1’s . Think of these as representing binary “decimals” between .000000… and .111111… . In this representation .1=1/2, .01=1/4, .11=3/4, etc.

The power set of the natural numbers, P(N), can also be represented by the set of all countably infinite sequences of 0’s and 1’s. Each sequence represents a subset of N by interpreting a 0 in position n to mean that the number n is not in the subset and a 1 in position n to mean the number n is in the subset. This way of specifying a set is called the “characteristic function” of the set.

One way to represent all countably infinite sequences of 0’s and 1’s is to use Cartesian product notation:

{0, 1} x {0, 1} x {0, 1} x … = {0, 1}aleph0

Since in set theory {0, 1} = 2, we can also write this as:

2aleph0

So we now have:

aleph0 < c = card(R) = card((0,1)) = card(P(N)) = 2aleph0

3.1.2 CH and GCH

Since CH is the proposal that c is the next level of infinity above aleph0, namely aleph1, and we have just shown that c = 2aleph0, another way to state CH is:

2aleph0 = aleph1

This is sometimes called the “arithmetic version of CH.” In 1908 Felix Hausdorffproposed the following generalization of CH:

For any cardinal alepha,   2alepha = alepha+1

This is the Generalized Continuum Hypothesis or GCH. Another way to state GCH is:    {card(N), card(P(N)), card(P(P(N))), card(P(P(P(N)))), . . .} = {aleph0aleph1aleph2aleph3, . . .}

Obviously CH follows from GCH and we have:

ZF+GCH |- CH

Note that ZF+GCH |- AC so it would be redundant (and misleading) to put “ZFC+GCH” on the left side of the turnstile.

3.1.3 Sample Cardinalities

After Cantor showed that there are different levels of infinity, Cantor and others quickly discovered the cardinality of many sets, including the following.

Cardinality    Samples
aleph0
  • N = natural numbers
  • w = [N, <] = natural numbers in their natural order
  • Z = integers
  • Q = rational numbers
  • algebraic numbers
  • set of all finite sets of natural numbers
  • set of all cofinite sets of natural numbers (sets whose complements are finite)
  • <ww = <wN = set of all finite sequences of natural numbers
aleph1
  • w1 = set of all countable ordinals
c = 2aleph0
  • R = real numbers
  • C = complex numbers
  • irrational numbers
  • transcendental numbers
  • R2 = 2-dimensional Euclidean space
  • R3 = 3-dimensional Euclidean space
  • Rn = n-dimensional Euclidean space
  • any non-empty open set of reals
  • any perfect set of reals
  • any Cantor set
  • any uncountable closed set of reals
  • any uncountable Borel set of reals
  • any uncountable analytic set of reals
  • any set of reals with positive measure
  • any set of reals of second category (not meager)
  • P(N) = set of all subsets of the natural numbers
  • ww = wN = set of all countably infinite sequences of natural numbers
  • w2 = set of all countably infinite sequences of 0’s and 1’s
  • set of all coinfinite sets of natural numbers (sets whose complements are infinite)
  • set of all infinite coinfinite sets of natural numbers
  • set of all open sets of reals
  • set of all closed sets of reals
  • set of all Borel sets of reals
  • set of all analytic sets of reals
  • C(R) = set of all continuous functions from R to R
  • set of all analytic functions from R to R
2c = 22aleph0
  • P(R) = set of all subsets of the real numbers
  • RR = set of all functions from R to R
  • P(P(N)) = set of all subsets of the power set of N

In this hierarchy of cardinalities, CH is the claim that the aleph1 and c levels should be merged into one level. And GCH would mean that 2c = aleph2, 22c = aleph3, etc.

    Leave a Reply