2
$\begingroup$

PA doesn't prove Con(PA) but ZFC does. That means the extra axiom of infinity is of tantamount importance in the proof. Not seen such a proof, think it would be interesting. Heard of it.

$\endgroup$
7
  • 7
    $\begingroup$ ZFC proves that the natural numbers (which exist by the axiom of infinity) are a model of PA, and therefore by soundness that PA is consistent? $\endgroup$ Dec 22, 2010 at 16:52
  • 4
    $\begingroup$ Is this a research-level question? $\endgroup$ Dec 22, 2010 at 18:23
  • 3
    $\begingroup$ Vote to close since this is too elementary a question for MO. $\endgroup$ Dec 22, 2010 at 18:36
  • $\begingroup$ Wikipedia's article en.wikipedia.org/wiki/Axiom_of_infinity has a good explanation of how ZF proves that there is a set $\omega$ and an operation $S$ obeying the Peano axioms. In other words, ZF proves that there is a model of PA. (continued...) $\endgroup$ Dec 23, 2010 at 13:45
  • $\begingroup$ This no doubt reveals my ignorance of set theory, but it seems to me to be a little tricky to finish from here. I would like a theorem of ZF saying "For any theory T, if T has a model then Con(T)". It's not clear to me that this claim can be expressed in ZF! Everytime I try, I wind up wanting a truth predicate planetmath.org/encyclopedia/… . (continued) $\endgroup$ Dec 23, 2010 at 13:53

2 Answers 2

8
$\begingroup$

Within ZFC you can formalize Tarski's definition of truth, then prove that the axioms of PA are all true and that the rules of inference preserve truth. This gives a formal proof of Con(PA).

This allows you to prove not just the consistency of PA, but the consistency of PA + Con(PA), or PA + Con(PA) + Con(PA+Con(PA)), etc. Nothing close to the full strength of ZFC is needed for any of this (though of course you need something beyond PA).

$\endgroup$
2
  • $\begingroup$ @Steven : Small typo in the first line: The second ZFC should be PA. $\endgroup$ Dec 22, 2010 at 17:04
  • $\begingroup$ Andres: Thanks. I went to edit this, but it looks like Terry Tao did it for me. $\endgroup$ Dec 22, 2010 at 20:01
1
$\begingroup$

You can also prove the consistency of PA with second order logic.

The key thing is that you need a higher order induction hypothesis. In first order logic + PA, the induction hypothesis are limited to first order expressions.

The strength of a logic is often determined by what you allow in the induction hypothesis.

$\endgroup$

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