"Mathematische Logik 002.ps.gz" - читать интересную книгу автора

Vorlesung u"ber Mathematische Logik1

Martin Ziegler

Freiburg SS 1997, SS 2000

1Version 5.1 (3.8.2000)

Inhaltsverzeichnis 1 Pra"dikatenkalku"l 3

1 Strukturen und Formeln . . . . . . . . . . . . . . . . . . . . . . . 3 2 Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Allgemeingu"ltige Formeln . . . . . . . . . . . . . . . . . . . . . . 13 4 Der Go"delsche Vollsta"ndigkeitssatz . . . . . . . . . . . . . . . . . 16 5 Der Sequenzenkalku"l . . . . . . . . . . . . . . . . . . . . . . . . . 24 6 Der Herbrandtsche Satz und automatisches Beweisen . . . . . . . 29

2 Mengenlehre 36

7 Die Axiome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 8 Die natu"rlichen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . 44 9 Ordinalzahlen und Kardinalzahlen . . . . . . . . . . . . . . . . . 48 10 Metamathematik von ZFC . . . . . . . . . . . . . . . . . . . . . . 54

3 Rekursionstheorie 58

11 Registermaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . 58 12 Primitiv rekursive Funktionen und Go"delisierung . . . . . . . . . 64 13 Rekursiv aufza"hlbare Mengen . . . . . . . . . . . . . . . . . . . . 70 14 Go"delnummern von Formeln . . . . . . . . . . . . . . . . . . . . . 72 15 Ein anderer Aufbau der rekursiven Funktionen . . . . . . . . . . 74

4 Arithmetik 76

16 Definierbare Relationen . . . . . . . . . . . . . . . . . . . . . . . 76 17 Das System Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 18 Peanoarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

1

19 Der Go"delsche Unvollsta"ndigkeitssatz . . . . . . . . . . . . . . . . 88 Literaturverzeichnis 89 Index 90 A"nderungen 94

2 Kapitel 1 Pra"dikatenkalku"l

1 Strukturen und Formeln Eine Struktur ist eine nicht-leere Menge mit ausgezeichneten Elementen, Operationen und Relationen. Zum Beispiel

ein Ring: (R; 0; 1; +; \Gamma ; \Delta ) eine Gruppe: (G; e; ffi; \Gamma 1) die reellen Zahlen (R; 0; 1; +; \Gamma ; \Delta ; !) die natu"rlichen Zahlen N = (N; 0; S; +; \Delta ; !)

(S ist die Nachfolgeroperation x 7! x + 1 .)

In diesen Beispielen sind die Relationen zweistellig und die Operationen ein- oder zweistellig. Im Allgemeinen sind beliebige positive Stelligkeiten erlaubt. Nicht alle Gegensta"nde der Mathematik sind Strukturen. Zum Beispiel ist die Klasse aller Gruppen mit der Isomorphie als zweistelliger Relation keine Struktur, weil der Grundbereich -- die Klasse aller Gruppen -- zu gross ist. Eine topologischer Raum ist keine Struktur, auf ihm ist vielmehr eine Menge von (offenen) Teilmengen ausgezeichnet.