Downward Löwenheim–Skolem
Every infinite structure in a countable first-order language has a countably infinite elementary substructure. You can even require it to contain any chosen countable collection of elements.
THE LÖWENHEIM–SKOLEM THEOREM
A smaller infinity.
The same truths.
Can you shrink a mathematical universe without changing what it says?
In first-order logic, the answer is surprisingly often yes.
01 / Keep the answers. Lose the points.
THE WITNESS WORKSHOPA VIEW INTO TWO UNIVERSES
ℝ The real numbersUNCOUNTABLE
↓ keep only the points you need ↓
A Your growing collection2 POINTS · FINITE
Two points are a start. Add a witness to answer your first request.
Every finite stage still has gaps and endpoints. No finite stage is the finished model.
THE COUNTING TRICK
Added in batches. Listed forever.
List each new batch after the last. Even after infinitely many rounds, every chosen point gets a place on a countable list.
ℵ₀
The limit is countably infinite.
Imagine continuing the full-round rule forever. Any two selected points eventually get a witness between them, and every selected point eventually gets a point on either side. The union A is a dense linear order without endpoints.
For the language containing only < (with equality), A is an elementary submodel of ℝ: all first-order formulas agree, even with parameters from A. This uses a special fact about dense linear orders called quantifier elimination. The finite picture above only illustrates the construction.
02 / Can a question tell them apart?
THE TRUTH LABTry the rationals ℚ and the reals ℝ: different sizes, the same first-order truths about order. The integers ℤ make a useful contrast.
03 / THE BIG IDEA
Logic can describe order.
It can’t fix infinity’s size.
A model is a universe of objects with interpretations for the symbols in a language. First-order quantifiers range over those objects; they don’t automatically range over every subset.
“Countably infinite” means its objects can be listed as first, second, third, and so on. The reals are too numerous for such a list.
Upward Löwenheim–Skolem
In a countable first-order language, a theory with an infinite model has models of every infinite cardinality. Its axioms cannot single out exactly one infinite size.
The countable-language assumption matters. “Same truths” always refers to a specified language.
Why does collecting witnesses work in general?
Start with a countable set of elements. For each existential formula with parameters from that set that is true in the large structure, choose one witness. Include the language’s constants and close under its functions too. In a countable language, there are only countably many such requests, so this still adds at most countably many elements.
New elements create new requests. Repeat countably many times and take the union. Every finite tuple in that union appeared at some stage, so every relevant existential request has a witness in the union. The Tarski–Vaught criterion then says that the union is elementary.
Our order workshop is a special, simpler example: filling gaps and extending both ends is enough because of the theory of dense linear orders. For other structures, those two kinds of requests alone would not suffice.
Wait. Can a countable model believe in uncountable sets?
Yes—if set theory has a model, it has a countable one. This is Skolem’s paradox. Change your viewpoint:
The model’s “uncountable” means no suitable bijection in the model exists. An external listing need not be an object in the model. There is no contradiction, and this does not make the actual real numbers countable.