Questions: Downward Löwenheim-Skolem Theorem

Question 1

ZFC set theory proves that uncountable sets exist. By the Downward Löwenheim-Skolem theorem, ZFC has a countable model. A student says this is a contradiction: 'a countable model cannot contain uncountable sets.' What is the correct resolution?

• A. ZFC cannot actually prove uncountable sets exist within a countable model
• B. The countable model contains a set that appears uncountable from inside the model because no bijection to ω exists within the model itself
• C. The theorem only applies if ZFC is consistent, and ZFC might be inconsistent
• D. The model is only 'countable' in an informal sense; technically it contains uncountably many elements

Answer: (B)

This is Skolem's paradox, resolved by recognizing that 'uncountable' is model-relative. The model is countable when viewed from outside (an external bijection to ω exists), but the model cannot see that bijection — it does not exist as an element or function within the model. Inside the model, the real numbers appear uncountable because no internal bijection witnesses their equinumerosity with ω. 'Uncountable' always means 'no bijection to ω exists in this universe,' and the relevant universe depends on your vantage point.

Question 2

A logician wants to write a countable set of first-order axioms whose models are all and only uncountable structures. Can this be done?

• A. Yes — just add the axiom 'there exist uncountably many elements' in first-order syntax
• B. Yes — Cantor's diagonal argument can be transcribed into a finite set of first-order axioms
• C. No — the Downward Löwenheim-Skolem theorem guarantees any such theory with an infinite model also has a countable model
• D. No — but only because first-order logic has no quantifiers that range over sets

Answer: (C)

First-order logic cannot express 'there are uncountably many elements' as a first-order sentence — cardinality conditions of this kind lie beyond first-order expressibility. Downward LS makes this precise: any countable first-order theory that has any infinite model must also have a countable model. So you cannot rule out countable models using first-order axioms alone. This is a fundamental limitation of first-order logic: it cannot control the cardinality of its models from above.

Question 3

The Downward Löwenheim-Skolem theorem states that nearly every first-order theory has a countable model.

• T. True
• F. False

Answer: False

The theorem requires two conditions: the theory must be countable (finitely or countably many sentences), and it must have at least one infinite model. A theory satisfied only by finite structures need not have a countable infinite model. Also, an inconsistent theory has no models at all. The correct statement is: if a countable first-order theory has an infinite model, then it has a countable model. Finite models and theories with only finite models are not covered.

Question 4

The proof of Downward Löwenheim-Skolem constructs a countable elementary substructure by closing a countable seed set under Skolem functions — and the closure of a countable set under countably many functions is countable.

• T. True
• F. False

Answer: True

This is the core construction. For each existential formula φ(x, a₁,...,aₙ), a Skolem function picks a specific witnessing element. Starting from any countable seed (even a single element), closing under countably many Skolem functions adds at most countably many elements per step. A countable union of countable sets is countable. The result is an elementary substructure — it satisfies exactly the same first-order sentences as the original model — and it is provably countable.

Question 5

What does Skolem's paradox reveal about the nature of 'uncountability,' and how is the apparent contradiction resolved?

Model answer: Skolem's paradox reveals that uncountability is not an absolute property but is relative to a model. A set can be 'uncountable' within a model (no internal bijection to ω exists) yet be countable when viewed from outside (an external bijection exists). The contradiction dissolves because 'uncountable' means 'no bijection to ω in this universe,' and the relevant universe differs depending on whether you are inside or outside the model.

ZFC proves ℝ is uncountable, meaning the model satisfies the sentence 'there is no bijection from ℝ to ω.' In the countable model, this sentence is still true — the model contains no such bijection as an internal object. But externally, the entire domain of the model is countable, so a bijection exists outside the model. This shows that cardinality claims are always relative to a background set-theoretic universe, not absolute facts. The same lesson applies to power sets, measurability, and many other set-theoretic notions.