Time: 4:00 pm
Venue: Madras School of Economics, Chennai
Title: Gödel’s Incompleteness Theorems
Abstract: Early 1900s was the time when the foundations of today’s mathematics and computer science were being laid down. Cantor just came forward with the radical ideas in (naive) Set Theory: “Infinities of Different sizes”. Russell and Whitehead in their three volumes of “Principia Mathematica” tried to demonstrate that mathematics is objective and logical. David Hilbert pushed the dream that all of mathematics can be done in a consistent and complete formal system. Further he proposed that given this formal system, all of mathematics is just symbol manipulation governed by rules in the system and this system can prove it’s own consistency by finitary means. In 1931, an young Austrian logician, Kurt Gödel, using the logical system of “Principia Mathematica”, published the seminal paper in Logic: “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme” (On formally undecidable propositions of “Principia Mathematica” and related systems). This obliterated Hilbert’s dream in a way. Essentially, in this paper, he proved two theorems which informally goes as: In a “nice” logical system which can encode arithmetic, there will always be some truths which cannot be proven, and, such “nice” formal systems cannot prove it’s own consistency. Together, they are called “Gödel’s Incompleteness Theorems”. This paper laid down the limitations of formal logical systems which can encode arithmetic in them.
Our main aim for the couple of talks is to explore these two theorems. We will start from the absolute basics: First Order Logic. Then, we will proceed to the theory of Peano Arithmetic (PA), followed by encoding PA within itself using primitive recursive functions. Then we shall see what it means to be “provable” in PA. Thereafter, we will go through the first incompleteness theorem. By this point, if we are left with time, we will conclude our venture by exploring the second incompleteness theorem.