Kurt Gödel Research Center

Lehrveranstaltungen im Wintersemester 1999/2000

Siehe auch den Abschnitt Logik im Vorlesungsverzeichnis der Universität Wien.

Hörsaal Josephinum, Währinger Str. 25

Seminarraum 101, Kurt Gödel Research Center for Mathematical Logic, Josephinum, Währinger Str. 25

• Mathematische Logik I (Mathematical Logic I), Friedman, lecture 4h in English Di 13.30–15.00, Do 13.30–15.00, Seminarraum

Dieser Kurs führt in die grundlegenden Ideen der modernen mathematischen Logik ein. Wir stellen die Logik erster Stufe vor, die als allgemeine Sprache der ganzen Mathematik dient, und beweisen Gödels Vollständigkeitssatz, der impliziert, dass alle wahren Aussagen der Logik durch einen Computer aufgelistet werden können. Auß;erdem präsentieren wir Gödels Unvollständigkeitssatz, der impliziert, dass kein Computer allgemein entscheiden kann, welche Aussagen der Mathematik wahr sind.

Es werden keinerlei Kenntnisse in Logik vorausgesetzt.

• Seminar zu Mathematische Logik I (Seminar for Mathematical Logic I), Schindler, seminar 2h im German Do 15.30–17.00, Seminarraum
• Axiomatische Mengentheorie I (Axiomatic Set Theory I), Zeman, lecture 3h in German Mo 13.15–14.00, Di 11.00–12.30, Seminarraum

Der Schwerpunkt dieses Kurses liegt bei mengentheoretischen Methoden und deren Anwendungen auf Analysis, Topologie des Rⁿ und Kombinatorik. Es werden nur Grundkenntnisse der Analysis vorausgesetzt.

Es werden Grundbegriffe der Mengentheorie wie Mächtigkeit, Wohlordnung, fundierte Relationen und Rekursion, Ordinalzahlen, Auswahlaxiom und Kardinalzahlen ausführlich behandelt. Dann wird das Zermelo-Fraenkelsche Axiomensystem (ZF) eingeführt und der Begriff der Widerspruchsfreiheit erklärt. Im Rahmen von ZF mit Auswahlaxiom (ZFC), bzw. ZFC erweitert um kombinatorische Prinzipien wie Kontinuumshypothese, Diamond, Square oder Martins Axiom, werden zahlreiche kombinatorische Objekte, wie unendliche Bäume, Graphen, Mengen- und Funktionssysteme untersucht und beim Studium der Struktur von R Regularitätseigenschaften von R (Legesque-Messbarkeit, Bairesche Eigenschaft) und Kardinalzahlaritmetik angewandt. Schließ;lich werden "einfachere" Teilmengen von Rⁿ, wie Borelsche und analytische Mengen, betrachtet, durch unendliche Bäume dargestellt und deren Regularitätseigenschaften (auch die "perfect set property") studiert.

• Übung zu Axiomatische Mengentheorie I (Exercises for Axiomatic Set Theory I), Piwinger, exercise 2h in German Mo 14.15–15.45, Seminarraum
• Rekursionstheorie (Recursion Theory), Friedman, lecture 2h in English Mi 13.30–15.00, Seminarraum

Der Begriff einer rekursiven Funktion ist aus Gödels wichtiger Arbeit über die Unvollständigkeit des Axiomensystems erwachsen. Weitere Entwicklungen resultierten in der abstrakten Theorie der Berechenbarkeit. Dieser Kurs stellt die Rekursionstheorie vor, ohne dabei Vorkenntnisse im Bereich der Logik vorauszusetzen. Ein besonderer Schwerpunkt wird auf die Theorie der Turing-Reduzierbarkeit gelegt werden, bei der Mengen danach verglichen werden, wie schwierig sie zu berechnen sind.

• Seminar zu Rekursionstheorie (Seminar for Recursion Theory), Zeman, seminar 1h in German Mi 11.15–12.00, Seminarraum
• Logik für die Informatik (Computer Science Logic), Schindler, lecture 2h in German Mo 14.15–15.45, Hs. Josephinum

Komplexitätstheorie. Die Frage, ob P = NP, ist eine der prominentesten der theoretischen Informatik. Ausgehend von den zentralen Begriffen der Berechenbarkeit und Entscheidbarkeit wollen wir uns etwa der Frage zuwenden, nicht ob eine Aufgabe prinzipiell gelöst werden kann, sondern wieviel Zeit oder Speicherplatz die Lösung eines gegebenen Problems konkret erfordert. Hierzu hat man heute eine Vielzahl von Einsichten gewonnen. Anhand von Beispielen werden insbesondere die Klassen P und NP eingeführt, und es wird die "NP-Vollständigkeit" überraschend einfacher Probleme aufgezeigt.

Die Vorlesung folgt den entsprechenden Abschnitten im sehr lesbaren neuen Buch von Sipser: M. Sipser, Introduction to the theory of computation, Boston 1997.

• Privatissimum: Axiomatische Mengentheorie (Advanced Seminar: Axiomatic Set Theory), Friedman, seminar 2h in English Di 15.30–17.00, Seminarraum
• Seminar für Neuroinformatik (Seminar for Computational Neuroscience), Christian, seminar 2h in German Fr 10.30–12.00, Hs. Josephinum