                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

1 Arithmetic II

We return to the two first-order formalizations of arithmetic to make some remarks on how the study of these subjects can be developed further.

1.1 Peano Arithmetic: Definability

Since First-order Arithmetic is known to be rather intractable (it is undecidable), when looking for an effective approach to number theory, something which one might use for an automated theorem prover, it is natural to consider Peano Arithmetic since, as we said, all standard theorems of number theory which can be formulated as first-order statements can be derived from PA. To see that this is true one needs to return to the formulations in the previous section and show that they can be used in PA.

DEFINITION 1

(a) A relation r ⊆ ω^{n} is defined in PA by the formula φ(x_{1}, …, x_{n}) if for each (k_{1}, …, k_{n}) ∈ ω^{n} we have

(k_{1}, …, k_{n}) ∈ r  ⟹  PA ⊢ φ(k̄_{1}, …, k̄_{n})
(k_{1}, …, k_{n}) ∉ r  ⟹  PA ⊢ ¬φ(k̄_{1}, …, k̄_{n})

(b) A function f : ω^{n} ⟹ ω is defined in PA by the formula φ(x_{1}, …, x_{n}, y) if for each (k_{1}, …, k_{n}, k) ∈ ω^{n+1} we have

f(k_{1}, …, k_{n}) = k  ⟹  PA ⊢ φ(k̄_{1}, …, k̄_{n}, k̄)
f(k_{1}, …, k_{n}) ≠ k  ⟹  PA ⊢ ¬φ(k̄_{1}, …, k̄_{n}, k̄)
and  PA ⊢ ∃!y φ(k̄_{1}, …, k̄_{n}, y)

In his 1931 paper Gödel showed that the relations and functions discussed in the previous section on first-order arithmetic are indeed definable in PA^{1}. Using this expressive power of PA Gödel went on to give explicit first-order sentences which are true in ω but cannot be derived from PA.

1As are all decidable relations and computable functions.

Exercises Problem 1

(a) Show < and ≤ are definable in PA.

(b) Show | is definable in PA.

(c) Show prime(x) is definable in PA.

(d) Show coprime(x) is definable in PA.

(e) Show Gödel’s β function is definable in PA.

(f) Show x^{y} is definable in PA.

1.2 The Two Arithmetics

Let us briefly review the two versions of the natural numbers which we have considered.

First-Order Arithmetic • Symbols ∧, ∨, ¬, ⟹ , ∀, ∃, +, ×, 0, 1 and variables

• Formulas first-order formulas

Truth  Derivation
⊧ φ  ⊢ φ

means φ is true of the nonnegative numbers

Axioms

Rules of Inference

nothing reasonable exists

We know from the work of Gödel (1931), Church and Rosser (1936) that we cannot hope for a reasonable^{2} sound and complete logic to derive all the first-order truths of number theory. But if we are willing to settle for some of the truths of number theory we can try PA, the first-order formulation of Peano’s axioms. Then indeed we have a logic system

2reasonable roughly means that we want to be able to generate the axioms and rules of inference.

Peano Arithmetic

• Symbols ∧, ∨, ¬, ⟹ , ∀, ∃, +, ×, 0, 1 and variables

• Formulas first-order formulas

Truth  Derivation
PA ⊧ φ  PA ⊢ φ

means φ is true in any structure in which PA is true

Axioms  Rules of Inference

PA

usual rules for first-order logic

which is sound and complete (provided it is consistent); and all known theorems of traditional number theory which can be expressed in first-order form can be derived from this system. There are some very interesting open problems which can be expressed in first-order arithmetic, e.g., the Riemann Hypothesis. We do not know if these questions can be settled by Peano Arithmetic — the completeness is with respect to all models of PA, not just the nonnegative numbers.

References

[1] A. Church, An unsolvable problem of elementary number theory. The American J. of Math. 58 (1936), 345–363.

[2] K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter System. I. Monatshefte für Mathematik und Physik, 38 (1931), f173–198. [transl. in From Frege to Gödel, van Heijenoort, Harvard Univ. Press, 1971.]

[3] J.B. Rosser, Extensions of some theorems of Gödel and Church. J. Symbolic Logic 1 (1936), 87–91.