4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Indeed ZFC is incomplete (if consistent). The Completeness Theorem does not assert that any particular theory is complete. It says that any sentence true in all models of a theory $T$ is provable from $T$. $\endgroup$ – André Nicolas Mar 25 '16 at 22:01
  • $\begingroup$ So basically the Completeness Theorem says that a theory is complete if and only if all its models have the same theory. $\endgroup$ – Captain Lama Mar 25 '16 at 22:10
  • $\begingroup$ It is more correct to say that natural numbers can be encoded as sets, and that peano's axioms can be established to hold for the encoding. $\endgroup$ – DanielV Mar 25 '16 at 22:20
  • $\begingroup$ Peano intended his induction axiom to be 2nd order, but the theory known today as Peano Arithmetic (PA) is a first order theory: the induction axiom is a schema of countably many axioms, one for each first-order formula. There is such a thing as 2nd order PA, but one always explicitly adds "2nd order" when talking about that. $\endgroup$ – BrianO Mar 25 '16 at 22:36
  • $\begingroup$ For first-order theories, the "completeness" of the Completeness Theorem is relative to the axioms and rules of the calculus, being "enough" to derive all logical consequences of the axioms. The "incompleteenss" of the Incompleteness Theorem is relative to the specific axioms of theories including a "certain amount" of arithmetic being "not enough" to derive all the sentences that are true in the standard (or intended) model of natural numbers. 1/2 $\endgroup$ – Mauro ALLEGRANZA Mar 26 '16 at 11:03
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ah, this is very intriguing. What would be examples of theories as in your second paragraph? $\endgroup$ – Andrés E. Caicedo Mar 26 '16 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.