FOM: more on Hilbert

[Neil Tennant]

This is in reply to Bill Tait's helpful posting about the term
"Entscheidbar" in Hilbert's 1904 paper. Bill puts the terminology of
the 1917 paper "Axiomatisches Denken" into better perspective.
At pp.412-413 of the latter, Hilbert listed certain "difficult
epistemological questions of a specifically mathematical flavor".
These included, among other, the question of the solubility
(L"osbarkeit) of every mathematical question, and the problem of the
decidability (Entscheidbarkeit) of a mathematical question by a finite
number of operations.

That these are mentioned as separate questions or problems would lead
one to expect them to be logically distinct. But before we infer that
the second problem is exactly the modern one of decidability (of
*theories*), we ought perhaps to consider alternative interpretations
in the context of Hilbert's own beliefs, even if some of these beliefs
are mistaken. 

The strongest possible modern interpretation of the (false) claim that
every mathematical question is decidable is something like:

(I)	 Given a comprehensive language L for the expression of all
	 of mathematics, there is a mechanical method M such that
	 for all sentences S in L, M(S) is "yes" or "no" according
	 to whether S is true or false, respectively.

A slightly weaker interpretation would be something like

(II)	 Given a comprehensive language L for the expression of all
	 of mathematics, and given any sentence S of L, there is some
	 correct axiomatic theory A (not necessarily effectively
	 determinable from S---but a system of whose correctness we
	 can nevertheless become convinced) and some decision
	 procedure M for provability-in-A, such that either M(S) or
	 M(not-S) is "yes". 

On this interpretation, mathematical knowledge could be idealized as
generated by a chain of *decidable* axiomatic theories A_1, A_2,
... (each A_i included in A_i+1), with the sequence not necessarily
mechanically enumerable, but with every mathematical truth eventually
captured within some A_i. By stipulating that the sequence is not
necessarily mechanically enumerable, we of course avoid having as a
consequence that (II) collapses into (I). (II) asserts, as it were,
piecemeal theoretical decidability, rather than global decidability.

An even weaker interpretation would be

(III)	 Given a comprehensive language L for the expression of all
	 of mathematics, and given any sentence S of L, there is some
	 correct axiomatic theory A (not necessarily effectively
	 determinable from S---but a system of whose correctness we
	 can nevertheless become convinced) such that either A proves
	 S or A proves not-S (and does so, of course, in a finite
	 number of steps).

On this interpretation, mathematical knowledge could be idealized as
generated by a chain of (possibly *undecidable*) axiomatic theories
A_1, A_2, ... (each A_i included in A_i+1), with the sequence not
necessarily mechanically enumerable, but with every mathematical truth
eventually captured within some A_i. Thus (III) is the claim of
solubility L"osbarkeit) of every mathematical question---what I called
Mathematical Optimism in earlier postings. 

The exegetical question is whether (I) or (II) would be the better
interpretation of what Hilbert had in mind, in 1904 and in 1917. From
the way he expresses himself in 1917, it seems that this question is
at least moot. On p.413 of "Axiomatisches Denken" he writes of "das
Problem der *Entscheidbarkeit* einer mathematischen Frage durch eine
endliche Anzahl von Operationen."  It seems to me that Interpretation
(II) above would fit this quite nicely. Later, on p.415, he refers to
"die eben behandelte Frage nach der Entscheidbarkeit durch endlich
viele Operationen", and this, too, fits with Interpretation (II). I do
concede to Bill, though, that we cannot impose the yet weaker
Interpretation (III) on these phrases, especially in light of Hilbert's
explicitly separate mention of the problem of L"osbarkeit.

Whether one would be entitled to insist, however, on Interpretation
(I) (existence of a global decision procedure) for Hilbert's use of
"Entscheidbarkeit einer mathematischen Frage" is not at all clear. Hao
Wang refers (on p.55 of "Reflections on Kurt G"odel") to a "published
statement of Bernays in 1930 that to the effect that decidability is
stronger than completeness." [Wang's system of bibliographical
references here is somewhat obscure, so I have not yet tracked down
the exact source of Bernays' statement.] It is difficult to tell
whether this statement is about decidability and completeness of
*theories* (the modern interpretation), or about decidability and
completeness (Entscheidbarkeit and L"osbarkeit) of mathematics as a
whole, in the less precise senses from Hilbert 1917 under discussion
above. I would suggest, however, that Interpretation (II) above would
go some way to making explanatory sense of Bernays' statement here. To
a modern foundationalist, the statement would otherwise seem curiously
naive and obviously mistaken. 

But Wang himself seems to think that it was only with Turing 1936 that
workers in foundations realized that for formal axiomatic theories,
completeness implies decidability. It would be worthwhile to try to
determine when exactly in Hilbert's own thinking and writings (if at
all) decidability came to be thought of as a property of particular
axiomatic *theories* rather than as a feature of "mathematical questions".
Only then will we be able to determine whether Bernays can be held to
have made an elementary blunder.

Neil Tennant