- Titel: Mathematische Logik
- Organisation: UNI HEIDELBERG
- Seitenzahl: 248
Inhalt
- I Collegium Logicum
- Die Aussagenlogik
- Syntax der Aussagenlogik
- Definition der aussagenlogischen Formeln
- Induktion und Rekursion
- Beweis durch Induktion über den Formelaufbau
- Definition durch Rekursion über den Formelaufbau
- Semantik der Aussagenlogik
- Wahrheitsfunktionen
- Interpretation von aussagenlogischen Formeln
- Definition der wichtigsten semantischen Begriffe
- Einige wichtige allgemeingültige Formeln
- Einige wichtige Äquivalenzen
- Boolesche Gesetze
- Einsetzungsregel
- Ersetzungsregel
- Normalformen
- Entscheidungsverfahren für Boolesche Normalformen
- Boolescher Repräsentationssatz
- Das Dualitätsprinzip
- Der semantische Folgerungsbegriff
- Zusammenhang zwischen Folgerung und Erfüllbarkeit
- Der syntaktische Folgerungsbegriff
- Axiomensysteme und Beweise
- Korrektheit und Vollständigkeit
- Einige Axiomensysteme der Aussagenlogik
- Vollständigkeit und Kompaktheit
- Verallgemeinerte Expansion
- Lemma über die Negation
- Tautologiesatz
- Deduktionstheorem
- Widerspruchsfreiheit und Vollständigkeit von Theorien
- Lemma über Beweisbarkeit und Konsistenz
- Vervollständigung
- Verallgemeinerter Vollständigkeitssatz
- Kompaktheitssatz der Aussagenlogik
- Strukturen und formale Sprachen
- Strukturen
- Beispiele
- Mehrsortige Strukturen
- Symbole für formale Sprachen
- Unterstrukturen und Morphismen
- Beispiele
- Satz über Unterstrukturen
- Homomorphes Bild, Identifizierung
- Terme einer Sprache
- Interpretation von Termen
- Spracherweiterung durch Namen
- Erzeugte Unterstrukturen
- Formeln einer Sprache
- Beweis durch Induktion über den Formelaufbau
- Freie und gebundene Variable
- Substitution
- Modelle und Theorien
- Das Wahrheitsprädikat
- Satz über neue Konstanten
- Axiome und Theorien
- Der Kompaktheitssatz und einige Folgerungen
- Kompaktheitssatz
- Satz über die Existenz unendlicher Modelle
- Diagramme
- Diagrammlemma
- Universelle Theorien
- Modellerweiterungssatz von Keisler
- Erhaltungssatz für universelle Formeln
- Satz von Los-Tarski
- Einige mathematische Theorien
- Ordnungen
- Gruppen- und Körpertheorie
- Axiomatisierbarkeit
- Zahlentheorie
- Mengenlehre
- Gesetze der Prädikatenlogik
- Ein Axiomensystem für die Prädikatenlogik
- Axiomensystem von Shoenfield
- Definition eines Beweises
- Der Tautologiesatz
- Substitution und universeller Abschluß
- Hintere Generalisierung
- Satz über die Generalisierung
- Substitutionsregel
- Substitutionssatz
- Abschlußsatz
- Ersetzung und Umbenennung, Gleichheit
- Ersetzungstheorem
- Eigenschaften des Gleichheitsprädikates
- Pränexe Normalformen
- Umformungen mit der Negation
- Umformungen mit Konjunktion und Disjunktion
- Umformungen mit der Implikation
- Das Dualitätsprinzip für die Prädikatenlogik
- Das Deduktionstheorem
- Erweiterungen von Theorien, Widerspruchsfreiheit
- Erweiterungen und Expansionen
- Satz über rein sprachliche Erweiterungen von Theorien
- Widerspruchsfrei/widerspruchsvoll
- Beweisbarkeit und Widerspruchsfreiheit
- Termmodelle
- Kanonische Struktur einer Theorie, Termstruktur
- Satz über Termmodelle
- Vervollständigung von Theorien
- Satz von Lindenbaum
- Henkin-Theorien
- Der Gödelsche Vollständigkeitssatz
- Vollständigkeit der Prädikatenlogik / Modellexistenz-Satz
- Satz von Löwenheim
- Kompaktheitssatz
- II Mengenlehre
- Grundlagen der Mengenlehre
- Ordinalzahlen
- Ordnungen
- Definition der Ordinalzahlen
- Satz
- Die Ordnung der Ordinalzahlen
- Mengen und Klassen
- Komprehensionsaxiom
- Auswege aus den Antinomien
- Die mengentheoretische Sprache mit Klassentermen
- Überblick über verschiedene Axiomensysteme
- Extensionalität und Aussonderung
- Relationen und Funktionen
- Vereinigung und Produkt
- Vereinigung
- Potenzmenge und allgemeines Produkt
- Überblick über die ZF-Axiome
- Mengen von Mengen von …
- Induktion und Rekursion
- Ordnungen auf Klassen
- Minimumsprinzip
- Induktionsprinzip für Wohlordnungen
- Segmente
- Rekursionssatz für Wohlordnungen
- Repräsentationssatz für Wohlordnungen
- Transfinite Rekursion
- Die von-Neumannsche Hierarchie
- Die Rolle des Unendlichkeitsaxioms
- PA in mengentheoretischer Sprache
- Die Theorie der endlichen Mengen
- Anwendungen der numerischen Rekursion
- Das Auswahlaxiom
- Zermelos Axiom
- Mengentheoretisch äquivalente Formen
- Der Zermelosche Wohlordnungssatz
- Maximumsprinzipien von Zorn und Hausdorff
- Anwendungen des Auswahlaxioms
- Jeder Vektorraum besitzt eine Basis.
- Der Satz von Hahn-Banach
- Nicht-meßbare Mengen
- Äquivalenz verschiedener Stetigkeitsdefinitionen
- Satz von Tychonoff
- Boolesches Primidealtheorem
- Mächtigkeiten und Kardinalzahlen
- Endliche und abzählbare Mengen
- Abzählbare Mengen
- Überabzählbare Mengen
- Mächtigkeiten
- Satz von Cantor-Schröder-Bernstein
- Vergleichbarkeitssatz von Hartogs
- Satz von Cantor
- Kardinalzahlen
- Operationen auf den Kardinalzahlen
- Satz von Hessenberg
- Satz von Bernstein
- III Grundlagen der Modelltheorie
- Hin und her
- Elementare Äquivalenz
- Die Theorie der dichten linearen Ordnung
- Kategorizität
- Auf und ab
- Elementare Substrukturen
- Diagrammlemma (Fortsetzung)
- Kriterium von Tarski
- Satz von Löwenheim-Skolem-Tarski (abwärts)
- Satz von Löwenheim-Skolem-Tarski (aufwärts)
- Test von Vaught
- Vereinigungen, Durchschnitte und Ketten
- Satz über Ketten von Strukturen
- Satz von Chang- Los-Szusko
- Produkte und Ultraprodukte
- Direktes Produkt
- Filter und Ultrafilter
- Ultrafiltersatz, Boolesches Primidealtheorem
- Reduziertes Produkt
- Satz von Los
- Kompaktheitssatz
- Modellvollständigkeit
- Robinsonscher Test
- IV Unvollständigkeit und Unentscheidbarkeit
- Berechenbare Funktionen
- Turing-Maschinen
- URM-berechenbare Funktionen
- Churchsche These
- Aufzählbarkeitssätze
- Primitiv-rekursive Funktionen
- Rekursive und partiell-rekursive Funktionen
- Partielle Entscheidbarkeit
- Definierbarkeit berechenbarer Funktionen
- Eine endlich-axiomatisierbare Teiltheorie von PA
- Arithmetische Formeln
- Enderweiterungen
- Erhaltungseigenschaften unter Enderweiterungen
- Lemma
- Gödels Lemma
- Definierbarkeitssatz für rekursive Funktionen
- Repräsentierbarkeit
- Die Gödelschen Sätze
- Gödel-Nummern
- Diagonalisierungslemma
- Satz von Gödel-Rosser
- Erster Gödelscher Unvollständigkeitssatz
- Kombinatorische Prinzipien
- Zweiter Gödelscher Unvollständigkeitssatz
- Wahrheit ist nicht arithmetisch definierbar
- Unentscheidbarkeit
- Literatur
Vorschau
Skriptum zur Vorlesung Mathematische Logik
Klaus Gloede Mathematisches Institut der Universit¨ t Heidelberg a Wintersemester 2006/07
INHALTSVER EICHNIS
i
Inhaltsverzeichnis
I Collegium Logicum
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
4 5 5 6 8 9 10 10 11 12 14 14 15 15 16 17 19 20 21 23 24 25 25 26 27 29
1 Die Aussagenlogik 1.1 Syntax der Aussagenlogik . . . . . . . . . . . . . . . . . . . 1.1.1 Definition der aussagenlogischen Formeln . . . . . . . 1.1.2 Induktion und Rekursion . . . . . . . . . . . . . . . . ¨ 1.1.3 Beweis durch Induktion uber den Formelaufbau . . . . ¨ 1.1.4 Definition durch Rekursion uber den Formelaufbau . . 1.2 Semantik der Aussagenlogik . . . . . . . . . . . . . . . . . . 1.2.1 Wahrheitsfunktionen . . . . . . . . . . . . . . . . . . 1.2.2 Interpretation von aussagenlogischen Formeln . . . . . 1.2.3 Definition der wichtigsten semantischen Begriffe . . . 1.2.4 Einige wichtige allgemeing¨ ltige Formeln . . . . . . . u ¨ 1.2.5 Einige wichtige Aquivalenzen . . . . . . . . . . . . . 1.2.6 Boolesche Gesetze . . . . . . . . . . . . . . . . . . . 1.2.7 Einsetzungsregel . . . . . . . . . . . . . . . . . . . . 1.2.8 Ersetzungsregel . . . . . . . . . . . . . . . . . . . . . 1.3 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Entscheidungsverfahren f¨ r Boolesche Normalformen u 1.3.2 Boolescher Repr¨ sentationssatz . . . . . . . . . . . . a 1.3.3 Das Dualit¨ tsprinzip . . . . . . . . . . . . . . . . . . a 1.4 Der semantische Folgerungsbegriff: Erf¨ llbarkeit . . . . . . . u 1.4.1 usammenhang zwischen Folgerung und Erf¨ llbarkeit u 1.5 Der syntaktische Folgerungsbegriff: Beweisbarkeit . . . . . . 1.5.1 Axiomensysteme und Beweise . . . . . . . . . . . . . 1.5.2 Korrektheit und Vollst¨ ndigkeit . . . . . . . . . . . . a 1.5.3 Einige Axiomensysteme der Aussagenlogik . . . . . . 1.6 Vollst¨ ndigkeit und Kompaktheit . . . . . . . . . . . . . . . . a
INHALTSVER EICHNIS
ii
1.6.1 1.6.2 1.6.3 1.6.4 1.6.5 1.6.6 1.6.7 1.6.8 1.6.9
Verallgemeinerte Expansion . . . . . . . . . . . . . . ¨ Lemma uber die Negation . . . . . . . . . . . . . . . Tautologiesatz . . . . . . . . . . . . . . . . . . . . . Deduktionstheorem . . . . . . . . . . . . . . . . . . . Widerspruchsfreiheit und Vollst¨ ndigkeit von Theorien a ¨ Lemma uber Beweisbarkeit und Konsistenz . . . . . . Vervollst¨ ndigung . . . . . . . . . . . . . . . . . . . a Verallgemeinerter Vollst¨ ndigkeitssatz . . . . . . . . . a Kompaktheitssatz der Aussagenlogik . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
31 32 32 33 33 34 35 35 36 37 38 38 39 40 41 43 44 44 45 45 46 47 48 49 50 51 53 53 55 56 57 57 58 59 59
2 Strukturen und formale Sprachen 2.1 Strukturen . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Beispiele . . . . . . . . . . . . . . . . . . . . 2.1.2 Mehrsortige Strukturen . . . . . . . . . . . . . 2.1.3 Symbole f¨ r formale Sprachen . . . . . . . . . u 2.2 Unterstrukturen und Morphismen . . . . . . . . . . . . 2.2.1 Beispiele . . . . . . . . . . . . . . . . . . . . ¨ 2.2.2 Satz uber Unterstrukturen . . . . . . . . . . . 2.2.3 Homomorphes Bild, Identifizierung . . . . . . 2.3 Terme einer Sprache . . . . . . . . . . . . . . . . . . 2.3.1 Interpretation von Termen . . . . . . . . . . . 2.3.2 Spracherweiterung durch Namen . . . . . . . . 2.3.3 Erzeugte Unterstrukturen . . . . . . . . . . . . 2.4 Formeln einer Sprache . . . . . . . . . . . . . . . . . ¨ 2.4.1 Beweis durch Induktion uber den Formelaufbau 2.4.2 Freie und gebundene Variable . . . . . . . . . 2.4.3 Substitution . . . . . . . . . . . . . . . . . . . 3 Modelle und Theorien 3.1 Das Wahrheitspr¨ dikat: Modelle . . . . . . . . . . a ¨ 3.1.1 Satz uber neue Konstanten . . . . . . . . . 3.2 Axiome und Theorien . . . . . . . . . . . . . . . . 3.3 Der Kompaktheitssatz und einige Folgerungen . . . 3.3.1 Kompaktheitssatz . . . . . . . . . . . . . . ¨ 3.3.2 Satz uber die Existenz unendlicher Modelle 3.4 Diagramme . . . . . . . . . . . . . . . . . . . . . 3.4.1 Diagrammlemma . . . . . . . . . . . . . .