prevented people from getting my results. This fact is a clear proof that the prejudice is a mistake.
Gödel’s theorem on the completeness of first-order logic and his discovery of the incompleteness phenomenon together with the undefinability of truth vs. definability of formal demonstrability showed that formal provability cannot be treated as an analysis of truth, that the former is in fact weaker than the latter. It was also shown in this way that Hilbert’s dreams to justify classical mathematics by means of finitistic methods cannot be fully realized. Those results together with Tarski’s definition of truth (in the structure) and Carnap’s work on the syntax of a language led also to the establishing of syntax and semantics in the 1930s.
On the other hand, it should be added that Gödel shared Hilbert’s “rationalistic optimism” (to use Hao Wang’s term) insofar as informal proofs were concerned. In fact, Gödel retained the idea of mathematics as a system of truth, which is complete in the sense that “every precisely formulated yes-or-no question in mathematics must have a clear-cut answer” (cf. Gödel 1970). He rejected however – in the light of his incompleteness theorem – the idea that the basis of these truths is their derivability from axioms. In his Gibbs lecture of 1951, Gödel distinguishes between the system of all true mathematical propositions from that of all demonstrable mathematical propositions, calling them, respectively, mathematics in the objective and subjective sense. He claimed also that it is objective mathematics that no axiom system can fully comprise.
←29 | 30→
Gödel’s incompleteness theorems and in particular his recognition of the undefinability of the concept of truth indicated a certain gap in Hilbert’s program and showed in particular, roughly speaking, that (full) truth cannot be comprised by provability and, generally, by syntactic means. The former can be only approximated by the latter. Hence there arose a problem: How should Hilbert’s finitistic point of view be extended?
Hilbert in his lecture in Hamburg in December 1930 (cf. Hilbert 1931) proposed to admit a new rule of inference. This rule was similar to the ω-rule, but it had rather informal character (a system obtained by admitting it would be semiformal). In fact, Hilbert proposed that whenever A(z) is a quantifier-free formula for which it can be shown (finitarily) that A(z) is a correct (richtig) numerical formula for each particular numerical instance z, then its universal generalization ∀xA(x) may be taken as a new premise (Ausgangsformel) in all further proofs.
Gödel pointed in many places that new axioms are needed to settle both undecidable arithmetical and set-theoretic propositions. In 1931 (p. 35), he stated that “[...] there are number-theoretic problems that cannot be solved with number-theoretic, but only with analytic or, respectively, set-theoreticmethods”.Andin1933 (p. 48)he wrote: “there are arithmetic propositions which cannot be proved even by analysis but only by methods involving extremely large infinite cardinals and similar things”. In (1970) Gödel proposed “cultivating (deepening) knowledge of the abstract concepts themselves which lead to the setting up of these mechanical systems”. In (1972) (this paper was a revised and expanded English version of 1958), Gödel claimed that concrete finitary methods are insufficient to prove the consistency of elementary number theory and some abstract concepts must be used in addition. In the paper (1946), Gödel explicitly called for an effort to use progressively more powerful transfinite theories to derive new arithmetical theorems.
Also Zermelo proposed to allow infinitary methods to overcome restrictions revealed by Gödel. According to Zermelo, the existence of undecidable propositions was a consequence of the restriction of the notion of proof to finitistic methods (he said here about “finitistic prejudice”). This situation could be changed if one used a more general “scheme” of proof. Zermelo had here in mind an infinitary logic, in which there were infinitely long sentences and rules of inference with infinitely many premises. In such a logic, he insisted, “all propositions are decidable!” He thought of quantifiers as infinitary conjunctions or disjunctions of unrestricted cardinality and conceived of proofs not as formal deductions from given axioms but as metamathematical determinations of the truth or falsity of a proposition. Thus syntactic considerations played no role in his thinking.
To give a rough account of how those suggestions and proposals to extend the finitistic point of view do in fact work, let us quote some technical results. We ←30 | 31→restrict ourselves to the case of the arithmetic of natural numbers, more exactly to Peano arithmetic PA.
Generally speaking, one can obtain completions of PA by:
admitting the ω-rule,
adding new axioms (in particular reflection principles) and
adding (partial) notion(s) of truth.
Let us start by considering the case of the ω-rule, i.e., of the following rule:
Denote by (PA)ω Peano arithmetic PA with the ω-rule. One can easily see that (PA)ω is complete – it follows from the fact that its unique model up to isomorphism is the standard model
One can ask: How many times must the ω-rule be applied to obtain a complete extension of PA? To give an answer, let us define the following hierarchy of theories where T is any first-order theory in the language L(PA) of Peano arithmetic:
| To | = | T, |
|
|
= |
Tα ∪{φ ∶ φ is of the form ∀xψ(x) and |
| Tα+1 | = |
the smallest set of formulas containing |
| Tλ | = |
|
One can now prove that
Theorem 1
Recall the hierarchy of formulas of the language L(PA). Let
Theorem
