Lógos and Máthma 2. Roman Murawski

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 Hence

      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 for every n ∈N},
Tα+1	=	the smallest set of formulas containing and closed under the rules of inference of PA,
Tλ	=	for λ limit.

      One can now prove that

      Theorem 1

      Recall the hierarchy of formulas of the language L(PA). Let be the set of all quantifier free formulas and all formulas with bounded quantifiers. Define to be the set of all formulas of the form ∃xψ for and to be the set of all formulas of the form ∀xψ for We also define Δas the set of all n formulas equivalent (in PA) to a formula and to a formula. One can prove that

      Theorem 2 For every n ∈ N the theory PAn is complete with respect to sentences.

In PA one can define partial notions of truth, i.e., one can define satisfaction and truth for formulas of a given class of the arithmetical hierarchy. Denote by ←31 | 32→the definition of satisfaction for SatΠformulas; similarly let denote the definition of satisfaction for formulas. Note that and formulas are and that and (for n ≥ 1) are and respectively. Let further and denote truth predicates for and sentences.18 In the sequel, we shall identify formulas defining satisfaction and truth and their extensions in the standard model No.

      The previous theorem can now be formulated as:

      In the definition of the hierarchy Tα no restriction was put on formulas to which the ω-rule was applied. Consider now a hierarchy in which such a restriction is put. So let T be any theory in the language L(PA). Define the following hierarchy of theories (cf. Niebergall 1996):

T(o)	=	T,
	=	is of the form ∀xψ(x) and and
		for every n ∈N},
T(α+1)	=	the smallest set of formulas containing and closed