# Some questions about mathematical content of Gödel's Completeness Theorem

I'm trying to refresh my knowledge about mathematical logic and I'm still unsatisfied with my insight of Gödel's Completeness Theorem.

In my only "raid" into MathOverflow, I posed a similar question about Gödel's Completeness Theorem.

Gödel's proof is equivalent to Konig's Lemma [Gödel's paper says "it follows by familiar arguments" and a footnote by the editor comments : "Apparently by Konig's infinity lemma"].

R.Smullyan, into his First-Order Logic (1968), in his exposition of Compactness Theorem for propositional logic, refers to Konig's Lemma (pag.31); but he also points out (pag.34) "that although we used both analytic tableaux and Konig's lemma in our proof of the compactness theorem, neither is really essential". This is not clear to me ...

Question. Is it possible to "avoid" $\mathsf {ZF}$ and formalize Gödel's original proof only into f-o $\mathsf {PA}$ ?

• Re q1, yes, but one has to be careful about how things are formulated. Perhaps it is better to work on $\mathsf{ACA}_0$, which is conservative over $\mathsf{PA}$ for arithmetic statements. This is discussed, for example, in Simpson's Subsystems of second order arithmetic. – Andrés E. Caicedo Jan 8 '14 at 20:21
• The the bounty on the question actually makes me more hesitant to answer it. I think it might be better to wait longer before placing bounties. – Carl Mummert Jan 11 '14 at 12:00
• I suspect that one reason you get few answers is that your questions are not phrased as just about the mathematics, they are thoroughly mixed with references to historical books and to older textbooks that people may not know. You also tend to ask several different questions at once. People prefer to be able to answer off the top of their head using their personal knowledge, rather than having to dig up old books. If you had just asked "Can Goedel's completeness theorem be formalized in Peano Arithmetic?" I suspect you would get an answer very quickly. – Carl Mummert Jan 11 '14 at 12:02
• @Carl Mummert . I appreciate very much your suggestions, but I'm really interested into understanding "old books": may I specify in the header of the question that I'm asking for help understanding e.g."Smullyan's proof of ..." ? – Mauro ALLEGRANZA Jan 11 '14 at 15:58
• @Mauro ALLEGRANZA Yes, you can certainly do that. But, in order to answer it, someone would have to be intimately familiar with the proof, or they would have to look up the book (if they even have it...) before they can answer. I think this may be a reason why you don't get too many answers to your questions. That is not to say that you can't ask them, but if you make them easier to answer by people who just know the mathematics, I think you will get more answers. – Carl Mummert Jan 11 '14 at 23:29

The completeness theorem is stated for arbitrary (even possibly uncountable) theories. If you restrict the theorem to only countable theories, then it is possible to prove the completeness theorem in weak subsystems of second-order arithmetic, such as $\mathsf{WKL}_0$, which has a consistency strength lower than PA.
• Two more questions : (i) in saying that "the challenge with proving the completeness theorem in PA itself is stating the completeness theorem in PA itself", you are meaning that is not possible (or, up to now, no one found how) to do it ? (ii) about "weak subsystems of second-order arithmetic, such as $WKL0$", I think that I can find all the details in Simpson's book Subsystems of Second Order Arithmetic; is it too difficult ? (taking into account that - as you have seen - that I'm not mastering very well axiomatic set theory). – Mauro ALLEGRANZA Jan 13 '14 at 13:32
• The problem is not that nobody knows how to state completeness in PA; it's that the language of PA is too impoverished to do it in any way that resembles what is usually called the completeness theorem ("a consistent first-order theory has a model"). On the other hand that can be stated in second-order arithmetic with only a mild restriction: any countable, consistent first-order theory has a countable model. As for Simpson's book, I am afraid it is quite advanced. Unfortunately there are no good undergraduate-level references on $\mathsf{WKL}_0$ that I know of. – Carl Mummert Jan 13 '14 at 14:01