Logik und Berechenbarkeit SS 2013

Di 13-15 im SR C307. Beginn Di 5. März 2013.

Inhalt der Vorlesung

Aussagenlogik und ihre Entsprechung in der Theorie der Booleschen Algebren und der Verbandstheorie;
Sprachen erster Ordnung bis hin zum Gödelschen Vollstaendigkeitssatz (jede widerspruchsfreie Theorie hat ein Modell); Ultraprodukte wären natürlich lustig, werden sich zeitlich aber nicht ausgehen.
Berechenbare und nicht berechenbare Funktionen, primitiv rekursive Funktionen und μ-operator, Turing Maschinen, Halteproblem; rekursive und rekursiv aufzählbare Mengen;
und aus Gründen der mathematischen Allgemeinbildung die elementarsten Tatsachen über Ordinalzahlen und Kardinalzahlen.

Literatur

Es wird empfohlen, in erster Linie nach der eigenen Vorlesungsmitschrift zu lernen. Daneben gibt es auch Bücher, siehe unten. Die VO folgt größtenteils dem Buch von Cori und Lascar.

• R. Cori, D. Lascar, Mathematical logic vols. I,II, Oxford Univ. Press 2000, 2001
• H. Ebbinghaus, J. Flum, W. Thomas, Einf. in die mathematische Logik, Spektrum Verlag, 5.Aufl. 2007.
• P. G. Hinman, Fundamentals of mathematical logc, A K Peters, 2005
• M. Goldstern und H. Judah, the incompleteness phenomenon - a new course in mathematical logic, A K Peters 1998.
• W. Rautenberg, Einführung in die Mathematische Logik, 3.Aufl 2008
• D. Cohen, Computability and Logic, Ellis Horwood, 1987.