Mathematische Logik
Anton Deitmar
WS 2016/17
Zuerst Collegium Logicum
Da wird der Geist Euch wohl dressiert,
in spanische Stiefeln eingeschnürt,
daß er bedächtiger so fortan
hinschleiche die Gedankenbahn
und nicht etwa, die Kreuz und Quer,
irrlichteliere hin und her.
(Goethe)
Inhaltsverzeichnis
1
Aussagenlogik und Logik erster Stufe
1.1 Aussagenlogik . . . . . . . . . . . . . . .
1.2 Sprachen der ersten Stufe . . . . . . . .
1.3 Der Begriff der Theorie . . . . . . . . . .
1.4 Strukturen, Interpretation und Modelle
1.5 Herleitungen . . . . . . . . . . . . . . . .
1.6 Der Vollständigkeitssatz . . . . . . . . .
.
.
.
.
.
.
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
8
13
17
22
25
Kapitel 1
Aussagenlogik und Logik erster Stufe
1.1
Aussagenlogik
Die formale Aussagenlogik besteht aus
• einer abzählbaren Menge von Aussagensymbolen A, B, C oder
A1 , A2 , A3 , . . . ,
• Klammern “(” und “)” sowie den Junktoren “¬” und “∨”.
Definition 1.1.1. Eine Aussage ist eine Zeichenkette, die sich aus den
Symbolen der Aussagenlogik zusammensetzt und auf folgende Weise
entsteht (induktive Definition)
• Jedes Aussagensymbol ist eine Aussage,
• Sind A und B Aussagen, so sind (A ∨ B) und (¬A ) Aussagen.
Der Begriff der induktiven Definition beinhaltet, dass jede Aussage
durch endliche Anwendung dieser Prinzipien entsteht.
Lemma 1.1.2. Jede Aussage besitzt genausoviele Linksklammern wie
Rechtsklammern.
3
Logik
4
Eine Aussage kann nur auf genau eine Weise durch sukzessives Anwenden der
Definitionsprinzipien gewonnen werden. Genauer heißt das: Ist C eine
Aussage, dann gilt genau einer der drei Fälle:
(a) C ist ein Aussagensymbol, oder
(b) es gibt genau eine Aussage A mit
C = (¬A ),
oder
(c) es gibt genau ein Paar von Aussagen (A , B), so dass
C = (A ∨ B).
Beweis. Induktion nach der Laenge der Zeichenkette. Wir zeigen
zunaechst, dass jede Aussage A gleichviele Linksklammern wie
Rechtsklammern besitzt. Sei dazu l(A ) die Anzahl der Linksklammern
und r(A ) die Anzahl der Rechtsklammern.
• Ist A ein Aussagensymbol, so besitzt die Formel A weder Linksnoch Rechtsklammern.
• Ist A = (B ∨ C ) mit Formeln B und C , so haben B und C kleinere
Laenge als A , wir koennen also nach Induktionsvoraussetzung
annehmen, dass l(B) = r(B) und ebenso fuer C . Dann folgt
l(A ) = 1 + l(B) + l(C ) = 1 + r(B) + r(C ) = r(A ).
• Ist A = (¬B) fuer eine Formel B, dann koennen wir ebenfalls
nach IV annehmen, dass l(B) = r(B gilt, also ist
l(A ) = 1 + l(B) = 1 + r(B) = r(A ).
Fuer den Beweis der zweiten Aussage beachten wir folgendes: Das
erste Symbol einer Aussage ist entweder ein Aussagensymbol oder eine
Logik
5
Linksklammer. Fuer eine beliebige Zeichenkette Z , ∅ sei der Defekt:
d(Z ) = l(Z ) − r(Z ). Ist dann W , ∅ eine weitere Zeichenkette so dass
A = Z W eine Formel ist, dann gilt d(Z ) > 0. (Dies muss man streng
genommen wieder durch eine Induktion nach der Laenge von A
beweisen.)
Nun koennen wir die zweite Aussage zeigen: Ist die Laenge von C
gleich 1, so ist C ein Aussagensymbol und wir sind fertig. Ist die
Laenge > 1, so muss C mit einer Linksklammer beginnen. Ist das erste
Zeichen nach der Linksklammer ein “¬”, dann kann C nicht von der
Form (A ∨ B) sein, da keine Aussage A mit einem “¬” beginnt. Also
ist C von der Form (¬A ) fuer eine Aussage A , diese ist eindeutig
bestimmt, denn sie entsteht aus C durch Wegnahme der ersten beiden
und des letzten Zeichens. Ist das erste Symbol nach der Linksklammer
kein “¬”, dann muss C von der Form (A ∨ B) sein. Es bleiben zwei
Faelle: ist der erste Zeichen nach der Klammer ein Aussagensymbol,
dann ist A ein Aussagensymbol, welches eindeutig bestimmt ist und
ebenso ist die Ausage B eindeutig bestimmt. Andernfalls ist das erste
Symbol nach der Linksklammer wieder eine Linksklammer, der Defekt
steigt also auf den Wert 2. Das erste Zeichen, das den Defekt wieder auf
1 bringt, muss eine Rechtsklammer sein, die die Formel A beendet.
Damit ist A und also auch B eindeutig bestimmt.
Zur Schreibweise: Wir lassen äußere Klammern meistens weg. Wir
lassen auch innere Klammern manchmal weg, wobei wir vereinbaren,
dass ¬ stärker bindet als ∨, also soll etwa
¬A ∨ B
als (¬A) ∨ B gelesen werden. Innere Klammern können nicht immer
weggelassen werden, denn ¬(A ∨ B) ist durchaus verschieden von
Logik
6
¬A ∨ B.
Definition 1.1.3. Wir führen die folgenden Abkürzungen ein:
A ∧ B steht für ¬(¬A ∨ ¬B)
A → B steht für ¬A ∨ B
Beispiele 1.1.4.
• ¬(A ∨ B) ist eine Aussage, ebenso ist (¬A) ∨ (¬B)
eine Aussage.
• () ∨ ¬ABCD((( ist keine Aussage.
Ferner vereinbaren wir, dass bei gleichen Zeichen Rechtsklammerung
herrscht, also soll
A→B→C→D
dasselbe sein wie
A → (B → (C → D)).
Wahrheitsbelegung
Definition 1.1.5. Eine Wahrheitsbelegung ist eine Funktion W, die
jedem Aussagensymbol einen Wahrheitswert in {w, f } zuordnet, also
eine Abbildung
W : S → {w, f },
wobei S die Menge der Aussagensymbole ist.
Lemma 1.1.6. Ist W eine Wahrheitsbelegung, dann gibt es genau eine
Fortsetzung von W zu einer Abbildung
W : Auss → {w, f },
wobei Auss die Menge der Aussagen ist, so dass gilt
W(¬A ) = w
⇔
W(A ) = f,
Logik
7
W(A ∨ B) = w
⇔
W(A ) = w oder W(B) = w.
Beweis. Wir definieren die Fortsetzung induktiv durch W(A ∨ B) = w
falls W(A ) = w oder W(B) = w und W(A ∨ B) = f andernfalls, sowie
W(¬A ) = f falls W(A ) = w und umgekehrt. Diese Vorschrift liefert per
Induktion eine Fortsetzung, die, was man wieder per Induktion
verifiziert, die Bedingung erfüllt, so dass die Existenz gesichert ist. Man
beachte, dass hier die Eindeutigkeit des induktiven Aufbaus zum
Tragen kommt. Wäre dem nicht so, müsste man an dieser Stelle ein
Wohldefiniertheitsproblem lösen.
Die Eindeutigkeit zeigt man dann ebenfalls über eine (einfache)
Induktion.
Definition 1.1.7. Zwei Aussagen A und B heissen aussagenlogisch
äquivalent, wenn für jede Wahrheitsbelegung W gilt
W(A ) = w
Beispiele 1.1.8.
⇔
W(B) = w.
• Die Aussagen A ∧ (B ∨ C) und (A ∧ B) ∨ (A ∧ C)
sind aussagenlogisch äquivalent. Dies sieht man ein, indem man
die möglichen Werte aller Wahrheitsbelegungen in einer
Wahrheitstafel vergleicht
A B
C B∨C A∧(B∨C) A∧B A∧C (A∧B)∨(A∧C)
w w w
w
w
w
w
w
w w
f
w
w
w
f
w
w
f
w
w
w
f
w
w
w
f
f
f
f
f
f
f
f
w w
w
f
f
f
f
f
w
f
w
f
f
f
f
f
f
w
w
f
f
f
f
f
f
f
f
f
f
f
f
Logik
8
• Die Aussage
A1 → A2 → · · · → An
ist aussagenlogisch äquivalent zu
(A1 ∧ A2 ∧ · · · ∧ An−1 ) → An .
Definition 1.1.9. Eine Tautologie ist eine Aussage A , die unter jeder
Wahrheitsbelegung den Wert w zugewiesen bekommt.
• A ∨ ¬A ist eine Tautologie.
Beispiele 1.1.10.
• Die Aussage
h
i
A ∧ (B ∨ C)
→
h
i
(A ∧ B) ∨ (A ∧ C)
ist eine Tautologie.
• Die Aussage A → (A → B) → B ist eine Tautologie, denn wir haben
uns schon klargemacht, dass diese Aussage äquivalent ist zu
[A ∧ (A → B)] → B
1.2
Sprachen der ersten Stufe
Definition 1.2.1. Die Grundzeichen einer Sprache (erster Stufe) sind
(a) abzählbar viele freie Variablen a1 , a2 , a3 , . . . ,
(b) abzählbar viele gebundene Variablen x1 , x2 , x3 , . . . ,
(c) für jedes n ≥ 0 eine Menge von n-stelligen Funktionszeichen
f, g, f n , gn und eine Menge von n-stelligen Prädikatszeichen
p, q, pn , qn , unter den 2-stelligen Prädikatszeichen das
Gleichheitszeichen “=”,
Logik
9
(d) die Junktoren ¬, ∨ und der Quantor ∀ (für alle).
Die Unterscheidung von freien und gebundenen Variablen ist ein
kleiner Trick, durch den man sich Unannehmlichkeiten erspart.
Beispiele 1.2.2.
• Das zweistellige Funktionszeichen + kommt in der
Sprache der Ringtheorie vor.
• Das zweistellige Prädikatszeichen ≤ kommt in der Sprache der
partiellen Ordnungen vor.
• Ein nullstelliges Funktionszeichen ist dasselbe wie eine Konstante,
etwa e für die Eulerzahl. Nullstellige Prädikatszeichen heissen
auch Aussagezeichen.
Definition 1.2.3. (Induktive Definition der Terme einer Sprache L)
(a) Jede freie Variable ist ein Term von L.
(b) Ist f ein n-stelliges Funktionszeichen und sind t1 , . . . , tn Terme, so ist
f t1 . . . tn ein Term von L.
Ein Term heißt geschlossener Term, wenn er keine Variablen enthält.
Konstanten sind Beispiele geschlossener Terme.
Zur klammerfreien Schreibweise. Als Mathematiker schreiben wir
gern f (t1 , . . . , tn ) statt f t1 . . . tn , das ist aber nur eine andere Schreibweise.
In diesem Skript benutzen wir die klammerfreie Schreibweise, da es
erstens induktive Beweise leichter macht und wir zweitens die
Klammern zu anderen Zwecken brauchen. Wir werden etwa F(a) für
eine Zeichenkette schreiben, in der die Variable a auftauchen kann (oder
auch nicht). Dann bezeichnet F(x) die Zeichenkette, die wir erhalten,
wenn wir jedes Auftreten von a durch x ersetzen. Ist etwa F(a) die
Zeichenkette →= aa = aa, dann ist F(x) die Zeichenkette →= xx = xx.
Logik
10
Man beachte, dass im ersten Abschnitt die Aussagenlogik mit
Klammern eingeführt wurde. Letztenendes ist das Geschmacksfrage,
man kann auch die Aussagenlogik klammerfrei machen, die Tautologie
h
i
A ∧ (B ∨ C)
→
h
(A ∧ B) ∨ (A ∧ C)
i
würde dann etwa
→ ∧A ∨ BC ∨ ∧AB ∧ AC,
was die Lesbarkeit nicht verbessert. Einigen wir uns darauf, theoretisch
eine klammerfreie Schreibweise zu benutzen, dann aber die jeweilige
Schreibweise mit Klammern als Abkürzung für die klammerfreie zu
betrachten.
Beispiele 1.2.4.
• a + b, ab + c sind Terme in der Sprache der Ringe.
Eigentlich müssten wir +ab und + · abc schreiben, aber die
geläufigen Schreibweisen dienen hier als Abkürzung.
• ea ist ein Term in der Sprache der vollständigen geordneten Körper,
wobei wir Freiheit haben, etwa e als Konstante zu definieren und
dann ea = pot(e, a) zu setzen, wobei pot das Zeichen des
Potenzierens sein soll, oder aber ea als e(a) zu interpretieren, wobei
wir e als einstelliges Funktionszeichen verstehen und gelegentlich e
als Abkürzung für e1 = e(1) benutzen.
Definition 1.2.5. Die Primformeln einer Sprache L sind die
Zeichenreihen pt1 . . . tn , wobei p ein n-stelliges Prädikatszeichen und
t1 , . . . , tn Terme von L sind.
Definition 1.2.6. (Induktive Definition der Formeln von L)
(a) Jede Primformel von L ist eine Formel von L.
(b) Sind A und B Formeln von L, so sind auch A ∨ B und ¬A Formeln
von L.
Logik
11
(c) Ist F(a) eine Formel, in der die freie Variable x nicht auftritt, dann ist
∀xF(x) eine Formel von L, wobei F(x) die Zeichenkette bedeutet, die
man erhält, wenn man jedes Auftreten der Variablen a durch x
ersetzt.
Beispiele 1.2.7.
• ∀x = xa ist eine Formel, weil = ba eine Formel ist,
in der x nicht auftritt.
• ∀x∀y = xy ist eine Formel.
• ∀xxy und ∀x∀x = xx sind keine Formeln.
• (∀xF(x)) ∨ (∀xG(x)) ist eine Formel, falls F(a) und G(a) Formeln
sind, in denen x nicht auftritt.
Definition 1.2.8. Eine Sprache L der ersten Stufe besteht aus den
Grundzeichen, den Termen und den Formeln von L.
Definition 1.2.9. Die logischen Grundzeichen einer Sprache L sind
¬, ∨, ∀, = .
Lemma 1.2.10. Haben zwei Sprachen L und L0 dieselben Grundzeichen, so
sind sie identisch.
Beweis. Die Sprachen haben dieselben Grundzeichen. Induktiv folgt,
dass sie dieselben Terme und Formeln haben.
Unsere Formeln sind klammerfrei, was der mathematischen
Gewohnheit widerspricht. Daher führen wir einige Abkürzungen ein:
Logik
12
Definition 1.2.11. Abkürzungen:
(A ∨ B) steht für
∨AB
A → B steht für
(¬A) ∨ B
A∧B
steht für
¬(¬A ∨ ¬B)
A ↔ B steht für (A → B) ∧ (B → A)
∃xF(x) steht für
¬∀x¬F(x)
x=y
steht für
= xy
x,y
steht für
¬(x = y)
Wir lesen auch ∀x F(x) als Abkuerzung fuer ∀x F(x). Desweiteren ist
∀x∈A F(x) eine Abkuerzung fuer ∀x (x ∈ A → F(x)).
Ferner steht auch ∃x F(x) fuer ∃xF(x). Zur Klammerersparnis
vereinbaren wir ausserdem:
(a) Aussenklammern werden meist fortgelassen,
(b) ¬ bindet am stärksten,
(c) ∧, ∨ binden stärker als →, ↔.
Definition 1.2.12. Ist F eine Formel, so sei FV(F ) die Menge der freien
Variablen in F . Ist FV(F ) = ∅, so heißt F eine geschlossene Formel.
Definition 1.2.13 (Allabschluss). Ist B eine Formel mit
FV(B) = {a1 , . . . , an }, dann ist B = F(a1 , . . . , an ). Jede Formel der Art
∀x1 ∀x2 . . . ∀xn F(x1 , . . . , xn )
heißt dann ein Allabschluss von B.
Beispiel 1.2.14. Ist B die Formel a = b, so sind die Formeln ∀x ∀ y x = y
und ∀x ∀ y y = x zwei Allabschlüsse von B.
Logik
1.3
13
Der Begriff der Theorie
Definition 1.3.1. Eine Theorie (der ersten Stufe) ist ein Paar
T = L(T), Ax(T) , bestehend aus einer Sprache L(T) und einer Menge
von Formeln Ax(T). Die Elemente von Ax(T) heissen die Axiome der
Theorie T.
Beispiel 1.3.2. (Gruppentheorie) Die nicht-logischen Zeichen der
Gruppentheorie sind:
• ein 0-stelliges Funktionszeichen, also eine Konstante e,
• ein 1-stelliges Funktionszeichen i und
• ein 2-stelliges Funktionszeichen m.
Wir schreiben t−1 für it und (s · t) für mst und lassen äußere Klammern
fort. Die Axiome der Gruppentheorie sind dann
G1: (a · b) · c = a · (b · c),
G2: a · e = a,
G3: a · a−1 = e.
Diese stehen abkürzend für
G1: = mmabcmambc,
G2: = maea,
G3: = maiae.
Der Nutzen der Abkürzungen dürfte damit klar sein.
Logik
14
Beispiel 1.3.3. (Ringe mit Eins) Die nicht-logischen Grundzeichen der
Theorie TR der Ringe mit Eins sind:
• die Konstanten 0 und 1,
• ein 1-stelliges Funktionszeichen −,
• zwei 2-stellige Funktionszeichen + und ·.
Die Axiome von TR sind
R1 (a + b) + c = a + (b + c),
R2 a + b = b + a,
R3 a + 0 = a,
R4 a + (−a) = 0,
R5 (a · b) · c = a · (b · c),
R6 a · 1 = a ∧ 1 · a = a,
R7 a · (b + c) = a · b + a · c,
R8 (a + b) · c = a · c + b · c.
Streng genommen müssen wir die rechten Seiten von R7 und R8
klammern: (a · b) + (a · c), wir benutzen aber die Konvention, dass ·
stärker bindet als + (Punktrechnung geht vor Strichrechnung). In der
logischen Schreibweise ist das
+ · ab · ac.
Erweitern wir TR um das Axiom
R9 a · b = b · a,
Logik
15
so erhalten wir die Theorie der kommutativen Ringe mit Eins.
Beispiele 1.3.4.
• (Zahlentheorie Z, Peano-Arithmetik) Die
nichtlogischen Grundzeichen von Z sind
– die Konstante 0,
– ein einstelliges Funktionszeichen S und zwei zweistellige
Funktionszeichen + und ·.
Die Axiome von Z sind
¬Sa = 0
Sa = Sb → a = b,
a+0=a
a + Sb = S(a + b)
a·0=0
a · Sb = a · b + a
und für jede Formel F(a), in der x nicht auftritt und in der ausser a
keine freie Variable auftritt, die Formel
F(0)
→
∀x (F(x) → F(Sx))
→
∀x F(x).
Man beachte, dass Z unendlich viele Axiome besitzt. Ferner fällt
auf, dass zum Beispiel das Assoziativgesetz der Addition nicht
verlangt wird. Dies kann man aber mit dem Induktionsschema
herleiten, wie wir später sehen werden, wenn wir definiert haben,
was eine Herleitung ist.
• Die erweiterte Peano Arithmetik entsteht aus Z, wenn man
zusätzlich ein zweistelliges Prädikat < hinzunimmt sowie die
Logik
16
Axiome
(a < b) ∨ (a = b) ∨ (b < a)
¬(a < a)
a < Sb ⇔ (a < b ∨ a = b)
Beispiel 1.3.5. (Theorie LO der linearen Ordnung) Einziges
nichtlogisches Grundzeichen ist ein 2-stelliges Prädikatszeichen <. Wir
schreiben a < b statt < ab. Die Axiome von LO sind
a<b→b<c→a<c
(Transitivität)
¬(a < a)
(Antireflexivität)
(a < b)
∨
(a = b)
∨
(b < a) (Linearität)
Aus LO entsteht die Theorie DLO der dichten linearen Ordnung ohne
Schranken, indem man die folgenden Axiome hinzufügt
a<b
→
∃ y (a < y ∧ y < b),
∃ y y < a,
∃ y a < y.
Definition 1.3.6. Eine Sprache L heißt algebraisch, wenn alle
nichtlogischen Grundzeichen Funktionszeichen sind. Eine Sprache
heißt relational, wenn alle nichtlogischen Grundzeichen Prädikate oder
Konstanten sind.
Beispiele 1.3.7.
• Die Gruppentheorie TG ist algebraisch, ebenso die
Theorie TR der Ringe mit Eins und die Zahlentheorie Z. Die
Ordnungstheorien LO und DLO sind relational.
Logik
1.4
17
Strukturen, Interpretation und Modelle
Definition 1.4.1. Sei L eine Sprache. Eine Struktur A zu L ist ein Tripel
A = (A, F, R) mit
(i) einer nichtleeren Menge A = |A |, genannt die Trägermenge von
A.
(ii) einer Familie F = ( fA ) f ∈L , die zu jedem n-stelligen
Funktionszeichen f von L genau eine n-stellige Funktion auf A
fA : An → A
enthält. Wir identifizieren 0-stellige Funktionen auf A mit ihrem
einzigen Wert in A.
(iii) einer Familie R = (pA )p∈L , die zu jedem n-stelligen nicht-logischen
Prädikatszeichen p von L genau eine n-stellige Relation pA ⊂ An
enthält.
Ist L eine algebraische/relationale Sprache, so nennt man A eine
algebraische/relationale Struktur.
Gruppen, Ringe und Körper sind algebraische Strukturen, geordnete
Mengen relationale.
Definition 1.4.2. Sei A eine Struktur zu L. Man erhält die Sprache L(A )
als Erweiterung von L, indem man zu jedem Element a ∈ |A | eine
Konstante, den Namen von a hinzufügt. Den Namen von a bezeichnen
wir wieder mit a. Dann wird A zu einer L(A )-Struktur erweitert,
indem man dem Namen von a das Element a zuordnet.
Beispiel 1.4.3. Sei L die Sprache der Ringe mit Eins und R der Körper
der reellen Zahlen. Dann enthält L(R) einen Namen für jede Zahl.
Logik
18
Lemma 1.4.4. (Interpretation) Sei A eine Struktur zur Sprache L. Dann gibt
es genau eine Zuordnung, die jedem geschlossenen Term t von L ein Element
A (t) ∈ |A | und jeder Formel F von L einen Wahrheitswert A (F) ∈ {w, f }
zuordnet, derart, dass gilt:
(a) fuer geschlossene Terme gilt
(i) Für c ∈ |A | ist A (c) = c,
(ii) Für jedes n-stellige Funktionszeichen f und geschlossene Terme
t1 , . . . , tn gilt
A ( f t1 . . . tn ) = fA (A (t1 ), . . . , A (tn )).
(b) Fuer Formeln gilt
(i) Sind a1 , . . . , an alle freien Variablen der Formel F = F(a1 , . . . , an ),
dann ist
A (F) = w
⇔
A (F(c1 , . . . , cn )) = w für alle c1 , . . . , cn ∈ |A |.
(ii) sind t1 , . . . , tn geschlossene Terme und p ein Praedikatszeichen, so gilt
A (pt1 . . . tn ) = w
(iii) A (¬A) = w
(v) A (∀x F(x)) = w
(A (t1 ), . . . , A (tn )) ∈ pA ,
A (A) = f ,
⇔
(iv) A (B ∨ C) = w
⇔
⇔
⇔
A (B) = w oder A (C) = w,
A (F(c)) = w für alle c ∈ |A |.
Diese Zuordnung wird die Interpretation der Sprache L(A ) in der Struktur
A genannt.
Beweis. Existenz: Man definiert die Zuordnung A induktiv, indem man
genau die geforderten Eigenschaften zur Definition benutzt. Man
Logik
19
definiert also A (c) B c, falls c ∈ |A | sowie
A ( f t1 . . . tn ) B fA (A (t1 ), . . . , A (tn )) und so weiter. Die Eindeutigkeit des
Aufbaus fuehrt dazu, dass kein Wohldefiniertheitsproblem entsteht.
Eindeutigkeit: Sei A 0 eine zweite solche Zuordnung. Fuer c ∈ |A | gilt
dann A (c) = c = A 0 (c). Sind t1 , . . . , tn geschlossene Terme, fuer die
A (t j ) = A 0 (t j ), j = 1, . . . , n gilt, dann ist
A ( f t1 . . . tn ) = fA (A (t1 ), . . . , A (tn )) = A 0 ( f t1 . . . tn ).
Induktiv folgt hieraus, dass A (t) = A 0 (t) fuer jeden geschlossenen Term
t. Fuer Formeln geht man ebenso vor.
Man beachte, dass für eine Formel F genau dann A (F) = w gilt, wenn
dies für ihren Allabschluss richtig ist.
Lemma 1.4.5. Sei ∀x F(x) eine Formel aus L(A ). Dann gilt
(a) A (∃x F(x)) = w ⇔ A (F(c)) = w für mindestens ein c ∈ |A |.
(b) A ∀x ∀ y F(x) → F(y) → x = y = w
⇔
A (F(c)) = w für höchstens ein c ∈ |A |.
Beweis. (a) ∃x F(x) ist ¬∀x ¬F(x). Also folgt aus der Definition der
Interpretation
A (¬∀x ¬F(x)) = w ⇔ A (∀x ¬F(x)) = f
⇔ A (¬F(c)) = w gilt nicht für alle c ∈ |A |
⇔ A (¬F(c)) = f gilt für mindestens ein c ∈ |A |
⇔ A (F(c)) = w gilt für mindestens ein c ∈ |A |.
Logik
20
(b)
A (∀x ∀ y (F(x) → F(y) → x = y)) = w
⇔ für alle c, d ∈ |A | folgt c = d aus A (F(c)) = A (F(d)) = w
⇔ es gibt höchstens ein c ∈ |A | mit A (F(c)) = w.
Interessanterweise ist also Es gibt (mindestens) ein... eine
Existenzaussage, wohingegen Es gibt höchstens ein... eine Allaussage ist.
Definition 1.4.6. (Modell) Sei T eine Theorie zur Sprache L.
(a) Sei A eine Struktur zu L. Eine Formel B gilt in A oder ist A -gültig,
falls A (B) = w. In diesem Fall schreiben wir
A |= B
und lesen dies als “in A gilt B”.
(b) Eine Struktur A ist ein Modell von T, wenn jedes Axiom von T in
A gilt.
(c) Eine Formel B gilt in der Theorie T, wenn B in jedem Modell gilt.
Wir schreiben dann
T |= B.
Beispiele 1.4.7.
• Die Modelle der Gruppentheorie sind genau die
Gruppen, die Modelle der Ringtheorie sind genau die Ringe.
• Die Menge der natürlichen Zahlen mit Null: N0 ist ein Modell der
Zahlentheorie. Dies ist das Standardmodell der Zahlentheorie. Es
gibt aber noch weitere Modelle, wie wir später sehen werden.
Definition 1.4.8. Sei A eine Struktur zur Sprache L. Die Theorie
T(A ) = TL (A ) von A ist die Theorie zur Sprache L, deren Axiome
Logik
21
genau alle in A wahren Formeln sind:
n
o
Ax(T(A )) = C : C ist eine Formel aus L mit A (C) = w .
Lemma 1.4.9. Sei A eine Struktur zur Sprache L.
(a) A ist ein Modell von T(A ).
(b) Für jede Formel C aus L gilt
A |= C ⇔ C ∈ Ax(T(A ))
⇔ T(A ) |= C.
Beweis. (a) Die Axiome von T(A ) gelten nach Definition in A .
(b) Die erste Äquivalenz ist die Definition von Ax(T(A )). Zur zweiten:
Ist C ein Axiom von T(A ), dann gilt C in jedem Modell, also folgt
T(A ) |= C, d.h., C gilt in T(A ). Umgekehrt: gilt C in T(A ), dann gilt C in
jedem Modell, also insbesondere gilt C in A und damit liegt C nach
Definition in Ax(T(A )).
Bemerkung 1.4.10. (Sprachabhängigkeit der Theorie T(A ))
Man beachte, dass T(A ) = TL (A ) essentiell von der Sprache L abhängt
und sich zum Beispiel von TL(A ) (A ) unterscheidet. Wir machen das an
einem Beispiel klar. Sei L die logische Sprache, also ohne alle
nichtlogischen Grundzeichen. Jede Menge A definiert dann eine
L-Struktur. Sei A eine L-Struktur mit überabzählbarer Trägermenge
A = |A |. Da wir nur das Prädikat = haben und keine Funktionszeichen,
können wir in L nicht so viele interessante Formeln hinschreiben und
man macht sich klar, dass eine Formel in dieser Sprache, die in A gilt, in
jeder unendlichen Menge gilt. Wir brauchen eine unendliche Menge,
Logik
22
weil wir ja zum Beispiel für jedes n die Formel
∀x1 . . . ∀xn ∃ y y , x1 ∧ · · · ∧ y , xn
haben, die sichert, dass jedes Modell von TL (A ) unendlich ist. Da wir
aber mit unseren Formeln immer nur endliche Sachverhalte
ausdrücken können, ist es auch so, dass jede abzählbar unendliche
Menge ein Modell für TL (A ) ist.
Betrachten wir dieselbe Situation in der Sprache L(A ), so sieht die
Sache anders aus: Wir haben einen Namen a für jedes a ∈ A und die
unendlich vielen Formeln
a,b
für a , b in A gelten in A . Also gelten sie in jedem Modell von
TL(A ) (A ), woraus folgt, dass jedes Modell dieser Theorie eine
Kardinalität ≥ |A| haben muss.
1.5
Herleitungen
Definition 1.5.1. Sei F(A1 , . . . , An ) eine aussagenlogische Tautologie, die
ausser den Aussagenvariablen A1 , . . . , An nur noch die logischen
Junktoren ∨ und ¬ enthält. Sind dann Q1 , . . . , Qn Formeln in der
Sprache L, dann nennen wir
F(Q1 , . . . , Qn )
eine Tautologie in der Sprache L.
Definition 1.5.2. Die Logischen Axiome sind
1. alle Tautologien A der Sprache L,
(Tautologien)
Logik
23
2. alle Formeln
∀x F(x) → F(t),
wobei t ein Term ist,
(Ersetzungsregel)
3. alle Formeln
(∀x (A → B)) → (∀x A) → (∀x B),
(∀-Verteilung)
4. falls x nicht in F(a) auftritt,
F(a) → ∀x F(x)
für jede freie Variable a,
(Verallgemeinerung)
5. alle Formeln t = t für Terme t,
(Gleichheit)
6. alle Formeln
s = t → A → A0 ,
wenn A0 aus A entsteht, indem man an einigen Stellen s durch t
ersetzt. Hierbei sind s und t Terme.
(Termersetzung)
Wir schreiben
Ax(Log)
für die Menge der logischen Axiome.
Bemerkung 1.5.3. Die logischen Axiome gelten in allen Strukturen zur
Sprache L.
Definition 1.5.4. (Modus Ponens) Wir sagen, eine Formel B entsteht
durch Modus Ponens aus einer Formelmenge ∆, wenn ∆ die Formeln
A → B und A enthält. Wir schreiben dies als
(A → B, A)
`
B.
Logik
24
Definition 1.5.5. (Herleitung) Sei ∆ eine Menge von Formeln und sei F
eine Formel. Eine Herleitung von F aus ∆ ist eine Folge (F1 , . . . , Fn ) von
Formeln, so dass Fn = F gilt und für jedes j = 1, . . . , n die Formel F j
durch Modus Ponens aus den logischen Axiomen und (∆, F1 , . . . , F j−1 )
entsteht.
Wir sagen, F ist aus ∆ herleitbar, falls eine Herleitung aus ∆ existiert.
Wir schreiben dafür auch
∆
`
F.
Lemma 1.5.6. (a) Ist A ∈ ∆, dann gilt ∆
(b) Gilt ∆
`
`
A.
F, so gibt es eine endliche Teilmenge ∆0 ⊂ ∆, so dass ∆0
`
F.
Beweis. (a) Sei A ∈ ∆. Die Tautologie A → A ist herleitbar und daher ist
nach dem Modus Ponens ∆
`
A.
(b) Da eine Herleitung nur endlich viele Modus Ponens Schritte hat,
werden in ihr auch nur endlich viele Formeln aus ∆ benötigt.
Definition 1.5.7. Ist T eine Theorie und F eine Formel in der Sprache
von T, so schreiben wir
T
falls Ax(T)
`
`
F,
F, also falls die Formel F aus den Axiomen von T
herleitbar ist.
Satz 1.5.8 (Korrektheitssatz). Ist eine Formel herleitbar, dann gilt sie in
jedem Modell, also
T
`
F
⇒
T |= F.
Beweis. Sei F eine herleitbare Formel und sei (F1 , . . . , Fn ) eine Herleitung.
Wir beweisen den Satz durch Herleitungsinduktion, also Induktion
Logik
25
nach n. Ist n = 1, so entsteht F durch Modus Ponens aus logischen
Axiomen oder Axiomen von T, also etwa (A, A → F)
`
F. Da A und
A → F dann in allen Modellen gelten, gilt auch F in allen Modellen. Im
Induktionsschluss schliesst man ebenso, nur dass dann die Gültigkeit
von A und A → F aus der Induktionsvoraussetzung gefolgert wird.
Definition 1.5.9. Eine Theorie T heißt widersprüchlich, falls es eine
Formel F gibt, so dass in T sowohl F als auch ¬F herleitbar sind.
Eine Theorie heißt konsistent, wenn sie nicht widersprüchlich ist.
Korollar 1.5.10. Hat eine Theorie T ein Modell, so ist sie konsistent.
Beweis. Sei A ein Modell. Wäre T widersprüchlich, so gäbe es eine
Formel F, so dass F und ¬F beide herleitbar wären. Dann gölten aber
auch beide in A , was nach dem Korrektheitssatz dazu führt, dass A (F)
gleichzeitig w und f ist, was nicht sein kann.
1.6
Der Vollständigkeitssatz
Satz 1.6.1 (Vollständigkeitssatz). (a) Ist eine Theorie T konsistent, dann
hat sie ein Modell.
(b) Gilt eine Formel F in allen Modellen von T, dann ist sie auch herleitbar,
also
T |= F
⇒
T
`
F.
Korollar 1.6.2 (Ex falso quodlibet). Ist eine Theorie widersprüchlich, so
kann man jede Formel in ihr herleiten.
Logik
26
Beweis des Korollars. Ist T widersprüchlich, dann hat sie nach Korollar
1.5.10 kein Modell. Ist F irgendeine Formel in der Sprache von T, dann
gilt F in allen Modellen von T (denn es gibt ja keine). Damit ist F nach
dem Satz herleitbar.
Der Beweis des Satzes wird den Rest des Abschnitts in Anspruch
nehmen.
Definition 1.6.3. Sind α1 , . . . , αn , β Formeln, so sagen wir, dass
(α1 , . . . , αn ) die Formel β tautologisch impliziert, falls die Formel
α1 → α2 → · · · → αn → β eine Tautologie ist.
Lemma 1.6.4. Sind α1 , . . . , αn in T herleitbar und ist β von ihnen
tautologisch impliziert, so ist auch β in T herleitbar.
Beweis. Da α1 → α2 → · · · → αn → β eine Tautologie ist, ist es herleitbar.
Nun braucht man nur noch wiederholt den Modus Ponens
anzuwenden und erhält eine Herleitung für β.
Lemma 1.6.5 (Deduktionslemma). Gilt (∆, A)
∆
`
`
B, so gilt auch
A → B.
Beweis. Wir setzen der Einfachheit voraus, dass ∆ alle logischen
Axiome enthält. Wir zeigen durch Induktion über Herleitungsslänge,
dass A → B herleitbar ist. Sei (F1 , . . . , Fn = B) eine Herleitung von B. Sei
der letzte Schluss von (∆, A)
`
B der Modus Ponens (C, C → B)
`
B.
Damit liegen die Formeln C, C → B beide in (∆, A, F1 , . . . , Fn−1 ). Ist
C ≡ A, dann ist A → B in (∆, F1 , . . . , Fn−1 ) und damit nach Induktion aus
∆ herleitbar und wir sind fertig. Ist andererseits (C → B) ≡ A, dann ist
A → B dasselbe wie (C → B) → B. Die Formel C muss dann in
(∆, F1 , . . . , Fn−1 ) liegen, ist also aus ∆ herleitbar. Nun ist
C → (C → B) → B
Logik
27
eine Tautologie (Beispiel 1.1.10) und damit aus ∆ herleitbar, so dass
nach einem Modus Ponens die Formel (C → B) → B aus ∆ herleitbar ist.
Es bleibt der Fall, dass A verschieden von beiden C und (C → B) ist. In
diesem Fall liegen diese beiden Formeln also schon in (∆, F1 , . . . , Fn−1 ),
sind nach Induktionsvoraussetzung also aus ∆ herleitbar, daher ist
auch B aus ∆ herleitbar.
Lemma 1.6.6 (Reductio ad absurdum). Ist ∆ ∪ {A} nicht konsistent, dann
folgt ∆
`
¬A.
Beweis. Nach Definition gibt es eine Formel B, so dass in (∆, A) sowohl
B als auch ¬B herleitbar ist. Nach dem Deduktionslemma folgt, dass in
∆ sowohl A → B als auch A → ¬B herleitbar ist. Nun ist aber
(A → B) → (A → ¬B) → ¬A
eine Tautologie! Also folgt nach der tautologischen Implikation, dass
∆
`
¬A.
Definition 1.6.7. Eine Formelmenge Σ zu einer Sprache L heißt
maximalkonsistent, wenn sie maximal ist in der Menge aller
konsistenten Formelmengen zu L.
Lemma 1.6.8. (a) Eine konsistente Formelmenge Σ ist genau dann
maximalkonsistent, wenn für jede Formel F in der Sprache L gilt
L ∈ Σ oder ¬L ∈ Σ.
(b) Zu jeder konsistenten Formelmenge ∆ einer Sprache L gibt es eine
maximalkonsistente Formelmenge Σ, die ∆ enthält.
Beweis. (a) Sei Σ maximalkonsistent und F eine Formel der Sprache L.
Da Σ maximal ist, folgt: F ∈ Σ oder (Σ, F) ist nicht konsistent. Im
Logik
28
zweiten Fall folgt nach dem letzten Lemma, dass Σ
`
¬F und damit ist
(Σ, ¬F) konsistent, so dass wieder aus der Maximalität ¬F ∈ Σ folgt.
(b) Sei S die Menge aller konsistenten Formelmengen Σ ⊃ ∆. Wir wollen
das Lemma von Zorn auf S anwenden. Ist K ⊂ S eine linear geordnete
S
Teilmenge, dann behaupten wir, dass M = Σ∈K Σ immer noch
konsistent ist. Angenommen, M ist nicht konsistent, es gibt also eine
Formel A mit M
`
A und M
`
¬A. Nach Lemma 1.5.6 gibt es eine
endliche Teilmenge M0 von M so dass M0
`
A und M0
`
¬A. Da K
linear geordnet, gibt es ein Σ ∈ K so dass Σ ⊃ M0 , damit ist Σ aber
widersprüchlich, im Widerspruch zur Annahme.
Es folgt also, dass M konsistent ist, damit erfüllt S die Kettenbedingung,
hat also nach Zorns Lemma ein maximales Element Σ.
Lemma 1.6.9 (Verallgemeinerung). Es gelte ∆
`
F(c), wobei c ein
Konstantensymbol ist, das in keiner Formel von ∆ auftritt, dann gibt es eine
gebundene Variable x, die nicht in F(c) auftritt, so dass ∆
`
∀x F(x) gilt.
Ferner gibt es eine Herleitung für ∀x F(x), in der c nicht auftritt.
Beweis. Induktion über die Herleitung von F(c). Sei a eine freie Variable,
die in F(c) nicht auftritt. Ist F(c) ein logisches Axiom, dann ist auch F(a)
eines und damit ohne c herleitbar. Das logische Axiom Nummer 4
besagt F(a) → ∀x F(x) und damit ist mit Modus Ponens auch ∀x F(x) ohne
c herleitbar.
Der Fall F(c) ∈ ∆ tritt nicht auf, da keine der Formeln in ∆ die Konstante
c enthaelt.
Induktionsschritt: Sei (A(c), A(c) → F(c))
`
F(c) der letzte Schritt der
Herleitung. Nach Induktionsvoraussetzung sind in ∆ auch die Formeln
∀x A(x) und ∀x (A(x) → F(x)) ohne c herleitbar. Nach der ∀-Verteilung ist
dann auch ∀x A(x) → ∀x F(x) ohne c herleitbar und mit dem Modus
Ponens folgt ∆
`
∀x F(x) mit einer c-freien Herleitung.
Logik
29
Zum Beweis des Vollständigkeitssatzes stellen wie als erstes fest, dass
es reicht, Teil (a) zu zeigen. Sei dazu F eine Formel, die in allen
Modellen von T gilt. Nimm nun an, dass (T, ¬F) konsistent ist. Dann
hat sie nach Teil (a) auch ein Modell. Dies ist dann aber ein Modell von
T in dem ¬F gilt, also F nicht gilt, was ein Widerspruch ist!
Wir folgern also, dass (T, ¬A) nicht konsistent ist. Nach der Reductio ad
absurdum folgt, dass T
`
¬¬A. Nun ist ¬¬A → A eine Tautologie, also
beweist T die Formel A.
Nun beweisen wir Teil (a). Sei T konsistent und ∆ = Ax(T). Wir geben
im folgenden eine Konstruktion an, bei der wir die Sprache um neue
Konstantensymbole erweitern und ∆ zu einer Formelmenge Σ in der
neuen Sprache vergrößern, so dass folgendes gilt
(i) ∆ ⊂ Σ,
(ii) Σ ist in der erweiterten Sprache maximalkonsistent,
(iii) Σ ist eine Henkin-Menge, d.h., für jede Formel F(a) gibt es eine
Konstante c, so dass die Formel ¬∀x F(x) → ¬F(c) ein Element von
Σ ist mit einer Variablen x, die nicht in F(a) auftritt.
Wir konstruieren Σ wie folgt. Wir starten mit der Sprache L0 = L und
der Formelmenge ∆0 = ∆. Für jede freie Variable a, jede Formel F(a) der
Sprache L0 und jede gebundene Variable x, die nicht in F(a) auftritt,
wählen wir ein neues Konstantensymbol ca,F,x und erhalten so die
Sprache L1 . Dann erweitern wir ∆ für jedes (a, F, x) um die Formel
¬∀x F(x) → ¬F(ca,F,x ).
Lemma 1.6.10. ∆1 ist konsistent.
© Copyright 2024 ExpyDoc
