About ZFC, peano's axioms, first order logic and completeness?

Question

I read somewhere that the Peano's axioms can be derived out of ZFC. But if that is the case ZFC would be incomplete right( by Godel's incompleteness theorem)? But since ZFC is in first order logic , it would mean from the completeness theorem that it is complete, right? But Peano's axioms are in second order logic, right (the axiom of induction)? So where am I wrong?

Answer 1

There seem to be two confusions going on: about Peano arithmetic, and about the completeness theorem.

---

Peano arithmetic

The important thing to keep in mind is that there are actually two things which could reasonably called "Peano arithmetic"!

• First-order Peano arithmetic ($PA$). This is what the name usually means these days, although this is historically not what Peano introduced. Here, the induction axiom is of course verboten; instead, there is an induction scheme: for each formula $\varphi$ in the language of arithmetic, we have the axiom $$\forall y([\varphi(0, y)\wedge\forall x(\varphi(x, y)\implies \varphi(x+1, y))]\implies\forall x(\varphi(x, y))).$$ (The $y$ here is just a parameter, and can be ignored at first reading.) PA, like ZFC, is incomplete.

• Second-order Peano arithmetic ($PA_2$). This is what Peano originally introduced. It is categorical, and Godel's theorem does not apply to it (since it isn't first-order).

ZFC does indeed contain $PA$, but not $PA_2$.

Note that a similar thing is going on in ZFC! There is a second-order version of ZFC, in which the schemes of separation and collection are replaced by second-order versions.

EDIT: Keeping track of what's first-order and what's not can get very confusing. Personal favorite: there's a theory called "second-order arithmetic," which . . . is a first-order theory! So you always want to pay attention to what kind of theory it is you're talking about.

---

Completeness theorem

The completeness theorem does not say that every first-order theory is complete; rather, it says that the rules of proof for first-order logic are complete, in the sense that if $T$ is any first-order theory, and $\varphi$ is a first-order sentence true in every model of $T$, then $\varphi$ is provable from $T$. This is very different from what we mean when we say a theory is complete: a theory is complete if for every $\varphi$ in its language, it either proves or disproves $\varphi$.

Answer 2

It is easy to get confused between the completeness and incompleteness theorems.

First, we can forget about PA for a moment. ZFC is an effective theory in first-order logic which is sufficiently strong for the incompleteness theorems to apply (this is much weaker than being able to interpret Peano Arithmetic). So ZFC is incomplete, and ZFC does not prove its own consistency, because of the incompleteness theorems.

Second, the completeness theorem does apply to ZFC. There are many models of ZFC, because ZFC is consistent, and a sentence in the language of set theory is provable in ZFC if and only if the sentence is true in every model of ZFC.

Third, ZFC does verify that the natural numbers satisfy the second-order Peano Axioms. But that just means that, inside each model of ZFC, that model believes that its natural numbers satisfy the Peano Axioms. Different models of ZFC have different sets of "natural numbers", along with different sets of "natural numbers". So, even though ZFC proves that there is only one model of the second-order Peano axioms (up to isomorphism), that only means that inside each model of ZFC there is only one model of the second-order Peano axioms from the point of view of that model of ZFC. Different models of ZFC can and do have genuinely different models of the second-order Peano axioms.