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

Grundbegriffe der Mathematischen Logik
250130, VO, 2st, SS 2010

Zeit und Ort:

Pruefungen:

Schriftliche Pruefung (groesstenteils multiple choice). Naechster (und letzter) Pruefungstermin: Mittwoch, 26. Jaenner 2011, 10:00-13:00. Ort: Seminarraum KGRC.

Anmeldung zur Pruefung durch email an mich mit Name, Matrikelnummer und Studienkennzahl. (Eine weitere Anmeldung, zB bei Fr. Bauer, ist nicht noetig).

Beispiels-Pruefungsangaben: siehe naechster Punkt.

Im Sommersemester 2011 wird die naechste Grundbegriffe Vorlesung gehalten, von Hans Adler.

Die Pruefungstermine:

• 1. Termin: Mittwoch, 30. Juni 2010.
• 2. Termin: Donnerstag, 29. Juli 2010.
• 3. Termin: Donnerstag, 7.10.2010.
• 4. Termin: Mittwoch, 26. Jaenner 2011, 10:00-13:00.

Inhalt:

1. Teil: Rekursionstheorie

• Sammlung aller handschriftlichen Mitschriften zur Rekursionstheorie (mit ein paar Korrekturen)
• Kurz-zusammenfassung des Theorie-Pruefungsstoffs.
• Einige weiterfuehrende Bemerkungen, die ueber den Vorlesungsstoff hinausgehen (nicht fuer die Preuefung relevant).
• Beispiel-Pruefungsangaben fuer Rekursionstheorie und Aussagenlogik.

2. Teil: Praedikatenlogik

• Aussagenlogik: Handschriftliche Unterlagen, Beispiel-Pruefungsangaben siehe Rekursionstheorie.
• Handschriftliche Unterlagen zur Praedikatenlogik:
  Teil B wichtig fuer Motivation und Verstaendnis, vielleicht nicht unbedingt fuer die Pruefung.
  Teil A "Haupt-Stoff" zusaetzlich zum Ziegler Skriptum S3-16. Es wurden ein paar Korrekturen eingefuegt, markiert in Rot, und noch zwei weitere (danke an Herrn Arnberger) in Gruen, auf Seiten 6 und 8.
• Beispiel-Pruefungsangaben fuer Praedikatenlogik.
• In der Vorlesung wurde darueberhinaus etwas axiomatische Mengenlehre besprochen; das ist nicht Pruefungsstoff.

Skriptum

Es gibt kein Skriptum, aber ein paar handschriftliche Notizen (siehe oben). Im Wesentlichen ist alles im Skriptum von Martin Ziegler.
Im Folgendem unterscheidet sich die Vorlesung vom Ziegler-Skriptum:

Rekursionstheorie

• Registermaschinen werden nur fuer natuerlich Zahlen definiert (nicht wie bei Ziegler fuer allgemeine Alphabete)
• rekursive Funktionen werden fuer partielle Funktionen definiert, nicht nur fuer totale wie im Ziegler Skriptum.
• In der Vorlesung haben wir ein paar weitere Eigenschaften von r.e. Mengen erwaehnt.
• In der Vorlesung haben wir die Unloesbarkeit des 10. Hilbertschen Problems und des Wortproblems in Gruppen erwaehnt.

Praedikatenlogik

• Wir definieren frueher den Beweis bzw die Folgerung aus einer Satzmenge (nicht nur der leeren Menge).
• Wir bringen frueher bzw zusaetzliche Folgerungen (Skolem Loewenheim, Kompaktheitssatz, nonstandard Modelle etc)

Proseminar

Das Proseminar wird von Hans Adler geleitet. Übungsangaben finden Sie (ca 1 woche vor den jeweiligen Übungen) auf seiner Website.

Allgemeine Informationen

Inhalt

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

Geplante Themen:

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

Voraussetzungen:

Die Vorlesung richtet sich an fortgeschrittene Studierende des Diplomstudiums und des Bachelorstudiums. Sie brauchen mathematisches Grundverständnis, insebesondere (intuitives) Verständnis der Konzepte Beweis und Algorithmus, und Sie müssen bereits mit elementarer Logik der Mathematik umgehen können. (Zum Beispiel: Es sollte Ihnen klar sein dass A → B "logisch äquivalent" zu ¬ B → ¬ A ist (aber sie müssen "logisch äquivalent" nicht definieren können.) Sie sollten schon einmal ein Computerprogramm geschrieben haben (egal in welcher Programmiersprache), und wissen, daß (und warum) es überabzählbar viele reelle, aber nur abzählbar viel natürliche Zahlen gibt.

Anrechenbarkeit:

• 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.
• Studierende anderer Studien, insbesondere Philosophie und Informatik sind willkommen, es wird aber wie erwähnt 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. Ich werde von Zeit zu zeit meine handschriftlichen Unterlagen online stellen (daraus sehen Sie dann zumindest welche Themen behandelt wurden). Alles was in der Vorlesung behandelt wird kann man in Büchern und in frei verfügbaren Skripten nachlesen:

• Logik Skriptum von Martin Ziegler.
• Rekursionstheorie Skriptum von Sebastiaan Terwijn.
• "Neues Skriptum" auf der Website von Martin Goldstern.
• 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).
• Kenneth Kunen: Set Theory.
  Eine gute Einführung in die axiomatische Mengenlehre und insbesondere Forcing.

Weiterführendes:

Wenn Sie sich für weiterführende Themen in der mathematischen Logik interessieren, sind Sie herzlich eingeladen die entsprechenden Vorlesungen am Kurt Gödel Research Center (KGRC) der Universität Wien und an der TU Wien zu besuchen. Am KGRC machen wir in erster Linie Mengenlehre, aber auch Modelltheorie und Rekursionstheorie. An der TU gibt es auch Mengenlehre (Martin Goldstern) aber vor allem theoretische Informatik, Beweistheorie und verwandte Gebiete (zB Matthias Baaz und Alexander Leitsch).

Inhalte der einzelnen Stunden

(Nur zur Dokumentation, halten Sie sich besser an die zuvor angefuehren Sammlungen der Unterlagen)

• 1. Stunde (2010-03-02): Rekursionstheorie: Registermaschinen
  Im wesentlichen: Seiten 60 und 61 des Ziegler Skriptums (nur fuer den Fall der natuerlichen Zahlen).
  Handschriftliche Unterlagen: Teil A, Teil B
• 2. Stunde (2010-03-09): Rekursionstheorie: mu-rekursion
  Im wesentlichen: Seiten 62 bis 64 des Ziegler Skriptums.
  Handschriftliche Unterlagen: Teil A, Teil B
• 3. Stunde (2010-03-16): Rekursionstheorie: rekursiv impliziert berechenbar
  Im wesentlichen: Seiten 64 bis 65 des Ziegler Skriptums.
  Handschriftliche Unterlagen: Teil A, Teil B
• 4. Stunde (2010-03-23): Rekursionstheorie: rekursiv impliziert berechenbar
  Im wesentlichen: Seiten 66 bis 67 des Ziegler Skriptums,
  dazu: Universelles Programm impliziert die Unloesbarkeit des Halteproblems
  Handschriftliche Unterlagen: Teil A, Teil B
• 5. Stunde (2010-04-13): Rekursionstheorie: berechenbar impliziert rekursiv (S.68 bis inklusive Beweis von Lem12.6 auf S.70 des Ziegler Skriptums),
  dazu: Berechenbarkeit auf anderen Bereichen, siehe 6. Stunde.
• 6. Stunde (2010-04-20): Rekursionstheorie: das Universelle Programm, Folgerungen: rekursiv impliziert berechenbar, Halteproblem ist unentscheidbar, Normalform fuer rekursive Funktionen. Definition r.e.
  Teil B: 10. Hilbertsches Problem.
  Handschriftliche Unterlagen: Teil A, Teil B (auch fuer 5. Stunde)
• 7. Stunde (2010-04-27): Aequivalente Definitionen von r.e. (Unterlagen).
  Wiederholung Aussagenlogik (Unterlagen, entspricht in etwa dem 2. Teil der Seite 13 des Ziegler Skriptums).
• 8. Stunde (2010-05-04): Praedikatenlokik: Ziegler Skriptum Seiten 3-5.
  Korrektur Rekursionstheorie (Unterlagen).
• 9. Stunde (2010-05-11): Praedikatenlokik: Ziegler Skriptum Seiten 5-10 (bis vor "Definition").
  Teil B: Allgemeines zur Logik (Unterlagen).
• 10. Stunde (2010-05-18): Praedikatenlokik: Ziegler Skriptum Seiten 10-11
  Teil B: Mengenlehre
• 11. Stunde (2010-06-01): Praedikatenlokik: Ziegler Skriptum Seiten 12-14 (bis inkl Lem 3.3)
  Teil B: Mengenlehre
• 12. Stunde (2010-06-08): Praedikatenlokik: Ziegler Skriptum Seiten 14-16 (exkl. Lem 4.2);
  Teil B: Mengenlehre

Repetitorium

Am Donnerstag, dem 6. Mai 2010 von 9:00-12:00 und
am Freitag, dem 7. Mai 2010 von 10:00-12:00
fand ein Repetitorium (=Wiederholung, Pruefungsvorbereitung) zum ersten Teil der Vorlesung, Rekursionstheorie, statt; am Donnerstag 17.6. und am Freitag 18.6., jeweils von 10:00-12:00, zur Praedikatenlogik statt. Ort: Seminarraum des KGRC.