Undecidability and Incompleteness

Catalog description

U and amp; I focuses on two fundamental results: the undecidability of logic (established by Alonzo Church and Alan Turing) and the incompleteness of mathematical theories (discovered by Kurt G and #246;del). The proofs of these results require a novel metamathematical perspective, but also striking logical concepts and fascinating mathematical techniques. In this course, the theorems are not just formulated but actually proved. We begin with the axiomatic development of elementary set theory that allows, at the same time, the formal representation of informal mathematics like number theory. With this basis, one can show that syntactic notions concerning set theory are representable in the very theory. It is then easy to prove that set theory is incomplete. To show that logic is undecidable, the crucial concept of computation is introduced via Turing machines. The two central concepts - proof and computation - are fundamental for mathematics, computer science and, in particular, artificial intelligence. The undecidability and incompleteness results are among the most significant contributions of modern logic to the foundations of mathematics. They provide also the beginnings of a deeper understanding of mental processes in cognitive science and, thus, of the human mind. To understand the latter connections, we will read about and discuss historical as well as philosophical aspects of the subject. Prerequisites: 21-300 Min. grade C or 80-310 Min. grade C or 80-211 Min. grade C or 15-251 Min. grade C or 21-127 Min. grade C or 80-210 Min. grade B