8

Edit: My question is specifically about Gödel's second incompleteness theorem. I get the significance of his first incompleteness theorem, which is of course completely amazing.

According to the Wikipedia entry on Gödel's second incompleteness theorem, "the broadly accepted natural language statement of the theorem is" as follows.

For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T includes a statement of its own consistency then T is inconsistent.

I accept that the above theorem is mathematically useful (say, for proving the inconsistency of a system). But why is it philosophically interesting? Assume it was false. Suppose there was a theory that was consistent, and also included the basic arithmetical truths that Gödel's theorem speaks of, and could also prove its own consistency. For concreteness, suppose ZFC could do this.

Well, so what? It's clearly circular.

Now I'm not doubting the mathematical usefulness of Gödel's theorem. But my question is, on a philosophical level, what's all the commotion about?

goblin GONE
  • 1,077
  • 6
  • 21
  • 1
    This belongs on philosophy.SE, voting to close as off topic. (I also flagged for moderator attention to have this migrated.) –  Feb 05 '13 at 13:47
  • Don't you think your question is off topic here, in particular since you say you're not questioning anything about mathematics but about philosophy...? –  Feb 05 '13 at 13:47
  • 1
    I've answered almost the same question before. –  Feb 05 '13 at 13:48
  • Migrating to philosophy. –  Feb 05 '13 at 14:58
  • So far my answer is the only one that points out an error in reasoning in the posted question. – Michael Hardy Feb 05 '13 at 20:43
  • A spelling note: By one very reasonable standard, "Gödel" is the same spelling as "Goedel", and "Godel" is different, the latter of the two is not correct, and the former of the two, in either of the two forms, is correct. – Michael Hardy Feb 06 '13 at 03:50

6 Answers6

10

You observe, correctly, that just because a formal system S "asserts" its own consistency — by means of a proof which, in a meta-language M, is isomorphic to a proof of consistency of S — does not mean that you should therefore trust S to be consistent. Any inconsistent system which is rich enough to admit Gödel numbering (or an equivalent technique), and which has an explosive implication (so that everything follows from a falsehood), is able to prove its own consistency; although it would be interesting to know whether or not it allows you to derive "consistency claims" without passing through blatant contradictions of the form A & ¬A to do so.

The big deal with Gödel's Second Incompleteness theorem is that the only formal systems which can "prove" their own consistency via encoding in Peano Arithmetic (or an equivalent system) — and which is also able to prove that addition and multiplication are total functions — are in fact inconsistent. Even if we knew from first principles that we could not rely on internally proven consistency claims, there is the ironic twist that such "proofs of consistency" are in fact proofs for precisely the opposite.

What this really means is that consistency is a bit of a chimeral property of a formal system to have. We are denied even the conceit of self-verifiability in totalizing formal systems. You can of course prove that a formal system S is consistent in another formal system M — but then why should you accept that M is consistent? Proving it so in another system M' is just pushing the problem away a further step. The consequence is that consistency of a formal system is an unavoidably negative property: a failure to be able to exhibit a contradiction, in which case you can never be sure if it is really consistent, or if you just haven't realized how to produce a contradiction in the system.

In the end, Gödel's Second Incompleteness theorem says that unless (like Gödel himself) you believe that humans somehow have a sort of occult-ish access to timeless Platonic truth, mathematics is subject to the same epistemological limitations as the natural sciences, in which formal systems play the role of theories and the discovery of inconsistencies play the role of falsification.

Niel de Beaudrap
  • 10,058
  • 4
  • 32
  • 52
  • @ArthurFischer: hi! That's actually quite intriguing. I will have to take a close look at Willard's self-verifying system (in which, for the folks at home, multiplication is not provably a total function) to grok what's going on there. – Niel de Beaudrap Feb 05 '13 at 16:09
  • My comment above was in reference to a comment correcting an earlier version of my post, which didn't account for the existence of a formal system as described in a post on MathOverflow about such systems of arithmetic. Gödel's Second Incompleteness theorem relies on certain properties of arithmetic which --- if a formal system cannot prove them --- is ipso facto exempt from Gödel's theorem. Of course, if the system is sufficiently different from Peano Arithmetic, it's not clear what the long-range implications are. – Niel de Beaudrap Feb 05 '13 at 16:18
  • "In the end, Gödel's Second Incompleteness theorem says that... mathematics is subject to the same epistemological limitations as the natural sciences, in which formal systems play the role of theories and the discovery of inconsistencies play the role of falsification." I certainly agree with the conclusion, but how does Godel's second incompleteness theorem imply it? It seems to me the very nature of the axiomatic method implies it. You start with some assumptions, and use those assumptions to prove the consistency of other systems of assumptions. But if you're original assumptions were..... – goblin GONE Feb 05 '13 at 21:50
  • ...inconsistent, then your precious proof ultimately amounted to nothing. – goblin GONE Feb 05 '13 at 21:51
  • 2
    @user18921: indeed. Of course, people felt differently, perhaps because they thought that perhaps one could obtain very simple systems of axioms which were "manifestly" (i.e. could be trusted to be) consistent, and that one could then prove the consistency of other systems using it. This is a charicature of Hilbert's programme, of course. Gödel proved that you can't hope to do such a bootstrapping proof of consistency, from something which is simpler: any such attempt will fail. And so positivism, which is the most prevalent social attitude to mathematics, is refuted. – Niel de Beaudrap Feb 06 '13 at 00:37
  • Niel, you write: "Gödel proved that you can't hope to do such a bootstrapping proof of consistency, from something which is simpler: any such attempt will fail." Well sometimes you can. You assume system A is consistent, and use this prove B is consistent. If it's possible to succeed, then (by definition) system A has greater (or equal) consistency strength than system B. If you can do converse - start with the assumption of B's consistency, and then prove A's consistency - we say that A and B are equiconsistent... – goblin GONE Feb 06 '13 at 02:27
  • ...Now there's a very boring system of maximum consistency strength. Namely, add the statement "0 does not equal 0" to Peano Arithmetic. Call this new system PA. Then the statment "For all systems B, if PA is consistent, then so too is B" is vacuously true. Okay so maximum consistency strength is a pretty boring idea.... – goblin GONE Feb 06 '13 at 02:28
  • ...So how about, maximum consistency strength with the restriction that you don't go so far that the resulting system is inconsistent? A theory with this level of strength would be able to found all of mathematics. However, Godel's FIRST incompleteness theorem tells us no such system can exist. Okay.... so where do the SECOND incompleteness theorem come in? – goblin GONE Feb 06 '13 at 02:29
  • @user18921: Surely if you could see that your axioms were inconsistent to begin with you wouldn't embark on attempting anything in said system? The point of proof is that you have an agreed upon system of axioms and agreed means of justifying the steps in a proof. If that agreement isn't there to begin with then all bets are off. Unless you're capable of seeing directly that a system of axioms is inconsistent, then surely the inconsistency demands a proof? – Mozibur Ullah Feb 06 '13 at 05:01
  • @user18921: consider where the notion of "consistency strength" comes from. Gödel's 2nd shows that A having consistency strength enough to support B is a strict order, i.e. irreflexive and antisymmetric. And as we have now both observed, there is no way to simply find a consistent formal system of maximal strength; that's where the circularity of assumption comes in. We know that to establish PA (and systems of increasing consistency strength), one tends to posit more elaborate objects; modulo a definition of "elaborate", Gödel's 2nd shows that this is unavoidable. – Niel de Beaudrap Feb 06 '13 at 08:43
  • @NieldeBeaudrap I assume you mean, "A strict order i.e. irreflexive and transitive." – goblin GONE Feb 06 '13 at 08:59
  • @NieldeBeaudrap In any event, I don't think it is strict. The definition of "A is stronger than B" is "Con(A) implies Con(B)", where this statement needs to be proved in a background theory, which usually involves the Peano Axioms or similar. (I only just learned this). So therefore it should be non-strict. – goblin GONE Feb 06 '13 at 09:04
  • @user18921: I do mean antisymmetric; transitivity I took for granted, but I wanted to emphasize the antisymmetry. If you want it to be reflexive, in the sense of "Con(A) implies Con(B)", then you have to give up the statement that a system of stronger consistency strength allows you to prove consistency. This "weakly stronger" relation fails to capture what is necessary for A to actually have a proof that B is consistent. Once again, Gödel's 2nd shows that if B is actually consistent, then A must be strictly stronger. – Niel de Beaudrap Feb 06 '13 at 09:40
  • In that case, my definitions are off. What's the standard definition of "stronger"? – goblin GONE Feb 06 '13 at 09:41
  • @user18921: I think I've been expressing myself poorly. Yours is the correct notion of "consistency strength"; but with Gödel's Second Incompleteness theorem, we're trying to establish more than just a hierarchy of strength of consistency — we're considering a hierarchy of establishability, wherein A can actually prove the consistency of B, which is a coarser relation. (I should not have used 'consistency strength' to refer to this term, but unfortunately, as I am not actually a logician, I do not know what the standard terminology is). – Niel de Beaudrap Feb 06 '13 at 09:52
  • Yeah neither am I. It's all very subtle - there's a huge difference between "Con(A) implies Con(B)," on the one hand, and "A proves Con(B)," on the other. And the whole time we have to keep in mind the background theory..... Sigh. – goblin GONE Feb 06 '13 at 09:55
  • Anyway, I think "A proves Con(B)" is what you mean by "A establishes B." And you're saying if A is sufficiently strong, then establishment becomes irreflexive, by Goedel's second theorem. – goblin GONE Feb 06 '13 at 09:56
  • This is a good answer, but the descriptor “occultish” is a bit odd. If anything, this access to truth seems like the opposite of occult! That is, under that view, these things (e.g. the consistency of PA, arising from our mental picture of the natural numbers) are directly accessible to the intuition, even for a child or someone lacking formal training in mathematics. If anything, “manifest” or “perspicuous” would seem to be a better descriptor. – user76284 Apr 13 '20 at 23:44
  • @user76284: To a hypothetical psychic, their ability to read the minds of others or to see the future might also seem like a direct sensing. The issue is that it is not direct for anyone other than the psychic, that this 'direct sense' is of a domain inaccessible to others. So yes: I do mean 'occult', because I believe that this is the nature of claims of mathematical Platonism (particularly as the sense of it obviously must be cultivated from the tenderest of ages). – Niel de Beaudrap Apr 14 '20 at 07:18
  • @NieldeBeaudrap I don't think you understood my point. The average child or layperson doesn't believe they have psychic powers, which are inaccessible to others. My point is that the opposite is true for mathematical intuition: Everyone has it, and sometimes uses it without being explicitly aware of it. "Inaccessible to others" is precisely the opposite of what's going on here! Perhaps a closer analogue might be the "intuition" that there's an external world, or something like that. – user76284 Apr 14 '20 at 07:33
  • ...and, following that example, I'd hardly call realism an "occult" notion. That's stretching the meaning of the word "occult" well past its breaking point. Furthermore, you say "it [the psychic thing] is not direct for anyone other than the psychic". Well, if you've ever teached mathematics to a student (and seen the "aha!" on their faces), or talked with other colleagues about a particular mathematical problem or concept, you'll see that's a complete 180 to what that is like :) – user76284 Apr 14 '20 at 07:37
  • 1
    @NieldeBeaudrap In short, that something is mysterious—say, that there is anything at all—does not mean it is "occult". Far from it. – user76284 Apr 14 '20 at 07:52
  • @user76284: The average person has a mathematical intuition which our society strains to cultivate in them from an early age. It may not be extremely difficult to teach children to count to 10, but any responsible parent does their best to encourage it, and it comes with missteps in practise. That basic, 'average' level of skill is not extremely difficult to inculcate, but it comes obviously less naturally than general language, which also sees quite a bit of variation in facility. Is that what we expect out of a sense such as vision or hearing? – Niel de Beaudrap Apr 14 '20 at 08:52
  • We brook no negotiation in what mathematics is like, because it is an extremely powerful tool. The utility of that tool is, at best, independent of the existence of a Platonic realm; it is because it is usable in practise (a fact which is consistent with but not dependent on the existence of a platonic realm) to the point where an inability to do at least workmanlike use of it is a severe handicap in society. And so we form the impression of mathematics as an independent thing: the so-called Platonic realm is our mental model of the abstract system, as we might speak of "U.S. Law". – Niel de Beaudrap Apr 14 '20 at 08:55
  • Meanwhile, this 'average' ability does not allow the 'average person' to immediately and clearly perceive many things that mathematicians consider obvious --- obvious, because we have drummed it into our heads nearly as thoroughly as the average person has drummed the number 3 into theirs. This has the hallmarks of the study of something obscure. To the extent that it is worth a name, i.e. beyond being able to perform one-to-one correspondence up to 1000 and shortcuts allied to this goal, access to the "Platonic realm" is in fact a cultivated skill in seeing hidden patterns, i.e., the occult. – Niel de Beaudrap Apr 14 '20 at 09:01
10

The other answers miss something important. The real impact of the Second Theorem isn't in the limitations it places on a 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 the consistency of a richer theory T+ which extends T (since proving the richer theory is consistent, proves a cut-down part of it is consistent). Hence the fact that an arithmetic theory like PA can't prove its own consistency means 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 very 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. (For a great deal more about this, see my Gödel book!)

Peter Smith
  • 1,090
  • 6
  • 7
  • see my comments under Niel de Beaudrap's answer. EDIT: If you're interesed, of course. – goblin GONE Feb 06 '13 at 02:31
  • On second thoughts, don't worry about my other comments. Tell me, is the following what you mean: suppose I wish to prove that ConA -> ConB in a metatheory. A simple approach would be to prove (in the language of A) a suitable interpretation of the statement ConB. What you're saying is that if A is sufficiently rich that Godel's second inconsistency theorem applies, then this simple approach cannot work. EDIT: So basically, we can still try to prove ConA -> ConB in the metatheory, but the aforementioned simple approach won't do it. – goblin GONE Feb 06 '13 at 04:45
  • I cannot edit the above comment, but it should read "Suppose I wish to prove that ConA -> ConB in a metatheory, where B is richer theory than A." – goblin GONE Feb 06 '13 at 05:03
  • @user18921 The point I take from Peter's post is that the significance of the second incompleteness theorem is that it puts a sort of upper bound on the strength of theories if they are to prove their own consistency. In particular, it shows us that a very weak theory capable of formulating a theory as weak as PA can't prove its own consistency. So, since any stronger theory would contain the necessary materials to perform the needed arithmetization of syntax (Godel Numbering) it would also fall victim to Godel's theorem and thus would be unable to establish its consistency. – Dennis Feb 06 '13 at 18:32
  • @user18921 The reference to Hibert's Programme is about Hilbert's attempts to found all of mathematics upon finitary mathematics. You can read about it at the SEP.

    Section 4 should be of special interest to you as it discusses the implications of incompleteness for the Program. Apparently there is controversy over which of the two theorems dealt the death-blow to Hilbert's Program.

     – Dennis Feb 06 '13 at 18:39
  • @Dennis yes i understand that it puts an upper bound on theories that can prove their own consistency. My question is, why is this so important? – goblin GONE Feb 06 '13 at 23:22
  • @user18921 Well, it strikes a blow against certain foundational approaches to mathematics--- like Hilbert's Program. If you're in the business of grounding the upper reaches of mathematics in the "more secure" then you are gonna have to make due with a seriously austere foundation. Absent some fairly awesome proof techniques, the foundations which could be deemed secure (i.e., proved consistent) would be too weak to provide a foundation for much mathematics of interest. So that is one reason. I feel like the corollary to be found in Tarkski's undefinability of truth work may be of interest. – Dennis Feb 07 '13 at 05:56
  • Well goedels first theorem implies that we can never finish founding mathematics. This is indeed a blow. Where does the second theorem fit in. – goblin GONE Feb 07 '13 at 08:25
3

An additional gloss to Peter Smiths answer that a weaker system cannot prove a stronger system consistency, is that a system incomparable to another may prove it consistent.

For example, in Gentzen's proof of the consistency of PA (Peano Arithmatic) he uses PRA (Primitive Recursive Arithmatic) and quantifier free transinfinite induction. It is not stronger than first order arithmetic (it can't prove induction), nor is it weaker (it can prove consistency of PA which PA can't).

I know that after learning about Gödel's incompleteness theorem, it came as a surprise to me that there could be a proof of PA's consistency.

Mozibur Ullah
  • 47,073
  • 14
  • 93
  • 243
  • How are you defining incomparable? If you're saying that "A is incomparable to B" means "neither Con(A) implies Con(B), nor does Con(B) imply Con(A)," then I don't understand how theory A can prove the consistency of an incomparable theory B. – goblin GONE Feb 06 '13 at 10:00
  • @user18921: I don't understand the details of the proof - so I can't enlighten you as to exactly how Gentzen manages this. But I do know its accepted by the mathematical community, and I can also see that the claim of incomparability stands as I've indicated above. – Mozibur Ullah Feb 07 '13 at 00:51
0

It's not circular!

If the mere fact that one can prove consistency of a system within the system is cited as evidence that it's consistent, that is circular reasoning. But such a proof gives you more than that: you know the details of the specific proof. In particular, you know which of the axioms of the system it relies on. If you use the first three of the system's axioms to prove consistency of the whole system of 20 axioms (including those first three), and therefore conclude that the whole system is consistent because you were already confident of the consistency of the first three, then you are not reasoning circularly. But Gödels incompleteness result tells you that in certain kinds of cases, that cannot be done

Michael Hardy
  • 294
  • 2
  • 10
  • Michael, can you clarify a little? I sort of get the "vibe" of what you're saying, but the details aren't transparent to me. – goblin GONE Feb 06 '13 at 02:40
  • Say you have a set of 20 axioms and for some good reason you believe that the set of the first three of those 20 is consistent. If you then write a proof of consistency of the set of all 20, relying only on the first three in that proof, then that's a proof of the consistency of all 20 within the system whose consistency you're proving. And it's not circular. If that doesn't clarify what I'm saying, then probably you need to clarify your questions. – Michael Hardy Feb 06 '13 at 03:48
  • What language is the proof of consistency written in? The language of the 3 axioms, or a metalanguage? – goblin GONE Feb 06 '13 at 04:07
  • It's in the same language as the three axioms, not a metalanguage. Otherwise it wouldn't be within the system. – Michael Hardy Feb 06 '13 at 15:59
0

Here's what I wrote on circularity, but didn't post (I am really just agreeing with what Michael Hardy said in more detail.. this should be a comment but it's too long):

I think it's a really good point that proving a mathematical theory (like PA or ZFC) consistent using the theory itself is circular. If the theory did happen to be inconsistent, it could prove its own consistency! So the mere existence of a consistency proof doesn't tell you anything: The real value in a consistency proof is telling you how strong an induction principle (or how big an infinite ordinal) you need to show that there isn't a proof of false: For example we need $\omega^2$ for the simple typed lambda calculus (which corresponds to a very simple constructive propositional logic), $\epsilon_0$ for PA.

  • 2
    You're "really good point" is confused. If the mere fact that one can prove consistency of a system within the system is cited as evidence that it's consistent, that's circular reasoning. But such a proof gives you more than that: you know the details of the specific proof. In particular, you know which of the axioms of the system it relies on. If you use the first three of the system's axioms to prove consistency of the whole system of 20 axioms, and therefore conclude that the whole system is consistent because you were already confident of the consistency of the first three, then..... – Michael Hardy Feb 05 '13 at 20:39
  • 1
    ....you are not reasoning circularly. But Gödels incompleteness result tells you that in certain kinds of cases, that cannot be done. – Michael Hardy Feb 05 '13 at 20:40
  • @MichaelHardy, I don't understand your remark 'You're "really good point" is confused' at all. You just repeated back exactly what I said except you focus on "a subset of the axioms" rather than proof theoretic ordinals. As I already said we are in agreement, I only posted my text because I think people were confused about the meaning of your comment and downvoted you because of that. –  Feb 05 '13 at 20:43
  • 1
    Your first sentence says "proving a mathematical theory (like PA or ZFC) consistent using the theory itself is circular." That is at best unclear. It's not circular. Knowing only that there is such a proof, without knowing any of its details, and concluding consistency, would be circular. But "proving [it] consistent using the theory itself" doesn't mean that. You wouldn't know only that there is such a proof; you'd know specifically what the proof is. – Michael Hardy Feb 05 '13 at 20:46
  • @user58512 You're saying that if such a proof of the consistency of T existed within T, then we'd be able to conclude that, "If T is consistent, then it's proof theoretic ordinal is at least.... WHAT?" Can you clarify? – goblin GONE Feb 05 '13 at 21:40
  • I was not making any assertion about proof-theoretic ordinals. Say you have a set of 20 axioms and for some good reason you believe that the set of the first three of those 20 is consistent. If you then write a proof of consistency of the set of all 20, relying only on the first three in that proof, then that's a proof of the consistency of all 20 within the system whose consistency you're proving. And it's not circular. – Michael Hardy Feb 06 '13 at 03:47
0

Gödel showed that truth and provability don't necessarily coincide. In a certain sense, he also showed that not every statement is necessarily either meaningless or either true or false. Already Aristotle envisioned that this might be the case for statements about the future.

The question whether mathematics is consistent is interesting, but so is the question: "Are mathematical models fundamentally different from the real world around us, or is it possible to approximate by mathematical models the important aspects of the world around us which we want to investigate?"

Once we believed that the world around us is deterministic, and that mathematics itself is "even more" deterministic. We learned later that the world around us is not as deterministic as we thought, and Gödel's incompleteness theorems taught us that mathematics is also less deterministic than we expected.

I once asked myself: "How to model non-existence (or not-yet existence) mathematically?". If I recall correctly, I was thinking about questions of measurability at that time. However, the point remains that a consistent and finitistic mathematic would probably be too limited to reflect the infinite, unbounded and inconsistent real world sufficiently accurate.

Thomas Klimpel
  • 3,959
  • 22
  • 38
  • You write: "Gödel showed that truth and provability don't necessarily coincide." Firstly, this is slightly inaccurate. We always knew that the truth and provability of sentences don't necessarily coincide. For instance, if my system for talking about the natural numbers consists of only one axiom, which postules the existence of an element, well clearly not all that is true about the natural numbers can be proved in this system.... – goblin GONE Feb 06 '13 at 02:37
  • ...What Godel ACTUALLY showed is that, contrary to what we'd always hoped, truth and provability can't be made to coincide; no matter how many finitely many axioms we add, it's not enough. In fact, even if we allow for a semidecision procedure to specify our axioms, IT'S STILL NOT ENOUGH. Pretty amazing. However, that's Godel's FIRST incompleteness theorem. My question is, what's the significance of his SECOND? – goblin GONE Feb 06 '13 at 02:38
  • This does seem to be about Gödel's first incompleteness theorem rather than his second incompleteness theorem. The latter is what the question was about. – Michael Hardy Feb 06 '13 at 03:49
  • It's true that this answer isn't specifically about the SECOND incompleteness theorem. It tries to explain why incompleteness and undefinability theorems in general have implications for the philosophy of mathematics (especially for the relation between mathematics and the real world). While writing, I asked myself how much this answer is only concerned with finitistic mathematical systems (and implicit compactness properties), and whether the actual incompleteness theorems are really limited to the finitistic case. Also, the concept of a "real world" might have needed clarification. – Thomas Klimpel Feb 06 '13 at 07:39
  • @user18921 I can remove this answer, if you think it doesn't address your question. I agree that it doesn't even try to refer to the SECOND incompleteness theorem, but I think that it isn't limited to the first incompleteness theorem either. It just says that the incompleteness theorems are an important contribution to better understand the relationship between mathematical models and the "real world". – Thomas Klimpel Feb 06 '13 at 07:48
  • There's no need for removal - I rather enjoyed reading it. That being said, the question I'm interested in at the moment is very specific, and as we've agreed, isn't really addressed by your answer. But it's no big deal. – goblin GONE Feb 06 '13 at 08:53