Vorlesung im Sommersemester 2000
Logik und Grundlagen der Mathematik
Ort und Zeit: Montag und Donnerstag, 13.45 - 15.15 Uhr, D7,27, Raum 103
Die Logik ist einerseits ein Teilgebiet der Mathematik, das sich, wenn es etwa um die
Boolesche Algebra geht, nur wenig von anderen Teilgebieten unterscheidet; andererseits
ist sie auch eines der fundamentalen Werkzeuge der Mathematik.
In der Vorlesung soll zunächst herausgearbeitet werden, wie sich die Grundbegriffe des
logischen Schließens durch eine mathematische Theorie beschreiben lassen. Dabei sollen
neben der klassischen Aussagenlogik auch Alternativen wie etwa modale Logiken vorgestellt
werden sollen. Außerdem geht es um die Wahrheitsdefinitionen von Tarski und von Hintikka.
Ein wesentlicher Teil der Vorlesungen dreht sich um Entscheidbarkeitsprobleme. Hier sind
natürlich die Sätze von Gödel, Turing und anderen zu nennen, aber mindestens genauso
wichtig sind positive Resultate über algorithmische Entscheidbarkeit, die beispielsweise in
der Logikprogrammierung Anwendung finden. Vor allem aber interessieren die Auswirkungen
solcher Sätze auf klassische mathematische Probleme. Unentscheidbarkeiten treten etwa auf
bei der Frage nach der Existenz einer ganzzahligen Lösung einer Polynomgleichung oder der
Gleichheit analytischer Ausdrücke und auch bei der Untersuchung des Langzeitverhaltens
von Lösungen einer Differentialgleichung. Algorithmisch entscheidbar sind unter anderem
die Euklidische Geometrie sowie ein für das praktische Rechnen interessanter Teil der
reellen Zahlen.
Vorläufige Gliederung:
0. Historische Einleitung
a) Die aristotelische Logik
Aussagen, Syllogismen, Grenzen
b) Euklids Elemente
Struktur eines Beweises bei Euklid, die Rolle der Axiome und der Logik
1. Die Sprache der Logik
a) Aussagenlogik
Extensionale Junktoren und ihre Begründung, Wahrheitstafeln,
Normalformen als Beweishilfsmittel
b) Prädikatenlogik
Prädikate, Quantoren, Schlußregeln, das Problem der Gleichheit,
Prädikatenlogiken höherer Stufe
c) Modelle
Theorien und ihre Modelle, der Tarskische Wahrheitsbegriff,
Hintikkas spieltheoretische Semantiken, der Kompaktheitssatz
von Hintikka und Nichtstandardmethoden in der Mathematik
d) Modale Logiken
Das Problem der Implikation, Möglichkeit und Notwendigkeit,
die Modallogiken T, S4, S5 und ihre semantische Interpretation
über mögliche Welten
2. Entscheidungsverfahren
a) Entscheidbarkeit in der Prädikatenlogik erster Stufe
Tableaux, Skolemisierung, Herbrand-Universen, Prolog-Algorithmus
b) Der Satz von Tarski-Seidenberg
Quantorenelimination, berechenbare Zahlen, Entscheidbarkeit algebraischer
Gleichungssysteme, Entscheidbarkeit der Elementargeometrie
3. Unentscheidbarkeitsprobleme
a) Der Unentscheidbarkeitssatz von Gödel
Hilberts Programm, der Satz von Gödel, Turings Beweis einer
Verallgemeinerung, Chaitins quantitative Version
b) Der Satz von Matiyasevich
Hilberts zehntes Problem, diophantische Gleichungen und Mengen,
rekursiv aufzählbare Mengen, jede ist diophantisch, Folgerungen
für die Zahlentheorie, "zufällig richtige" mathematische Aussagen
c) Unentscheidbare Probleme der Analysis
Der Satz von Richardson über die Unentscheidbarkeit der Gleichheit zweier
reeller Zahlen, Unentscheidbarkeit der elementaren Integrierbarkeit,
unentscheidbare Probleme bei Differentialgleichungen, Unentscheidbarkeit
der Mandelbrotmenge
4. Grundlagen der Mathematik
a) Mathematische Erkenntnis in Kants Kritik der reinen Vernunft
Transzendentalphilosophie, analytische und synthetische Erkenntnisse,
Erkenntnisse a priori und a posteriori, Einordnung mathematischer Erkenntnisse
bei Kant, die Hintikka-Parsons-Debatte
b) Die drei Klassiker vom Anfang des zwanzigsten Jahrhunderts
Formalismus, Intuitionismus, Logizismus
c) Benaceraffs Dilemma
Schließen Beweisbarkeit und Wahrheit einander aus?
d) Die Quasi-Empirizismus-Debatte in der zweiten Hälfte des
zwanzigsten Jahrhunderts
Poppers Ansatz für die Wissenschaftstheorie, Lakatos's
Anwendung auf die Mathematik via Beweise und Widerlegungen und
die Methodologie von Forschungsprogrammen,
Gegenpositionen und Vergleich mit der historischen Entwicklung
e) Braucht Mathematik Grundlagen?
Die These von Putnam und anderen, daß es besser geht ohne.