Thoralf Skolem Einfacher Beweis der Unmöglichkeit eines allgemeinen Lösungsverfahren für aritmetische Probleme

Abstract

Thoralf Skolem was a leading Norwegian mathematician of the last century. He is particularly known for his work in mathematical logic and set theory, but he also contributed a number of important results to algebra, number theory and combinatorics. From his early education and first work experience as an assistant in geophysics he had a broad knowledge of both pure and applied mathematics. We learn from his early work that he was above all interested in structures and algorithms and that axioms and proofs were at most necessary tools and did not in themselves represent the real «substance» of mathematics. It is therefore not surprising that he was not at all convinced when he first learned of the Russell and Whitehead’s approach to elementary arithmetic through abstract logic and set theory. We get the impression that Skolem «knew» what numbers are and that he wrote his fundamental paper on primirive recursive arithmetic in 1923 as an protest against the logicism of Principia Mathematica.

We see a similar attitude in his work on proof structures. His approach was bottom-up, and he wanted step-by-step to develop algorithms to decide questions of validity and proof in first order logic and arithmetic; see his paper of 1928 in Norsk Matematisk Tidsskrift. This was not in any way an unreasonable strategy in the 1920s. But this approach came to an abrupt stop with the publication of Gödel’s incompleteness theorem in 1931 and the later work by Church and Turing in 1936. The interest now turned to explore the unknown territory between the decidable and the undecidable. One main challenge was Hilbert’s 10th problem asking for a general algorithm for solving Diophantine equations. A Diophantine equation is a special kind of arithmetical statement. A general arithmetical statement is a first order statement with numbers constants, with addition and multiplication as the only operatins, and equality as the only relation, and where «first order» means that we only have number and not set quantifiers. A Diophantine equation is an arithmetical statement consisting of a string of existential quantifiers prefixed to an equation of fixed degree, thus the validity of the statement is the same as asking for a solution to the equation.

The mathematical substance of Skolem’s note of 1940 is a proof of the impossibility of an algorithm for the the class of arithmetical problems. His proofproceeds by first establishing that any equation between recursive functions is equivalent to an arithmetical statement. The proof is a simple extention of a key technical lemma from Gödel’s 1931 paper, which proves this result for primitive recursive functions (Skolem 1923). A standard diagonal argument then completes the proof. Hilbert’s 10th problem would follow if we in an arithmetical statement could reduce a mixed prefix of existential and universal quantifiers to a pure existential form. We would have expected that Skolem with his formidable skills in logic, number theory and combinatorics had immediately turned to this challenge, but there is no trace of any such attempt in his later works. The reduction, by a clever and head-on use of standard methods that in principle was well known to Skolem, was obtained in 1970 by the young Russian mathematician Y. Matiyasevich.