[Math] About ZFC, peano’s axioms, first order logic and completeness

first-order-logicpeano-axioms

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?

Best Answer

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

Related Question