Mount Hood Reflected in Mirror Lake (Public Domain)
A reflection principle gives circumstances in which K⊧φ iff M⊧φ, where K⊆M. “As above, so below.”1 The absoluteness of Δ0 formulas could be called a reflection principle: if φ is Δ0, then the transitivity of K and M is all we need. Usually though people reserve the term for the downward Löwenheim-Skolem theorem and its descendents.
The original downward Löwenheim-Skolem was the first really deep theorem of first-order logic. It says that if M is a structure for a countable language ℒ and K0⊆M, K0 countable, then there is a K with K0⊆K⊆M, K also countable, with K “reflecting” M in this sense: for any formula φ(x̄) in ℒ and any ā in K,
K⊧φ(ā) ↔M⊧φ(ā)
We say K is an elementary substructure of M. Standard notation: K≼M.
The absoluteness of Δ0 formulas says that for a highly restricted class of formulas, truth is reflected, with very modest conditions on the pair K⊆M. The downward LS says that for any formula φ(x̄) and any M, we can find a K that “reflects” M. In a later post I will outline how reflection is used. Briefly, it compensates for failures of absoluteness.
Let’s quickly recap the proof of the downward Löwenheim-Skolem theorem. (The Logic notes give a fuller discussion.) K is a union of an ascending chain K0⊆K1⊆…. We obtain Kn+1 from Kn by adding “witnesses”: for every closed formula of the form
∃x φ(x,c̄), c̄∈Kn
if M⊧∃x φ(x,c̄), then we pick an element w∈M (the witness) for which M⊧φ(w,c̄), and add it. That is, Kn+1 is Kn plus all these witnesses. Note that we allow names of any elements of Kn to appear in the formula ∃x φ(x,c̄). This construction is not computable, of course, and assumes the axiom of choice. The countability of K is easy to verify.
To prove that K=⋃n Kn is an elementary substructure of M, we do the usual induction on formula complexity. This is a routine crank-turning, except for one case: formulas of the form ∃x φ(x,c̄) with c̄∈K. But even that is easy, because we must have c̄∈Kn for large enough n. Suppose M⊧∃x φ(x,c̄). Let w be the witness for this, so w∈Kn+1 and so w∈K. By inductive hypothesis, K⊧φ(w,c̄) if and only if M⊧φ(w,c̄). So K⊧∃x φ(x,c̄). The converse (if K⊧∃x φ(x,c̄) then M⊧∃x φ(x,c̄)) is trivial.
From Löwenheim-Skolem to Reflection
Let’s try to apply the Löwenheim-Skolem theorem to the universe V. Our “structure” is (V,∈). Problem: this is not a structure in the formal sense, since the domain is a proper class and not a set. So the Löwenheim-Skolem theorem doesn’t apply.
One can surmount this by invoking Axiom SM. This says that there is a set M such that (M,∈) is a transitive model of ZF. Axiom SM implies that ZF is consistent, and so ZF cannot prove it (by Gödel’s Second Incompleteness Theorem). Assuming SM, Löwenheim-Skolem then tells us that there is a countable model of ZF.
Should we believe SM? Cohen gives this justification:
The Löwenheim-Skolem theorem allows us to pass to countable submodels of a given model. Now, the “universe” does not form a set and so we cannot, in ZF, prove the existence of a countable submodel. However, informally we can repeat the proof of the theorem. We recall that the proof merely consisted of choosing successively sets which satisfied certain properties, if such a set existed. In ZF we can do this process finitely often. There is no reason to believe that in the real world this process cannot be done countably many times and thus yield finally a countable standard model for ZF. The only reason this cannot be done in ZF is simply that there is no property A(n,x) in ZF which expresses, for each n, the property of x which we wish to consider at the n-th stage.
The undefinability of truth is the rub. The proof we sketched relies on the notion of satisfaction. We could express Cohen’s A(n,x) formally, if we had a formula true(⌜φ⌝) expressing truth in (V,∈). But as we noted in the previous post, no such formula exists.
But ZF can prove more limited reflection principles. One is the Lévy-Montague reflection principle. This says that for any formula φ(x̄) and any Vα, there is a Vβ⊇Vα that “reflects the universe” with respect to φ. That is, for all c̄∈Vβ,
V⊧φ(c̄) ↔Vβ⊧φ(c̄)
You can adapt the proof outlined above to show this. Since Vα is not usually countable, you need to use transfinite induction. For each formula ∃x φ(x,c̄) with c̄∈Vα, if V satisfies it, then you will find a witness by ascending far enough in the cumulative hierarchy. Because the ordinals go on “forever”, this transfinite process eventually produces a Vα′ with all the witnesses we need. The remainder of the argument is pretty much the same. (See Drake (§3.6) for a proof without frantic handwaving.)
Another version says that there is a countable model (M,∈) reflecting all ZF formulas up to a given parsing depth. This follows from the existence of a ZF formula expressing truth in V up to a given parsing depth—see the previous post. As a special case, we can reflect any finite set of ZF formulas.
Minor variation: we can demand that M contain any countable set K. And if K is a transitive set, we can demand that M is also transitive. This last bit uses the Mostowski Collapsing Lemma of the next post.
The famous Skolem paradox
Consider the theorem “𝒫(ω) is uncountable”. The proof of this uses only a finite number of ZF axioms, so it has a countable model. What gives? Answer: in any countable model, 𝒫M(ω) possesses a 1–1 correspondence with ω, but the correspondence isn’t in the model. (Skolem’s paradox has many variations, all with similar resolutions.)
[1] A quote from the Emerald Tablet of Hermes Trismegistus, a alchemical sacred text.
Diagonal Argument 