Kurt Godel (1906–1978) is a bizarre character in history of mathematics whose 1931 theorem on the incompleteness of formal arithmetic has dominated 20th century mathematics. Personally Godel is a tragic neurotic man impossible to relate to.
In S. Hawking’s review of Godel’s 1931 paper we read that Godel clarified the distinction between What is provable and What is true.
Godel’s 1928 doctoral thesis established that the system of first order predicate logic was complete (all true propositions can be proved within the system), and consistent (only true propositions can be proved within the system). This was no surprise to anybody. Beyond first order logic, the next logical structure is formal arithmetic (additive and multiplicative properties of natural numbers). In Godel’s 1931 Habilitationschrift he argued for the incompleteness of formal arithmetic. This meant establishing the existence of “true propositions” in formal arithmetic which cannot be proved within the system. This implied that “if formal arithmetic is consistent, then that consistency cannot be proven within formal arithmetic itself.”
How is this achieved?
Godel claims to establish a numbering for all the propositions of formal arithmetic. This enables the curious possibility of representing propositions and metaproperties about propositions as formal properties of natural numbers themselves. This supposes somehow that the proposition \(P\): \(2+2=4\) can be represented by a Godel number \(N=N_P\), and that properties about \(P\) are represented by arithmetic properties of \(N\). The specific correspondance between properties of \(P\) and properties of it’s Godel number \(N_P \in {\bf{N}}\) is not typically described in the popular literature.
The purpose of Godel’s numbering is to study the Godel number of the following proposition:
[\(G\)] The proposition with Godel number \(g\) is not provable within formal arithmetic.
The bizarre claim of Godel’s argument is that the Godel number of \(G\) is \(g\) itself, i.e. \(N_G=g\). Thus the truth of \(G\) appears to somehow describe the truth of the nonprovability of \(G\) within arithmetic.
Remark. It’s curious that one is not capable of putting \(G\) symbolically into the Godel statement, for example the following statement:
[\(G'\)] The proposition \(X\) with Godel number \(g\) is not provable within formal arithmetic.
The difference between \(G\), \(G'\) is simply the presence of the dummy variable \(X\) in the formula. By construction of Godel numbering, it would appear that \(G\), \(G'\) have distinct Godel numbers. Again this variation follows from the presence of the dummy variable \(X\) in \(G'\). But it seems almost self-evident that \(N_{G'}\) cannot possibly coincide with \(g\). I.e., by the construction of the Godel numbering the presence of \(G\) precludes the coincidence between Godel numbers. This is our main criticism of Godel’s argument, that the following claim is not properly addressed.
Claim: The Godel number of \(G'\) is not equal to \(g\).
The claim that the Godel number of \(G\) (or \(G'\)) is equal to \(g\) leads to the following standard line of reasoning: “If \(G\) is true, then the proposition whose Godel number is \(g\) cannot be proved within formal arithmetic. But by construction this proposition is \(G\) itself. Therefore \(G\) is true and cannot be proved within formal arithmetic. Therefore formal arithmetic is incomplete.” And alternately one reasons that “If \(G\) is false, then the proposition whose Godel number is \(g\) can be proved within formal arithmetic. But by construction this proposition is \(G\) itself. Therefore \(G\) is simultaneously false and provable within formal arithmetic. Therefore formal arithmetic is inconsistent.”
So what? It’s tautological that \(G\) or \(\lnot G\) is true, and therefore formal arithmetic is either incomplete or inconsistent according to Godel’s argument. That is, formal arithmetic satisfies a law of excluded middle: formal arithmetic is either incomplete or inconsistent. (Again this is assuming the possibility of \(N_G=g\) as claimed above).
The above reasoning does not yet establish Godel’s Incompleteness Theorem. The final step is to argue that \(G\) is actually True. In fact it’s often claimed that \(G\) is self evidently true. But how? Recall that \(G\) is the statement “The proposition with Godel number \(g\) is not provable within formal arithmetic”. Again if we suppose that \(G\) is the subject of the proposition, then \(G\) is True only if \(G\) is provable.
Our next critique of Godel’s argument is the typically “weak” argument for establishing \(G=\text{True}\). Sir R. Penrose claims that \(G\) is “obviously true” because the truth of \(G\) depends on our trust in the “rules” by which we prove theorems. “The statement is true by virtue of your belief in the rules, but the statement is not provable by the rules.” But as we review Godel’s argument, we ourselves don’t see how or why \(G\) is true. Our “belief in the rules” is not formalized at this stage. Presumably this belief in the rules means the belief in Godel’s numbering system, and the Godel number \(N_G\) of proposition \(G\) coinciding with \(g\).
[end -JHM]