Gödel Completeness theorem
I realized recently that I did not understand well the completeness theorem of Godel, and how it interacts with the incompleteness theorems.
What I understand now (and you will see my understanding is not consistent !)
Incompleteness means that, as long as I have some kind of arithmetic power (let's say multiplication) in my axioms, my theory is incomplete : there are (even FOL) formulae that can't be proved nor disproved.
Completeness means that for any First Order Logic (FOL) formula, if this formula is true in all the models of my theory, there is a proof of that formula in my theory.
So I take a theory (with potent arithmetic) where integers are the same in every model of the theory (axiom of infinity ?), and I look at the FOL formulas on those integers. I feel that there is a contradiction between 1. and 2., because my formulae "live" only in one model of $\mathbb N$ but there are some of them without proof.
As I feel confident with the incompleteness theorem, I think I misunderstand the completeness theorem.
I found that question but I don't understand the answer that says the theory is not complete but the logic used in the language is. Can someone elaborate ?
logic incompleteness
XoffXoff
What you have discovered there is a proof (by contradiction) of the fact that there is no consistent recursively axiomatized first-order theory "where integers are the same in every model of the theory".
Such a theory can't exist because, thanks to the incompleteness theorem, we can add either the Gödel sentence or its negation to the theory without getting an inconsistent theory out of it. Since the two different extended theories are both consistent and FOL is complete, both have models. And these models must also be models of the original theory (we've just been adding an axiom in each), but they must have different integers, because if they had the same integers, they would agree about whether the Gödel sentence is true or not.
In order to get a theory where the integers are always the same, you need to move to second-order logic. For example, the second-order Peano axioms (where instead of an infinity of induction axioms for different induction formulas you have a single one that quantifies over all predicates) guarantees that, when the standard semantics of second-order logic is used.
On the other hand, under standard semantics second-order logic is not complete.
hmakholm left over Monicahmakholm left over Monica
$\begingroup$ So if I understand your answer : Completeness theorem only applies to first-order theories ? And (shame on me) why the axiom of infinity in ZF is not first order ? $\endgroup$
– Xoff
$\begingroup$ @Xoff: The completeness theorem does not apply to theories at all! It tells you something about the rules of logic, independently of which theory you apply them to afterwards. All of the ZF axioms are first-order, including the axiom of infinity. The axiom of infinity does not (as you seem to believe) guarantee that the integers will be the same in every model. $\endgroup$
– hmakholm left over Monica
$\begingroup$ Ok, so I really did not understand the completeness theorem. And if I define integers as S(S(... S(0))), I'm not sure how I can have different models, but If you have some links about different models of such integers, it will be very interesting for me, as I only found articles about different models of integers in Peano (where integers are not forced to be some finite successor of 0). $\endgroup$
$\begingroup$ @Xoff: The usual meaning of "the integers" in the context of PA is "the entire domain of the model". In the context of ZF, "the integers" usually means "all elements of the smallest inductive set in the model" (or equivalently "all ordinals $\alpha$ such that there is no limit ordinal $\le\alpha$"). What you're speaking about here is usually called numerals; they are important but not first-class logical citizens. For example it is not possible to quantify over numerals and only numerals, and in set theory the numerals do not necessarily form a set (nor necessarily a class). $\endgroup$
$\begingroup$ Books: Peter Smith, who writes here, has a book out specifically about these matters. I haven't read it myself, but what I've seen of the author here suggests that the book is both technically solid and reasonably accessible. $\endgroup$
Not the answer you're looking for? Browse other questions tagged logic incompleteness or ask your own question.
Is Robinson Arithmetic complete and not-complete?
Relations between Gödel's theorems
Is a Gödel sentence logically valid?
Interaction of completeness and second incompleteness theorems
How does Gödel Completeness fail in second-order logic?
FOL and Gödel's Incompleteness Theorem 1
What is the effective axiomatization in Godel's incompleteness theorem?
The arithmetized completeness theorem
Is there any way to avoid Gödel incompleteness theorem?
Explanation about completeness and incompleteness theorems in logic
Incompleteness theorem: Peano arithmetic vs. standard model of arithmetic