How Common is the Incompleteness Phenomenon?

[Dorimant]

Everyone must have wondered about this question from the very first moment they hear about the incompleteness theorem. It is what scared everyone back in 1931 after all, no? ('If he's right then...' -they must have thought in Cambridge and Göttingen at the time. And indeed such comments have been documented and are well known). The question is important. For if it is indeed very common, and you have no way of finding out whether your problem lies within the unprovable ones or not, you are in trouble. Without knowing, you may be trying to know something unknowable. The voyage to Ithaka is always interesting and wonderful and all, but you aim to get there eventually right? 'That's what you're destined for'.. But what if Ithaka doesn't exist? And so we know since 1931 that sometimes it doesn't. But what if Ithakas not uncommonly do not exist? Could there be any quantitative approach regarding this problem?

Now of course, history is against us. 'It can't be that common!' one says. Fermat's last theorem, the four colour problem and many other intricate problems have been dealt with successfully within the 20th century. 'Surely, if we believed that Gödel's incompleteness result prevails in that level of complexity we could just not work on these subjects and they would still remain conjectures. But we didn't and here we are with many fruitful results'. So surely one has to try. But Riemann's hypothesis, most famously, together with a number of other problems in mathematics (and theoretical physics which, by necessity, is highly mathematical and increasingly so!), persistently remain mere hypotheses. Could it be that they exist in a higher level of complexity where the incompleteness phenomenon becomes more common? Can we approach this question somehow or are we doomed to just try our luck time and again hoping we escape this mathematical black hole?

The importance of this issue was very clear to me already, when I picked up a book from the library last week called 'conversations with a mathematician' (the mathematician being G.Chaitin) but i had no idea that the field 'algorithmic information theory' -or perhaps 'information theory' itself(?)- deals with questions like these. The book (a collection of lectures) is interesting and stimulating, for the basic idea is beautiful: It deals with viewing the constructions of mathematical systems as systems of information input (axioms and rules of logic) and information output (theorems). From this point of view the incompleteness theorem is saying something like this: The whole mathematical realm of possible propositions is an almost infinite amount of information (output) towards which you cannot arrive from the finite amount of axioms and calculating methods you provide (input). The author claims the theory has a very close analogy to a computer program and uses the calculation concept of a Turing machine. Needless to say that in order to acquire a personal opinion on the matter one needs to work out the theory itself and get a quantitative knowledge of the issues involved. For example how does one define 'information' in this sense and how 'complexity'? I have no idea, perhaps other members could enlighten us on this.

For the record, the question "How common is the incompleteness phenomenon?" is in fact answered by the author claiming that it is pervasive and common in mathematics - the higher the complexity as defined in alg.inf.theory.

Here follows part of one of the lectures. You can find all of it here: http://www.cs.auckland.ac.nz/~chaitin/vienna.html


"Let me make my question more explicit. There are many problems in the theory of numbers that are very simple to state. Are there an infinity of twin primes, primes that are two odd numbers separated by one even number? [A prime is a whole number with no exact divisors except 1 and itself. E.g., 7 is prime, and 9 = 3 × 3 is not.] That question goes back a long way. A question which goes back to the ancient Greeks is, are there infinitely many even perfect numbers, and are there any odd perfect numbers? [A perfect number is the sum of all its proper divisors, e.g., 6 = 1 + 2 + 3 is perfect.]

Is it possible that the reason that these results have not been proven is because they are unprovable from the usual axioms? Is the significance of Gödel's incompleteness theorem that these results, which no mathematician has been able to prove, but which they believe in, should be taken as new axioms? In other words, how pervasive, how common, is the incompleteness phenomenon?

If I have a mathematical conjecture or hypothesis, and I work for a week unsuccessfully trying to prove it, I certainly do not have the right to say, ``Well obviously, invoking Gödel's incompleteness theorem, it's not my fault: Normal mathematical reasoning cannot prove this---we must add it as a new axiom!'' This extreme clearly is not justified.

When Gödel produced his great work, many important mathematicians like Hermann Weyl and John von Neumann took it as a personal blow. Their faith in mathematical reasoning was severely questioned. Hermann Weyl said it had a negative effect on his enthusiasm for doing mathematics. Of course it takes enormous enthusiasm to do good research, because it's so difficult. With time, however, people have gone to the other extreme, saying that in practice incompleteness has nothing to do with normal, every-day mathematics.

So I think it's a very serious question to ask, ``How common is incompleteness and unprovability?'' Is it a very bizarre pathological case, or is it pervasive and quite common? Because if it is, perhaps we should be doing mathematics quite differently."

Best

ps. Ithaka, as some of you may have noticed, comes from the rather known poem by Cavafy (http://www.cavafy.com/poems/content.asp?id=74&cat=1). He wasn't talking about mathematics of course (it was before 1931 so this is certain!). A quite disappointing conclusion if one relates the meaning with mathematical thinking.. but a beautiful journey nevertheless.

 

[davilla]

I understand the connecion between "constructions of mathematical systems" and computability by Turing machines, or at least I did back in the day, but the connection between that and Gödel's Incompleteness Theorem isn't so clear or immediate.

Incompleteness is indeed a strange thing, maybe too strange if a simple question like the existence of odd perfect numbers could be unanswerable. In fact I think that's a really bad example because it's a fairly straight-forward exercise to determine if a given odd number is perfect. Could the question really be independent of all the arithmetic axioms? I would think not. Let me see if I can sketch a proof of that.

Suppose the existence of odd perfect numbers can neither be proved nor disproved. Then for any given number, it cannot be an odd perfect number because that would prove that odd perfect numbers exist, which contradicts our assumption. Therefore we will never find an odd perfect number. But since all finite numbers are constructible (that is, reachable or expressible), and barring divine intervention that would smite anyone who were just about to discover an odd perfect number, that means there are no odd perfect numbers. But this conclusion then contradicts our assumption. So the existence of odd perfect numbers cannot be unprovable unless their existence is disprovable.

I don't know if that proof holds water, but it's rather interesting that it relies on what we can compute, with the very strange language of any finite number being constructible. Maybe that's the link between Gödel and Turing. To reach one of these statements that are independent of the axioms, you have to go out to a certain level of uncomputability, so to speak. "Are there infinitely many such-and-such" is a much more obtuse sort of question, and the Riemann hypothesis, which asks about the nature of an infinite sum, is so out there I barely consider it to be arithmetic.

What I would like to know is if any of the statements "such-and-such conjecture can neither be proved nor disproved" are themselves neither provable nor disprovable. That would be really evil. Not only would some mathematicians spend their entire lives trying to prove a theorem that can't be proved, and others spend their entire lives trying to disprove it, but then civilization itself would spend an eternity trying to show, in vain, that it can neither be proved nor disproved.

Could anything really be so wicked? Does the above proof work in application to this problem? Suppose the question of whether a conjecture can neither be proved nor disproved is itself neither provable nor disprovable. Then for any given proof, it cannot be a proof that the conjecture is neither provable nor disprovable, since that would contradict our assumption. Now, does that imply that there are no proofs of the nature of the conjecture? Are all proofs reachable, that is, constructible or expressible?

That question I have absolutely no confidence about. It seems that statements of the nature "a conjecture can neither be proved nor disproved" form a system that is subject to Gödel, so there really must be some evil in mathematics. ~~~~

 

[HallsofIvy]

Goedel Incompleteness is often stated as "there exist true statements that cannot be proved". That's an oversimplification, however. In logic and mathematics statements are never "true" or "false"- those terms are not part of the subject. Statements are either "provable" (even if we don't know how) or "disprovable" (i.e. the negation is provable- again, even if we don't know how), or, and this is Goedel's point, neither provable nor disprovable. If statement A falls into that last category, then there is nothing wrong with taking either A or "not A" as a new axiom and proceeding from there. Of course, (1) there will still be other statements that can neither be proved nor disproved. (2) it might happen that we were wrong about A being in the third category and just didn't know the proof (or disproof) of A which might cause trouble. But then assuming A as an axiom and finding that our axiomatic system is no longer consisten would be a proof of "not A"!

 

[davilla]

Yes, "neither provable nor disprovable" is equivalent to "independent of the axioms".

(2) it might happen that we were wrong about A being in the [neither provable nor disprovable] category and just didn't know the proof (or disproof) of A which might cause trouble.

It was my understanding that, at least in some cases, it's possible to prove that A is in that categorty, that the axioms plus A are consistent if and only if the axioms plus not A are consistent, which would imply that either the original axioms are inconsistent (and there's no way to know that they aren't) or that A must truly be independent of them. My rambling proceded in the direction of, if the statement that "A is in that category" is true, then is it always possible to prove as much? ~~~~

 

[chronon]

Gödel's incompleteness theorem is frequently misunderstood - it does not claim that statements about the integers are absolutely undecidable, rather that they may be undecidable given a particular set of axioms. But mathematicians working on the twin primes conjecture are not limited a particular set of axioms - they can use anything that they intuitively know to be true about the integers (this intuition may be wrapped up in other fields of mathematics such as that of modular forms).

I've written more about this on my website at
http://www.chronon.org/Articles/fermat_undecidable.html
God gave us the integers...
and
Gödel's incompleteness theorem

 

[Hurkyl]

My rambling proceded in the direction of, if the statement that "A is in that category" is true, then is it always possible to prove as much? ~~~~

No; at least, not internally. Suppose the answer is yes:


There is a computable ordering on all statements made in the language of integer arithmetic. (the dictionary ordering, for example)

Because the class of Peano's axioms is computable, we can create a new ordering on the class of all statements such that a Peano axiom is smaller than any statement that isn't a Peano axiom.


Then, we can define the following set of axioms:
P is an axiom if and only if it cannot be disproven from the collection of statements smaller than P.


This theory is decidable, consistent, contains Peano's axioms, and has a computable set of axioms. This contradicts Godel's incompleteness theorem. Therefore, the answer to your question is no.

 

[davilla]

No [it isn't always possible to prove that "A is in that category"]; at least, not internally. Suppose the answer is yes [...and...] define the following set of axioms: P is an axiom if and only if it cannot be disproven from the collection of statements smaller than P.

This theory is decidable, consistent, contains Peano's axioms, and has a computable set of axioms. This contradicts Godel's incompleteness theorem.

Wow, I think you just proved that math is evil. Okay then, there must be a hole in my sketchy "proof" somewhere. I've tried to reformulate it more formally and I'm hitting a stumbling block in that, whereas I used a proof by contradiction above, I can't assume that a characterization of statements of independence are either true or false, as in provable or disprovable, as that was the very question in the first place. So I guess it's a kind of cyclic argument. Chronon's writing suggest that there are "really undecidable" problems for which it is impossible even to determine if they are undecidable, and it seems like this application of Gödel naturally leads in that direction.

But what then about simple statements like the existence of odd perfect numbers or the equality in Fermat's last theorem? If my second argument above was falacious, what about the simpler first? In those cases we're not talking about the nature of statements, which may be provable or unprovable or neither, but of numbers, which must either exist or not. I assert that the question of decidability is not undecidable in those cases. If you assume that the question of existence is undecidable, that assumption immediately contradicts itself. If existence is undecideable, then the object could not exist, but then that establishes its non-existence.

A little more formally, if A is computable then suppose the statement S = "for all x, not A(x)" is undecidable. If A(n) is true for some n, then with A (and n) computable there exists a constructible proof of A(n), and this would prove that S is false, which is a contradiction. Therefore A(x) is not true for any x, i.e. S is true. But this is also a contradiction. Therefore our assumption was wrong, and S must be decidable.

Again, this doesn't work if A is not computable, as was the case for A = "for some proof p, p(x)" i.e. the question of decidability itself. Likewise I don't think it works for sets where some of the elements are not reachable. But odd perfect numbers and solutions to a^p+b^p=c^p are not examples of that, and must simply either exist or not. ~~~~

 

[wuliheron]

Mathematics is a class of languages which, like every other abstraction, have philosophical foundations. Linguistically speaking, the axioms of different mathematics are their metaphysical foundations. Therefore to answer the incompleteness theorem requires that you first decide which philosophy you believe in.

Personally, I take a pragmatic approach. Metaphysics in and of themselves are as useless as tits on a boar hog. Like everything else, I suppose, mathematicians will have to deal with the uncertainty of life just like the rest of us.

 

[setAI]

I am intrigued by some of the thinking lately [especially by Tegmark here: http://arxiv.org/abs/0704.0646 ] concerning the nature of computability/incompleteness as it applies to existence of physical reality- that is that the physical universe exists because it is a result of consistent causal laws- such causal structures are described by Turing machines and support the Church-Turing Thesis- our universe must be an algorithmic structure because it is a causal structure with rules which is a definition for what an algorithm fundamentally is-

so then incompleteness does not appear to apply to the physical universe since the universe has to be able to compute itself to maintain a consistent causality- and the idea is that the classes of mathematical and formal systems which aren't computable which incompleteness refers cannot be consistent causal structures and therefore do not have the quality of 'existence'- they cannot be 'real' without being computable- to compute themselves and maintain a causal structure-

so Existence then is described as the phase space of all possible computable structures- and uncomputable ones are unreal- however incompleteness crops up in the outcome of computations as they cannot be determined due to things like the Halting Problem and Uncertainty- you cannot know even in principle the history that will be observed based on the current state/rules- however all the possible histories are each computable results-

 

[Moridin]

I would not advocate that the Incompleteness theorem applies to science, but to formal systems only. A formal system has well-defined rigid axioms a well-defined rigid means of inference. A formal system, like mathematics, must be free of contradictions. Science can at any point drop the earlier assumptions and form entirely new ones without being worried to contradict old ones if the evidence supports it. In fact, such behavior is encouraged.

A case in point would of course be Classical Mechanics and Theory of Relativity. Please correct me if I am wrong, but I doubt that you could reach ToR by limiting yourself only to the axioms of CM at this point? Indeed, Einstein's second postulate surely does not follow from Classical Mechanics?

 

[Hurkyl]

however incompleteness crops up in the outcome of computations as they cannot be determined due to things like the Halting Problem and Uncertainty

I'm not sure what you mean by that. Incompleteness doesn't crop up in the outcome of computations -- Goedel incompleteness, in this context, simply states that a certain class of functions are not computable.

(specifically, the class of truth functions for Peano arithmetic)

Incompleteness has nothing to do with uncertainty. At least, there is no apparent relationship, except for the fact that in an entirely different context, those English words describe similar phenomena.

 

[setAI]

I'm not sure what you mean by that. Incompleteness doesn't crop up in the outcome of computations -- Goedel incompleteness, in this context, simply states that a certain class of functions are not computable.

(specifically, the class of truth functions for Peano arithmetic)

Incompleteness has nothing to do with uncertainty. At least, there is no apparent relationship, except for the fact that in an entirely different context, those English words describe similar phenomena.

what I mean is that Incompletenes seems to apply to the decidability of future states- there is no theory even in principle that can decide the outcome of a series of quantum observables- Unitary QM says that all the future states exist- but there is no way even in principle to figure out which future will be observed- only a probability distribution of the possibilities- and uncertainty increases with the entropy as unknown information in a system propogates in all futures- this just is an example of how even though we can have a theory which precisely computes the possible outcomes- it cannot with certainty tell you which outcome will be observed- to me this is the same thing that Gödel Incompletenes describes in a more genreal fashion- some information about a system is always unknowable- even in a simple discrete system where the rules and current states are completely known

 

[Hurkyl]

to me this is the same thing that Gödel Incompletenes describes in a more genreal fashion- some information about a system is always unknowable- even in a simple discrete system where the rules and current states are completely known

Godel's incompleteness theorem only applies to a specific class of formal systems. And not all formal systems are logically incomplete -- there are useful theories that are logically complete, such as elementary Euclidean geometry, and elementary real arithmetic.

Furthermore, you can even have a logically complete theory of integer arithmetic, in spite of Godel's theorem; in fact, any consistent theory can be extended to a logically complete theory. (Even Unitary QM!) It's just that such a theory might not be computable.



You talk about uncertainty and entropy -- those have absolutely nothing to do with either logical meaning of the word "complete".