22
$\begingroup$

Given that the consistency of a system can be proven outside of the given formal system, Gödel says,

It must be noted that proposition XI... represents no contradiction to the formalities viewpoint of Hilbert....

Why do others disagree?

Who cares whether a system cannot prove its own consistency? Why would we expect such a thing?

Is it possible that a theory without multiplication, but with some other axiom or axioms (i.e., weaker in one sense but stronger in another) could prove P consistent and itself consistent?

$\endgroup$
  • 1
    $\begingroup$ Are you asking who cares if a theory is consistent, or are you taking as given that the consistency of mathematical theories is important? $\endgroup$ – MJD Feb 26 '15 at 15:10
  • 3
    $\begingroup$ "Given that the consistency of a system can be proven outside of the given formal system." This is your problem. The the proof of consistency of your theory must be from a stronger theory, but, if you are wondering whether a theory is consistent, shouldn't you be worried about using a stronger theory? $\endgroup$ – James Feb 26 '15 at 15:14
  • $\begingroup$ Who cares if a theory can prove itself consistent, if it can be proven using some other method? $\endgroup$ – MadScientist Feb 26 '15 at 15:16
  • 1
    $\begingroup$ You have to think about what a proof of consistency is: It is a claim that there is no sequence of sentences in your base language $L$, that satisfies certain conditions, and ends in $x \neq x$. So, to prove consistency, you need to be able to reason about the sentences in the language or be able to talk about things that have properties resembling sentences (e.g. Godel numbering). Thus, a proof of the consistency of $T$ from some $S$ requires that $S$ has the resources interpret the syntax of $T$. Edit: This is how the Godel proof goes, consistency proofs in set theory are more involved. $\endgroup$ – James Feb 26 '15 at 20:06
  • 1
    $\begingroup$ "finitary proof" is a philosophical notion, so, it depends on precisely what you mean. $\endgroup$ – James Feb 26 '15 at 22:16
12
$\begingroup$

Hilbert's program aimed at "solving" the foundational issues (form Cantor and Frege, to Russell and Brouwer) proving the consistency of the "main" mathematical theories, like arithmetic, real analysis and set theory.

In order to prove that, the program developed concepts and tools of metamathematics, i.e. the discipline based on mathematical logic able to study the mathematical theories as mathematical objcets themselves.

This metamathematical activity has to be "performed" into a "secure" mathematical theory: the "elementary" part of arithmetic.

This theory must supply the tools sufficient for the consistency proof of other theories.

Of course, this "gound-level" mathematical theory must be itself consistent.

Unfortunately, Gödel's Second Incompleteness Theorem shows that a formalized arithmetical theory having "enough resources" (this concept is made precise by the theorem) to be suitable for the metamatheatical aims is not able to prove its own consistency, and neither the consistency of "more powerful" theories like real analysis and set theory.


Regarding Gödel's comment after Th.XI :

I wish to note expressily that Theorem XI do not contradict Hilbert's formalistic viewpoint [emphasis added]. For this viewpoint presupposes only the existence of a consistency proof in which nothing but finitary means of proof is used, and it is conceivable that there exist finitary proofs that cannot be expressed in the formalism of $P$.

And this was exactly what happened with Gentzen's consistency proof.

Some comments are useful here :

  • Hilbert's concept of finitary is not precise: but it's hard to escape from the expectation that the "finitary part" of arithmetic must include $\mathsf{PA}$; thus, G's Th applies.

  • Gentzen's proof is hardly "finitistic".

  • the original aim of Hilbert's program was to "convince" intuitionstic mathematicians that axiomatized set theory was "secure"; if so, any "ostensive" consistency proof based on a model of, e.g. arithmetic, built up into set theory was clearly useless.


Added

Regarding your added question, you can see (in general) :

In particular, you can see the overview of Presburger's arithmetic for a (very weak) first-order theory of the natural numbers with addition, without multiplication.

This theory is complete and decidable; thus, it "eludes" G's First Th.

Unfortunately, without multiplication it has not enough resources to implement the arithmetization of syntax; thus, it is unable to "perform" the basic metamathematical tasks and so it cannot prove relevant metamathemetical properties, like consistency of a theory (and neither of itself).

Gentzen's consistency proof "eludes" in some way G's Second Th :

Gentzen showed that the consistency of first-order arithmetic is provable, over the base theory of primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal $ε_0$.

Gentzen's proof also highlights one commonly missed aspect of Gödel's second incompleteness theorem. It is sometimes claimed that the consistency of a theory can only be proved in a stronger theory. The theory obtained by adding quantifier-free transfinite induction to primitive recursive arithmetic proves the consistency of first-order arithmetic but is not stronger than first-order arithmetic.

For example, it does not prove ordinary mathematical induction for all formulae, while first-order arithmetic does (it has this as an axiom schema). The resulting theory is not weaker than first-order arithmetic either, since it can prove a number-theoretical fact - the consistency of first-order arithmetic - that first-order arithmetic cannot. The two theories are simply incomparable.

$\endgroup$
  • $\begingroup$ I was unaware of this. My only knowledge of the second incompleteness theorem is from godels paper. $\endgroup$ – MadScientist Feb 26 '15 at 16:23
  • $\begingroup$ @MadScientist - I know ... the link to Stanford's entry provides you with a very useful intro to the background of G's Th. $\endgroup$ – Mauro ALLEGRANZA Feb 26 '15 at 16:24
  • $\begingroup$ Thanks. I'm going to get back to this with proper responses. Currently dealing with a fussy baby. $\endgroup$ – MadScientist Feb 26 '15 at 16:30
31
$\begingroup$

You asked in a comment:

Who cares if a theory can prove itself consistent, if it can be proven using some other method?

Let us first observe that inconsistent theories are entirely worthless. You want to know if $X$ is true, and then you prove that it is a consequence of theory $T$, so you now go around believing $X$. If you later find that $T$ is inconsistent, then $T$ cannot lend any support whatever to $X$. You might as well be flipping coins to decide what theorems are true. $T$ is worthless; you will have to find some other reason to believe $X$.

So you would like to find some theory $T$ for which you have good reason to believe $T$ is consistent. One plausible-seeming method is to choose axioms that are as simple as possible and which seem intuitively true. But the crisis of set theory around 1905 shows that this method does not always work. The comprehension axiom of naïve set theory is as simple and intuitively plausible as anything, and it is false. The discovery that it was false precipitated the formalist programs of Hilbert and Whitehead & Russell, and was the direct motivation for Gödel's work.

So you might like a proof that theory $T$ is consistent. Unfortunately, Gödel's theorem shows that $T$ cannot do it and neither can any theory strictly weaker than $T$. So if you want to show that $T$ is not completely worthless, you need a theory, say $T'$, that is stronger in at least one aspect. So suppose you show that $T$ is consistent, using $T'$.

If $T'$ is chosen to be strictly stronger than $T$, so that $T'$ shows as much as $T$ does and also shows that $T$ is consistent, then now you are in a very stupid position. If you weren't sure that $T$ was consistent, $T'$ cannot help you, because if $T$ is inconsistent, then so is $T'$. So you didn't trust $T$, but you have even less reason to trust $T'$. Suppose Shady Joe offers to sell you the Empire State Building for $5. You are not sure, and suspect that Joe is trying to scam you. Joe insists that he is honest, and suggests his Uncle Louie as a character witness. So you go up to the state prison where Uncle Louie is serving a fifteen-year sentence for fraud, and, from his prison cell, Louie assures you that Shady Joe is offering you a fair deal.

But this is exactly the position we are in. We would like to prove things about numbers, say the twin prime conjecture. We have the Peano axioms, which we believe capture how numbers work. But how do we know that from these axioms there is not some proof, perhaps a very long one, that $4923 = 4925$? This would not show that $4923$ actually equals $4925$; it would only show that PA was broken. We would have to throw away PA and use something else instead, as we did with naïve set theory. If we knew that PA was consistent, we would know that there was no such proof. And there is a proof of the consistency of PA using ZF set theory! But this is like asking Uncle Louie if Shady Joe is telling the truth, because if PA is inconsistent, then so is ZFC; if PA was inconsistent, then ZFC would prove that PA was consistent anyway.

$\endgroup$
  • 1
    $\begingroup$ Is it completely impossible that a theory without multiplication, but with some other axiom or axioms (ie weaker in one sense but stronger in another) could prove it consistent and itself consistent. That is how I interpreted godel. $\endgroup$ – MadScientist Feb 26 '15 at 15:59
  • 8
    $\begingroup$ Dammit, so Shady Joe was scamming me all that time?! And to think I trusted Louie! >:( $\endgroup$ – Asaf Karagila Feb 26 '15 at 16:07
  • 8
    $\begingroup$ Dude, you've devoted your life to trusting Louie. $\endgroup$ – MJD Feb 26 '15 at 16:20
  • 2
    $\begingroup$ I don't know the answer, but it's not easy to see how a theory could be useful for proving things about mathematics if it can't even express the well-known claim that $2\times 2 = 4$. $\endgroup$ – MJD Feb 26 '15 at 16:23
  • 2
    $\begingroup$ @MadScientist I suppose if you believe that true and false are not a strict dichotomy, then it might make sense to have multiple theories that give opposing results. Of course, at that point, you've thrown the notion of consistency out the window. $\endgroup$ – jpmc26 Feb 26 '15 at 18:30
4
$\begingroup$

Based on your last comment:

"Who cares if a theory can prove itself consistent, if it can be proven using some other method? "

It's not that we can prove it using some other method, but we can prove it using some other (stronger) theory. But how can we prove that this stronger theory is consistent? (if this stronger theory itself is not consistent, it means that our proof does not amount to much as nobody assures as that it's result are indeed true)

So now we want to prove the consistency of this stronger theory. But we need another theory for that! A stronger one! And how do we prove the consistency of the latter?

You see where we are heading? You can make the exact same reasoning for ever, so proving the consistency of a theory using another one doesn't do much because then we can't prove the consistency of the latter, and we are doomed

$\endgroup$
  • $\begingroup$ Did Godel himself not appreciate this point when he wrote that it "represents no contradiction to the formalistic standpoint of hilbert. For this presupposes only the existence of a consistency proof effected by finite means and there might be finite proofs that are not in p. " isn't it possible that the consistency proof of p could be in a system that is weaker than p (in the sense that it doesn't include multiplication for example, but perhaps something else?) $\endgroup$ – MadScientist Feb 26 '15 at 15:30
  • $\begingroup$ @MadScientist If you can prove something with a system weaker that $p$, then you can prove it with $p$ itself - isn't that what "weaker" means? $\endgroup$ – MartianInvader Feb 27 '15 at 0:25

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.