Independence of FOL-validity

A sentence ϕ of a dialect of First Order Logic is FOL-valid if and only if ϕ is true in every non-empty model under every interpretation. By the Goedel Completeness Theorem, ϕ is valid if and only if ϕ is a theorem of FOL (i.e., has a proof from no axioms beyond any axioms of FOL). (Note: This does not use the Axiom of Choice since we are dealing with a single sentence.)

Here is a meta-logic fact that I think is not as widely known as it should be.

Proposition: Let T be any consistent recursive theory extending Zermelo-Fraenkel set theory. Then there is a sentence ϕ of a dialect of First Order Logic such that according to some models of T, ϕ is FOL-valid (and hence a theorem of FOL) and according to other models of T, ϕ is not FOL-valid (and hence not a theorem of FOL).

Note: The claim that ϕ is FOL-valid according to a model M is shorthand for the claim that a certain complex arithmetical claim involving the Goedel encoding of ϕ is true according to M.

The Proposition is yet another nail in the coffins of formalism and positivism. It tells us that the mere notion of FOL-theoremhood has Platonic commitments, in that it is only relative to a fixed family of universes of sets (or at least a fixed model of the natural numbers or a fixed non-recursive axiomatization) does it make unambiguous sense to predicate FOL-theoremhood and its lack. Likewise, the very notion of valid consequence, even of a finite axiom set, carries such Platonic commitments.

Proof of Proposition: Let G be a Rosser-tweaked Goedel sentence for T with G being Σ₁ (cf. remarks in Section 51.3 here). Then G is independent of T. In ZF, and hence in T, we can prove that there is a Turing machine Q that halts if and only if G holds. (Just make Q iterate over all natural numbers, halting if the number witnesses the existential quantifier at the front of the Σ₁ sentence G.) But one can construct an FOL-sentence ϕ such that one can prove in ZF that ϕ is FOL-valid if and only if Q halts (one can do this for any Turing machine Q, not just the one above). Hence, one can prove in T that ϕ is FOL-valid if and only if I holds.

Thus, in T it is provable that ϕ is FOL-valid if and only if G holds. But T is a consistent theory (otherwise one could formalize in T the proof of its inconsistency). Since G is independent of T, it follows that the FOL-validity of ϕ is as well.