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
9
  • 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, 2013 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, 2013 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, 2013 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 GONE
    Aug 12, 2013 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, 2013 at 9:52

1 Answer 1

Reset to default
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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .