Haben wir eine feste Struktur
M
der Sprache L
gewählt, so erhalten wir für jeden Term T von
L ein Element der
Grundmenge M von M,
den sogenannten Wert des Terms
(in M).
Formeln und Aussagen sind in M
gültig oder nicht---bei Aussagen setzen wir einfach die Werte
der Terme ein, eine Formeln
A(x1,x2,...,xn,)
ist in M
gültig, falls die Generalisierung
x1
x2 ...
xn
A(x1,x2,...,xn,)
gültig ist.
Wir schreiben dann M
A und nennen
M
ein Modell von A. Dies lässt sich auch auf
Mengen von Formeln übertragen:
|
Eine Theorie ist eine
beliebige Formelmenge {A1, A2, ... }
der Sprache L.
Eine Struktur M für L ist ein Modell für {A1, A2, ... }, M {A1, A2, ... },
falls alle diese Formeln Ai in
M gelten.
Die Theorie ist
|
Wir benutzen das Symbol "" noch in
einer anderen Bedeutung:
|
Eine Formel B folgt aus
der Theorie {A1, A2, ... },
falls B in jedem Modell von
{A1, A2, ... } gilt.
Wir schreiben dann
{A1, A2, ... }
B.
Der deduktive Abschluß Ded({A1, A2, ... }) ist die Menge aller Folgerungen aus ihr (also die Menge aller Formeln, die in jedem Modell der Theorie gelten). |
"Ded" ist ein
Hüllenoperator, d.h.
|
|
Q sei eine Theorie (also eine Menge von Formeln), A und B seien Formeln.
Abtrennungsregel: Wenn Q (A  B),
dann Q  {A} B.
Deduktionstheorem: Wenn Q {A} B,
dann Q (A B)
|
Wir nennen zwei Formeln A und B äquivalent,
A  B, falls A in genau denselben
Strukturen gilt, wie B, d.h. falls A  B
in jeder Struktur gilt.
|
Tatsächlich ist "Äquivalenz" sogar eine Kongruenz
bzgl. "
",
"
",
"
",
"",
"
", ...
Das bedeutet: Gilt A1
A2
und B1
B2, so folgt
A1
A2,
B1
A2
B2,
x A1
x A2, usw.
Es gelten alle aussagenlogischen Äquivalenzen, aber darüberhinaus auch noch folgende:
x A
x A
x A
x
A
x (A B)
x A
x B
x (A B)
x A
x B
x y A
y
x A
x y A
y
x A
x (A B) und
x A
x B;
auch keins der folgenden drei Formeln ist äquivalent:
x y A,
bzw.
y x A, bzw.
y x A
| Die rechts aufgelisteten Äquivalenzen gelten falls x in B nicht frei vorkommt: |
|
Vorsichtigere Charaktere ziehen es vielleicht vor, mit Formeln
zu arbeiten, bei denen eine Variable nie in derselben Formel
frei und gebunden erscheint, und bei der je zwei gebundene
Erscheinen jeder Variable durch denselben Quantor gebunden
sind. Zu jeder Formel gibt es so eine äquivalente
"Nummer-Sicher" Formel.
So ist z.B.
y x
( y z = + x y
y y = + x z)
zu
y x
( y1 z = + x y1
y2 y2 = + x z)
äquivalent.
Wieder kann man Formeln in Normalform bringen.
Diesmal möchte man, daß zuerst alle
Quantoren (zusammen mit den gebundenen Variablen) erscheinen,
und der Rest der Formel in (kanonischer) konjunktiver bzw.
disjunktiver Normalform ist. Das heißt dann
pränexe Normalform.
Näheres finden Sie im Abschnitt über
pränexe
und Skolemsche Normalformen.
Definitorische Erweiterungen
Die Sprache
L1
sei eine Sprachwerweiterung der Sprache
L,
d.h. jedes Symbol von
L kommt auch
in L1
mit derselben Stelligkeit vor.
"R" sei ein n-stelliges Relationenzeichen in
L, aber nicht in
L1.
"R" heißt
L-definierbar in einer
Struktur M'
von L1,
falls es eine L-Formel
A(x1,...,xn) gibt
so daß R(x1,...,xn)
genau dann in M'
gilt, falls A(x1,...,xn) in
M'
gilt.
So ist beispielsweise "größer"
durch die Formel
A(x,y): z (y = + x z
x = z)
(M,+)-definierbar in (N,+),
und auch die 1-stellige Relation (d.h. Eigenschaft)
"ist gerade"
ist durch
B(x): z (x = + z z)
(M,+)-definierbar in (N,+).
Interessanterweise ist etwa
"größ,er" nicht (M,+)-definierbar in (Z,+).
|
Gödelscher Vollständigkeitssatz:
Es sei Q eine Theorie der Sprache (1. Stufe)
L.
Für jede Aussage A der Sprache gilt:
A folgt genau dann aus Q wenn A aus Q
ableitbar ist.
|
Somit folgt aus dem Endlichkeitssatz fürs Ableiten:
|
Endlichkeitssatz:
Wenn A aus einer Theorie Q folgt, so
folgt Q bereits aus einer endlichen Teiltheorie von Q.
|
|
Kompaktheitssatz:
Eine Theorie Q ist genau dann (semantisch) widerspruchsfrei,
wenn jede endliche Teiltheorie von T widerspruchsfrei ist.
|
Ded(Q),