Per Lindström, 1936-2009

From the ASL Newsletter, I just learned that Per Lindström died two months ago:

Per (Pelle) Lindström, the Swedish logician, died in Gothenburg, Sweden, on August 21, 2009, after a short period of illness. He was born on April 9, 1936, and spent most of his academic life at the Department of Philosophy, University of Gothenburg, where he was employed first as a lecturer (‘docent’) and, from 1991 until his retirement in 2001, as a Professor of Logic. Lindström is most famous for his work in model theory. In 1964 he made his first major contribution, the so-called Lindström’s test for model completeness (c.f., Chang & Keisler, Model Theory, 3rd ed., Thm. 3.5.9: if a countable set of first-order sentences has only infinite models, is categorical in some infinite power, and is such that the set of its models is closed under unions of chains, then it is model complete). In 1966 he proved the undefinability of well-order in Lω1ω (obtained independently and in more generality by Lopez-Escobar), an early example of the use of recursion theory to obtain model-theoretic results. The same year he also introduced the concept of a Lindström quantifier, which has now become standard in model theory, theoretical computer science, and formal semantics. The paper also contains a characterization of elementary logic among logics with generalized quantifiers, generalizing a result by Mostowski. The proof uses Lindström’s version of what is now known as Ehrenfeucht-Fraissé (EF) games, a concept he came up with independently. Another paper from 1966 (“On relations between structures”) gives a powerful and extremely general formulation of a preservation/interpolation theorem, again based on EF games. These results were published in the Swedish philosophical journal Theoria and written in an extremely terse style, which had the effect that they escaped the notice of most of the logic community for a while. It was his 1969 paper “On extensions of elementary logic” (also in Theoria), where he presented his famous characterizations of first-order logic—Lindström’s Theorem—in terms of properties such as compactness, completeness, and Löwenheim-Skolem properties, that was first recognized as a major contribution to logic. It laid the foundation of what has become known as abstract model theory (c.f., Barwise & Feferman (eds.), Model-Theoretic Logics, 1975). The proof was based on EF games and on a new proof of interpolation, following the line of argument in the papers on relations between structures and Lindström quantifiers. Several other characterizations of first-order logic followed in later papers. Beginning at the end of the 1970’s, Lindström turned his attention to the study of formal arithmetic and interpretability. He started a truly systematic investigation of this topic, which had been somewhat dormant since Feferman’s pioneering contributions in the late 1950’s. In doing so he invented novel technically advanced tools, for example, the so-called Lindström fixed point construction, a far-reaching application of Gödel’s diagonalization lemma to define arithmetical formulas with specific properties. His approach to interpretability was based on the study of related lattices, such as the lattice of interpretability types over a fixed extension of Peano Arithmetic (PA), or the lattices of Σn– and Πn -sentences over PA, for some fixed n, and he established many interesting structural properties of these. Other memorable results include the Lindström-Solovay theorem that the interpretability relation between sentences over PA is Π20-complete and the characterization of faithful interpretability over PA as a combination of Π1– and Σ1-conservativity. In the 1990’s, he also contributed to the area of provability logic: he gave a simplified proof of the de Jongh-Sambin fixed point theorem and characterized the bimodal logic of PA and PA augmented by the reflection rule: infer a sentence φ from ‘φ is provable’.

Pelle Lindström had an exceptionally clear and concise style in writing mathematical logic. His 1997 book, Aspects of Incompleteness, remains a perfect example: it provides a systematic introduction to his work in arithmetic and interpretability. The book is short but rich in material; it also contains some results one cannot find in journal publications, for example, his solution to one of the 102 problems formulated by Harvey Friedman.

Throughout his life, Pelle Lindström also took an active interest in philosophy. He participated in the debate following Roger Penrose’s new version of the argument that Gödel’s Incompleteness Theorems show that the human mind is not mechanical. He presented his own philosophy of mathematics, which he called ‘quasi-realism’, in a paper in The Monist in 2000. It is based on the idea that the ‘visualizable’ parts of mathematics are beyond doubt (and that classical logic holds for them). He counted as visualizable not only the ω-sequence of natural numbers but also arbitrary sets of numbers, the latter visualizable as branches in the infinite binary tree, whereas nothing similar can be said for sets of sets of numbers, for example. Moreover, he made numerous contributions over the years to the Swedish popular philosophy journal Filosofisk Tidskrift—one of these will be published posthumously—on subjects as diverse as the freedom of will, the mind-body problem, utilitarianism, and counterfactuals.

Pelle Lindström will be remembered by the logic community as a great logician, and by his family, friends and colleagues as a remarkable human being.

Leave a Reply

Your email address will not be published. Required fields are marked *