Lindström's theorem - Misplaced Pages

(Redirected from Lindstrom's theorem) Theorem in mathematical logic

In mathematical logic, Lindström's theorem (named after Swedish logician Per Lindström, who published it in 1969) states that first-order logic is the strongest logic (satisfying certain conditions, e.g. closure under classical negation) having both the (countable) compactness property and the (downward) Löwenheim–Skolem property.

Lindström's theorem is perhaps the best known result of what later became known as abstract model theory, the basic notion of which is an abstract logic; the more general notion of an institution was later introduced, which advances from a set-theoretical notion of model to a category-theoretical one. Lindström had previously obtained a similar result in studying first-order logics extended with Lindström quantifiers.

Lindström's theorem has been extended to various other systems of logic, in particular modal logics by Johan van Benthem and Sebastian Enqvist.

Notes

In the sense of Heinz-Dieter Ebbinghaus Extended logics: the general framework in K. J. Barwise and S. Feferman, editors, Model-theoretic logics, 1985 ISBN 0-387-90936-2 page 43
A companion to philosophical logic by Dale Jacquette 2005 ISBN 1-4051-4575-7 page 329
Chen Chung Chang; H. Jerome Keisler (1990). Model theory. Elsevier. p. 127. ISBN 978-0-444-88054-3.
Jean-Yves Béziau (2005). Logica universalis: towards a general theory of logic. Birkhäuser. p. 20. ISBN 978-3-7643-7259-0.
Dov M. Gabbay, ed. (1994). What is a logical system?. Clarendon Press. p. 380. ISBN 978-0-19-853859-2.
Jouko Väänänen, Lindström's Theorem

References

Per Lindström, "On Extensions of Elementary Logic", Theoria 35, 1969, 1–11. doi:10.1111/j.1755-2567.1969.tb00356.x
Johan van Benthem, "A New Modal Lindström Theorem", Logica Universalis 1, 2007, 125–128. doi:10.1007/s11787-006-0006-3
Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994), Mathematical Logic (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-94258-2
Sebastian Enqvist, "A General Lindström Theorem for Some Normal Modal Logics", Logica Universalis 7, 2013, 233–264. doi:10.1007/s11787-013-0078-9
Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1
Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, ISBN 0-19-852981-3, section 9.4

Mathematical logic

General

Theorems (list)
and paradoxes

Gödel's completeness and incompleteness theorems
Tarski's undefinability
Banach–Tarski paradox
Cantor's theorem, paradox and diagonal argument
Compactness
Halting problem
Lindström's
Löwenheim–Skolem
Russell's paradox

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types of sets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps and cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Set theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive