Logik und Berechenbarkeit WS 10/11
2VO+1UE geblockt als 4VO+2UE in der zweiten Hälfte
des WS10/11; VO-Beginn Di. 23.11.2010 16-18 SR C208;
UE-Beginn Di. 30.11. 16-18 SR C208.
Vortragende: Sophie
Frisch; die
Übungen schupft Roswitha Rissner.
Ort/Zeit normalerweise
Di 16-18 C208 VO und Do 16-18 C307 VO;
Do 10-12 C208 UE.
Zur Ergänzung der Vorlesung gibt es ein
Seminar zu Gödels Unvollständigkeitssatz.
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,
aber ob sich die zeitlich ausgehen werden?
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 ueber Ordinalzahlen und
Kardinalzahlen.
Gödelscher Unvollständigkeitssatz wird sich im Rahmen
der Vorlesung nicht ausgehen, bei Interesse kann der Unvollstaendigkeitssatz
parallel zur Vorlesung in einem Seminar behandelt werden. Zu diesem Zweck
bitte das von Tichy, Grabner, Elsholz und mir angekündigte
Zahlentheorie-Seminar inskribieren und sich bei mir melden. Vorbesprechung
im Anschluß an die erste Vorlesungsdoppelstunde am 23.Nov.
Literatur
Es wird empfohlen, in erster Linie nach der eigenen Vorlesungsmitschrift
zu lernen. Daneben sind folgende Bücher empfehlenswert:
- 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.
A little point set topology.
VO-Mitschrift von Frau Klopf - AS IS - nicht durchgesehen:
erste Woche,
zweite Woche,
dritte Woche,
vierte Woche,
fünfte Woche,
sechste Woche.