| INHALTSVERZEICHNIS | öffnen |
Inhaltsverzeichnis
Einleitungxv
Notationenxix
1 Aussagenlogik 1
1.1 Boolesche Funktionen und Formeln 2
1.2 Semantische Äquivalenz und Normalformen 9
1.3 Tautologien und aussagenlogisches Folgern 14
1.4 Ein vollständiger aussagenlogischer Kalkül 18
1.5 Anwendungen des Kompaktheitssatzes 25
1.6 Hilbert-Kalküle 29
2 Prädikatenlogik 33
2.1 Mathematische Strukturen 34
2.2 Syntax elementarer Sprachen 43
2.3 Semantik elementarer Sprachen 49
2.4 Allgemeingültigkeit und logische Äquivalenz 58
2.5 Logisches Folgern und der Theoriebegriff 62
2.6 Spracherweiterungen 67
3 Der Gödelsche Vollständigkeitssatz 71
3.1 Ein Kalkül des natürlichen Schließens 72
3.2 Der Vollständigkeitsbeweis 76
3.3 Erste Anwendungen - Nichtstandardmodelle 81
3.4 ZFC und die Paradoxie von Skolem 87
3.5 Aufzählbarkeit und Entscheidbarkeit 92
3.6 Vollständige Hilbert-Kalküle 95
3.7 Fragmente der 1. Stufe und Erweiterungen 99
4 Grundlagen der Logikprogrammierung 105
4.1 Termmodelle und der Satz von Herbrand 106
4.2 Aussagenlogische Resolution 112
4.3 Unifikation 119
4.4 Logikprogrammierung 122
4.5 Der Beweis des Hauptsatzes 129
5 Elemente der Modelltheorie 131
5.1 Elementare Erweiterungen 132
5.2 Vollständige und k-kategorische Theorien 137
5.3 Das Ehrenfeucht-Spiel 142
5.4 Einbettungs- und Charakterisierungssätze 145
5.5 Modellvollständigkeit 151
5.6 Quantorenelimination 157
5.7 Reduzierte Produkte und Ultraprodukte 163
6 Unvollständigkeit und Unentscheidbarkeit 167
6.1 Rekursive und primitiv-rekursive Funktionen 169
6.2 Gödelisierung 176
6.3 Repräsentierbarkeit arithmetischer Prädikate 182
6.4 Der Repräsentationssatz 189
6.5 Die Sätze von Gödel, Tarski, Church 194
6.6Übertragung durch Interpretation 200
6.7 Die arithmetische Hierarchie 205
7 Zur Theorie der Selbstreferenz 209
7.1 Die Ableitungsbedingungen 210
7.2 Die Theoreme von Gödel und Löb 217
7.3 Die Modallogik G 221
7.4 Modale Behandlung der Selbstreferenz 223
7.5 Eine bimodale Beweislogik für PA 226
7.6 Modale Operatoren in ZFC 228
Lösungshinweise zu den Übungen 231
Literatur 241
Stichwortverzeichnis 247
Symbolverzeichnis 255
[weiter lesen] |
|
|
|
|
| REGISTER | öffnen |
Stichwortverzeichnis
Aa.a. (algebraisch abgeschlossen), 38
- VFormel, VAussage, 54
- V-Theorie, 66
- V 3-Aussage, V 3-Theorie, 148
Abbildung (Funktion), xix
- bijektive, xix
- identische, xix
- injektive, surjektive, xix abelsche Gruppe, 38
- dividierbare, 81
- torsionsfreie, 82
ableitbar, 18, 29
Ableitungsbedingungen, 210
Abschlußaxiome, 200
Abschluss (eines Modells in T), 152
Absorptionsgesetze, 39
Ackermann-Funktion, 175
Algebra, 34
algebraisch, 38
allgemeingültig, 14, 51
allgemeingültigkeitsgleich, 61
Alphabet, xx Anfang, xx, 37
Anfangssequenz, 18
Anfrage, 122
Anordnung, 37
Antivalenz, 2 äquivalent, 9, 51
- in (oder modulo) T, 66
- in einer Struktur, 59
Äquivalenz, 3 Äquivalenzklasse, 41
Äquivalenzrelation, 36
arithmetisch, 184
arithmetische Hierarchie, 205
arithmetisierbar, 177, 194
Artin, 153
assoziativ, xxi aufzählbar, 92, 175
Aussage, 47
Aussagenvariable, 4
- modalisierte, 224
Auswahlaxiom, 90
Auswahlfunktion, xxi Automorphismus, 40
axiomatisierbar, 81
- endlich, rekursiv, 81
Axiomensystem, 65
- logisches, 29, 95
B ß-Funktion, 189
Basisregeln, 18, 72
Basissatz, 140, 161
Baum, 26
Belegung, 7, 49, 221
benachbart, 25
berechenbar, 127, 169
beschränkt, 37
Beweis (formaler), 29, 96
beweisbar, 19, 29
beweisbar rekursiv, 212
Beweislogik, 224
Bild, xix
Birkhoffsche Regeln, 99
Blatt, 113
Boolesche Algebra, 39
Boolesche Basis, 140, 160
Boolesche Funktion, 2
- duale, selbstduale, 12
- lineare, 8
- monotone, 13
Boolesche Kombination, 45
Boolesche Matrix, 40
Boolesche Signatur, 5
CCharakteristik eines Körpers, 39
Chinesischer Restsatz, 189
Church, 92
Churchsche These, 171
Cohen, xviii
D - b-Funktion, 170
- Δ o-Formel, Δ0 -Prädikat, 185
- Δ o-Induktion, 206
Davis, 199
Deduktionstheorem, 16, 31
deduktiv abgeschlossen, 16, 64
definierbar
- (elementar) in einer Struktur, 54
- Δ o-defmierbar, 212
- explizit, implizit, 69
- in Theorien, 211
- mit Parametern, 85
- Ei-definierbar, 212
Definitionsbereich, xix DeJongh, 225
Diagramm, 132
- elementares, 133
- universales, 149
direkte Potenz, 42
Disjunktion, 2
Distributivgesetze, 39
Durchschnitt, xix- 3-abgeschlossen, 155- 3-Formel, 54
- einfache, 158
EEhrenfeucht-Spiel, 142
Einbettung, 40
elementare, 136
Einschränkung, 35
Einselement, 38
Einsetzung, 58, 223
elementar-äquivalent, 55
elementarer Typ, 139
Enderweiterung, 84
endliche Modelleigenschaft, 98
Endlichkeitssatz, 21, 24, 74, 81
entscheidbar, 81, 169
erfüllbar, 14, 51, 65, 112
erfüllbarkeitsgleich, 69
Erfüllungsrelation, 14, 49
Ersetzungstheorem, 10, 59
Erweiterung, 36, 62, 64
- definitorische, 69
elementare, 133
endliche, 65
- konservative, 53, 67
- transzendente, 153
- unmittelbare, 153
existentiell abgeschlossen, 149, 155
Expansion, 36, 62
explizite Definition, 67, 68
Extensionalitätsprinzip, 2
Ff-abgeschlossen, 35
Faktorstruktur, 41
Falsum, 5
fast alle, 48, 163
Fermatsche Vermutung, 199
Fibonacci-Folge, 174
fiktives Argument, 8
Filter, 28
Fixpunktlemma, 194
Folge, xx
Folgerungsrelation
- aussagenlogische, 15
- globale, lokale, 63
- prädikatenlogische, 51
Formel, 4, 45
- arithmetische, 185, 212
- atomare, 45
- Boolesche, 5
- definierende, 67
- duale, 12
- geschlossene, 47
- pränexe, 61
- quantorenfreie (= offene), 45
- repräsentierende, 8, 184, 187
- universale, 54
Formelalgebra, 34
Formelinduktion, 6, 46
Frege, 60
Funktion, xix
- charakteristische, xx
- nstellige, xx
- primitiv-rekursive, 169
rekursive (= m-rekursive), 169 funktional vollständig, 12
- Funktionsterm, 44
GGeneralisierte, 51
Generalisierung, 62
Gentzen-Kalkül, 18
geordnetes Paar, 89
gleichheitsfrei, 80
gleichmächtig, 87
Gleichung, 45
- diophantische, 185, 198
Gödel, xvii, 71, 189, 225
gödelisierbar, 177, 194
Gödelterm, 191
Gödelzahl, 173
- einer Zeichenfolge, 176
- eines Beweises, 177
Graph, 37
- einfacher, 25
- k-chromatischer, 25
- einer Operation, xxi
- planarer, 26
Größenbereich, 38
Grundinstanz, 107, 123
Grundterm, 44
Gruppe, Gruppoid, 38
geordnete, 38
HHalbgruppe, 38
Halbordnung, 37
Halbring, 38
Halbverband, 39
Harrington, 219
Hauptpolynom, 82
Henkin-Menge, 77
Herbrand-Modell, 108
- minimales, 110
Herbrand-Struktur, 108
Herleitung, herleitbar, 19
Hubert, xvii Hilbert-Kalkül, 29, 95
Hilberts Programm, xvii, 168
Homomorphismus, 40
- natürlicher, 41
- strenger, 40
Hörn-Resolution (HResolution), 116
Hornformel, 109
- Basis-Hornformel, 109
- positive, negative, 109
[weiter lesen] |
|
|
|