#9: Incompleteness by Rebecca Goldstein

The proof and paradox of Kurt Gödel

I have admired Gödel since I read Hofstadter's: Gödel, Escher, Bach: an eternal golden braid. I hadn't read his work as a logician, but would talk with friends about it (and its implications) informally. That is, until I was chatting with Suman in 2008. He could tell that I would benefit from reading a popularization of his incompleteness theorems that dealt more directly with the content of his proof, so he and Anjali gifted me this book for my birthday (Harvey-mas).

The book was a joy to read (man have I been lucky with these books - I seem to say that they all are great). I enjoyed learning about Gödel's life - his life in Vienna, his work on the proofs, and his cherished walks with Einstein, another scientist who Rebecca Goldstein argues is intellectually exiled* by his theories/proofs - and the proof itself.

When I was an undergraduate in an introductory course on philosophy and discussing a number of important proofs, I found myself wishing for an airtight proof that the axioms of an argument were correct. Could there be assurance that I was using the right axioms? If not, I might come to the completely wrong conclusion despite using a rational argument. As you know, in any argument, the conclusions follow from the premises via rules of inference. 

At the time, I constructed an argument by analogy that no such proof existed since we could not imagine removing a condition, which we could not imagine removing (e.g. one could not imagine removing from the set of axioms that a human mind is a prerequisite for rational argument). Just as a fish would not have a concept for water (since it had always been fully surrounded by water and there had never been not water for it), so too, we humans could be fully immersed in some set of beliefs or conditions which would be impossible to imagine going without. 

Via Gödel's incompleteness theorems**, Gödel proved that such a program was useless: we cannot justify a set of premises in a logical system using the logic alone. If you are interested in the context from which Gödel's work arose, check out: Hilbert's program, and the Liar's paradox (i.e. "This sentence is false".

Implications of incompleteness

While many others extended the incompleteness theorems to the humanities, the computer sciences, and intelligence research (see Penrose for example), Gödel himself was more reticent to extend his theories. He does have this to say about the differences between men and machines though:

Either the human mind surpasses all machines (to be more precise it can decide more number theoretical questions than any machine) or else there exist number theoretical questions undecidable for the human mind.

By this, Gödel seems to suggest that either we are not like a machine (because our decision mechanism is not, at base, mechanical), and we have access to truths that a formal system would find unprovable; or else, we are at base complicated machines that have deluded ourselves into believing we have access to unformalizable mathematical truths.

_______________

* While both Einstein and Gödel achieved a large degree of fame for their discoveries, Goldstein argues that it was the world's subjectivist interpretations of each man's theory that lead to their respective marginalization. For Einstein and Gödel, their work bespoke the objectivist reality of Physics (physical realism) and Mathematics (Platonism).

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

Problems, solutions and verification

Puzzles are fun. But what is a puzzle really. Puzzles are a class of problems that have been solved before. In this essay, I want to draw your attention to three classes of problems: puzzles, near-puzzles and theories.

The first class comprises the sort of problems for which a known algorithm exists to get us to the solution. These types of problems have the property that as soon as we identify their type (i.e. that it is a puzzle like one I have already solved), we just need to apply the correct formula and eventually we will get the answer. Let's call the class of these puzzle type problems, P.

The second class of problems are problems, for which, while no algorithm may exist to reach a solution, if a solution is offered, it could be tested and shown to be a solution. Since these problems are similar to puzzles, we'll call the class of near-puzzle type problems, NP.

There is a third class of problems. These are the problems that have not been solved, and/or if a solution existed, the solution could not be verified. This class of problems are similar to theories, and therefore we'll call the class of theory-type problems, T.

Some examples

Summation. Summation is a kind of "puzzle." The summation puzzle asks, "For any two numbers, what number is their resulting sum?" We know that this puzzle is a P-type problem since there is a strict rule for summation of any two numbers and the rule always generates the answer.

Temporal questions. One cannot predict the future. I can be pretty sure, but I can't be certain about it until it has safely become the past. So problems like what will I have for lunch tomorrow is a NP-type problem. I may think it will be a peanut butter and jelly sandwich, but until I have it, I can't be sure. Of course, these solutions can be verified simply by waiting long enough.

Theory verification. Some problems are problems that relate to the truth of general theories. Theory verification has been known to be a general problem for a long time in the philosophy of science. Given any scientific theory there is no way to prove that it is true. For example, if I have a theory that has some explanatory power, such as, "Evolution via natural selection is an explanatory principle for the myriad complex living organisms that exist today," it pertains as an explanation until it doesn't. That is, until I find enough scientific data that debunk it (such as serious inconsistencies in the fossil record, for example) I can believe it to be true. This is true of all scientific theories, even the historically unexceptionable ones like quantum mechanics or the modern evolutionary synthesis.

Is the Goldbach Conjecture P, NP or T?

GC: "Every even integer greater than 2 can be written as the sum of two primes"

Let's presume, as Euler may have, that the GC is true but not provable. This conjecture would belong to the T-type problems.

However, if it were false, then it would presumably belong to the NP class (would be verifiable), and by extension, belong to the P class since the counter-example would be a finite number and an algorithm that checked every even integer greater than 2 would be a valid algorithm.

Some interesting properties of P's and NP's.

You may have noticed that the class of P problems are very similar to NP problems, in some regards. Unlike T problems, an NP problem is similar to a P problem, in that, given its solution, it can be verified. We could certainly imagine mistaking a P-type problem for an NP-type problem in cases where we didn't notice that it was the same riddle in a different frame, figuratively speaking. Another interesting feature of P-type problems is that it is not inconsistent to classify them as NP problems. All P-type problems are NP-type problems. Notice, if the reverse is true, then near-puzzles would be puzzles.

Given all the similarities, we may begin to suspect that, in actual fact, P=NP. It is at least possible that for all those NP-type questions, they are really P-type questions, and it is our own limited knowledge that has allowed us to initially misclassify them. How could we find out? Does P=NP? That is an interesting problem. Is that problem, itself, a P-, NP- or T-type problem?

Classifying "P=NP?"

Assuming that "P=NP?" is one of the three, it is either the case that "P=NP?" is a P- (and therefore also NP), NP- or T-type problem.

Let's write out the question completely. The question we are asking is, "Is the problem 'Are all puzzle type problems the same as all near-puzzle type problems?' a member of P or NP or T?"

It is possible that the question does not belong to P or NP (case: not P, not NP).

In this case, the question could belong to the T-type questions. If that were the case, then there would be no way to satisfactorily answer "P=NP?". It is possible that it could be true that P=NP, but there would be no way to prove it. This is similar to the incompleteness result guaranteed in sufficiently complex (and consistent) formal systems as explained by Gödel.

Let's presuppose that there is a solution to this problem and set aside the possibility that the general question is a T-type problem. The following two possibilities would remain ([not P but NP] or [P and NP])

It is possible that the question does not belong to P but does belong to NP (case: not P but NP).

In this case, it is clear that the underlying question "P=NP?" would need to be false since if it were the case that P=NP, the above presupposition (not P but NP) would be meaningless. Assuming that the above presupposition is not meaningless, it must be the case that P≠NP. However, it is not consistent for the question "P=NP?" to be a member of NP (and not P) and to show that P≠NP. For, if we were able to definitively show that P≠NP, then the question "P=NP?" must be a member of P and NP (the solution algorithm thereby classifying it as P would of course be this proof!).

Continuing to assume that the question is not a T-type question, it follows that the only choice that remains is that the question belongs to P and (trivially) NP (case: P and NP).

If the problem "P=NP?" is a member of P, this means that the question "Are all puzzles and near-puzzles equivalent?" has a solution and there is an algorithm to demonstrate it! Either P=NP or P≠NP.

If P=NP, we must be capable of imagining an algorithm existing, which can rule out any problems with algorithmically verifiable solutions, for which, no algorithm can provide the solution (an algorithm exists and it rules out NP-type problems that are not also P-type). This should be an easy task since we have already assumed that there exists an algorithm that has solved the harder problem "P=NP?" It is a contradiction in terms to suppose that an algorithm that can verify solutions cannot also generate solutions themselves. For example, the algorithm, try all potential solutions one at a time would be a viable algorithm for any problem one can suppose.

Notice that since we have assumed that there is a solution to the problem (that it is not a T-type problem) we have implicitly eliminated all true but unprovable claims from the pot of questions that are valid. Under these premises we are assuming that an algorithm doesn't get stuck checking the types of problems that would ultimately be T-type problems. If we know a priori which types of problems these are, then we guarantee that all our searches for solutions will terminate, and in that case, the search space is finite. This guarantees that P=NP.

For similar reasons as above, we have ruled out the possibility that P≠NP. For that to be true, it must be possible for there to exist an algorithm that can identify at least one problem for which solutions, if found, could be verified and further, the algorithm must show that for this problem there exists no algorithm one might use to find a solution. Further, this algorithm must be able to reconcile this fact with the fact that the more general problem is P=NP? is itself a P-type problem. Just as before, there is no way that P≠NP is a solution given the particular search space to which we have confined ourselves.

Conclusions

I have shown that either "P=NP?" has no solution (i.e. it is a theory type question) or P=NP. I have purposefully used the computer science terminology in their own P vs. NP debate because I believe the argument above is at least useful as an analogy. Unlike the computer science debate, the above has not made specific mention of an algorithm's time scaling with respect to a given input, which is of course a very important detail. For example, algorithms with exponential time solutions would still be members of P according to the above argument, while they would be excluded from P in the computer science version of the argument.