The Löwenheim–Skolem theorem
ProvedFamousTheorems.lowenheim_skolemThe Löwenheim–Skolem theorem. Let be an infinite structure in a first-order language , and let be an infinite cardinal with . Then there is an -structure of cardinality exactly that is an elementary substructure or an elementary extension of .
This combines the downward and upward theorems. First-order logic cannot pin down the cardinality of an infinite structure: there are countable models of set theory (Skolem's paradox) and uncountable nonstandard models of arithmetic. It is a starting point of model theory and of Lindström's characterisation of first-order logic.
Formalization note. Mathlib's FirstOrder.Language.exists_elementaryEmbedding_card_eq. The structure N is bundled; cardinalities of L (number of symbols) and κ are compared after lifting to a common universe.
import Mathlib
namespace FamousTheorems
universe u v w w'
theorem lowenheim_skolem (L : FirstOrder.Language.{u, v}) (M : Type w') [L.Structure M] [Infinite M] (κ : Cardinal.{w})
(h1 : Cardinal.aleph0 ≤ κ) (h2 : Cardinal.lift.{w} L.card ≤ Cardinal.lift.{max u v} κ) :
∃ N : CategoryTheory.Bundled.{w} L.Structure,
(Nonempty (L.ElementaryEmbedding N M) ∨ Nonempty (L.ElementaryEmbedding M N)) ∧ Cardinal.mk N = κ := by sorry
end FamousTheorems