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

**CONTENT:**

**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.

A.Leitsch