Lindström's theorem

Lindström's theorem characterizes first-order logic as the strongest logic satisfying compactness and the downward Löwenheim–Skolem property, under suitable assumptions on abstract logics.

Connect

Compactness theorem: A logical system is compact when every finitely satisfiable set of sentences is satisfiable. One of the two properties that jointly restrict the strength of a logic.
Tarski–Vaught test: A criterion for determining whether a substructure is elementary by checking witnesses to existential formulas. It helps construct elementary substructures used in the downward part of the argument.
Per Lindström: A Swedish logician known for results characterizing first-order logic through model-theoretic properties. He established the theorem that bears his name.
Second-order logic: A logic that quantifies over relations, functions, or sets as well as individual elements. Its greater expressive power comes at the cost of first-order compactness under standard semantics.
Downward Löwenheim–Skolem theorem: A theorem stating that structures with infinite universes have elementary substructures of specified smaller infinite cardinalities. The other property in the characterization, limiting how strongly a logic can distinguish large structures.
Skolem hull: The smallest elementary substructure containing a specified set of elements, obtained by closing under witness functions. Small hulls make the downward Löwenheim–Skolem property concrete.
Model theory: The mathematical study of structures through the formal languages and theories that describe them. Lindström's theorem arose within model theory's study of logic and structures.
Infinitary logic: A family of logics allowing conjunctions, disjunctions, or quantifier strings of infinite length. Many infinitary extensions exceed first-order expressive power but lose compactness.
Abstract logic: A formal system of sentences and consequence relations described through general properties rather than a fixed syntax. Lindström's result compares first-order logic with broader candidate logics.
Hanfs number: A cardinal threshold associated with a logic, beyond which a sentence with arbitrarily large models has models in all larger cardinalities. Bounds on sentence spectra help expose stronger logics that violate the theorem's hypotheses.