Gödel incompleteness

Abstract This chapter is devoted to the proof of Godel’s first incompleteness theorem for recursively axiomatized theories extending PA−. Godel’s theorem is often considered because of its role in foundational issues in mathematics (in this context the first incompleteness theorem tells us that ‘arithmetic truth is not axiomatizable’). We shall be also interested in it for a different reason: the incompleteness theorem, in conjunction with the completeness theorem, equips us with a rich supply of interesting models. The techniques we employ, such as the representability of recursive functions in PA- and the diagonalization lemma, will also yield other well-known and interesting results in logic, such as Tarski’s theorem on the undefinability of truth and Godel's second incompleteness theorem.