MODERN LOGIC: FROM FREGE TO GÖDEL: LöWENHEIM

A number of significant results concerning the first-order functional or predicate calculus (with identity) date from a paper published in 1915 by Leopold Löwenheim (1878–1957), a mathematician of Schröder's school. In this paper, "Über Möglichkeiten im Relativkalkül" (Mathematische Annalen 76 [1915]: 447–470), Löwenheim showed how the problem of deciding the validity of formulas in this calculus reduces to the problem of determining the validity of formulas in which only two-place predicate letters occur. Since (from the point of view of decidability) such formulas are accordingly no less general than arbitrary formulas of the calculus, we know from a later result, by Alonzo Church, that the decision problem for this class is unsolvable. However, Löwenheim was able to provide a decision procedure for a more restricted class of formulas, those in which only one-place predicate letters occur. He also showed that no formula of this restricted class could be valid in every finite domain, yet not be valid in an infinite domain, and his most famous result, known as Löwenheim's theorem, states that any formula of the full calculus which is valid in a denumerable domain is valid in every nonempty domain.

Although it is not difficult to show that if a formula is valid in a given domain, it is valid in any smaller domain, we cannot in general claim that validity in a given domain establishes validity in a larger domain. But as Löwenheim recognized, a formula may be valid in every domain comprising only finitely many of the natural numbers, yet not be valid in the domain of all natural numbers. The significance of Löwenheim's result is thus that validity in a denumerable domain guarantees validity not simply in any smaller domain but in domains which, like that of the real numbers, are of even greater cardinality than the set of natural numbers.

Bede Rundle (1967)