Prof Dr Benedikt Loewe: Vorlesung "Modelle der Mengenlehre" (SS 2021)

	Vorlesung Mathematische Logik & Mengenlehre SS 2021 Universität Hamburg Fachbereich Mathematik
Dozent.	Prof. Dr. Benedikt Löwe.
Kursbeschreibung.	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.
Übungsbetrieb.	Es wird wöchentliche Aufgaben geben, die in drei Gruppen fallen: Präsentationsaufgaben, welche in der Übungsgruppe präsentiert werden, aber nicht schriftlich abgegeben werden; Gruppenaufgaben, welche in der Übungsgruppe in kleinen Gruppen (zwei bis drei Studierende) bearbeitet werden; Hausaufgaben, welche schriftlich bearbeitet und abgegeben werden. Die ersten 15 bis 20 Minuten der Übungsgruppe sind der Vorstellung der Präsentationsaufgabe gewidmet. Sie können Ihre Aufgabenlösung entweder alleine oder als Zweiergruppe präsentieren. Teil der Aufgabe ist es, sich zu überlegen, wie man die Präsentation in der Zoom-Übungsgruppe am besten durchführen kann. Um die Zulassung für die Klausur zu erwerben, muß jede Teilnehmerin oder jeder Teilnehmer mindestens eine Präsentationsaufgabe vorgestellt haben. Die Gruppenarbeiten setzen voraus, daß die Studierenden dem Stoff der Vorlesung gefolgt sind, erfordern aber ansonsten keine Vorbereitung. In der Zoom-Sitzung der Übungsgruppe werden Breakout-Räume erzeugt, in die sich die Kleingruppen zurückziehen, um an der Gruppenaufgabe zu arbeiten. Einer der Übungsgruppenleiter wird durch die Breakout-Räume gehen, um Fragen zu beantworten. Um die Zulassung für die Klausur zu erwerben, muß jede Teilnehmerin oder jeder Teilnehmer mindestens an der Hälfte der Gruppenarbeiten teilgenommen haben. Die Hausaufgaben werden nicht korrigiert: jede bearbeitete Aufgabe (unabhängig davon, ob sie korrekt oder inkorrekt bearbeitet wurde) wird gezählt. Wir stellen korrekte studentische Lösungen über Moodle zur Verfügung, so daß Sie überprüfen können, ob Ihre Lösung korrekt war. Um die Zulassung für die Klausur zu erwerben, muß mindestens die Hälfte der Hausaufgaben bearbeitet werden.
Literatur.	Ebbinghaus, Flum, Thomas, Einführung in die Mathematische Logik 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. Der Link verweist auf die relevante Seite des Bibliothekskatalogs Beluga. Klicken Sie auf Volltextzugang Campus. Dieser Link funktioniert nur von einem Rechner der Universität Hamburg oder wenn Sie über VPN mit dem RRZ verbunden sind.
8. April 2021: Erste Vorlesung.	Wie funktioniert mathematische Erkenntnis? Beweise und Gegenbeispiele in der Mathematik. Beweise und Gegenbeispiele in der Umgangssprache. Definitionen: hinreichende und notwendige Bedingungen. Clusterbegriffe. Notwendigkeit der präzisen Definition des Beweises, um die Unbeweisbarkeit einer Aussage zu zeigen. Alphabete, Symbole, Zeichenreihen. Die Kardinalität der Menge der Zeichenreihen über einem höchstens abzählbaren Alphabet. Kodierung von Zeichenreihen durch Primzahlpotenzen. Vorlesungsnotizen.
12. April 2021: Zweite Vorlesung.	Anfangsstücke und echte Anfangsstücke von Zeichenreihen. Das Alphabet der Sprachen der ersten Stufe: logische Symbole und nicht-logische Symbole, Signaturen. Terme, Termableitungen, Ableitbarkeit. Ausdrücke oder Formeln, Formelableitungen, Formelableitbarkeit. Induktion über die Länge der Termableitung. Induktion über den Termaufbau. Vorlesungsnotizen. Übungsblatt #1. (Anmerkung zu P1. Die historisch interessierten unter Ihnen finden unten den Artikel The logic of the nation: nationalism, formal logic, and interwar Poland von David E. Dunning (Stud. Hist. Sc. 17, 2018, 207-251) zur Entwicklung der polnischen Notation.) Lösungsvorschlag für Aufgabe P1. Studentische Lösungen für H1.
15. April 2021: Dritte Vorlesung	Beweis des Prinzips der Induktion über den Termaufbau. Induktion über den Formelaufbau. Beispiele: die leere Zeichenkette ist kein Term und keine Formel, ein einzelnes Funktionssymbol ist kein Term. Eindeutige Lesbarkeit von Termen und Folgen von Termen. Rekursion über den Termaufbau und Rekursion über den Formelaufbau. Beispiele: Länge einer Formel, Anzahl der Vorkommnisse eines Symbols, Schachtelungstiefe, Menge der vorkommenden Variablen, Menge der Teilausdrücke. Vorlesungsnotizen.
19. April 2021: Vierte Vorlesung	Freie Variablen und Sätze. Ausdrücke mit freien Variablen hängen von der Belegung der Variablen ab, Sätze lediglich von der Struktur. Strukturen, Belegungen, Interpretationen. Die Modellbeziehung. Beispiele. Vorlesungsnotizen. Übungsblatt #2. Studentische Lösungen für H2.
22. April 2021: Fünfte Vorlesung	Weiteres ausführliches Beispiel zur Modellbeziehung. Koinzidenzlemma (s. auch Übungsblatt #3). Wahrheit von Sätzen in Strukturen. Die Folgerungsbeziehung: Allgemeingültigkeit, Tautologie, logische Äquivalenz, Erfüllbarkeit. Einbettungen, Isomorphismen, Substrukturen. Quantorenfreie Formeln bleiben unter Einbettungen erhalten. Vorlesungsnotizen.
26. April 2021: Sechste Vorlesung	Bemerkung zur Injektivität von Einbettungen und dem Beweis, daß quantorenfreie Formeln unter Einbettung erhalten bleiben. Universelle Formeln und das dazugehörige Induktionsprinzip. Universelle Algebra: S-Algebren, S-Gleichungen, Gleichungsdefiniertheit, Varietäten. Das Substrukturlemma. Substrukturen und Unterstrukturen in der Algebra (Beispiele: Gruppen, Ringe, Eins-Ringe). Das Isomorphielemma. Substitution: Diskussion des Problems und Motivation. Vorlesungsnotizen. Übungsblatt #3. Studentische Lösungen für H3.
29. April 2021: Siebte Vorlesung	Simultane und sukzessive Substitution. Die Substitutionsfunktion. Drei Beispiele für Substitution. Das Substitutionslemma: Beweis für den Existenzquantor-Fall. Vorlesungsnotizen.
3. Mai 2021: Achte Vorlesung	Teil II: Mengenlehre. Allgemeine Bemerkung zum Ziel der axiomatischen Methode: wir definieren nicht, was eine Menge ist, sondern wie sich Mengen zueinander verhalten; Beispiele: Gruppentheorie, Körpertheorie, Arithmetik, Geometrie. Übliche Symbole in der Mengenlehre. Die Sprache der Mengenlehre LST und ihre Strukturen: gerichtete Graphen. Ein- und zweielementige gerichtete Graphen. Extensionalität vs Intensionalität. Das Extensionalitätsaxiom. Das Leere Mengenaxiom. Das Paarmengenaxiom. Einermengen aus Paarmengen. Zweielementige Strukturen können kein Modell des Paarmengenaxioms sein. Es gibt ein einelementiges Modell des Paarmengenaxioms. Modelle von Leer+Paar sind unendlich (kein Beweis). Teilmengen und das Potenzmengenaxiom. Vorlesungsnotizen. Übungsblatt #4. Studentische Lösungen für H4.
6. Mai 2021: Neunte Vorlesung	Starke und schwache Versionen der Mengenexistenzaxiome. Die schwache Version impliziert nicht die starke Version. Das Axiom der universellen Menge (Univ). Univ impliziert die schwachen Mengenexistenzaxiome. Teilmengen und Potenzmengen in einer Struktur. Das Potenzmengenaxiom. Beweis des Satzes, daß Modelle von Leer+Paar unendlich sind. Das kleine und das große Vereinigungsaxiom. Das Fregesche Komprehensionsschema. Komprehension impliziert Univ. Russells Antinomie: kein Modell erfüllt Komprehension. Das Aussonderungsschema. Aussonderung impliziert, dass die schwachen Mengenexistenzaxiome die starken Mengenexistenzaxiome implizieren; Aus impliziert Leer; Aus impliziert, dass es keine universelle Menge gibt (kein Beweis). Vorlesungsnotizen.
10. Mai 2021: Zehnte Vorlesung	Paar folgt aus Pot und kleiner Vereinigung. Beweis, daß Aus die Negation von Univ impliziert. Das Axiomensystem FST. Lokalendliche Graphen; es gibt einen unendlichen, lokalendlichen Graphen, der ein Modell von FST ist (ohne Beweis). Relationale und funktionale Definitionserweiterungen: Existenz und Eindeutigkeit. Rekonstruktion der Mathematik in FST: geordnete Paare (Kuratowski), kartesische Produkte, Relationen, Funktionen, die Menge alle Funktionen. Existenz dieser Objekte in FST. Vorlesungsnotizen. Übungsblatt #5. Studentische Lösungen für H5.
17. Mai 2021: Elfte Vorlesung	Rekonstruktion der abstrakten Mathematik in FST: Funktionen und ihre Notation, Strukturen, Gruppen, Ordnungen, Äquivalenzrelationen, Äquivalenzklassen, Quotientenstrukturen. Mengen, deren Existenz man in FST widerlegen kann: die Menge aller Mengen, die Menge aller Einermengen, die Menge aller Gruppen. Mengen, deren Existenz in FST nicht garantiert ist: natürliche, ganze, rationale, reelle Zahlen. Konstruktion eines lokalendlichen Graphenmodells von FST. Vorlesungsnotizen. Übungsblatt #6. Studentische Lösungen für H6.
20. Mai 2021: Zwölfte Vorlesung	Unendlichkeit und Dedekind-Unendlichkeit. Das Axiom der Dedekind-Unendlichkeit. Definierbare unendliche Klassen in FST-Modellen. Das Axiom der Unendlichkeit. Die kleinste induktive Menge: die natürlichen Zahlen. Zermelo-induktive Mengen und Zermelo-natürliche Zahlen. Der Satz der vollständigen Induktion. (Grassmann-)Rekursionsgleichungen für die arithmetischen Operationen: Addition und Multiplikation. Das Rekursionstheorem für Funktionen auf den natürlichen Zahlen. Vorlesungsnotizen. Übungsblatt #7. Studentische Lösungen für H7.
27. Mai 2021: Dreizehnte Vorlesung	Peano-Strukturen. Die natürlichen Zahlen sind eine Peano-Struktur. Satz von Dedekind: je zwei Peano-Strukturen sind isomorph. Eigenschaften der natürlichen Zahlen. Die Ordnung der natürlichen Zahlen. Addition und Multiplikation der natürlichen Zahlen und grundlegende Eigenschaften. Vorlesungsnotizen.
31. Mai 2021: Vierzehnte Vorlesung	Eigenschaften der Ordnungen auf den natürlichen Zahlen: Linearität. Ordnungsinduktion und das Prinzip des kleinsten Elements auf den natürlichen Zahlen. Kommutativität der Addition auf den natürlichen Zahlen. Rekonstruktion der ganzen, rationalen und reellen Zahlen aus den natürlichen Zahlen (ohne Details aus der Algebra). Die Zermelo-Mengenlehre reicht aus, um die Objekte der herkömmlichen Mathematik einzufangen, aber diese Objekte sind nur bis auf Isomorphie eindeutig bestimmt. Vorlesungsnotizen. Übungsblatt #8. Übungsnotizen zu Präsentationsaufgabe P8. Studentische Lösungen für H8.
3. Juni 2021: Fünfzehnte Vorlesung.	Fundiertheit. Wohlordnungen. Beispiele und grundlegende Eigenschaften. Anfangsstücke und Anfangsabschnitte. Isomorphismen zwischen Wohlordungen. Der Fundamentalsatz über Wohlordnungen. Vorlesungsnotizen.
7. Juni 2021: Sechzehnte Vorlesung.	Die Einbettungsrelation zwischen Wohlordnungen ist (bis auf Isomorphie) eine Wohlordnung. Wohlordnungsrepräsentantenmengen (WORM) sind durch die Einbettungsrelation wohlgeordnet. Ordinalzahlen: Beispiele; Nachfolger von Ordinalzahlen sind Ordinalzahlen; Elemente von Ordinalzahlen sind Ordinalzahlen; Trichotomoie der Ordinalzahlen. Ordinalzahlen als eindeutige Repräsentanten der Isomorphieklassen von Wohlordnungen (Existenzbeweis fehlt noch). Vorlesungsnotizen. Übungsblatt #9. Studentische Lösungen für H9.
10. Juni 2021: Siebzehnte Vorlesung.	Transitive Mengen von Ordinalzahlen sind Ordinalzahlen. Theorem von Burali-Forti: es gibt keine Menge aller Ordinalzahlen. Wie beweist man die Existenz der Ordinalzahl ω+ω? Das Axiomenschema der Ersetzung. Beweis der Existenz von ω+ω. Der allgemeine Rekursionssatz. Der Repräsentationssatz für Wohlordnungen: jede Wohlordnung ist isomorph zu einer eindeutigen Ordinalzahl. Vorlesungsnotizen.
14. Juni 2021: Achtzehnte Vorlesung.	Bemerkungen zur Notwendigkeit des Ersetzungsaxioms für Theoreme (z.B. den Repräsentationssatz). Nachfolger- und Limesordinalzahlen. Transfinite Induktion und Rekursion. Ordinalzahlarithmetik: Addition und Multiplikation. Beispiele: \(\omega+1\neq 1+\omega\) und \(\omega\cdot 2\neq 2\cdot\omega\). Überabzählbare Ordinalzahlen. Der Satz von Hartogs. Das Hartogs-Aleph \(H_x\). Initiale Ordinalzahlen oder Kardinalzahlen. Suprema von Mengen von Kardinalzahlen sind Kardinalzahlen. Vorlesungsnotizen. Übungsblatt #10. Studentische Lösungen für H10.
17. Juni 2021: Neunzehnte Vorlesung.	Die ersten überabzählbaren Kardinalzahlen und ihre Elemente. Die Kardinalzahl ω1 ist unter Ordinalzahladdition und -multiplikation abgeschlossen. Satz von Hessenberg (ohne Beweis; Verweis auf H10.3). Die Aleph-Hierarchie. Alephs. Charakterisierung der Kardinalzahlen: entweder natürliche Zahlen oder Alephs. Kardinalitäten: Gleichmächtigkeit, Bolzanos Paradox, der Satz von Cantor-Schröder-Bernstein (ohne Beweis). Kardinalitäten sind keine Mengen. Wohlordenbarkeit. Zermelos Wohlordnungssatz (kein Beweis). Vorlesungsnotizen.
21. Juni 2021: Zwanzigste Vorlesung.	Konsequenzen von Wohlordenbarkeit. Cantor-Schröder-Bernstein für wohlordenbare Mengen. Auswahlfunktionen und das Auswahlaxiom. Varianten des Auswahlaxioms: indizierte Auswahlfunktionen und das indizierte Auswahlaxiom; Produktversion des Auswahlaxioms; Auswahlfunktion für Potenzmengen. Zermelos Wohlordnungssatz (Beweis unter Verwendung des Auswahlaxioms). Beweis, daß der Zermelosche Wohlordnungssatz das Auswahlaxiom impliziert. Diskussion der Unabhängigkeit des Auswahlaxioms (ohne Beweis). Wünschenswerte und unerwünschte Konsequenzen des Auswahlaxioms. Das Vergleichbarkeitsprinzip und seine Äquivalenz zum Auswahlaxiom. Bemerkungen: die Kontinuumshypothese und ihre Unabhängigkeit; das Fundierungsaxiom; ZF und ZFC. Vorlesungsnotizen. Übungsblatt #11. Studentische Lösungen für H11.
24. Juni 2021: Einundzwanzigste Vorlesung.	Ein intuitiver formaler Ableitungsbegriff; semantische Folgerung vs syntaktische Folgerung. Korrektheit und Vollständigkeit. Praktische Konsequenzen von Korrektheit (Methode des Gegenbeispiels) und Vollständigkeit (David Hilbert: "Wir müssen wissen. Wir werden wissen"). Regeln, Kalküle, Ableitungen. Beispiele: Termkalkül und Formelkalkül. Gentzenscher Sequenzenkalkül: Sequenzen, Antezedens, Sukzedens, Korrektheit von Sequenzen, Korrektheit von Regeln, Korrektheit eines Kalküls. Endlichkeitssatz, Widersprüchlichkeit, Widerspruchsfreiheit. Vorlesungsnotizen.
28. Juni 2021: Zweiundzwanzigste Vorlesung.	Konsequenzen der Korrektheit und Vollständigkeit eines Kalküls. Endliche Erfüllbarkeit. Der Kompaktheitssatz. Konsequenzen des Kompaktheitssatzes: Nichtaxiomatisierbarkeit von Endlichkeit; Axiomatisierbarkeit von Unendlichkeit; Nichtaxiomatisierbarkeit der Aussage "alle Ketten sind endlich"; Nichtaxiomatisierbarkeit der Peano-Strukturen. Vorlesungsnotizen. Übungsblatt #12. Studentische Lösungen für H12.
1. Juli 2021: Dreiundzwanzigste Vorlesung.	Grenzen der Logik erster Stufe: Definierbarkeit, Axiomatisierbarkeit (\(\Delta\)--Elementarität), endliche Axiomatisierbarkeit (Elementarität). Der Gentzensche Sequenzenkalkül: die elf Regeln und ihre Korrektheit. Beweis der Korrektheit des Gentzenschen Sequenzenkalküls. Vorlesungsnotizen.
5. Juli 2021: Vierundzwanzigste Vorlesung.	Ableitbare Regeln: Modifizierte Widerspruchsregel, Kettenschlußregel. Analyse des Begriffs der Widersprüchlichkeit: Widersprüchlichkeit und Explosivität sind gleichbedeutend. Die Term-Struktur: Definition und grundlegende Eigenschaften. Henkins Idee für den Gödelschen Vollständigkeitssatz: Negationstreue, Beispiele, und Henkin-Mengen; Henkins Lemma (ohne Beweis). Vorlesungsnotizen. Übungsblatt #13.
8. Juli 2021: Fünfundzwanzigste & letzte Vorlesung.	Eigenschaften von Henkin-Mengen. Beweis von Henkins Lemma. Beweis des Gödelschen Vollständigkeitssatzes für abzählbare Sprachen und Satzmengen. Bemerkungen: Verallgemeinerung auf Formelmengen (Beweisidee); Verallgemeinerung auf überabzählbare Sprachen (ohne Beweis); Satz von Löwenheim-Skolem. Anwendung auf die reellen Zahlen: es gibt eine abzählbare zu den reellen Zahlen elementar-äquivalente Struktur. Vorlesungsnotizen.
Klausur: 21. Juli 2021	Am Mittwoch, 21. Juli 2021, von 15:45 Uhr bis 17:45 Uhr wird die Online-Klausur stattfinden. Die Online-Klausur ist eine Koffer-Klausur (open book): Sie dürfen Ihre Notizen sowie Ihre Bücher verwenden. Sie dürfen nicht während der Klausur mit anderen Personen in irgendeiner Form kommunizieren. Sie werden dies in der Form einer handschriftlichen und unterschriebenen Eigenständigkeitserklärung auf ihren Klausurlösungen bestätigen. Das Klausur-Aufgabenblatt wird am Klausurtag hier (unten) als Moodle-Aufgabe zu finden sein und wird exakt um 15:45 Uhr freigeschaltet. Laden Sie das Aufgabenblatt um 15:45 Uhr herunter. Danach können Sie von 15:45 bis 17:45 offline arbeiten. Sie schreiben die Klausur handschriftlich, entweder auf Papier oder auf einer graphischen Oberfläche. Nach Fertigstellung der Klausur erstellen Sie eine einzelne pdf-Datei (Option 1) indem Sie die handschriftlichen Papierseiten fotografieren und mit Hilfe eines Programms in eine einzelne pdf-Datei verwandeln (in diesem Fall achten Sie darauf, daß die Bilder leserlich sind und keine Seite fehlt), oder (Option 2) indem Sie den elektronischen handschriftlichen Text in einer pdf-Datei abspeichern. Diese pdf-Datei laden Sie dann als Abgabe im Moodle hoch. Für die Umwandlung der Klausur in pdf-Format und das Hochladen haben Sie 15 Minuten, so daß Sie bitte bis 18:00 Uhr Ihre Abgabe hochgeladen haben. Sollte es technische Probleme geben, melden Sie sich bitte umgehend per e-mail. Musterklausur. Sie finden hier eine Musterklausur. Lesen Sie insbesondere die Abschnitte Technischer Ablauf und Struktur der Klausur, damit sie gut auf die Klausurform vorbereitet sind. Sorgen Sie dafür, daß Sie die technischen Voraussetzungen bei der Klausur haben (Papier, Stift, Scanner, Smartphone mit Scansoftware, Tablet, Internetverbindung etc.). Musterklausur. Lösung der Musterklausur.
Wiederholungsklausur: 17. September 2021	Am Freitag, 17. September 2021, von 15:45 Uhr bis 17:45 Uhr wird die Online-Wiederholungsklausur stattfinden. Die Online-Wiederholungsklausur ist eine Koffer-Klausur (open book): Sie dürfen Ihre Notizen sowie Ihre Bücher verwenden. Sie dürfen nicht während der Klausur mit anderen Personen in irgendeiner Form kommunizieren. Sie werden dies in der Form einer handschriftlichen und unterschriebenen Eigenständigkeitserklärung auf ihren Klausurlösungen bestätigen. Das Klausur-Aufgabenblatt wird am Klausurtag hier (unten) als Moodle-Aufgabe zu finden sein und wird exakt um 15:45 Uhr freigeschaltet. Laden Sie das Aufgabenblatt um 15:45 Uhr herunter. Danach können Sie von 15:45 bis 17:45 offline arbeiten. Sie schreiben die Klausur handschriftlich, entweder auf Papier oder auf einer graphischen Oberfläche. Nach Fertigstellung der Klausur erstellen Sie eine einzelne pdf-Datei (Option 1) indem Sie die handschriftlichen Papierseiten fotografieren und mit Hilfe eines Programms in eine einzelne pdf-Datei verwandeln (in diesem Fall achten Sie darauf, daß die Bilder leserlich sind und keine Seite fehlt), oder (Option 2) indem Sie den elektronischen handschriftlichen Text in einer pdf-Datei abspeichern. Diese pdf-Datei laden Sie dann als Abgabe im Moodle hoch. Für die Umwandlung der Klausur in pdf-Format und das Hochladen haben Sie 15 Minuten, so daß Sie bitte bis 18:00 Uhr Ihre Abgabe hochgeladen haben. Sollte es technische Probleme geben, melden Sie sich bitte umgehend per e-mail.