Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Graphentheorie erster Ordnung

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:

  1. (G1) "x Ø Adj x x
  2. (G2) "x "y (Adj x y ® Adj y x)
oder auch
(D3)
" x " y ((x = y Ú Adj x y) Ú ($ z (Adj x z Ù Adj z y) Ú $ z (Adj x z Ù $ w (Adj z w Ù Adj w y)))),
oder auch
(D3*) " x " y $ u $ z $ w (x = y Ú Adj x y Ú (Adj x u Ù Adj u y) Ú (Adj x z Ù Adj z w Ù Adj w y)),
(das ist die pränexe disjunktive Normalform von (D3))

oder auch
(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 ) ) ) ) ] )

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 nicht in jeder solchen Struktur gültig, G1 und G2 sind etwa beide im Modell ({1,2},{(1,1},(1,2)}) der Sprache ungültig.

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.


Lässt sich die Aussage "Der Graph ist zusammenhängend" in der Sprache ausdrücken? Wieso nicht folgendermaßen?
" x " y (Ø x = y ® $ n Î N $ z1 x = z1 $ z2 Adj z1 z2 ... $ zn (Adj zn-1 zn Ù zn = y)).
Das ist leider keine Formel der Sprache. Erstens stört "$ n Î N"---wir dürfen nur über Symbole für Elemente der Eckenmenge quantifizieren, nicht über natürliche Zahlen. Das könnte man noch beheben (indem man sich auf endliche Graphen beschränkt und die Eckenmenge immer als Teilmenge von N auffasst), aber die Punkte in der Formel sind tödlich.
Erich Prisner
erstellt im Juni 2000.