KURT GÖDEL AND THE INCOMPLETENESS THEOREM

Kurt Gödel is universally considered a genius and one of the most important mathematicians of the 20th century: his incompleteness theorem radically changed disciplines as diverse as mathematics, philosophy, logic, and computer science.

In reality he is the author of practically only a small 25-page essay ("Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" (“On formally undecidable propositions of Mathematics Principle and similar systems I“), written at the age of 24 and published the following year, in 1931.

Before this work that revolutionized modern thought, only his doctoral dissertation, which contains the completeness theorem (of predicate calculus), left us.

After that, until his death at the age of 71, there was essentially nothing.

The Viennese years

Born in Brno (then Brünn) in 1906, into an affluent German-speaking family, he went to Vienna in 1924 to study physics, mathematics and logic.

La Vienna During those years, it was the true center of the world. The arts, architecture, literature, and science flourished in the Austrian capital. Its charming, elegant cafés were frequented by Musil and Zweig, Schiele and Wittgenstein, Kraus and Loos.

In the logical and epistemological field, the so-called "Vienna Circle”, a group of mathematicians and philosophers gathered around Moritz Schlick (among them Rudolf Carnap, Otto Neurath, and Hans Hahn) inspired by the charismatic Ludwig Wittgenstein, who, however, never attended the group's meetings. The philosophical movement promoted by the Wiener Kreis is Logical Positivism.

The young Gödel began attending the group's meetings and, even if he never intervened in the discussions, he internalized the most discussed issues of that period.

Among these, the most notable is the theme of the foundation of mathematics and its coherence and completeness: essentially, Hilbert's program hoped to demonstrate that arithmetic is a complete formal system based on self-evident axioms and rules of inference that, when correctly applied, lead to non-contradictory theorems in finite time. The truth of a proposition produced by the system coincides with its provability; semantics dissolves into syntax: solving arithmetic problems means following rules mechanically, exactly as a computer would.

Substantially the same attempt carried out by Bertrand Russel in the "Mathematics Principle” to found arithmetic on axioms from which to deduce the entire corpus of true theorems deducible from the system.

A similar one formal system must have four characteristics:

  1. be powerful enough to allow arithmetic to be deduced,
  2. be consistent (i.e. do not deduce theorems that contradict each other),
  3. be complete (i.e. capable of deriving all the truths of the system itself),
  4. be decidable (the truth or falsity of any statement can be decided in a finite time).

Gödel is convinced that no formal system has these characteristics and wants to prove it in the literal sense of proving mathematically, not simply arguing. The opportunity presents itself in 1930 on the occasion of the “Second Congress of Epistemology of the Exact Sciences” in Königsberg during which the young Kurt was given the opportunity to give a speech almost on the fringes of the conference.

And it is on this occasion that Gödel enunciates and demonstrates his famous incompleteness theorem.

The Incompleteness Theorem

These are actually two closely related theorems, but only the first one is fully proven:

  • The first theorem states that any formal system powerful enough to describe arithmetic allows one to derive propositions that cannot be proved or disproved within the system.
  • The second theorem holds that the consistency of such a system cannot consequently be proved from within the system itself.

 

In addition to the groundbreaking nature of the incompleteness theorem, Gödel's method for its proof is extraordinary.

Gödel uniquely assigns a natural number to all the logical-mathematical symbols needed to describe arithmetic, and combines these numbers to form propositions within the system. Propositions translated into Gödel numbers transform logical problems and statements into numbers: this makes it possible to encode all propositions and proofs into numbers.

 

Furthermore, thanks to this method Gödel creates formulas which, through the numbering, they speak of themselves or of their demonstrability within the formal system.

One of these is the proposition “G”, which essentially says "I am not provable." Now, if the system proves the statement, then it proves a falsity since the statement claims not to be provable, and is therefore inconsistent; but if the system does not prove it, it is revealed to be incomplete since it does not prove a true statement, namely, "I am not provable." On the other hand, if it did prove it, the statement would be false and the system inconsistent.

If it proves it, then it is false and therefore the system proves a falsity. If, however, it doesn't prove it, the system is incomplete because it doesn't prove a true statement (precisely because it is unprovable).

The second incompleteness theorem then states that no consistent formal system, such as that of Mathematics Principle, can demonstrate its coherence, which can only be affirmed from outside the system itself.

Gödel and Turing

With this, Gödel puts an end to the claim of completely formalizing mathematics and reducing it to a pure mechanical-algorithmic system.

A few years later another mortal blow to the program of formalization of mathematics will be inflicted by Alan Turing who will demonstrate in his essay “On Computable Numbers, with an Application to the Entscheidungsproblem” that there are problems relating to computation that by definition cannot be solved computationally.

Taken together, Gödel's and Turing's theorems, by erasing the claim of formalization of mathematics, place clear limits on computability and on the identification of truth with provability and, consequently, on the ability of machines to think.

Thinking is more than following algorithms (computing).

Interestingly, these limitations are essentially connected to self-referentiality in formal systems, which inevitably tends to generate paradoxes. This self-referentiality, however, does not pose a problem for the human mind, which is characterized by consciousness.

The flight to the United States

Gödel and his wife (a former cabaret dancer) will escape from Nazi Austria in 1940 to take refuge in Princeton where Gödel was assigned a job that was initially precarious and then permanent.

The journey to Princeton will be a true Odyssey: for bureaucratic reasons related to visas, the couple will have to travel the entire Trans-Siberian Railway and then reach Japan, to embark for San Francisco and from there cross all the States to Princeton.

From the day of his arrival, Gödel will never move again.

He will become great friends with Albert Einstein with whom he gets into the habit of walking together along the road that leads to the Institute for Advanced Studies.

He died in 1978, devastated by mental illness and the long fasts he subjected himself to for fear of being poisoned, another paradox.

 

We thank Paolo Riccardo Felicioli for his contribution

Jump to content