from Hilbert’s tenth problem to Gödel’s trichotomy

From Hilbert’s tenth problem to Gödel’s trichotomy

1 Hilbert on the pursuit of knowledge

In the Summer of 1900 the Second International Congress of Mathematicians took place in Paris and Hilbert’s paper to the Congress has the form of a statement of the strategical goals to be pursued by the discipline. But in his paper Hilbert not only drew up a chart of the resulting future profile of the discipline but he also reflected on the human faculty which makes mathematical experience possible.

We can therefore distinguish two main components in Hilbert’s strategy.

One first component was his chart, which took the form of the today well known list of twenty three problems, the solution of which would then enrich the discipline with ever new goals and methods. With the benefit of hindsight we can see today that not only the list of problems revealed to be a happy choice, but that some of their solutions did indeed deliver the announced new directions.

The second component was the already mentioned reflection on the human faculty that makes mathematical experience possible, as it reveals itself in pattern recognition and in particular in problem solving. Indeed for Hilbert it is only the existence of problems that makes the pursuit of knowledge alive. And this results from the experienced fact that only the search for the solution of a problem provides the inspiration needed to discover new patterns of inference.

2 The two sources of mathematical knowledge

As to the source from which the growth of mathematical knowledge is obtained Hilbert sees in first place, in accordance with the then dominating Zeitgeist, the pressures that result from an attempt to understand the external world by means of physical theories. Accordingly, only the solution of Problem number 6 in his chart will provide the axioms of physical theories with the certainty enjoyed by mathematical theories.

But the success obtained in the solution of problems concerning external reality will enrich the mathematician’s mind with the insight about its own independence. He will then be able to discover within the mind new problems, which prima facie do not depend on physical stimulation. This stimulation will be replaced by permutations of logical patterns, the best examples of which are the introduction and the elimination of quantifiers in inferential thinking and above all in the decomposition or analysis of a concept in its constituent parts. This new realm of experience will not eliminate the pressures from the external world, but it will turn out that these pressures are better addressed if the insights gained in pure thought are brought to bear on their solution.

It is this recurring shift from objective reality to mental experience that gives rise to a form of leibnizian pre-established homology between the conceptual structure of (only) apparently diverse domains of knowledge.

3 Hilbert’s epistemological optimism

This homology of conceptual structure applies also within mathematics itself, and accordingly Hilbert rejected the then popular misconception that the definition of mathematical rigor was only attainable in number theory, eventually also in analysis.

His view was that if a mathematical concept is prompted by considerations in geometry, physics or even epistemology, the mathematician’s task is to bring to light the underlying properties buried in the concept, and articulate them in set of axioms. In this way the rigor of the reasoning about the new concept is secured by proofs that have the same logical necessity of the proofs in number theory.

Therefore the object of mathematics is to unfold the deductive structure of systems of concepts. In view of the fact that every consistent set of axioms has a model, it would seem reasonable to argue that the choice of axioms is also forced upon us by requirements of evidence, either towards physical experience or towards the previously built body of mathematical knowledge.

Thus for Hilbert the rewarded effort found in solving whatever problems present themselves to the mathematician’s consideration creates the unshakable conviction that every problem has a solution which can be found by pure thought.

He therefore rejected Kant’s position according to which the human mind has the uncanny ability to formulate problems for which it can find no solution, the so called paralogisms of pure reason.

Hilbert on the contrary was an adept of a form of epistemological optimism which he very well captured in his motto:

"Wir müssen wissen, wir werden wissen!"

He expected of course that his optimism in the power of the mind to solve problems that the mind itself it is able to formulate, would also apply to his Tenth Problem, concerning the development of a decision procedure for the solution of Diophantine equations.

The mathematical proof that this optimism is unfounded is due to Matijasevicz.

But we report now on a very profound logical and epistemological examination of the network of questions involved in Hilbert’s optimism, due to K. Gödel, and begin by introducing some background material which will prove useful to fully appreciate Gödel’s contribution.

4 Stricto sensu and conditional mathematics

In spite of the fact that the nature of mathematical knowledge has been a recurring theme since Classical Antiquity, the relevant results that support an informed analysis of its limits have only been available since the early XX century. Two such results are due to Gödel and they will in the sequel be referred to as Propositions I and II.

[The reader interested in a logical and formal exposition of these propositions (and their proofs) may find useful to read the PM entry "beyond formalism: Gödel’s incompleteness" (http://planetmath.org/BeyondFormalism).]

A third foundational result should be mentioned, namely the successful analysis of the concept of "finite procedure" by A. Turing.

A significant measure of this success lies in the fact that although the concept can be defined in a variety of ways, the resulting definitions always turn out to be equivalent. In essence, for Turing, a finite procedure is a machine whose component parts are finite in number.

Now the existing contrast, familiar in natural deduction systems, between a proof from a premiss (or a conditional proof) and a proof from the empty set of premises (or an absolute proof), suggests the use of a similar partition of mathematical theorems. We will then have on one side the class of all theorems that are true conditionally, like the theorems of a hypothetical-deductive system in plane geometry, and on the other side the class of all those theorems that are true in an absolute sense. It is in this case that we say that the theorems are true stricto sensu, and we want to call the set of all such theorems stricto sensu mathematics. In the domain of stricto sensu mathematics we will include formal logic and recursive arithmetic.

There is however a small difficulty with the definition of the space of stricto sensu mathematics and it results from the fact that the concept "formal logic", used in the description of the domain, can be interpreted in more than one way.

For example, in the PM entry "intuitionistic logic" (http://planetmath.org/IntuitionisticLogic) there is a list of classical logical principles the universal validity of which is questioned by intuitionistic logic.

It is to be observed that in this conception stricto sensu mathematics is a necessary condition of conditional mathematics, since without the absolute validity of some logical principles, like modus ponens, the proofs of the theorems of conditional mathematics could not be established.

Of course the difficulties about the above mentioned definition of the space of stricto sensu mathematics depend on a previously adopted position in mathematical philosophy. This is very obviously revealed in the dispute about the universal validity of the tertium non datur or about the significance of the general concept of set.

But in any case Propositions I and II have not only proven the existence of the incompleteness phenomenon, but have above all also shown that this phenomenon is independent of a previously adopted position in mathematical philosophy.

5 The cumulative hierarchy

That this phenomenon does not depend not a previously accepted foundational position can be best shown by turning our attention to one of the most natural of all foundational positions, the axiomatic theory of sets.

Indeed we have the striking fact that the accepted body of mathematical knowledge has a most natural representation in the network of concepts of axiomatic set theory. But if we now try to identify the incompleteness phenomenon in the process of formulating the axioms for set theory, we become aware of the following contrast:

Whereas one can formulate the axioms of some mathematical theories with a finite number of axioms (an example of which is geometry), the formulation of the axioms of abstract set theory requires an infinite number of axioms.

In particular one can always reiterate extensions for the formulated axioms and it is not possible to bring all this body of rules under a single finite rule.

Under these circumstances Gödel has suggested that in order to maintain the theory immune to the paradoxes one has to adopt a gradual approach to axiomatization, along the stages of a cumulative hierarchy, the primitive function of which, $𝔓$, builds the power set of a given set.

The cumulative hierarchy can be characterized by the following rules:

1. There is an initial stage.

2. If $𝔖$ is a stage, there is the stage $𝔖+1$.

3. Each stage is obtained from its predecessor and its content is the power set of the predecessor.

4. If an initial segment $\Im$ of the hierarchy does not have a maximum, $\Im +1$ is the union of all preceding stages.

With each stage we associate:

• i) A natural number $n$, the number of its rank and

• ii) The axioms about the $n$-entities.

If one starts with the simplest case, stage 0, one has accordingly a set of natural numbers $𝔐$ and the axioms about $𝔐$.

Stage 1 contains $𝔐,𝔓(𝔐)$ and the axioms about the 1-entities.

Stage $n$, denoted by ${𝔖}_n$, contains all entities built up to stage $n$ and the axioms about them.

Next we have the stage of all finite entities, that is of rank $\omega$, denoted by ${𝔖}_{\omega }$ and we can now build the stage of all its subsets together with the axioms about them.

To proceed beyond $\omega$ we can use transfinite induction and associate with each stage an ordinal number. Thus starting with the empty set we could then have the following definition:

1. ${𝔖}_0=\mathrm{\varnothing }$

2. ${𝔖}_{n+1}=𝔓({𝔖}_n)$

3. If $\alpha$ is a limit ordinal then ${𝔖}_{\alpha }=\bigcup _{\beta \in \alpha }{𝔖}_{\beta }$.

6 Diophantine equivalent of number theoretical statements

Now it turns out that for the development of present day mathematics the really relevant stages are the first three. That in turn means that the initial project of carrying out an axiomatization with a finite number of axioms is after all a possibility.

But this possibility does not weaken the significance of the cumulative hierarchy. On the contrary, an important result shows precisely the relevance of the higher rank axioms even for the initial stage, that is the theory of integers, namely that each of these higher axioms contains the solution of Diophantine problems with no solution with the axioms of lower rank.

We are referring to Gödel’s 1934 Princeton Lectures, in particular Section 8 on the Diophantine equivalent of the undecidable proposition of a formal theory for arithmetic or of the proposition stating the consistency of the theory.

[The PM entry "beyond formalism: Gödel’s incompleteness" (http://planetmath.org/BeyondFormalism) reports on undecidable propositions in classical number theory, and builds the proposition stating the consistency of the system.

For a suitable definition of a Diophantine equation as a polynomial equation with integer coefficients and solutions in the integers see the PM entry "diophantine equation" (http://planetmath.org/DiophantineEquation).]

Let us assume that:

$P(x_1,\mathrm{\dots },x_n)$

is a polynomial with coefficients in $\mathbb{Z}$. Introducing quantifiers we can make statements in $\mathbb{Z}$ about a Diophantine equation:

$P(x_1,\mathrm{\dots },x_n)=0$

with the following forms:

• i)   $(\exists x_1,\mathrm{\dots },\exists x_n)P(x_1,\mathrm{\dots },x_n)=0$,

  which asserts the existence of a solution of the Diophantine equation;

• ii)   $(\forall x_4)(\exists x_1,\exists x_2,\exists x_3,\exists x_5,\mathrm{\dots },\exists x_n)P(x_1,\mathrm{\dots },x_n)=0$

  which asserts that the equation has a solution for all values assigned to $x_4$. We want to call these formulas Diophantine statements.

In his lectures Gödel shows that there is a sequence of quantifiers $(Q_1,\mathrm{\dots },Q_n)$ and a Diophantine equation $P(x_1,\mathrm{\dots },x_n)=0$ such that the Diophantine statement:

$(Q_1,\mathrm{\dots },Q_n)[P(x_1,\mathrm{\dots },x_n)=0]$

is the number theoretical equivalent to the undecidable proposition. The reduction of number-theoretical propositions to Diophantine statements is done by the elimination of negation and disjunction.

Gödel introduces the notion of a normal form that all arithmetic expressions can be brought to. An arithmetic expression is built by means of the symbols for the propositional connectives, the arithmetical functional symbols for sum and product, equality and, in this version, the variables range over $\mathbb{N}$.

In particular:

$(𝔇)$  If $\mathrm{f}$ and $\mathrm{g}$ are polynomials with coefficients in $\mathrm{N}$, then $\mathrm{f}\mathrm{=}\mathrm{g}$ is an arithmetical expression.

The domain of arithmetical expressions is closed under the logical operations and quantification.

All arithmetical expressions can have the normal form:

$(Q)[A=B]$

where $A$ and $B$ are polynomials with coefficients in $\mathbb{N}$.

If the arithmetical expression has $0$ occurrences of logical functions and quantifiers then the expression is in normal form by $(𝔇).$

We assume now that an arithmetical expression:

$𝔄=(Q)[A=B]$

has an occurrence of $x$ in ($Q$).

Then $(\forall x)𝔄$ is the formula:

$(\forall x)(Q)[A=B].$

Similarly $(\exists x)𝔄$ is the formula:

$(\exists x)(Q)[A=B].$

The same holds for an arithmetical expression:

$𝔅=(Q^{*})[A^{*}=B^{*}]$

with distinct variables in $(Q)$ and $(Q^{*}).$

From propositional and predicate calculus we use the following facts:

• i) The set of propositional connectives can be reduced to the pair $(\sim ,\vee );$

• ii) $P\vee (\exists x)F(x)\leftrightarrow (\exists x)[P\vee F(x)];$ and

• iii) $P\vee (\forall x)F(x)\leftrightarrow (\forall x)(P\vee F(x)].$

Case 1: Disjunction

To define $𝔄\vee 𝔅$ we simply use substitution and since we have for $𝔄$ the formula $(Q)[A=B]$ and for $𝔅$ the formula $(Q^{*})[A^{*}=B^{*}]$ the resulting formula will be:

$(Q)(Q^{*})[A=B\vee A^{*}=B^{*}].$

From this we deduce that:

$(Q)(Q^{*})[A-B=0\vee A^{*}-B^{*}=0].$

This implies that:

$(Q)(Q^{*})[(A-B)\cdot (A^{*}-B^{*})=0].$

Carrying out the product gives:

$(Q)(Q^{*})[A\cdot A^{*}-A^{*}\cdot B-A\cdot B^{*}+B\cdot B^{*}=0].$

But this is the same as:

$(Q)(Q^{*})[A\cdot A^{*}+B\cdot B^{*}=A^{*}\cdot B+A\cdot B^{*}]$

which already is the desired normal form.

Case 2: Negation

We define $\sim 𝔄$ as being the formula:

$\sim (Q)[A=B].$

We use again two facts from predicate calculus, in particular:

• i) $\sim (\forall x)P\leftrightarrow (\exists x)\sim P$; and

• ii) $\sim (\exists x)P\leftrightarrow (\forall x)\sim P$

which allow to shift the negation sign from the prefix into the expression.

This will then give a negation-free prefix $(𝔔)$ such that:

$(𝔔)[\sim (A=B)].$

This implies that $A-Ã\mathrm{‚}â\mathrm{‚}\mathrm{\neg }Ã\mathrm{‚}â\mathrm{€}\mathrm{œ}B\ne 0$ and a fortiori that ${(A-B)}^2>0.$

Computing the square and transposing gives:

$(𝔔)[A^2+B^2>2\cdot A\cdot B]$

and therefore it follows that:

$(𝔔)[A^2+B^2\ge 2\cdot A\cdot B+1].$

Eliminating $>$ gives:

$(𝔔)(\exists k)[A^2+B^2=2\cdot A\cdot B+1+k],$

which has the desired normal form.

Using the introduced notation we can accordingly give a formulation of a general Diophantine Problem by means of the following statement:

($\mathrm{\Delta }$) Either the equation $P\mathrm{=}\mathrm{0}$ has (finite or infinite in number) solutions in $\mathrm{Z}$ for all values in $\mathrm{Z}$ of its parameters, or there are values in $\mathrm{Z}$ for which $P\mathrm{=}\mathrm{0}$ has no solutions in $\mathrm{Z}$.

Gödel’s representation of recursively enumerable sets was instrumental for the later work on Hilbert’s 10th Problem by Martin Davis, Julia Robinson and Yuri Matijasevicz, so that by 1970 the result was available that there is no finite procedure to solve all Diophantine equations.

7 The incompleteness and consistency propositions

We want now to return to the already mentioned Propositions I and II and bring them into the context of the general Diophantine problem ($\mathrm{\Delta }$):

Proposition I:

In every consistent and well formed system of axioms and rules of inference there are Diophantine problems of the kind of ($\mathrm{\Delta }$) which can not be decided by the axioms and the rules of inference.

The term "well formed" that occurs in the Proposition implies a specifiable formal system, whose axioms can be effectively given and whose rules of inference establish if a conclusion actually follows from the premises.

This requirement is equivalent to have a Turing machine capable of writing all the consequences that follow from the axioms. Under these circumstances Proposition I ensures that a finite procedure to decide all Diophantine problems of type ($\mathrm{\Delta }$) does not exist.

If one has a well formed system of axioms and rules of inference, the consistency question about the system can also be transformed in a Diophantine statement. This results from the fact that the symbols of the consistency formula are identified with Gödel numbers and therefore represented as integers.

To formulate Proposition II we have to assume:

• i) The consistency of the system and

• ii) That in the system, Peano arithmetic derivations can be carried out in such a way that they are finitistic meaningful.

Proposition II:

In every well formed system of axioms and rules of inference, the proposition that expresses its consistency is not derivable from the axioms and the rules of inference.

8 Sketch of a Gedankenexperiment

We consider now a mathematician M reflecting on the situation so far created by the preceding constructions and in particular by Propositions I and II.

Let us assume that there is a stage in his reflection in which M arrives at the following perceptions:

• i) He perceives the evidence of the correction of the axioms and the rules of inference used; and

• ii) He perceives that outside (of the space that they define) there is no mathematics.

We can call his reflections a Gedankenexperiment and want now to analyze whether it is consistent and therefore has a model.

1. If M perceives the correction of the axioms and the rules of inference to the point of realizing their evidence, then with the same degree of evidence he can also realize that the system is consistent;

2. Now this evidence about the consistency of the system is, as we know from the arithmetization of metamathematics, equivalent to the evidence that M has about the number-theoretical proposition that expresses the consistency of the system, which is in turn equivalent to a Diophantine statement. It is therefore in kind a mathematical evidence.

3. But Proposition II above asserts that the consistency of the system can not obtained from the axioms and the rules of inference, that is from within the system itself.

4. This implies that the evidence of the consistency of the system is both mathematical (by 2.) and can not be obtained from within the system (by 3.).

5. There is therefore mathematical knowledge in another space outside, in contradiction to perception 2.

This proves that the Gedankenexperiment is inconsistent and therefore does not amount to a model of the space created by both perceptions.

9 Gödel’s trichotomy

To learn something from this Gedankenexperiment we co-define now the space of stricto sensu mathematics as the domain in which mathematical propositions are true.

In that case the inconsistency of the Gedankenexpriment teaches us that there is no correct system of axioms and rules which contains the whole body of mathematical knowledge.

If instead of truth we use as leading concept the concept of proof, and co-define accordingly stricto sensu mathematics as the domain in which mathematical propositions are provable, then we don’t learn this lesson.

But in this last case (of proof) it will be convenient to talk of mathematics as dependent on the deductions of a reflective subject, in short subject-dependent. In the first case (of truth) we would be talking about a domain of mathematics which does not dependent of a reflective subject, in short subject-independent.

In any case Proposition II shows that no system can contain the whole body of mathematics known by the perceptions of a reflective subject, since the proposition that expresses the consistency of the system (or its Diophantine equivalent) can not be an object of the system.

We can now reshape our Gedankenexperiment into a situation in which M is endowed with a finite rule $\rho$, and such that $\rho$ produces as output all the evident axioms of the domain of mathematics that are subject-dependent.

In this case M could never have the perception of the correction of any and every proposition that the system might produce. But in such a case he could realize the truth of each proposition of the system, one at a time. This is the case in which M’s mind could be considered to be equivalent to a finite machine which would be able to monitor the rules of its own operation.

But even in the case of this equivalence, the evidence for the truth that such rules do not lead to an inconsistency would lie out of the limits of M’s mind.

Let us call a problem undecidable in an absolute sense if:

• i) In a given formal system there is no solution which could decide the problem; and

• ii) A solution that could decide it lies outside the limits of textbfM’s mind and can not be perceived by M.

Then the postulated equivalence between M’s mind and a finite machine would entail the existence of Diophantine problems undecidable in an absolute sense, (like the proof of the consistency of the system), since their solution would lie beyond the perceptive range of M’s mind.

To sum up we are lead to the following trichotomy:

1. Reject the equivalence between M’s mind and a finite machine, and ascribe to M’s mind the power to decide more number-theoretical statements than any finite machine.

2. Contrary to Hilbert’s motto, assert the existence of number theoretical statements, like Diophantine problems, undecidable in an absolute sense, and that means out of the bounds of cognition of M’s mind.

3. Recognize that 1. and 2. are not an exclusive disjunction.

Gödel thought that the acceptance of the truth of his trichotomy was in no way dependent on the position one might want to take in foundations. He tried to accommodate the intuitionistic dissent by saying that it was due to a question of internal strategy.

Of his trichotomy, in intuitionism statement 1. will be accepted but statement 2. will be rejected.

In contrast in predicativism (http://planetmath.org/Predicativism) (see [2]) Gödel’s trichotomy is accepted.

Title	from Hilbert’s tenth problem to Gödel’s trichotomy
Canonical name	FromHilbertsTenthProblemToGodelsTrichotomy
Date of creation	2013-03-22 18:34:06
Last modified on	2013-03-22 18:34:06
Owner	gribskoff (21395)
Last modified by	gribskoff (21395)
Numerical id	10
Author	gribskoff (21395)
Entry type	Topic
Classification	msc 03A05
Classification	msc 03-01
Synonym	diophantine equivalent
Synonym	diophantine problem
Synonym	Gödel’s Gibbs Lecture
Related topic	AnOutlineOfHilbertsProgramme
Related topic	BeyondFormalism
Related topic	DiophantineEquation
Related topic	GodelsBetaFunction
Defines	Gödel’s trichotomy