 |
Vorlesung & Übung Mathematische Logik & Mengenlehre
SS 2019
Universität Hamburg
Fachbereich Mathematik
|
| LV-Nummer: |
| (Modul WP24) 65-067
|
| Lehrende:
|
| Prof. Dr. Benedikt Löwe,
email:
bloewe@science.uva.nl;
Pascal Gollin,
Lucas Wansner
|
| Inhalt:
|
|
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.
|
| Klausur:
|
| Die Klausur wird am 19. Juli 2019 stattfinden. Um zur Klausur
zugelassen zu werden, müssen folgende Bedingungen erfüllt sein:
- schriftliche Bearbeitung von mindestens der Hälfte der
Übungsaufgaben;
- regelmäßige Anwesenheit und aktive Teilnehme in der
Übungsgruppe (aktive Teilnahme beinhaltet Vorrechnen an der Tafel).
|
|---|
| Ort & Zeit:
|
| Vorlesung:
Montag 16–18 H3, Mittwoch 14–16 H2.
Übung:
Dienstag 10–12 Geom 241 (Gollin);
Dienstag 14–16 Geom 415 (Löwe).
|
|---|
| Mitschrift:
|
| Sowohl Herr Oliver Gertke
als auch Herr Niclas Confurius haben
sich freundlicherweise bereiterklärt, ihre persölichen Mitschriften
allen Vorlesungsteilnehmerinnen und -teilnehmern zur Verfügung zu
stellen. Diese studentische Mitschrift
wird nicht von den Lehrenden korrekturgelesen, aber hier auf dieser
Webseite in ihrer jeweils aktuellsten Form
bereitgestellt:
Mitschrift Gertke;
Mitschrift Confurius.
|
|---|
| Ablauf:
| Montag, 1. April 2019
| Erste Vorlesung. Überblick über die Geschichte der
Logik: Lullus, Leibniz, Babbage, Lovelace, Boole, Schröder, Frege,
Cantor, Hilbert, Gödel, Cohen. Entwicklung der Mathematik im
neunzehnten Jahrhundert: Abstraktion und Präzision. Präzise
Definitionen sind eine notwendige Voraussetzung für negative
Resultate: Nichtbeweisbarkeit, Nichtdefinierbarkeit (limitative
Theoreme). Die Hilbertsche Hoffnung, daß alle mathematische Fragen
lösbar seien: "Wir müssen
wissen, wir werden wissen!" Gödelscher Unvollständigkeitssatz.
Cantors Definition der Gleichmächtigkeit:
Überabzählbarkeit der reellen Zahlen. Kontinuumshypothese.
Unentscheidbarkeit der Kontinuumshypothese in der Standard-Mengenlehre.
|
|---|
| Mittwoch, 3. April 2019
|
Zweite Vorlesung. Logische Symbole, Nichtlogische Symbole: Konstantensymbole, Funktionssymbole,
Relationssymbole. Signaturen und Stelligkeiten. Terme. Induktion über den Termaufbau. Termableitungen.
Übungsblatt #1 (Abgabe: 9. April 2019).
|
| Montag, 8. April 2019 | Dritte Vorlesung. Jeder Term hat eine
Termableitung. Atomare Formeln. Formeln. Induktion über den Formelaufbau. Beispiele für Formeln.
Formelableitungen. Jede Formel hat eine Formelableitung. Rekursion über Term- und Formelaufbau.
Übungsblatt #2 (Abgabe: 16. April 2019).
|
| Mittwoch, 10. April 2019
| Vierte Vorlesung. Rekursionsprinzipien: auf den
natürlichen Zahlen, auf den Termen und auf den Formeln. Beispiele:
die Menge der Variablen, die in einem Term / einer Formel vorkommen; die
Schachtelungstiefe eines Funktionssymbols, die Menge der in einer Formel
freien Variablen. Sätze. Semantik: Strukturen; Beispiele von
Strukturen.
|
| Montag, 15. April 2019
| Fünfte Vorlesung. Belegungen. Interpretationen.
Fortsetzung einer Interpretation auf alle Terme. Definition der Wahrheit
einer Formel in einer Interpretation.
Beispiele.
Wahrheit von Sätzen in einer Struktur.
Koinzidenzlemma (ohne
Beweis; s. Übungsblatt #3). Semantische Folgerungsbeziehung.
Übungsblatt #3 (Abgabe: 23. April 2019).
|
| Mittwoch, 16. April 2019
|
Sechste Vorlesung.
Tautologien.
Axiomatisierbarkeit.
Strukturerhaltende Abbildungen.
Einbettungen.
Isomorphismen.
Unterstrukturen.
Übersetzung von Termen unter strukturerhaltenden Abbildungen.
Quantorenfreie Formeln.
Erhaltung von quantorenfreien Formeln unter Einbettungen.
Universelle Ausdrücke und universelle Sätze.
Erhaltung von universellen Sätzen in Unterstrukturen.
|
| Montag, 22. April 2019
| Ostermontag
|
| Mittwoch, 24. April 2019
| Siebte Vorlesung. Erhaltung von Formeln und Formelklassen.
Elementare Einbettungen. Die Theorie einer Struktur. Vollständige
Satzmengen. Beispiele für unvollständige Satzmengen.
Elementare Äquivalenz. Das Isomorphielemma. Definierbarkeit von
Mengen. Invarianz definierbarer Mengen unter Automorphismen. Beispiele
von nicht-definierbaren Mengen.
Übungsblatt #4 (Abgabe: 30. April 2019).
|
| Montag, 29. April 2019
| Achte Vorlesung. Beispiel zur Definierbarkeit: Redukte der rationalen Zahlen und ihre definierbaren Teilmengen.
Definitionserweiterungen: relationale Definitionserweiterungen und relationale Übersetzungen; das Eliminationslemma (ohne Beweis, s. Aufgabe (21)
auf Übungsblatt #5); Einführung zu funktionalen Definitionserweiterungen.
Übungsblatt #5 (Abgabe: 7. Mai 2019).
|
| Mittwoch, 1. Mai 2019
| Maifeiertag
|
| Montag, 6. Mai 2019
| Neunte Vorlesung (vertreten durch Herrn Gollin).
Funktionale Definitionserweiterungen.
Redukte.
Motivation: das Problem bei Substitutionen.
Die Substitutionsfunktion.
Das Substitutionslemma: Formulierung und Beweisskizze.
Übungsblatt #6 (Abgabe: 14. Mai 2019).
|
| Mittwoch, 8. Mai 2019
| Zehnte Vorlesung. Mengenlehre als Grundlage der Mathematik.
Die Sprache der Mengenlehre LST und LST-Strukturen (gerichtete Graphen).
Die Extension eines Knoten in einem Graphen. Das
Extensionalitätsaxiom. Teilmengen in gerichteten Graphen. Das
Leeremengenaxiom, das Einermengenaxiom, das Paarmengenaxiom.
Gütigkeit der Axiome in einigen einfachen gerichteten Graphen.
Modelle von (LM) und (Einer) können nicht endlich sein. Das
binäre Vereinigungsaxiom, das Vereinigungsaxiom. Das
Aussonderungsschema.
|
| Montag, 13. Mai 2019
| Elfte Vorlesung.
Aussonderung
impliziert (LM).
Das Komprehensionsschema: positive
Konsequenzen (Existenz der leeren Menge, Existenz der Einermenge der
leeren Menge), negative Konsequenzen (Russells Paradox).
Aussonderung impliziert, dass es keine universelle
Menge gibt. Rekursive Konstruktion eines Graphenmodells, in dem (Ext), (Paar)
und (Aus) gelten, aber (Ver) nicht.
Übungsblatt #7 (Abgabe: 21. Mai 2019).
|
| Mittwoch, 15. Mai 2019
| Zwölfte Vorlesung. Beweis des Aussonderungsaxioms und
Widerlegung der Vereinigungsaxioms im Graphenmodell für die
Paarmenge. Das Potenzmengenaxiom. Widerlegung des Potenzmengenaxioms im
Graphenmodell für die Paarmenge. Das Axiomensystem \(\mathsf{FST}\):
Diskussion der Konstruktion eines Modells für \(\mathsf{FST}\) (ohne
Details und Beweis). Das geordnete Paar, kartesische Produkte, Mengen
von Relationen und Funktionen in \(\mathsf{FST}\).
|
| Montag, 20. Mai 2019
| Dreizehnte Vorlesung.
Induktive Mengen und das Unendlichkeitsaxiom. Existenz einer kleinsten induktiven Menge, bezeichnet als \(\mathbb{N}\). Induktionstheorem für \(\mathbb{N}\).
Transitivität von Mengen. Eigenschaften von \(\mathbb{N}\): \(\mathbb{N}\) und seine Elemente sind transitiv und durch die Elementrelation strikt linear geordnet (vgl.
Übungsblatt #8). Rekursionstheorem für \(\mathbb{N}\) (mit Beweis der Eindeutigkeit und der ersten Hälfte des Beweises der Existenz).
Übungsblatt #8 (Abgabe: 28. Mai 2019).
|
| Mittwoch, 22. Mai 2019
| Vierzehnte Vorlesung. Rekursionstheorem für
\(\mathbb{N}\) (Ende des Beweises). Grassmann-Rekursionsgleichungen:
rekursive Definitionen für Addition und Multiplikation. Begriffe
der Endlichkeit und Unendlichkeit und grundlegende Eigenschaften.
Gleichmächtigkeit. Dedekind-Endlichkeit. Abzählbarkeit.
Überabzählbarkeit. Satz von Cantor: keine Menge ist
gleichmächtig zu ihrer Potenzmenge. Frage: gibt es eine unendliche
Menge von Mengen unterschiedlicher unendlicher Mächtigkeiten?
\(\mathbb{N}\) ist Dedekind-unendlich.
|
| Montag, 27. Mai 2019
| Fünfzehnte Vorlesung. \(\mathbb{N}\) ist unendlich.
Funktionale Formeln und das Ersetzungsschema.
Die Zermelo-Fraenkelsche Mengenlehre (ohne Fundierung) \(\mathsf{ZF}_0\).
Stärkere Version des
Rekursionssatz auf den natürlichen Zahlen. Anwendung: eine
unendliche Menge von überabzählbaren Mengen, die paarweise
unterschiedliche Mächtigkeit haben.
Partielle und lineare Ordnungen, Dichtheit und Diskretheit.
Das Prinzip des kleinsten Elements für \(\mathbb{N}\).
Übungsblatt #9 (Abgabe: 4. Juni 2019).
|
| Mittwoch, 29. Mai 2019
| Sechzehnte Vorlesung.
Wohlordnungen: Beispiele und Nichtbeispiele.
Anfangssegmente und echte Anfangssegmente.
Induktionstheorem für Wohlordnungen.
Rekursionstheorem für Wohlordnungen.
Ordnungserhaltende Abbildungen und Isomorphismen und ihre Eigenschaften.
|
| Montag, 3. Juni 2019
| Vorlesung fällt aus.
|
| Mittwoch, 5. Juni 2019
| Siebzehnte Vorlesung
(vertreten durch Herrn Dr. Khomskii).
Hauptsatz über Wohlordungen (ohne Beweis).
Ordinalzahlen: Definition, Beispiele und Eigenschaften.
Nachfolgerordinalzahlen und Limesordinalzahlen.
Hauptsatz über Ordinalzahlen.
Die Ordinalzahlen bilden keine Menge.
Satz von Hartogs.
Induktion und Rekursion auf Ordinalzahlen.
Ordinalzahlarithmetik: Zusammenhang der rekursiven Definitionen mit
der Ordnungssumme und dem Ordnungsprodukt (ohne Beweis).
(Tafelfotos der Vorlesung).
Übungsblatt #10 (Abgabe: 18. Juni 2019).
|
| Montag, 10. Juni 2019
| Pfingstmontag
|
| Mittwoch, 12. Juni 2019
| Pfingstpause
|
| Montag, 17. Juni 2019
| Achtzehnte Vorlesung Wiederholung: Hauptsatz über
Wohlordungen (immer noch ohne Beweis). Ordinalzahlen: Definition,
Beispiele und Eigenschaften. Nachfolgerordinalzahlen und
Limesordinalzahlen. Hauptsatz über Ordinalzahlen. Die Ordinalzahlen
bilden keine Menge, die abzählbaren Ordinalzahlen bilden eine Menge
(Satz von Hartogs). Verallgemeinerung: Hartogs-Alephs. Transfinite
Induktion und Rekursion. Ordinalzahlarithmetik und Beispiele für
die Nichtkommutativität von Addition und Multiplikation.
Übungsblatt #11 (Abgabe: 25. Juni 2019).
|
| Mittwoch, 19. Juni 2019
| Neunzehnte Vorlesung. Ordinalzahlarithmetik: Monotonie,
Nichtkommutativität, rechtsseitige Subtraktion, rechtsseitige
Division mit Rest.
Synthetische
Definition der Ordinalzahladdition und Äquivalenz zur rekursiven
Definition (mit Beweis).
Synthetische Definition der Ordinalzahlmultiplikation und Äquivalenz zur rekursiven Definition
(ohne Beweis).
|
| Montag, 24. Juni 2019
| Zwanzigste Vorlesung (Probevorlesung von Herrn Dr. Khomskii).
Auswahlfunktionen und das Auswahlaxiom. Zermelos Wohlordnungssatz. Satz
von Cantor-Schröder-Bernstein (ohne Beweis). Kardinalitäten
und Kardinalzahlen. Die ℵα: Beweis, daß
jede Kardinalzahl ein Aleph ist.
Übungsblatt #12 (Abgabe:
2. Juli 2019).
|
| Mittwoch, 26. Juni 2019
| Einundzwanzigste Vorlesung. Gerade und ungerade Ordinalzahlen. Beweis, daß κ+κ = κ. Abzählbare Vereinigungen abzählbarer Mengen
sind abzählbar. Satz von Hessenberg (ohne Beweis). Nachfolgerkardinalzahlen \(\kappa^+\) sind nicht Vereinigungen von \(\kappa\) Mengen der Kardinalität
\(\leq\kappa\). Kurze Diskussion der Kardinalität von \(\mathbb{R}\): das Kontinuumsproblem und seine Unlösbarkeit. Das Fundierungsaxiom. Fundierung impliziert,
daß \(x\notin x\) für alle Mengen \(x\). Definition der von Neumann-Hierarchie. Fundierung ist äquivalent dazu, daß jede Menge in einem
\(\mathbf{V}_\alpha\) liegt (ohne Beweis). Das intuitive Bild des Mengenuniversums als kumulative Hierarchie.
|
| Montag, 1. Juli 2019
| Zweiundzwanzigste Vorlesung. Diskussion der Bedeutung des
Vollständigkeitssatzes. Formaler Beweisbegriff: Gentzensche
Sequenzen und ihre Bedeutung. Kalküle und Regeln. Ableitungen und
Ableitbarkeit. Korrektheit von Sequenzen, Regeln und Kalkülen.
Korrektheit von Sequenzenregeln. Die Regeln des Gentzen-Kalküls:
Abschwächungsregel, Voraussetzungsregel, Fallunterscheidungsregel,
Widerspruchsregel. Ableitbarkeit von Regeln.
Übungsblatt #13 (Abgabe:
9. Juli 2019).
|
| Mittwoch, 3. Juli 2019
| Dreiundzwanzigste Vorlesung. Junktorenregeln im Antezedens
und im Sukzedens. Gleichheitsregel. Substitutionsregel. Quantorenregeln
im Antezedens und Sukzedens. Korrektheit des Gentzenkalküls.
Gödelscher Vollständigkeitssatz (ohne Beweis).
Widersprüchlichkeit und Widerspruchsfreiheit.
Konsequenzen des Vollständigkeitssatzes: Kompaktheitssatz.
|
| Montag, 8. Juli 2019
| Vierundzwanzigste Vorlesung. Der Gödelsche
Vollständigkeitssatz ist äquivalent zu: "jede
widerspruchsfreie Satzmenge ist erfüllbar". Weitere Konsequenzen
des Kompaktheitssatzes: Konstruktion nichtarchimedischer Körper;
Konstruktion von Nichtstandardmodellen der Analysis. Das Termmodell:
Motivation und Definition.
|
| Mittwoch, 10. Juli 2019
| Fünfundzwanzigste Vorlesung. Das Termmodell:
Eigenschaften. Das Termmodell für \(\mathsf{ZFC}\) ist kein Modell
von \(\mathsf{ZFC}\). Negationstreue und Enthalten von Beispielen.
Eigenschaften von negationstreuen Satzmengen, die Beispiele enthalten.
Henkins Lemma ("Widerspruchsfreie, negationstreue Satzmengen, die
Beispiele enthalten, sind erfüllbar"). Konstruktion von
negationstreuen Satzmengen, die Beispiele enthalten: Beweis des
Vollständigkeitssatzes für abzählbare Sprachen.
Konsequenz: jede widerspruchsfreie Satzmenge hat ein abzählbares Modell.
Q&A für die Klausur.
|
| Freitag, 19. Juli 2019
| Klausur. 10:00-12:00 (120 Minuten).
|
| Mittwoch, 18. September 2019
| Wiederholungsklausur. 13:00-15:00 (120 Minuten).
|