Movatterモバイル変換

Lindström's theorem

From Wikipedia, the free encyclopedia

Theorem in mathematical logic

Inmathematical logic,Lindström's theorem (named after Swedish logicianPer Lindström, who published it in 1969) states thatfirst-order logic is thestrongest logic^[1] (satisfying certain conditions, e.g.closure underclassical negation) having both the(countable) compactness property and the(downward) Löwenheim–Skolem property.^[2]

Lindström's theorem is perhaps the best known result of what later became known asabstract model theory,^[3] the basic notion of which is anabstract logic;^[4] the more general notion of aninstitution was later introduced, which advances from aset-theoretical notion of model to acategory-theoretical one.^[5] Lindström had previously obtained a similar result in studying first-order logics extended withLindström quantifiers.^[6]

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

Notes

[edit]

^In the sense ofHeinz-Dieter EbbinghausExtended logics: the general framework inK. J. Barwise andS. Feferman, editors,Model-theoretic logics, 1985ISBN 0-387-90936-2 page 43
^A companion to philosophical logic by Dale Jacquette 2005ISBN 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

[edit]

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

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 ofsets	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