2
$\begingroup$

My reference book is A Course on Mathematical Logic by S.M. Srivastava.

Not so long ago, MO linked me to a video of a conference by Voevodsky wherein he considered the possibility of arithmetic being inconsistent. Apparantly, there is no (known) proof of consistency for $\mathsf{PA}$ or for $\mathsf{ZF}$.

Yet, example 2.3.3 on page on page $20$ of said book claims $\mathbb{N}=\lbrace 0,1,2,\dots\rbrace$ (with the usual interpretations of $0,S,+,\times, \lt $) is a model for Peano Arithmetic, and Theorem 4.4.8 (Completeness theorem, second form) on page $63$ says "a theory $T$ is consistent iff it has a model".

Why is this not proof of the consistency of $\mathsf{PA}$? What am I misunderstanding here?

Adding to my confusion, on page $74$, Theorem 5.3.10 states that $\mathsf{PA}$ is consistent iff $\mathsf{ZF}-\mathsf{Axiom~of~Infinity}$ is consistent.

If the root of the problem is set theory, the pending question of the consistency of $\mathsf{ZF}$, how can any theory $T$ be given a model, i.e. a set with a collection of interpretations for constants, functions and relations?

  • 2
    In general, a model is used to prove that one theory is equiconsistent with another, meaning that if$A$is consistent, then B is. In the scenario Voevodsky is discussing, both PA and ZF would be inconsistent. The following are closely related to your question: http://mathoverflow.net/questions/40920/what-if-current-foundations-of-mathematics-are-inconsistent http://mathoverflow.net/questions/35746/inaccessible-cardinals-and-andrew-wiless-proof2011-08-07

3 Answers 3

8

Why is this not proof of the consistency of PA?

It is a proof of the consistency of PA. It is the same sort of proof that is used to show that the negation of the parallel postulate is consistent with the remainder of the axioms of Euclidean geometry, by constructing a model of non-Euclidean geometry.

What am I misunderstanding here?

Perhaps you heard that it is not possible to prove the consistency of PA. That is simply false; for example you can prove it directly from the axiom "PA is consistent". What is true is just that there is no proof of the consistency of PA within PA itself.

Apparantly, there is no (known) proof of consistency for PA or for ZF.

There are (at least) three proofs of the consistency of PA that are important:

  • The proof in ZFC, which proceeeds by just verifying that $\mathbb{N}$ is a model of PA.

  • The proof by Gentzen. Here consistency is proved in a much weaker theory than ZFC (but of course the theory is not included in PA).

  • The proof by Gödel using what is now called the Dialectica interpretation. This proof uses a completely different method than Gentzen's proof, but obtains the same result. It is also conducted in a weak system, but a different weak system than Gentzen's proof.

  • 0
    You could do the same thing in type theory (e.g. in second-order arithmetic for a countable theory). In this case the model would might still be a set, but it would be a set as formalized in some theory other than ZF. There are also very different types of models, e.g. Kripke models and topoi. But the key step in proving "having a model implies consistency" is just using the set of sentences that are true in the model to obtain a consistent extension of the starting theory. The rest of the structure of the model is vital for model theory but not needed just to prove consistency of the theory.2011-08-07
6

I’m using the community wiki mode because this is not an answer. This is just a collection of links. (Some of them had already be given in the comments.) Please feel free to add others.

Vladimir Voevodsky’s talk

MO questions

Ed Nelson’s webpage

FOM

Excerpts (from the correspondence):

HF: Apparently, you think it worthwhile to spend some of your time to prove the inconsistency of PA. Un my opinion, that result would be the greatest result of all time in mathematics by orders of magnitude. And that doesn't touch on how it would compare with results in science and general human intellectual activity.

HF: It would of course be useful if you would reassess or restate your position that "the consistency of PA is a legitimate open problem in mathematics" in light of our correspondence.

VV: So far I do not plan to reassess anything in my position.

  • 0
    @Carl: Thanks! If you see more links to add ...2011-08-07
4

The usual proofs of the Completeness Theorem are like proofs in any other branch of mathematics. They are rigorous, but not formal proofs in ZFC.

However, the proofs can be made formal, and ZFC is strong enough to carry it out. From a proof of consistency point of view, this is not particularly helpful, since it shifts the burden of consistency to ZFC, a stronger theory.

A better candidate for a consistency proof for Peano Arithmetic is the long-ago work of Gentzen. True, it involves transfinite induction up to $\varepsilon_0$, but it has a finitary character. Unfortunately, "finitary character" is a matter of opinion, not rigorous definition.

  • 1
    Just to add slightly on the topic, there are assertions which are stronger than ZFC can prove, and when added to the axioms can prove the consistency of ZFC. However we do not know if such ZFC+P would be consistent as well.2011-08-07