Lehrveranstaltungsleiter: Alexander Leitsch
Diese Lehrveranstaltung ist Wahlfach im Magisterstudium Computational Intelligence
(Bereich "Diskrete Mathematik und Logik").
This course also belongs to the advanced modules Logical foundations and Inference in classical and nonclassical logics of the international Master Programme in Computational Logic.
Time and Place:
Thursday 17:00 - 19:30
Labor 185/2, Favoritenstrasse 9, 3rd floor, yellow zone
begin: May 4, 2006
Goedel's incompleteness theorem
Goedel's incompleteness theorem is one of the most important logical results of the 20th century. It establishes the fundamental difference between truth and provability: for any axiom system for arithmetic there exists a true but non-derivable sentence which can be constructed effectively. Together with the results of Turing and Church about computability, Goedel's incompleteness theorem implies that arithmetic truth cannot be generated mechanically; in particular there exists no complete mechanization of mathematics. In this course we address the following topics: arithmetization of syntax, minimal arithmetic, representability of recursive functions, undecidability and incompleteness, unprovability of consistency.