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 ?
Thank you very much !
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.