Uni
HH Logo

Vorlesung Mathematische Logik & Mengenlehre
SS 2020
Universität Hamburg
Fachbereich Mathematik

Lehrende. Prof. Dr. Benedikt Löwe
Lucas Wansner
Tim Seifert
Beschreibung.

Mathematik ist eine deduktive Wissenschaft: Aussagen werden nicht durch Beobachtung oder Experimente verifiziert, sondern in axiomatischen Systemen bewiesen. Wir gehen davon aus, dass bewiesene Sätze wahr sind, aber ist auch jeder wahre Satz in einem geeigneten Axiomensystem beweisbar? Und wenn ja, wie entscheiden wir, welches Axiomensystem "geeignet" ist?

Die mathematische Logik beschäftigt sich mit Grundlagenfragen zur mathematischen Methode, der sogenannten Metamathematik. Sie gibt präzise mathematische Definitionen für grundlagentheoretische Begriffe wie "wahr", "formales System" und "beweisbar" und beweist, dass formale Beweisbarkeit in einem axiomatischen System gleichbedeutend mit Wahrheit in allen Strukturen, die diese Axiome erfüllen, ist (der sogenannte Gödelsche Vollständigkeitssatz).

Nachdem man die Grundlagen der axiomatischen Methode gelegt hat, kann man die Mathematik in einem geeigneten grundlagentheoretischen System einfangen: das übliche Axiomensystem für dieses Unterfangen ist die Zermelo-Fraenkelsche Mengenlehre, die wir dann im zweiten Teil der Vorlesung genauer untersuchen werden.

Ablauf.

Die Vorlesung und die Übungen fanden online via Zoom statt. Die Bereitstellung von Informationen und Dateien sowie die Abgabe der Übungsaufgaben fanden über Moodle statt. Klausur und Nachklausur wurden in Präsenz unter Einhaltung der Hygienemaßregeln der Universität Hamburg im Sommer 2020 geschrieben. Diese Webseite wurde im März 2021 aus Moodle extrahiert.

Literatur.

Das Buch Einführung in die Mathematische Logik von Heinz Ebbinghaus, Jörg Flum und Wolfgang Thomas ist über die Bibliothek der Universität Hamburg als e-book verfügbar.

Das Lehrbuch von Heinz Ebbinghaus, Einführung in die Mengenlehre, ist nicht als e-book verfügbar. Allerdings haben uns der Autor und der Verlag freundlicherweise eine PDF-Datei für die Verwendung innerhalb der Vorlesung zur Verfügung gestellt. Diese Datei ist ausschließlich für die Verwendung für Zwecke der Vorlesung und Prüfungsvorbereitung für diese Vorlesung im Sommersemester 2020 bereitgestellt. Es ist unzulässig, nicht erlaubte zusätzliche Vervielfältigungen des Buches herzustellen oder es an Dritte weiter zu verteilen bzw. es öffentlich zugänglich zu machen.

Übungen.

Sie reichen Ihre Lösungen der Übungsaufgaben bitte als eine PDF-Datei ein (eine Datei pro Übungsblatt und Studierender/m). Wenn Sie Ihre Lösungen mit LaTeX tippen, dann haben Sie ohnehin eine PDF-Datei. Sollten Sie Ihre Lösungen handschriftlich machen, so scannen Sie diese Bitte als PDF-Datei ein. Falls Sie keinen Scanner haben, so gibt es verschiedene Scan Apps für das Smartphone, welche Ihr Telefon in einen Scanner verwandeln. Ein Beispiel ist die Adobe Scan App.

Klausur.

Musterklausur. Lösungsvorschlag für die Musterklausur.

V o r l e s u n g e n.
Woche 1.

20. April 2020. Erste Vorlesung. Entwicklung der Logik aus der Philosophie in die Mathematik: Septem Artes Liberales. Leibniz. Calculemus! Boole. Zunehmende Formalisierung der Mathematik im 19. Jahrhundert: Begriff der Gleichmächtigkeit. Cantor. Überabzählbarkeit der Potenzmenge. Frege. Grundgesetz V. Russells Paradox. Vorlesungsnotizen.

22. April 2020. Zweite Vorlesung. Alphabete. Das Alphabet von Sprachen der ersten Stufe. Funktionssymbole, Relationssymbole, Konstantensymbole. S-Terme. Termableitungen. Beweis per Induktion über den Termaufbau. Vorlesungsnotizen.

Übungsblatt #1. Studentische Lösungen zum Übungsblatt 1. In dieser Datei finden sich gute bis sehr gute Lösungen zu den Aufgaben, die von Studierenden abgegeben wurden. Die Autorinnen und Autoren der Lösungen haben zugestimmt, dass sie an dieser Stelle zur Verfügung gestellt werden.

Woche 2.

27. April 2020. Dritte Vorlesung. Anwendungen der Induktion über den Termaufbau: eindeutige Lesbarkeit von Termen. Induktion und Rekursion: informeller Beweis des Rekursionsprinzips. Rekursive Definitionen: die in einem Term auftretenden Variablen. Ausdrücke/Formeln. Formelableitungen. Induktion über den Formelaufbau. Freie Variablen und Sätze. Vorlesungsnotizen.

29. April 2020. Vierte Vorlesung. Semantik: Bedeutung der nichtlogischen Symbole, Bedeutung der logischen Symbole. Diskussion der Diskrepanz zwischen natürlichsprachlicher Interpretation von "und" und "oder" und aussagenlogische Interpretation. Brouwer und die Grundlagenkrise der Mathematik: Bedeutung von "oder" und Beweisbarkeit. Beispiel eines Beweises einer Disjunktion mit Fallunterscheidung, bei dem wir nicht wissen, welcher Fall eintritt. Strukturen, Belegungen, Interpretationen. Gültigkeit / die Modellbeziehung als Relation zwischen Interpretationen und Ausdrücken. Beispiele. Vorlesungsnotizen.

Übungsblatt #2. Studentische Lösungen zum Übungsblatt 2.

Woche 3.

4. Mai 2020. Fünfte Vorlesung. Definitionserweiterungen: durch eine Formel definierte Relationen (s. auch Aufgabe (12)). Die Folgerungsbeziehung. Allgemeingültige Formeln / Tautologien. Logische Äquivalenzen und die Reduktion der logischen Symbole auf Disjunktion, Negation und Existenzquantor (zur Reduktion der Anzahl der Fälle in Induktionsbeweisen). Das Koinzidenzlemma (s. auch Aufgabe (11)). Vorlesungsnotizen.

6. Mai 2020. Sechste Vorlesung. Redukte und Expansionen. Beispiele: Ringe, Ringe mit Eins und Eins-Ringe. Isomorphismen. Das Isomorphielemma. Konsequenzen des Beweises des Isomorphielemmas: definierbare Mengen in einer Struktur sind abgeschlossen unter Automorphismen. Informelle Diskussion von Substrukturen. Vorlesungsnotizen.

Übungsblatt #3. Studentische Lösungen zum Übungsblatt 3.

Woche 4.

11. Mai 2020. Siebte Vorlesung. Substrukturen. Universelle Ausdrücke. Quantorenfreie Ausdrücke. Lemma über die Absolutheit von quantorenfreien Ausdrücken. Substrukturlemma. Substitution: Motivation und Beispiele. Simultane Substitution vs konsekutive Substitution. Definition der Substitutionsfunktion. Vorlesungsnotizen.

13. Mai 2020. Achte Vorlesung. Beispiele für Substitution. Das Substitutionslemma mit Beweis. Mengenlehre: Grundlagen der Mathematik und die Suche nach einer allgemeinen Sprache, in der die unterschiedlichen Gebiete der Mathematik ausgedrückt werden können. Freges Komprehensionsprinzip. Russells Paradox als Theorem über beliebige Strukturen. Vorlesungsnotizen.

Übungsblatt #4. Studentische Lösungen zum Übungsblatt 4.

Woche 5.

18. Mai 2020. Neunte Vorlesung. Die Sprache der Mengenlehre: definierbare Relationen (Teilmenge) und Operationen (Einermenge, Paarmenge, Vereinigung etc.). Der intendierte Mengenbegriff: Abgrenzung zu Tupeln (geordneten Mengen), Multimengen, intensionalen Objekten. Das Axiom der Extensionalität. Das Axiom der leeren Menge. Bildliche Darstellung von Strukturen der Sprache der Mengenlehre als geordnete Graphen. Beispielstrukturen mit einer und zwei Ecken und die in ihnen geltenden Axiome. Eine Beispielstruktur mit vier Knoten, {0,1,2,3}, die Existenz von Potenzmengen in dieser Struktur. Vorlesungsnotizen.

20. Mai 2020. Zehnte Vorlesung. Das Einermengenaxiom. Strukturen, die (Ext)+(LM)+(Einer) erfüllen, sind unendlich. Das Paarmengenaxiom. Axiome und Axiomenschemata. Das Komprehensionsschema und das Russell-Axiom. Das Axiomenschema der Aussonderung. Universelle Mengen. Aussonderung impliziert, daß keine universelle Menge existiert. Weitere Anwendungen des Aussonderungsschemas: Existenz von Schnitten und Differenzen. Vorlesungsnotizen.

Übungsblatt #5. Studentische Lösungen zum Übungsblatt 5.

Woche 6.

25. Mai 2020. Elfte Vorlesung. Vereinigungsmengenaxiome (kleines und großes) und ihr Zusammenhang mit dem Einermengen- und dem Paarmengenaxiom. Das Potenzmengenaxiom. Das Axiomensystem FST der endlichen Mengenlehre. Rekonstruktion der strukturellen Mathematik in FST: was sind Funktionen und Relationen? Was sind geordnete Paare? Das Kuratowski-Paar. Vorlesungsnotizen.

27. Mai 2020. Zwölfte Vorlesung. Definierbarkeit der Begriffe "geordnetes Paar" und "geordnetes Paar mit erster Komponente in A und zweiter Komplenente in B". Definition des kartesischen Produkts. Binäre Relationen zwischen A und B und binäre Relationen auf A. Eigenschaften von Relationen: Reflexivität, Symmetrie, Antisymmetrie, Transitivität, Konnexität, und ihre Definitionen. Partielle Ordnungen, totale Ordnungen, strikte Ordnungen. Äquivalenzrelationen und Äquivalenzklassen. Die Menge aller Äquivalenzklassen. Funktionalität, Funktionen, Injektivität, Surjektivität. Die Menge aller Funktionen von A nach B. Vorlesungsnotizen.

Übungsblatt #6. Studentische Lösungen zum Übungsblatt 6.

1. Juni - 7. Juni 2020. P f i n g s t p a u s e.
Woche 7.

8. Juni 2020. Dreizehnte Vorlesung. Eingeführte Notation für Funktionen. Unendlichkeit: Dedekinds Definition der Unendlichkeit. Induktive Mengen und das Unendlichkeitsaxiom. Konstruktion der Menge der natürlichen Zahlen. Das Induktionsprinzip für die natürlichen Zahlen. Peano-Strukturen und der Beweis, daß die natürlichen Zahlen eine Peano-Struktur sind. Grundlegende Eigenschaften der natürlichen Zahlen. Vorlesungsnotizen.

10. Juni 2020. Vierzehnte Vorlesung. Die Ordnung der natürlichen Zahlen: die strikte Ordnung entspricht der Element-Relation; die Ordnung entspricht der Teilmengen-Relation; der Nachfolger von x ist die kleinste Zahl größer als x. Einfachstes Rekursionstheorem für die natürlichen Zahlen. Definition von Addition und Multiplikation auf den natürlichen Zahlen. Vorlesungsnotizen.

Übungsblatt #7. Studentische Lösungen zum Übungsblatt 7.

Woche 8.

15. Juni 2020. Fünfzehnte Vorlesung. Gleichmächtigkeit; Gleichmächtigkeit auf den natürlichen Zahlen ist Gleichheit. Synthetische / kardinale Definition von Addition und Multiplikation auf den natürlichen Zahlen. Hinzufügen von Inversen zu einem abelschen Monoid: Konstruktion der ganzen Zahlen aus den natürlichen Zahlen (mit Addition) und der rationalen Zahlen aus den ganzen Zahlen (mit Multiplikation). Vollständigkeit (= Dedekind-Vollständigkeit), Dedekind-Schnitte, Dedekind-Vervollständigung einer Ordnung. Definition der reellen Zahlen als Dedekind-Vervollständigung der rationalen Zahlen. Diskussion alternativer Konstruktionen: Körper der Cauchy-Folgen modulo Nullfolgen. Ordnungsinduktion: Beweis, dass Ordnungsinduktion auf den natürlichen Zahlen gilt (vgl. Aufgabe (35)). Satz des kleinsten Elements. Vorlesungsnotizen.

17. Juni 2020. Sechzehnte Vorlesung. Prinzipien: vollständige Induktion, Ordnungsinduktion, kleinstes Element. Äquivalenz des Prinzips der Ordnungsinduktion und des Prinzips des kleinsten Elements. Strukturen, die das Prinzip der Ordnungsinduktion, aber nicht das Prinzip der vollständigen Induktion erfüllen. Fundierte Relationen, Wohlordnungen. Strukturtheorie von Wohlordnungen: Fundamentalsatz über Wohlordnungen (mit Beweis). Vorlesungsnotizen.

Übungsblatt #8. Studentische Lösungen zum Übungsblatt 8.

Woche 9.

22. Juni 2020. Siebzehnte Vorlesung. Die Präordnung der Wohlordnungen ist fundiert. Transitivität von Mengen; äquivalente Formulierungen von Transitivität (ohne Beweis; s. Übungsblatt #9). Ordinalzahlen: grundlegende Eigenschaften. Ordinalzahlen als kanonische Repräsentanten der Isomorphieklassen von Wohlordnungen. Das Induktionsprinzip für Ordinalzahlen. Burali-Forti: es gibt keine Menge aller Ordinalzahlen. Vorlesungsnotizen.

24. Juni 2020. Achtzehnte Vorlesung. Transitive Mengen von Ordinalzahlen sind Ordinalzahlen. Funktionale Formeln. Das Ersetzungsaxiom. Die Mengenlehre ZF0. Beweis (mit Ersetzung), daß ω+ω existiert. Das allgemeine Rekursionstheorem. Nachfolgerzahlen und Limeszahlen. Transfinite Induktion und Rekursion auf den Ordinalzahlen. Ordinalzahladdition und -multiplikation: einige Beispiele, insbesondere 1+ω = ω ≠ ω+1 und 2·ω = ω ≠ ω·2. Vorlesungsnotizen.

Übungsblatt #9. Studentische Lösungen zum Übungsblatt 9.

Woche 10.

29. Juni 2020. Neunzehnte Vorlesung. Die Existenz überabzählbarer Ordinalzahlen: Kodierung von abzählbaren Ordinalzahlen als Teilmengen der natürlichen Zahlen. Der Satz von Hartogs. Das Hartogs-Aleph einer Menge. Die Aleph-Hierarchie: Anfangszahlen; jede Ordinalzahl liegt zwischen zwei Alephs; die Aleph-Hierarchie als Partition der Ordinalzahlen in Intervalle, welche Äquivalenzklassen der Gleichmächtigkeitsrelation sind. Wohlordenbarkeit. Ist jede Menge wohlordenbar? Hilberts Probleme. Vorlesungsnotizen.

1. Juli 2020. Zwanzigste Vorlesung. Äquivalente Beschreibungen von Wohlordenbarkeit. Repräsentationssatz für Wohlordnungen. Das Auswahlaxiom: Auswahlmengen, Auswahlfunktionen. Äquivalenz verschiedener Formulierungen des Auswahlaxioms. Existenz von Auswahlfunktionen für Potenzmengen wohlordenbarer Mengen. Der Zermelosche Wohlordnungssatz. Beweis in ZFC0.  Definition der Kardinalität einer Menge in ZFC0. Vergleichbarkeit von Mengen: der Satz von Cantor-Schröder-Bernstein. Bemerkung (ohne Beweis), daß er in ZF0 bewiesen werden kann. Hinweis auf das Fundierungsaxiom und Aufgabe (53). Cantors Theorem: keine Surjektion von X in Pot(X). Das Kontinuumsproblem: Unlösbarkeit in ZFC. Vorlesungsnotizen.

Übungsblatt #10. Studentische Lösungen zum Übungsblatt 10.

Woche 11.

6. Juli 2020. Einundzwanzigste Vorlesung. Unabhängigkeit und Nichtbeweisbarkeit. Was ist ein Beweis? Verschiedene Formalisierungen: Hilbert-Systeme, Fitch-Systeme, Gentzen-Systeme. Sequenzenkalkül: Sequenzen, Regeln, Kalküle, Korrektheit von Sequenzen, Regeln und Kalkülen. Gentzensche Regeln: Antezedenzregel, Voraussetzungsregel, Fallunterscheidungsregel, Widerspruchsregel. Ableitbare Regeln: modifizierte Widerspruchsregel, Kettenschlußregel. Widerspruchsfreiheit und Widersprüchlichkeit. Vorlesungsnotizen.

8. Juli 2020. Zweiundzwanzigste Vorlesung. Beispiel eines Nichtbeweisbarkeitsbeweises in einem trivialen Kalkül (Kalkül aus (Vor) und (Ant). Weitere Gentzensche Regeln (mit Korrektheitsbeweisen): Oder-Einführung im Antezedens und Sukzedenz, Existenz-Einführung im Antezedens und Sukzedens, Reflexivität der Gleichheit, Substitution. Der Gentzenkalkül. Der Korrektheitssatz. Beweis vs Gegenbeispiel. Der Vollständigkeitssatz (ohne Beweis). Anwendungen des Vollständigkeitssatzes: der Kompaktheitssatz. Anwendungen des Kompaktheitsheitssatzes: jede Menge von Formeln, die beliebig große endliche Modelle hat, hat unendliche Modelle; es gibt keine Axiomatisierung der Klasse aller endlichen Gruppen, Körper, Ringe, Graphen, etc. Vorlesungsnotizen.

Übungsblatt #11. Lösungsvorschläge zum Übungsblatt 11.

Woche 12.

13. Juli 2020. Dreiundzwanzigste Vorlesung. Geordnete Körper und Archimedizität. Die Klasse der archimedischen geordneten Körper ist nicht axiomatisierbar. Nichtarchimedische Körper, deren Theorie die wahre Theorie der reellen Zahlen ist. Beweis des Gödelschen Vollständigkeitssatzes: die Termstruktur und die Terminterpretation. Die Termstruktur von ZFC ist kein Modell von ZFC. Negationstreue und Enthalten von Beispielen. Der Satz von Henkin: Beweisskizze. Zwei Abschlusslemmas aus denen dann der Vollständigkeitssatz folgt (kein Beweis). Vorlesungsnotizen.

15. Juli 2020. Vierundzwanzigste Vorlesung. Der Satz von Henkin: Beweis. Lindenbaums Lemma. Beweis. Skolems Lemma. Beweis (unter Zusatzannahmen). Klassifikation dreier Fälle. Sätze von Löwenheim & Skolem: absteigend und aufsteigend. Vorlesungsnotizen.