MODERN LOGIC: FROM FREGE TO GÖDEL: SKOLEM

The Norwegian mathematician Thoralf Skolem (1887–1963) made extensive contributions to the development of logic, maintaining a steady output of important papers from 1920 until his death. Skolem's first major result was an extension of the above-mentioned theorem of Löwenheim that if a formula of the first-order functional calculus (with identity) is valid in a denumerably infinite domain, it is valid in every nonempty domain and that, equivalently, if such a formula is satisfiable at all, then it is satisfiable in a domain comprising at most a denumerable infinity of elements. In 1920, Skolem generalized this theorem to the case of classes (possibly infinite) of formulas, establishing that if a class of formulas is simultaneously satisfiable, then it is satisfiable in a denumerably infinite domain. Skolem's proof makes use of the axiom of choice and the Skolem normal form of a formula—a type of prenex normal form in which no universal quantifier precedes an existential quantifier—but both these devices were subsequently dropped, and a more constructive version of the proof was given in 1928, a version which led to the developments of Herbrand and to Gödel's completeness proof.

Skolem was led by his work on Löwenheim's theorem to consider set-theoretic concepts as in a certain sense relative. This view derives from the fact that suitable axiomatizations of set theory can be written in the notation of first-order logic, the only symbol foreign to this logic—the epsilon of membership—being replaced by a dyadic predicate letter. The result is a set of formulas which, if consistent, has by Löwenheim's theorem an interpretation within a denumerably infinite domain. At the same time, within the system of set theory we can establish, by Cantor's theorem, the existence of nondenumerably infinite sets. This apparent conflict between the magnitude of the sets in the axiomatic theory and the more limited domain in which it is modeled is known as the Löwenheim–Skolem paradox. Skolem's way out of this paradox was to suggest that the distinction between denumerable and nondenumerable be taken as relative to an axiom system, a set which is nondenumerable in a given axiomatization perhaps being denumerable in another.

The possibility of an enumeration not available within the original axiom system has led to the description of Löwenheim's theorem as the first of the modern incompleteness theorems, but Skolem's resolution of his paradox does not represent the only possibility. In the first place, it is not clear how the required enumeration could be devised even outside the system in question. To take an analogous case, Cantor's theorem shows that the members of a set containing three elements cannot be paired off with the members of the power set of this set. Since the power set in this case contains eight elements, Cantor's result is in no way surprising, but there is no inclination to say that further mappings might be devised which would yield a one-to-one correspondence between the three-member set and the eight-member set. In the second place, Löwenheim's theorem does not require us to suppose that the axiomatized theory guarantees an enumeration of the sets, since the reinterpretation of the original symbolism with respect to a denumerable domain results in a revision of the propositions implying or asserting the existence of a nondenumerable infinity of sets. By hypothesis, such propositions go over into propositions which hold in the denumerable model, but although their truth is preserved, their original meaning is altered: they could not without contradiction assert the nondenumerability of the new model.

The set-theoretic relativism that Skolem inferred from the Löwenheim–Skolem theorem led him to doubt whether mathematical concepts could be completely characterized axiomatically, and in 1934 he published a result confirming these doubts by demonstrating that no categorical system of postulates for the natural numbers can be expressed in the notation of quantification theory. Any attempt to give a unique characterization of the natural numbers by means of propositions expressed in this notation is bound to fail, even if a denumerable infinity of such propositions is allowed, since there will always be other systems of entities conforming to the structure so defined. Although this result was uncongenial to those who had hoped to delineate the numbers from a formalist standpoint, the nonstandard models which are yielded by such proofs have become increasingly important, and their application to such topics as independence proofs and mathematical analysis promises to be fruitful.

Skolem also made important contributions to the theory of recursive functions. His work in this field dates from a pioneering paper of 1923, in which he sought to develop arithmetic in a logic-free calculus. Essentially this meant the elimination of quantifiers, an elimination that Skolem proposed to effect by the extensive use of recursive definitions. For instance, instead of defining "a < b " as "(∃x )(a + x = b )," we can avoid the use of the existential quantifier by means of the joint stipulation of (i ) −(a < 1) and (ii ) a < (b + 1) ↔ (a < b ) ∨ (a = b ). In this and subsequent papers Skolem advanced such reductions as part of a finitistic program for securing the basis of arithmetic.

Also important are Skolem's contributions to set theory. The Zermelo–Fraenkel system is commonly presented with his modifications, and in his last years he took up the study of set-theoretic contradictions from the standpoint of systems of many-valued logic.

See also Cantor, Georg; Many-Valued Logics; Set Theory.

Bede Rundle (1967)