0
$\begingroup$

As I understand it, Godel's Second Incompleteness Theorem states that given a theory $T$ that is any extension of Robinson Arithmetic, that if that theory is consistent then it cannot prove a given consistency statement $-$ say, $\sim (0=1)$, within the theory itself. That is: $\not \vdash_T \sim (0=1)$.

While I think I understand the utility of a system that we use to prove its own consistency, I do not understand why we care that much about this given that we already assume that $T$ is consistent in order to prove the 2nd Incompleteness Theorem to begin with. Also, if it's an inconsistent theory, and we are using classical-logic as our meta-theory, then it follows that every formula in the language of $T$ is provable. So either case, it seems to me trivial. I have read Torkel Franzen's book on the subject and he seems to address this issue on page 105.

It then seems to me that the 2nd-Incompleteness Theorem is in a sense philosophically trivial for we are already assuming the consistency of our axioms before hand therefore the consistency of the whole system. Any thoughts and/or clarifications on where I may have gone wrong is appreciated as I think I am missing something.

$\endgroup$
  • $\begingroup$ See Peano axioms : first axiom : $∀x(0 \ne S(x))$; thus, by Universal Instantiation : $0≠S(0)$, and so : $\mathsf {PA} \vdash \lnot 0=1$. See in Gödel's Incompleteness Theorems : Gödel's second incompleteness theorem : Assume $F$ is a consistent formalized system which contains elementary arithmetic. Then $F \nvdash \lnot Prov_F(⌈0=1⌉)$. $\endgroup$ – Mauro ALLEGRANZA Aug 3 '15 at 18:55
  • $\begingroup$ We have to take care of the details ... As shown : (1) $\mathsf {PA} \vdash ¬0=1$; with the "machinery" of arithmetization, we have also : (2) $\mathsf {PA} \vdash Prov_{\mathsf {PA}} (⌈¬0=1⌉)$. If $\mathsf {PA}$ is consistent, form (1) follows : (3) $\mathsf {PA} \nvdash 0=1$, but the "incompleteness phenomen" strikes again here, because : (4) $\mathsf {PA} \nvdash ¬Prov_{\mathsf {PA}} (⌈0=1⌉)$. $\endgroup$ – Mauro ALLEGRANZA Aug 3 '15 at 19:09
4
$\begingroup$

No, the theorem actually says that if you can formalize internally what it means "that a theory proves a statement" (in particular, you formalize internally the notion of inference rules and proofs and formulas and so on); then whenever $T$ is such theory which is sufficiently strong, then $T$ does not prove the internalized sentence "$T$ does not prove a false sentence".

More specifically, if given a formula $\varphi(x)$ and you can say that $\varphi$ defines a set of Godel numbers of the sentences which make up $T$, then $T$ does not prove "There is no proof of a false statements from the theory whose Godel numbering is given by the set defined by $\varphi$.

It does not mean that $T$ itself does not prove $0\neq 1$. Peano as a whole does prove that $0\neq 1$. As do Robinson's axioms. What Peano does not prove is that the set of sentences which "should" be the codes for the axioms for Peano does not encode a proof of contradiction, and that's a whole other thing.

And the consequence of the incompleteness theorems is that there are other models of $\sf PA$, and whichever theory which is relevant here, is that in some models of $\sf PA$, you can find a code for a proof of a false statement. But the proof is not be given by a "standard" natural number (read: the interpretation of a closed term). It is encoded by a hyperfinite number (or trans-finite, although that's not a great term here), which might mean that the proof is "too long to be real" or that it uses inference rules which do not exist "outside" that model.

$\endgroup$
6
$\begingroup$

It then seems to me that the 2nd-Incompleteness Theorem is in a sense philosophically trivial for we are already assuming the consistency of our axioms before hand therefore the consistency of the whole system.

Suppose that there's a genuine issue about whether $T$ is consistent. Then even before we'd ever heard of Gödel's Second Theorem, we wouldn't have been convinced of its consistency by a derivation of $\mathsf{Con}_T$ inside $T$ (where $\mathsf{Con}_T$ codes up the the claim '$T$ can't prove $0 = 1$'). For we'd just note that if $T$ were in fact inconsistent, we'd be able to derive any $T$-sentence we like in the theory -- including a false statement of its own consistency!

The Second Theorem shows that we would indeed be right not to trust a theory's announcement of its own consistency. For (assuming $T$ includes enough arithmetic), if $T$ entails $\mathsf{Con}_T$, then the theory must in fact be inconsistent!

However, the real impact of the Second Theorem isn't in the limitations it places on a consistent theory's proving its own consistency. The key point is this. If a nice arithmetical theory $T$ can't even prove itself to be consistent, it certainly can't prove that a richer theory $T^+$ is consistent (since if the richer theory is consistent, then any cut-down part of it is consistent). Hence we can't use 'safe' reasoning of the kind we can encode in ordinary arithmetic to prove that other more 'risky' mathematical theories are in good shape. For example, we can't use unproblematic arithmetical reasoning to convince ourselves of the consistency of set theory (with its postulation of a universe of wildly infinite sets).

And that is a hugely interesting result, for it seems to sabotage what is called Hilbert's Programme, which is precisely the project of trying to defend the wilder reaches of infinitistic mathematics by giving consistency proofs which use only 'safe' methods. (That was an attractive programme. Theories like set theory may be about wildly infinitary worlds. But the point to emphasize that Hilbert and Bernays saw is that set theory itself involves finite proofs in a finitely characterised language, so we might hope to prove results about the theory, like consistency, using only finitary reasoning. Gödel saw that the relevant finitary reasoning can be treated as arithmetic reasoning after we'd coded up facts about the theory's sentences using numbers. But then, to repeat, since arithmetic, assuming it consistent, can't even prove its own consistency, it can't prove stronger theories consistent.)

You'll find lots more about this in the usual textbooks that cover Gödel's Theorems (including mine).

$\endgroup$
2
$\begingroup$

Your understanding is incorrect. $\lnot(0 = 1)$ is not a "consistency statement" and any sufficiently strong theory of arithmetic can prove it. However, in any sufficiently strong theory of arithmetic you can encode the notion of a provable formula, i.e., you can define a predicate $\mathsf{P}r$ such that $\mathsf{Pr}(x)$ is true iff $x$ encodes a provable formula. $\lnot\mathsf{Pr}(0=1)$ can then be viewed as a statement that the theory is consistent. The incompleteness theorems tells you that only an inconsistent theory can prove $\lnot\mathsf{Pr}{(0=1)}$.

$\endgroup$

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.