Wir konzentrieren uns auf dieser Seite auf Graphentheorie. Für Sätze über Graphen brauchen dann auch Variablensymbole für die Ecken, ein Symbol für Gleichheit und ein Symbol für Adjazenz von Ecken.
Wir haben die übliche Menge der technischen Zeichen S = { Ù, Ø, (, ), ", = }.
In unserem Graphentheoriebeispiel gibt es nur die trivialen Terme x, y, z, ... .
Atomare Formeln sind "x = y" oder "Adj x y" für Individuenvariable x und y. "Adj x y" steht natürlich für "x und y sind adjazent".
Beispiele für Aussagen sind etwa:
oder auch
Mit der obigen Sprache können wir nicht nur über
Graphen reden, wir können auch über geordnete Mengen
oder Äquivalenzrelationen reden, tatsächlich über
jede relationale Struktur mit nur einer binären Relation..
Natürlich sind die obigen Aussagen
(S1)
(
$x $v
[
Ø
(
x = v Ú
Adj x v
)
Ù
(
"y
(
Ø
(
Adj x y Ù Adj y v
)
Ù
"z
Ø
(
Adj x y Ù
(
Adj y z Ù Adj z v
)
)
)
)
]
®
"x "v
[
(
x = v Ú
Adj x v
)
Ú
(
$y
(
(
Adj x y Ù Adj y v
)
Ú
$z
(
Adj x y Ù
(
Adj y z Ù
Adj z v
)
)
)
)
]
)
Graphen sind genau die Modelle unserer Sprache, in denen
die obigen beiden Axiome G1
und G2 gelten.
Die Menge {G1,G2} ist die Theorie,
die die Graphentheorie beschreibt.
Nun stellt sich die Frage, ob die obigen beiden Formeln
D3 und S1 aus
{G1,G2} folgen, d.h. in jedem Graphen
gelten. D3 folgt offenbar nicht, denn es gibt
ein Modell von {G1,G2}
in dem D3 nicht gilt, nämlich
({1,2,3,4,5},{(1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4)}).
Nehmen wir nun an, daß ein höheres Wesen
alle (unendlich vielen) Modelle von
{G1,G2} überprüft hat und festgestellt
hat, daß S1 in jedem dieser Modelle gilt.
Dann folgt S1 aus {G1,G2} (semantisch).
Können wir dann S1 auch beweisen, also
(syntaktisch) aus {G1,G2} ableiten?
Es ist tatsächlich so, der
Vollständigkeitssatz
erzwingt dies.