3

Here's a couple of observations in rapid fire. Have any philosophers argued that these, and other, related observations mean that the Godel incompleteness theorems aren't as devastating as they're often made out to be?

Observation one. There's no 'incompleteness theorem for Turing-completeness'. In particular, there's plenty of Turing-complete computational languages.

Observation two. Define that the 'diagram of true arithmetic' is the set of all true sentences of the form

  • 3+2=5
  • not 3+2=6
  • etc.

More precisely, I guess I should be writing SSS(0)+SS(0)=SSSSS(0). Anyway, the point is, the diagram of true arithmetic is recursively ennumerable. Indeed, it is recursive, a more stringent condition. For example, we can decide whether 3+2=5 or not.

This means that, for example, that if we axiomatized arithmetic in a highly defective (but internally consistent) manner - say, for example, we ended up proving 438+21=555, or something like that - well we can demonstrate the our axiomatization is defective by noting that 'not 438+21=555' is an element of the diagram of true arithmetic.

|improve this question
  • 3
    Maybe you could share what you take to be the commonly reported "devastating" consequences of incompleteness? I'm not really sure what you have in mind, especially since a lot of quacks claim all sorts of consequences that simply don't follow. – Dennis Aug 11 '13 at 21:27
  • It might be devastating if you think if all truths should be 'provable', and this should also be true for formalised systems. – Mozibur Ullah Aug 12 '13 at 2:53
  • I don't know too much about it and I wonder what the observation two wants to imply? The truths which you can list like that will be amongst the ones provable from Peano arithmetic. But since the subsets of the natural numbers are not enumberable, I assume there are some statemes which you can't list. At least statments with sequences on numbers involved in limiting process. I don't think you can manually list the sequences. Captioning the statements, which use the axiomized induction over the terms which you can quantify over, seems problematic in general. – Nikolaj-K Aug 12 '13 at 7:41
  • @NickKidman, there's a subtle issue here. The diagram consists only of expressions of the form S(x)=y, not S(x)=y, x+y=z, not x+y=z, xy = z, not xy = z. Where x,y and z are numerals. This particular subset of the language of arithmetic can indeed be enumerated. You can write a C++ program that does it (at least if we imagine the program being executed on a computer with unlimited memory). However, without a sufficiently strong theory of arithmetic (like PA, for example), we have no way of proving that our C++ program actually does what its meant to do. Does that clarify things? – goblin Aug 12 '13 at 9:26
  • @user18921: Okay, buy why does the diagram not contain x+y+z=u+v? What is the point of introducing it, if not all relevant statements are of that form? – Nikolaj-K Aug 12 '13 at 9:52
3

The incompleteness theorems just state that there are true but unprovable statements in formal systems of number theory. A prototypical unprovable statement is that the Kolmogorov complexity of a given number is bigger than half its size. For any given formal system, this statement will be true, but unprovable, for nearly all numbers. This may be an interesting fact, but why did we expect in the first place that each such statement should be provable? Basically because Hilbert was convinced that this is the case, so the incompleteness theorems were a devastating blow for Hilbert and his followers.

However, the relation between Löb's theorem and the second incompleteness theorem indicates to me that the incompleteness theorems still contain an element which is hard to reconcile with my intuition.

|improve this answer

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.