# Logic III: Incompleteness and Undecidability (PH340)

Gödel's incompleteness theorems are commonly regarded as among the most important results of contemporary logic both because of the light they shed on the notions of truth and provability in mathematics and also because of the techniques involved in their proofs. The first theorem states that any consistent formal theory which is capable of expressing basic facts about elementary arithmetic is incomplete in the sense that there are true statements about the natural numbers which it cannot prove. The second theorem states that any such theory is incapable of proving its own consistency. Although these results were first obtained in the early 1930s,they continue to inspire debates in contemporary philosophy of mathematics -- e.g. are there "absolutely undecidable" propositions whose truth values cannot be determined by any demonstrably correct mode of mathematical reasoning? Can we even know that our mathematical reasoning is consistent?

After proving Gödel's theorems, we will consider the notion of ‘self-reference’ more generally. A self-referential statement is one which states that the statement itself has a certain property — e.g. truth or provability. This will lead us to consider logical paradoxes such as the Liar -- e.g. is the statement "This sentence is false” itself true or false? Such paradoxes are related to theorems of Tarski and Löb which generalize Gödel's results. We will also consider the relationship of Gödel's theorems to the existence of undecidable computational problems and to our ability to axiomatically describe mathematical structures. For instance, is it possible to determine whether a computer programmed to enumerate arithmetical sentences outputs only true statements? Are our number theoretic theories capable of ruling out non-standard interpretations containing "infinitely large" integers?