Löwenheim-Skolem Theorems

Mathematical Logic · Axiom Academy

LESSON The Löwenheim-Skolem Theorems Fundamental results revealing the expressive limitations of first-order logic: theories with infinite models cannot control the size of their models. 1. The Downward Löwenheim-Skolem Theorem If a first-order theory has an infinite model, then it has a countable model. This theorem says that no matter how large the models of your theory might be, there is always a "small" countable model. Even if you're trying to describe the real numbers (which are uncountable), first-order logic cannot force all models to be uncountable. Start with any infinite model of . Pick a countable subset of the domain and close it under all the functions in the signature using Skolem functions . This gives a countable substructure that satisfies the same sentences as the original model. More precisely: For each formula , add a function that "witnesses" the existential quantifier. The resulting structure, closed under these witnesses, is countable and elementarily equivalent to the original. 2. The Upward Löwenheim-Skolem Theorem If a first-order theory has an infinite model, then for every infinite cardinal , it has a model of cardinality . This is the "mirror image" of the downward theorem. Not only can we shrink models to countable size, we can also expand them arbitrarily. If there's any infinite model at all, there are models of every possible infinite size.

This is the written version of the interactive lesson above. See the full Mathematical Logic course.