Jakob Kellner
Kurt Gödel Research Center for Mathematical Logic at the University of Vienna

Grundbegriffe der Mathematischen Logik
250124, VO, 2st, SS 2009

Zu dieser LVA gibt es keine Prüfungen mehr.

Beispiels-Pruefungsfragen gibt es hier und hier.

• Unterlagen zur Logik finden Sie u.A. auf der Website von Martin Goldstern ("Neues Skriptum"). Der Stoff geht aber teilweise weit ueber unsere Vorlesung hinaus.
• Handschriftliche Notizen zum ersten Teil der Vorlesung: Naive Mengenlehre, Aussagenlogik. Nicht sehr leserlich, wenn Sie aber gefehlt haben oder dergl. koennen Sie zumindest sehen welcher Stoff durchgenommen wurde.

Übungen

Informationen zu den Übungen (und Angaben) hier.

Ort:

Das KGRC (und der Seminarraum) befindet sich im 2. Stock im rechten Trakt des Josephinums, Währinger Strasse 25.

Inhalt

Die Vorlesung stellt eine elementare Einführung in grundlegende Begriffe der klassischen mathematischen Logik (insebesondere Prädikatenlogik erster Stufe) dar.

• Naive Mengenlehre: Kardinalzahlen, Diagonalisierung, Auswahlaxiom, Zornsches Lemma, Ordnungen, Ordinalzahlen.
• Formalisierung der Mathematik, Sprachen: Syntax und Semantik, Aussagenlogik und Prädikatenlogik 1. Stufe, Vollständigkeitssatz.
• Axiomatische Mengenlehre: ZFC.
• eventuell: Berechenbarkeit/Entscheidbarkeit/Komplexität: Maschinenmodelle (Turingmaschine, μ-Rekursion), entscheidbar und rekursiv aufzählbar, universelle Programme (Interpreter), Unentscheidbarkeit des Halteproblems.

Zu der Vorlesung gibt es ein Proseminar, geleitet von Agatha Walczak-Typke.

Bemerkungen:

• Voraussetzungen: Die Vorlesung richtet sich in erster Linie an fortgeschrittene Studierende des Diplomstudiums und des Bachelorstudiums. Verlangt wird mathematisches Grundverständnis, insebesondere in intuitives Verständnis der Konzepte Algorithmus und Beweis. Es wäer auch gut, schon einmal ein Computerprogramm geschrieben zu haben (völlig egal in welcher Programmiersprache), und man sollte wissen, daß es überabzählbar viele reelle, aber nur abzählbar viel natürliche Zahlen gibt.
• Die Teilnahme am Proseminar wird dringend empfohlen. Das Rechnen von Beispielen erleichtert das Verstehen (und damit das Bestehen der Prüfung).
• Bachelorstudium Mathematik: Die Vorlesung und das Proseminar ist Pflichtfach in der Modulgruppe Vorbereitung auf wissenschaftliche Arbeit, empfohlen im 6. (letzten) Semester.
• Diplomstudium Mathematik: Die Vorlesung (aber nicht das Proseminar) ist Pflichtfach im 2. Abschnitt. Das Proseminar ist ein Wahlfach.
• Unterrichtsfach Mathematik: Die Vorlesung ist zwar im 2. Abschnitt als Wahlfach vorgesehen, es gibt aber sicher leichtere Arten zu einem Wahlfach zu kommen, und die Vorlesung ist für den Kern-Schulstoff nicht relevant.
  Prinzipiell sind aber Themen aus mathematischer Logik durchaus für die Schule geeignet: Es gibt einige sehr einfache, hübsche und überraschende Resultate über unendliche Zahlen (Hilberts Hotel), Logik (diverse Paradoxien), etwas weniger einfache aber sehr überraschende Resultate wie das Banach Tarski Paradoxon und der allseits beliebte Gödel'sche Unvollständigkeitssatz.
  Wenn Sie also Unterrichtsfach studieren und gerne etwas über Logik lernen wollen, melden Sie sich bei uns: Wir überlegen uns, bei Gelegenheit eine Vorlesung Logik fürs Lehramt anzubieten.
• Philosophie- und InformatikstudentInnen sind willkommen, es wird aber eine gute Kenntnis der Mathematik vorausgesetzt. Mit Fragen bezüglich der Anrechenbarkeit für Ihr Studium wenden Sie sich bitte an die für Sie zuständige Studienkommission.

Literatur:

Es gibt kein Skriptum zur Vorlesung. Bei Bedarf kann ich meine handschriftlichen Notizen kopieren (damit sieht man dann zumindest welche Themen behandelt wurden). Teile der Vorlesung übernehme ich von bestehenden Skripten und Büchern, dazu teile ich dann Kopien aus.

Einführende Literatur zu dem Thema:

• George S. Boolos, (John P. Burgess) und Richard Jeffrey: Computability and Logic.
  Ein wunderschöne, einfache Einführung in Logik mit Betonung auf Rekursiontheorie (Berechenbarkeit), inklusive Unvollständigkeitssatz.
• H. Enderton: A mathematical introduction to Logic.
  Eine sehr schöne und einfache Einführung in Logik (inklusive Unvollständigkeitssatz).
• Paul Halmos: Naive Mengenlehre.
  Eine sehr kurze, einfache, allerdings etwas veraltete Einführung in die naive (d.h. weitgehend "logikfreie") Mengenlehre (z.B. Äquivalenz von Auswahlaxiom und Zornschem Lemma etc.).
• Kenneth Kunen: Set Theory.
  Eine hervorragende, gründliche und elegante Einführung in die axiomatische Mengenlehre und insbesondere Forcing.
• Zu den anderen zwei klassischen Gebieten der Logik, Modelltheorie und Beweistheorie, kann ich nicht viel empfehlen. (Beweistheorie und auch "informatische" Logik wird an der TU, zB Matthias Baaz und Alexander Leitsch, betrieben.)
  Die Einführungskapitel des Handbook of Mathematical Logic (J. Barwise, Ed.) sind aber sicher ein guter Anfang (wenn auch nicht ganz einfahc zu lesen).