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 gültigen 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.

Wir führen zunächst axiomatisch die grundlegenden Begriffe der Mengenlehre (wie Ordinalzahlen, Kardinalzahlen) ein. Sodann werden wir Gödels Konstruktibles Universum L studieren, das benutzt werden kann, um die relative Konsistenz der Kontinuumshypothese zu zeigen. Wir werden schließlich Jensens Überdeckungssatz für L mit einfachen Methoden beweisen. Der Überdeckungssatz sagt, dass L eine gute Approximation an das mengentheoretische Universum ist, falls es keine großen Kardinalzahlen gibt

Erforderliche Vorkenntnisse: Grundbegriffe der Math. Logik. Zeugnis durch mündliche Prüfung.

We shall begin with the study of computability on the natural numbers:

Recursively enumerable sets and partial recursive functions. Index sets. Turing degrees and the jump operator. Post's Problem.

Then we will consider hyperarithmetic theory, a stronger notion of computation with important connections to other areas of logic: Π₁¹ sets, hyperdegrees. The Kleen-Suslin Theorem. Basis theorems.

Das mathematische Modell eines Computers ist die Turing-Maschine. Wir werden die grundlegenden Begriffe wie "Aufzählbarkeit", "Berechenbarkeit" und "Entscheidbarkeit" kennenlernen. Sodann werden wir uns der eher praktischen Frage zuwenden, mit welchem (etwa zeitlichen oder räumlichen) Aufwand ein gegebenes Problem gelöst werden kann. Gegen Ende wird ein Ausblick in die Kryptographie geboten.

Erforderliche Vorkenntnisse: keine. Zeugnis durch mündliche Prüfung.

The course deals with two subjects. The first, intermediate forcing arguments, beginning with the consistency of "all 1 dense sets of reals are isomorphic" and the Shelah club method. We use entangled sets of reals to show that this does not follow from Martin's Axiom alone, and study various forcing axioms leading up to the Open Coloring Axiom and some of its concequences. Second, we introduce the pcf theory of Shelah. Pcf stands for "possible cofinality", this theory has stunning consequences in cardinal arithemetic and combinatorics. We give the simplest known proofs to date of these results.

Students who have any interest in this material are encuraged to send me an email, in german or english.