Is the completeness theorem for first-order logic relative to one's choice of set theory?

Question

By the completeness theorem for first-order logic, every consistent theory has a model. However, to even make sense of the word "model," I believe we're assuming a set theory. So is there a set theory which yields a notion of "model" such that the completeness theorem fails?

Answer 1

The Gödel completeness theorem in the form familiar from basic logic texts says that every countable consistent set of first-order sentences (in a standard, countable language) has a model.

Now, this theorem can be proved in exceedingly weak set theories. In fact all you need to prove the theorem is to have available those sets of natural numbers whose membership is recursively decidable plus a weak version of König's Lemma that infinite binary trees have an infinite path. (And of course, if it is provable in that weak system, it is provable in any stronger system: adding more axioms to our theory can't make the theorem unprovable!)

More technically, the Completeness Theorem is provable in a weak subsystem of second-order arithmetic called $\mathsf{WKL_0}$. Details are in Stephen Simpson's encyclopaedic Subsystems of Second Arithmetic: you can freely download the first chapter which gives the headline news about such matters at https://www.personal.psu.edu/t20/sosoa/chapter1.pdf

So, failing to get the Completeness Theorem would have to mean using an extremely weak set theory (far weaker, even, than $\mathsf{ACA_0}$ which is the minimum required to reconstruct classical analysis).

Answer 2

If one assumes $\mathsf{ZF}$ the completeness theorem is not provable. Since the only difference from the "usual" set theory is the fact the axiom of choice is missing, there is no real difference in how we define a language, structure, and so on. This means that the notion of "model" is the same.

In fact assuming $\mathsf{ZF}$ the following theorems are equivalent:

1. The completeness theorem for first-order logic.
2. The compactness theorem for first-order logic.
3. Every filter can be extended to an ultrafilter.

Note that if $\mathsf{ZF}$ is consistent then $\mathsf{ZFC}$ is consistent, so we cannot prove the negation of the completeness theorem either. However it was proved that it is also consistent that the completeness theorem fails. In universe you can construct a counterexample (from an object whose existence is assured by additional axioms, of course).