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

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?

-

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 http://www.math.psu.edu/simpson/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).

-
My apologies if, in replying to a comment, I quite accidentlly deleted it! – Peter Smith Jan 26 '13 at 15:35
No no, I deleted it myself because it was wrong.... – goblin Jan 26 '13 at 15:50
@user18921 Phew! – Peter Smith Jan 26 '13 at 15:53
Peter, you can't delete other people's comment. Unless you're a moderator, of course. – Asaf Karagila Jan 26 '13 at 16:41
"And of course, if it is provable in that weak system, it is provable in any stronger system: adding more sets to our universe can't falsify the theorem!" My issue with this phrasing is that some axioms of set theory actually do reduce the number of sets in the universe; or more precisely, they rule out certain universe having certain sets. For example: "there does not exist an inaccessible cardinal." So in my opinion, it would be better to say that: "adding more axioms to our system can't miraculously falsify the theorem" or some such. – goblin Jul 5 '14 at 10:16

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).

-
"If one assumes 𝖹𝖥 the completeness theorem is not provable." How does this square with the completeness theorem being provable in $\mathsf{WKL_0}$? – Peter Smith Jan 26 '13 at 15:39
@PeterSmith It seems to be a general phenomenon that restricting attention to things coded by natural numbers makes theorems provable without choice. I recall some posts by Simpson along those lines... – Zhen Lin Jan 26 '13 at 15:48
@Peter: If the language is countable then no choice is needed. But the language doesn't always have to be countable. – Asaf Karagila Jan 26 '13 at 15:50
@Peter Smith: the difference is that the result in ZF is for arbitrary theories (which may have arbitrary cardinality) while the result in WKL is for countable theories; your answer and Asaf's describe different manifestations of the completeness theorem. ZF does prove the completeness theorem for countable theories. And, of course, the main foundational interest is in countable theories such as PA and ZFC. The most common way to encounter an uncountable theory is as the elementary diagram of a model, which will already be complete. – Carl Mummert Jan 27 '13 at 13:29
@Martin: math.stackexchange.com/questions/785819/… (Both question and the answers include references.) – Asaf Karagila Jul 3 '14 at 5:52