240035 Proseminar Einführung in die Logik (PS) (SoSe 2021)

Was ist eine Aussage? und wann ist eine Aussage wahr?

Wie üblich, läßt die Mathematik Wesensfragen unbeantwortet. Aber sie kann Modelle beisteuern, die wesentliche Aspekte einer Situation erfassen. Formale Logik liefert Modelle für sprachliche Dinge wie Sätze und Bedeutungen. Aufbauend darauf lassen sich dann die Begriffe "Aussage" und "wahr" angehen.

Ein Blick in den Spiegel zeigt, daß wir als Mathematiker ständig Aussagen formulieren und beweisen. Es drängt sich also auf, das entwickelte Modell auf die Aussagen der Mathematik anzuwenden, zum Beispiel um zu klären, was ein Beweis ist. Danach läßt sich unter anderem das interessantes Ergebnis formulieren, daß Wahrheit und Beweisbarkeit nicht zusammenfallen: jedes Axiomensystem für die Zahlentheorie (oder auch die Mengenlehre) ist entweder unvollständig (es gibt wahre Aussagen, die keinen Beweis erlauben) oder widersprüchlich (die Axiome implizieren einen Widerspruch und damit jede beliebige Aussage).

In diesem Themenkreis bewegt sich die Veranstaltung. Stichworte sind:

Aussagenlogik und Prädikatenlogik
Axiomensysteme, Theorien und Modelle
Erfüllbarkeit und Widerspruchsfreiheit
logische Kompaktheit
Widerspruchsfreiheit und Vollständigkeit der Prädikatenlogik erster Stufe
Unvollständigkeit der Arithmetik, Mengenlehre und Prädikatenlogik zweiter Stufe

Vorbesprechung
--------------
Dienstag, 9.2., ab 14:15 via Zoom

geplante Vorträge
-----------------
Woche 01 : Aussagenlogik: Syntax, Semantik, Kompaktheit und Entscheidbarkeit ......................... (2, 1-17) (1, 39-43) (4, A-1)
Woche 02 : Aussagenlogischer Kalkül: Korrektheit und Vollständigkeit ................................. (2, 18-24) (1, 61-74) (4, A-1)
Woche 03 : Prädikatenlogik erster Stufe: Syntax, Semantik, Erfüllbarkeit und Allgemeingültigkeit ..... (3, 3-16) (2, 33-57) (4, A-1)
Woche 04 : Prädikatenlogik erster Stufe: Beweiskalkül nach Gentzen und Schnittelimination ............ (5, 187-197) (7, 103-118) (4, D-2)
Woche 05 : Prädikatenlogik erster Stufe: Vollständigkeit, Kompaktheit, Satz von Löwenheim-Skolem ..... (3, 23-33) (4, A-1)
Woche 06 : Prädikatenlogik erster Stufe: Schnittelimination (modelltheoretisch) ...................... (3, 35-41) (12, 52-65)
Woche 07 : Prädikatenlogik erster Stufe: Satz von Herbrand (modelltheoretisch) ....................... (3, 43-49) (2, 106-111)
Woche 08 : Prädikatenlogik erster Stufe: Satz von Herbrand (beweistheoretisch) ....................... (7, 132-140) (4, D-2)
Woche 09 : Prädikatenlogik zweiter Stufe: Syntax und Semantik, Kategorizität ......................... (8, 140-146)
Woche 10 : Arithmetik: Kategorizität in der Prädikatenlogik zweiter Stufe ............................ (8, 147-152)
Woche 11 : Arithmetik: Nichtkategorizität in der Prädikatenlogik erster Stufe ........................ (8, 152-157)
Woche 12 : Prädikatenlogik zweiter Stufe: Nichtkompaktheit und ....................................... (9, 172-176) (10, 348-354)
Woche 13 : Zweiter Unvollständigkeitssatz: Rekursive Funktionen ...................................... (15) (2, 169-175) (4, D-1)
Woche 14 : Zweiter Unvollständigkeitssatz: Gödelisierung ............................................. (15) (2, 176-188) (4, D-1)
Woche 15 : Zweiter Unvollständigkeitssatz: Beweis .................................................... (15) (2, 189-199) (4, D-1)

Die Angaben in Klammern bezeichnen die Literaturgrundlage: (Nr. von unten, Seiten)

Teilnahmevoraussetzungen, notwendige Vorkenntnisse

Lineare Algebra I und II
Analysis I und II

Literaturangaben

[1] W. Rautenberg: Klassische und nichtklassische Aussagenlogik
[2] W. Rautenberg: Einführung in die mathematische Logik
[3] M. Ziegler: Mathematische Logik
[4] J. Barwise: Handbook of Mathematical Logic
[5] D. van Dalen: Logic and Structure
[6] G. Gentzen: Untersuchungen über das Logische Schließen I und II (Math. Z. 1935)
[7] L. Heindorf: Elementare Beweistheorie
[8] H. Hermes: Einführung in die mathematische Logik
[9] H. Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit
[10] W. Essler / E. Brendel: Grundzüge der Logik II - Klassen . Relationen . Zahlen
[11] P. Halmos: Naive Mengenlehre
[12] W. Pohlers: Proof Theory - The First Step into Impredicability
[13] W. Markwald: Einführung in die formale Logik und Metamathematik
[14] D. Hilbert, W. Ackermann: Grundzüge der theoretischen Logik
[15] K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme