Numerical strings, in turn, may be used to describe strings used in mathematics to denote natural numbers (nonnegative integers) such as “0”, “13” or “125 239”. Most of us are familiar with the term ‘string’ from computer science, a term traditionally used to describe any finite sequence of symbols. The following section is based on the chapter “ Computability, Formal Systems, and Incompleteness” in Franzén (2005). In order to construct the sketch for a computability proof which shows the same, we must first define a few necessary concepts. Newman’s wonderful book Gödel’s Proof: Steps of Gödel's proof (Nagel & Newman, 2001) In his proof, Gödel showed the following: i) How to construct a formula G of Peano arithmetic (PA) that represents the statement: 'The formula G is not demonstrable using the rules of Peano arithmetic' ii) That G is demonstrable if and only if its formal negation not-G is demonstrable iii) That although G is not formally demonstrable, it nevertheless is a true arithmetic statement iv) That since G is both true and formally undecidable within Peano arithmetic, Peano arithmetic must be incomplete v) How to construct a formula A of Peano arithmetic that represents the statement 'Peano arithmetic is consistent' and that the formula A ⊃ G is formally demonstrable inside Peano arithmetic vi) Finally, that the formula A is not demonstrable in Peano arithmetic Overviewįirst, let us sketch an outline of what Gödel showed in his first incompleteness proof, courtesy of Ernest Nagel and James R. Utilizing Turing and Church’s invention of computability, with the help of the late, great Torkel Franzén (2005) we can devise the sketch for a computability proof of Gödel’s incompleteness theorem that is equally as strong as Gödel’s version, but much easier to deduce.

Gödel hence instead proved his incompleteness theorem for a formal system of his own making, P, and argued that it contained properties shared by a wide class of systems. Gödel’s proof had to be this long, because it was formulated before the establishment of the general theory of computability (Turing, 1936 Church, 1936) and so the general concept of a formal system had indeed yet to be formulated (Franzen, 2005). It is 26 pages long, contains 46 preliminary definitions and several important propositions which are presented in a highly formal way (Nagel & Newman, 2001). Gödel’s 1931 paper containing the proof of his first incompleteness theorem is difficult to read. there are statements of the language of F which can neither be proved nor disproved in F.” “Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete i.e. A Computability Proof of Gödel’s First Incompleteness Theorem

Gödel's Theorem by Torkel Franzén