Two perspectives on Hilbert’s First and Second Problems

In the Birmingham paper ‘Evidence-Based Interpretations of PA’, we introduced the distinction between algorithmic verifiability and algorithmic computability.

We showed how the distinction naturally helped distinguish between a finitary algorithmic interpretation \mathcal{I}_{PA(N,\ Algorithmic)} of PA, and the non-finitary standard interpretation \mathcal{I}_{PA(N,\ Standard)} of PA.

We then showed how the former yielded a finitary proof of consistency for PA, as demanded by the second of Hilbert’s celebrated 23 problems.

In the previous post, we also highlighted why the the non-finitary standard interpretation \mathcal{I}_{PA(N,\ Standard)} of PA does not yield a finitary proof of consistency for PA.

Cantor’s Continuum Hypothesis

We now show that the difference between the conclusions suggested by finitary reasoning and those suggested by non-finitary reasoning in the previous pages (as in the case of Goodstein’s argument) is reflected further in the differing status of the Continuum Hypothesis (the first of Hilbert’s 23 problems) when viewed from finitary and non-finitary perspectives as detailed below.

The non-finitary set-theoretical perspective

The non-finitary set-theoretical perspective on the Continuum Hypothesis is well-known, and described succintly by Topologist Peter Nyikos in a short expository lecture given at the University of Auckland in May, 2000:

In 1900, David Hilbert gave a seminal lecture in which he spoke about a list of unsolved problems in mathematics that he deemed to be of outstanding importance. The first of these was Cantor’s continuum problem, which has to do with infinite numbers with which Cantor revolutionised set theory. The smallest infinite number, \aleph_{0}, `aleph-nought,’ gives the number of positive whole numbers. A set is of this cardinality if it is possible to list its members in an arrangement such that each one is encountered after a finite number (however large) of steps. Cantor’s revolutionary discovery was that the points on a line cannot be so listed, and so the number of points on a line is a strictly higher infinite number (c, `the cardinality of the continuum’) than \aleph_{0}. Hilbert’s First Problem asks whether any infinite subset of the real line is of one of these two cardinalities. The axiom that this is indeed the case is known as the Continuum Hypothesis (CH). …

Gödel [1940] also gave a partial solution to Hilbert’s First Problem by showing that the Continuum Hypothesis (CH) is consistent if the usual Zermelo-Fraenkel (ZF) axioms for set theory are consistent. He produced a model, known as the Constructible Universe, of the ZF axioms in which both the Axiom of Choice (AC) and the CH hold. Then Cohen showed in 1963 that the negations of these axioms are also consistent with ZF; in particular, CH can fail while AC holds in a model of ZF.”

Hilbert’s First and Second Problems and the foundations of mathematics, Topology Atlas Document # taic-52, Topology Atlas Invited Contributions vol. 9, no. 3 (2004) 6 pp.

Is CH a Definite Mathematical Problem?

Well, the non-finitary set-theoretical formulation of the Continuum Hypothesis isn’t, according to Solomon Feferman who, in a presentation at the inaugural Paul Bernays Lectures, ETH, Zurich, Sept. 12, 2012, restated in his presentation that:

\bullet My view: No; in fact it is essentially indefinite (“inherently vague”).

\bullet That is, the concepts of arbitrary set and function as used in its formulation even at the level of P(N) are essentially indefinite.

Why isn’t the Continuum Problem on the Millennium ($1,000,000) Prize List? CSLI Workshop on Logic, Rationality and Intelligent Interaction, Stanford, June 1, 2013.

Feferman sought to place in perspective the anti-Platonistic basis for his belief by quoting:

“Those who argue that the concept of set is not sufficiently clear to fix the truth-value of CH have a position which is at present difficult to assail. As long as no new axiom is found which decides CH, their case will continue to grow stronger, and our assertion that the meaning of CH is clear will sound more and more empty.”

… D. A. Martin, Hilbert’s first problem: The Continuum Hypothesis, in Mathematical Developments arising from Hilbert Problems, Felix E. Browder, Rutgers University, Editor – American Mathematical Society, 1976, 628 pp.

A finitary arithmetical perspective

However a possible candidate for a finitary arithmetical perspective (as proposed in the previous pages of these investigations) is reflected in the following:

Theorem: There is no set whose cardinality is strictly between the cardinality \aleph_{0} of the integers and the cardinality 2^{\aleph_{0}} of the real numbers.

Proof: By means of Gödel’s \beta-function \beta(b,\ c,\ i), we can show that if r(n) denotes the n^{th} digit in the decimal expansion \sum_{n=1}^{\infty}r(n).10^{-n} of a putatively given real number R in the interval [0,\ 1] then, for any given natural number k, we can define an arithmetical function R(k,\ n) such that:

r(n) = R(k,\ n) for all 1 \leq n \leq k.

Since Gödel’s \beta-function is primitive recursive, it follows that every putatively given real number R can be uniquely corresponded to an algorithmically verifiable arithmetical function R(x) within the first order Peano Arithmetic PA, where we define R(x) by:

R(n) = R(k,\ n) for all 1 \leq n \leq k,

and k is selected such that:

R(k,\ n) = r(n) for all 1 \leq n \leq k.

(For the purist, the above conclusion can be justified by the argument in this preprint.)

Definition: Algorithmically verifiable function

A number-theoretical function F(x) is algorithmically verifiable if, and only if, for any given natural number n, there is an algorithm AL_{(F,\ n)} which can provide objective evidence for deciding the value of each formula in the finite sequence \{F(1), F(2), \ldots, F(n)\}.

“It is by now folklore … that one can view the values of a simple functional language as specifying evidence for propositions in a constructive logic …”.

… Chetan R. Murthy. 1991. An Evaluation Semantics for Classical Proofs. Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, (also Cornell TR 91-1213), 1991.

Definition: Algorithmically computable function

A number theoretical function F(x) is algorithmically computable if, and only if, there is an algorithm AL_{F} that can provide objective evidence for deciding the value of each formula in the denumerable sequence \{F(1), F(2), \ldots\}.

Cantor’s diagonal argument

From a finitary arithmetical perspective, Cantor’s diagonal argument simply shows that there are algorithmically verifiable functions which are not algorithmically computable.

The correspondence is unique because, if R and S are two different putatively given reals in the interval [0,\ 1], then there is always some m for which r(m) \neq s(m). Hence we can always find corresponding arithmetical functions R(m,\ n) and S(m,\ n) such that:

r(n) = R(m,\ n) for all 1 \leq n \leq m.

s(n) = S(m,\ n) for all 1 \leq n \leq m.

R(m,\ m) \neq S(m,\ m).

Since PA is first order, the cardinality of the reals in the interval [0,\ 1] cannot, therefore, exceed that of the integers. The theorem follows. \hfill \Box

In other words, the Continuum Hypothesis is trivially true from a finitary perspective because of the seemingly heretical conclusion that: \aleph_{0} = 2^{\aleph_{0}}, an answer that Hilbert would probably never have envisaged for the first of the celebrated twenty three problems that he bequethed to posterity!

Skolem’s (apparent) paradox

It is an answer that should, however, give comfort to the shades of Thoralf Skolem. In his 1922 address delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians, Skolem improved upon both the argument and statement of Löwenheim’s 1915 theorem—subsequently labelled as the:

(Downwards) Löwenheim-Skolem Theorem

If a first-order proposition is satisfied in any domain at all, then it is already satisfied in a denumerably infinite domain.

Skolem then cautioned about unrestrictedly (and meta-mathematically) corresponding putative mathematical entities across domains of different axiom systems, and drew attention to a:

“… peculiar and apparently paradoxical state of affairs. By virtue of the axioms we can prove the existence of higher cardinalities, of higher number classes, and so forth. How can it be, then, that the entire domain B can already be enumerated by means of the finite positive integers? The explanation is not difficult to find. In the axiomatization, ‘set’ does not mean an arbitrarily defined collection; the sets are nothing but objects that are connected with one another through certain relations expressed by the axioms. Hence there is no contradiction at all if a set M of the domain B is non-denumerable in the sense of the axiomatization; for this means merely that within B there occurs no one-to-one mapping \Phi of M onto Z_{o} (Zermelo’s number sequence). Nevertheless there exists the possibility of numbering all objects in B , and therefore also the elements of M, by means of the positive integers; of course such an enumeration too is a collection of certain pairs, but this collection is not a ‘set’ (that is, it does not occur in the domain B).”

… Thoralf Skolem. 1922. Some remarks on axiomatized set theory. Text of an address delivered in Helsinki before the Fifth Congress of Scandinavian Mathematicians, 4-7 August 1922. In Jean van Heijenoort. 1967. Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts, p.295.

What do you think? Does the above argument apply to the finite ordinals? If so, is ZF inconsistent, or is it \omega-consistent?

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand