Linström's Theorem Department of Mathematics These lectures present Lindström's theorem, a seminal result in abstract model theory. Lindström's theorem characterizes first-order predicate logic a maximally expressive language that has the compactness property and the Löwenheim-Skolem property. Equivalently, the result shows that any attempt at increasing the expressive power of first-order logic in any way, for example by adding second-order quantifiers, cardinality quantifers, fixed point operators or infinitary connectives, must result in the loss of one or both of two classical theorems about first-order logic: the compactness theorem, or the Löwenheim-Skolem theorem. This result has both conceptual and practical importance. Conceptually, Lindström's theorem tells us something about what makes first-order logic special, what is essential about first-order logic: the compactness result and the Löwenheim-Skolem theorem are considered two of the most fundamental results in first-order model theory. Lindström's theorem shows that they are, in a sense, the fundamental properties of first-order logic: given some conditions on what counts as a ''logical system'', these properties single out first-order logic uniquely. On the practical side, there are good reasons to extend the expressive power of first-order logic: the inability of first-order logic to distinguish between infinite cardinalities leads to Skolem's paradox, i.e. although ZFC proves the existence of uncountable cardinals, its axioms are true (if consistent) in a countable universe. Also, the discovery of non-standard models arithmetic casts some doubt on whether first-order logic is suitable as a language for metamathematics. Lindström's theorem tells us something about our options here: it is not possible to remedy these issues without sacrificing either compactness or the Löwenheim-Skolem property. The main purpose of the lectures is to present the proof of Lindström's theorem, without presupposing familiarity with anything beyond a basic course in first-order predicate logic. The basic concepts of abstract model theory will be introduced, and the model theoretic concepts required for the proof (in particular the technique of ``back-and-forth'' systems, or Ehrenfeucht-Fraïsse games) will be introduced. We will explain the topological point of view on Lindström's theorem and how it leads to variants for logics without classical negation. If time permits, some additional Lindström-style characterization theorems will be presented: a characterization of the infinitary logic $\mathcal{L}_{\infty\omega}$ due to Barwise, and two Lindström theorems for modal logic due to de Rijke and van Benthem. |
Bibliography
Ebbinghaus, H.D.: Extended logics: the general framework. In Barwise, J. and S. Feferman (eds.), Model-theoretic logics. Perspectives in Mathematical Logic, Springer-Verlag (1985) Benthem, J. v.: A new modal Lindström theorem, Logica Universalis, 1 :125-138 (2007) Flum, J.: Characterizing logics. In Barwise, J. and S. Feferman (eds), Model-theoretic logics. Perspectives in Mathematical Logic, Springer-Verlag (1985) Lindström, P.: On extensions of elementary logic. Theoria 35:1-11 (1969) Poizat, B.: A course in model theory, Springer Verlag (2000) de Rijke, M.: A Lindström theorem for modal logic. In Ponse, A., de Rijke, M. and Y. Venema (eds.) Modal Logic and Process Algebra, pp. 217--230, CSLI Publications (1995) Caicedo, X.: Lindström's theorem for positive logics, a topological point of view, In Andrés Villaveces, Roman Kossak, Juha Kontinen & Åsa Hirvonen (eds.), Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics. De Gruyter. 73-90 (2015)
| ||||
