Lokalität (Logik)

Lokalität ist ein Begriff aus der mathematischen Logik, mit dem Grenzen der Ausdrucksstärke gewisser Logiken aufgezeigt werden können. Die Grundidee besteht darin, dass gewisse Logiken wie die Prädikatenlogik erster Stufe nur lokale Eigenschaften von Strukturen beschreiben können, aber andere Eigenschaften solcher Strukturen diese Lokalitätseigenschaft nicht haben, letztere sind also nicht in dieser Logik formulierbar. Man unterscheidet zwei Arten von Lokalität, die nach William Hanf benannte Hanf-Lokalität und die nach Haim Gaifman benannte Gaifman-Lokalität.

Einführung

Wir betrachten endliche Strukturen wie die eines Graphen. Ein Graph besteht aus einer endlichen Menge und einer zweistelligen Relation $E$ auf dieser Menge. Das Bestehen der Relation $E(x,y)$ bedeutet, dass es eine Kante von $x$ nach $y$ gibt. Der Buchstabe E erinnert an das englische Wort edge für Kante. Damit lassen sich Graphen in der Prädikatenlogik $L_{I}^{\sigma }$ erster Stufe beschreiben, wobei die Signatur $\sigma$ nur aus der Relation $E$ besteht, also $\sigma =\{E\}$. Wir stellen nun die Frage, welche Eigenschaften von Graphen sich in der Prädikatenlogik erster Stufe ausdrücken lassen. Ein einfaches Beispiel ist:

• „Der Graph ist vollständig“ wird ausgedrückt durch

$\forall x\forall yE(x,y)$.

Interessanter ist die Untersuchung von Wegen in einem Graphen:

• „Es gibt einen Weg von $x$ nach $y$ der Länge $\leq 0$“ wird ausgedrückt durch

$x=y$

• „Es gibt einen Weg von $x$ nach $y$ der Länge $\leq 1$“ wird ausgedrückt durch

$(x=y)\lor E(x,y)$

• „Es gibt einen Weg von $x$ nach $y$ der Länge $\leq 2$“ wird ausgedrückt durch

$(x=y)\lor E(x,y)\lor \exists z(E(x,z)\land E(z,y))$

• „Es gibt einen Weg von $x$ nach $y$ der Länge $\leq 3$“ wird ausgedrückt durch

$(x=y)\,\lor \,E(x,y)\,\lor \,\exists z(E(x,z)\land E(z,y))\,\lor \,\exists z_{1}\exists z_{2}(E(x,z_{1})\land E(z_{1},z_{2})\land E(z_{2},y))$

Indem man diese Kette in offensichtlicher Weise fortsetzt, erhält man für jedes feste $n$ einen $L_{I}^{\sigma }$-Ausdruck $\varphi _{n}(x,y)$, der die Existenz eines Weges von $x$ nach $y$ der Länge $\leq n$ ausdrückt. Zu anderen Eigenschaften finden sich keine Ausdrücke der Prädikatenlogik erster Stufe:

• „Es gibt einen Weg von $x$ nach $y$“: ?
• „Der Graph ist zusammenhängend“: ?

Könnte man die Existenz eines Weges von $x$ nach $y$ durch einen Ausdruck $\varphi (x,y)$ ausdrücken, so würde $\forall x\forall y\varphi (x,y)$ den Zusammenhang ausdrücken. Das scheint nicht gelingen zu wollen, da man hierzu Wege immer größerer Länge und letztlich eine unendlich lange oder-Verknüpfung zulassen müsste. Für beliebige Graphen kann es tatsächlich keinen $L_{I}^{\sigma }$-Satz $\psi$ geben, der den Zusammenhang ausdrückt. Um das einzusehen, erweitern wir die Sprache um zwei Konstanten $c_{1},c_{2}$ und betrachten die unendlich vielen Sätze

$\neg \varphi _{n}(c_{1},c_{2}),\,n\in \mathbb {N} _{0},\quad \psi$.

Jede endliche Teilmenge dieser Sätze enthält nur endlich viele Sätze der Form $\neg \varphi _{n}(c_{1},c_{2})$ und damit keine Sätze $\neg \varphi _{n}(c_{1},c_{2})$ mit $n\geq N$ für ein geeignetes, endliches $N$. Daher ist diese endliche Teilmenge durch den zyklischen Graphen $C_{2N}$ erfüllbar, wenn man $c_{1}$ und $c_{2}$ durch gegenüberliegende Punkte interpretiert. Nach dem Kompaktheitssatz wäre dann die Gesamtheit obiger Sätze erfüllbar und man erhielte einen Graphen, der wegen $\psi$ zusammenhängend ist und keinen Weg endlicher Länge von $c_{1}$ nach $c_{2}$ hat. Dieser Widerspruch zeigt, dass es einen $L_{I}^{\sigma }$-Satz $\psi$, der den Zusammenhang ausdrückt, nicht geben kann.

An dieser Argumentation ist die Anwendung des Kompaktheitssatzes unbefriedigend, denn dazu muss man auch unendliche Modelle zulassen. Da man die Endlichkeit eines Modells in der Prädikatenlogik erster Stufe bekanntlich nicht formulieren kann, ist nicht ausgeschlossen, dass es einen $L_{I}^{\sigma }$-Satz $\psi$ geben könnte, der für endliche Graphen den Zusammenhang ausdrückt. Um zu zeigen, dass auch das nicht möglich ist, betrachten wir Längen von Wegen zwischen zwei Punkten als Abstandsbegriff. Damit sagt $\varphi _{n}(x,y)$ aus, dass $y$ in einer gewissen Umgebung von $x$ liegt. Es scheint nun so zu sein, dass $L_{I}^{\sigma }$-Ausdrücke prinzipiell nicht zwischen Punkten in beliebig großen Entfernungen unterscheiden können, also nur zu lokalen Aussagen fähig sind. Die Präzisierung dieser Überlegungen führt zu den im Folgenden vorgestellten Lokalitätsbegriffen, mit denen unter anderem die Nichtformulierbarkeit des Zusammenhangs in der Prädikatenlogik erster Stufe gezeigt werden kann.

Eigenschaften von Strukturen

Eine Struktur ${\mathfrak {A}}=(A,I)$ zu einer Signatur $\sigma$ besteht bekanntlich aus einer Menge $A$, dem sogenannten Universum der Struktur, und einer Interpretation $I$ eines jeden Symbols aus $\sigma$. Einem k-stelligen Relationssymbol $R\in \sigma$ wird vermöge $I$ eine Teilmenge $R^{\mathfrak {A}}\subset A^{k}$ zugeordnet, das heißt eine k-stellige Relation über dem Universum. Ist wie in obiger Einführung $\sigma =\{E\}$ mit einer zweistelligen Relation $E$, so ist eine $\sigma$-Struktur nichts anderes als ein Graph. Ein Isomorphismus zwischen $\sigma$-Strukturen ist eine bijektive Abbildung zwischen den unterliegenden Universen, die die Interpretationen der Struktur erhält. Im Falle von Graphen, also $\{E\}$-Strukturen ${\mathfrak {A}}=(A,I)$ und ${\mathfrak {B}}=(B,I)$, heißt das einfach, dass die Abbildung, etwa $f:A\rightarrow B$, bijektiv ist, aus $E^{\mathfrak {A}}(a_{1},a_{2})$ stets $E^{\mathfrak {B}}(f(a_{1}),f(a_{2}))$ folgt und dass für die Umkehrabbildung $f^{-1}:B\rightarrow A$ dasselbe gilt. Hat die Struktur ein Konstanten-Symbol, etwa $c$, das in den Strukturen durch $c^{\mathfrak {A}}\in A$ bzw. $c^{\mathfrak {B}}\in B$ interpretiert ist, so bedeutet die Erhaltung der Struktur unter $f$ nichts anderes als $f(c^{\mathfrak {A}})=c^{\mathfrak {B}}$.

Wir interessieren uns im Folgenden für k-stellige Eigenschaften, die unter Isomorphismen invariant sind. Eine solche Eigenschaft, auch Query genannt, ordnet jeder Struktur ${\mathfrak {A}}=(A,I)$ eine Teilmenge $Q({\mathfrak {A}})\subset A^{k}$ zu, so dass für jeden Isomorphismus $f:{\mathfrak {A}}\rightarrow {\mathfrak {B}}$ gilt, dass $(a_{1},\ldots ,a_{k})\in Q({\mathfrak {A}})\Leftrightarrow (f(a_{1}),\ldots ,f(a_{k}))\in Q({\mathfrak {B}})$.

Ein Beispiel für eine 2-stellige Eigenschaft von Graphen ist die transitive Hülle, die der Kantenrelation ihre transitive Hülle in $A^{2}$ zuordnet.

Für $k=0$ setzt man $A^{0}=\{0\}$. Für eine 0-stellige Eigenschaft gibt es dann nur zwei Möglichkeiten, $\emptyset$ oder $\{0\}$, was man dann als falsch bzw. wahr interpretieren kann. Statt von 0-stelligen Eigenschaften spricht man daher auch von booleschen Eigenschaften. Ein typisches Beispiel ist der Zusammenhang von Graphen: Ein Graph hat diese Eigenschaft oder nicht und diese Eigenschaft bleibt bei Isomorphie erhalten.

Ist $\varphi (x_{1},\ldots ,x_{k})$ ein logischer Ausdruck mit $k$ freien Variablen $x_{1},\ldots ,x_{k}$, so ist durch

$Q({\mathfrak {A}}):=\{{\vec {a}}=(a_{1},\ldots ,a_{k})\in A^{k}|\,{\mathfrak {A}}\vDash \varphi ({\vec {a}})\}$

eine k-stellige Eigenschaft gegeben, $Q({\mathfrak {A}})$ ist die Menge aller Tupel, für die der Ausdruck in der Struktur wahr wird. Im Falle k=0 ist das wieder als falsch bzw. wahr zu interpretieren, dann wird die Eigenschaft durch einen Satz $\varphi$ als logischen Ausdruck definiert und statt $Q({\mathfrak {A}})$ schreibt man auch $\varphi ({\mathfrak {A}})$.

Es geht im Folgenden um die Frage, welche solcher Eigenschaften durch Ausdrücke gewisser Logiken nicht definiert werden können. Das beschreibt Grenzen der Ausdrucksstärke solcher Logiken.

Gaifman-Graph

Wir betrachten Signaturen, die nur aus Relationen bestehen, sogenannte relationale Signaturen. Funktionen können mit ihren Funktionsgraphen und somit ebenfalls als Relationen aufgefasst werden, allerdings mit einer um 1 erhöhten Stelligkeit, Konstanten können oft als einelementige, einstellige Relationen betrachtet werden. Um den oben erwähnten Abstandsbegriff zu erhalten, ordnen wir jeder Struktur ${\mathfrak {A}}=(A,I)$ einer relationalen Signatur $\sigma$ einen Graphen $G({\mathfrak {A}})$, den sogenannten Gaifman-Graphen zu. Seine Punkte sind die Elemente aus dem zugehörigen Universum $A$. Zwei verschiedene Punkte $a$ und $b$ sind genau dann durch eine Kante verbunden, wenn sie in einer Relation zueinander stehen, genauer, wenn es ein n-stelliges $R\in \sigma$ und $a_{1},\ldots ,a_{n}\in A$ gibt mit $R^{\mathfrak {A}}(a_{1},\ldots ,a_{n})$ und $a,b\in \{a_{1},\ldots ,a_{n}\}$. Dabei ist $R^{\mathfrak {A}}=I(R)$ die Interpretation von $R$ in der Struktur ${\mathfrak {A}}$.

In der in gegebenen Definition werden alle Paare $(a,a),\,a\in A$ zum Gaifman-Graphen hinzugenommen, das heißt, dass die Gleichheit wie die anderen Relationen behandelt wird. Das hat zur Folge, dass an jedem Punkt des Graphen eine Schleife hängt. Die hier verwendete Definition aus dem unten angegebenen Lehrbuch von Ebbinghaus und Flum schließt genau das aus, der Gaifman-Graph soll schleifenfrei sein. Für den hier einzuführenden Abstandsbegriff ist das unerheblich.

Besteht $\sigma =\{<\}$ beispielsweise aus einer zweistelligen Relation < und ist ${\mathfrak {A}}=(\{1,\ldots ,n\},I)$, wobei $I$ die Relation als die übliche Größenrelation zwischen natürlichen Zahlen interpretiert, so ist $G({\mathfrak {A}})$ der vollständige Graph mit Punkten $\{1,\ldots ,n\}$, denn je zwei verschiedene Elemente stehen bzgl. < in Relation, das heißt sind der Größe nach vergleichbar.

Ein weiteres Beispiel ist $\sigma =\{E\}$ mit einer zweistelligen Relation $E$, so dass jede endliche $L_{I}^{\sigma }$-Struktur ${\mathfrak {A}}$ ein gerichteter Graph ist. Der Gaifman-Graph ist dann der zugehörige ungerichtete, schleifenfreie Graph. Dieses Beispiel ist prototypisch für die folgenden Überlegungen.

Kugeln in Gaifman-Graphen

Da wir jeder Struktur ${\mathfrak {A}}=(A,I)$ ihren Gaifman-Graphen $G({\mathfrak {A}})$ zugeordnet haben, können wir vom Abstand zweier Elemente des zugehörigen Universums $A$ sprechen, wir setzen

$d_{\mathfrak {A}}(a,b)$   =   Länge eines kürzesten Weges von $a$ nach $b$ in $G({\mathfrak {A}})$,

falls die Punkte überhaupt durch einen Weg verbunden sind, sonst ist der Abstand unendlich. Insbesondere können wir von $r$-Kugeln bzgl. eines Tupels ${\vec {a}}=(a_{1},\ldots a_{n})$ sprechen:

$B_{r}^{\mathfrak {A}}({\vec {a}}):=\{a\in A|\,\min _{i=1,\ldots ,n}d_{\mathfrak {A}}(a,a_{i})\leq r\}=\bigcup _{i=1}^{n}\{a\in A|\,d_{\mathfrak {A}}(a,a_{i})\leq r\}$.

Da der Abstand nur ganzzahlige Werte oder $\infty$ annehmen kann, genügt es, ganzzahlige Radien $r$ zu betrachten. Die Grundidee besteht darin, zu untersuchen, wie weit gewisse logische Sätze der betrachteten Logik bzgl. dieses Abstandes reichen, das wird unten als Hanf-Lokalität bzw. Gaifman-Lokalität präzisiert. Aus diesem Grunde wollen wir die relative $\sigma$-Struktur auf den $r$-Kugeln betrachten. Da wir in $\sigma$ nur Relationen $R$ und keine Funktionen haben, ist das einfach die Einschränkung der Relationen $R^{\mathfrak {A}}$. Dabei sind folgende zwei Dinge zu beachten.

Enthält die Signatur Konstanten $c_{1},\ldots ,c_{m}$, so genügt es nicht, diese als einstellige, einelementige Relationen zu betrachten, da die Einschränkung auf eine Teilmenge von $A$, das heißt der Durchschnitt mit dieser Teilmenge, leer sein kann. Von Substrukturen verlangt man aber, dass sie die Konstanten ebenfalls enthalten. In diesem Fall muss man obige Definition durch

$B_{r}^{\mathfrak {A}}({\vec {a}}):=\{a\in A|\,\min _{i=1,\ldots ,n}d_{\mathfrak {A}}(a,a_{i})\leq r{\text{ oder }}\min _{i=1,\ldots ,m}d_{\mathfrak {A}}(a,c_{i})\leq r\}$

ersetzen. Das erweist sich lediglich als eine technische Ergänzung dieser Überlegungen.

Die Punkte der Umgebung $N_{2}^{\mathfrak {A}}(a)$ im Gaifman-Graph sind grün dargestellt.

Zweitens wollen wir die Zentren $a_{1},\ldots a_{n}$, zu denen Abstände gemessen werden, im Blick behalten. Dazu nehmen wir eine passende Konstantenexpansion vor, das heißt wir erweitern $\sigma$ um neue Konstanten zu ${\tilde {c}}_{1},\ldots ,{\tilde {c}}_{n}$, die durch $a_{1}\ldots ,a_{n}$ zu interpretieren sind, und setzten $\sigma _{n}:=\sigma \cup \{{\tilde {c}}_{1},\ldots ,{\tilde {c}}_{n}\}$.

Zu jeder $r$-Kugel um ${\vec {a}}$ definieren wir nun die eingeschränkte $\sigma _{n}$-Struktur $N_{r}^{\mathfrak {A}}({\vec {a}})$ durch

• Das Universum ist $B_{r}^{\mathfrak {A}}({\vec {a}})$.
• Jede k-stellige Relation $R\in \sigma$ wird als $R^{\mathfrak {A}}\cap (B_{r}^{\mathfrak {A}}({\vec {a}}))^{k}$ interpretiert.
• Jede Konstante ${\tilde {c}}_{j}$ wird als $a_{j}$ interpretiert.

Zwei Strukturen ${\mathfrak {A}},{\mathfrak {B}}$ mit Universen $A$ und $B$ sowie vorgegebenen Tupeln ${\vec {a}}\in A^{n},\,{\vec {b}}\in B^{n}$ heißen $r$-äquivalent, in Zeichen

$({\mathfrak {A}},{\vec {a}})\,\leftrightarrows _{r}\,({\mathfrak {B}},{\vec {b}})$,

falls es eine Bijektion $f:A\rightarrow B$ gibt, so dass für jedes $a\in A$

$N_{r}^{\mathfrak {A}}({\vec {a}}a)\cong N_{r}^{\mathfrak {A}}({\vec {b}}f(a))$.

Dabei steht ${\vec {a}}a$ für den um $a$ verlängerten Vektor, das heißt ${\vec {a}}a=(a_{1},\ldots ,a_{n},a)$, falls ${\vec {a}}=(a_{1},\ldots ,a_{n})$, und genauso ${\vec {b}}f(a)$. Die Isomorphiebeziehung $\cong$ bezieht sich auf $\sigma _{n+1}$-Strukturen, es gilt also insbesondere $a_{i}\mapsto b_{i}$ und $a\mapsto f(a)$. Es wird nicht verlangt, dass eine entsprechende Einschränkung von $f$ ein Isomorphismus sein soll, sondern nur, dass es irgendeinen Isomorphismus zwischen den $\sigma _{n+1}$-Strukturen geben soll, für einen solchen gilt allerdings wegen der zu berücksichtigenden Konstanten $a\mapsto f(a)$.

Für $n=0$ hat man keine vorgegebenen Tupel ${\vec {a}}$ und ${\vec {b}}$. In diesem Fall schreibt man einfach ${\mathfrak {A}}\,\leftrightarrows _{r}\,{\mathfrak {B}}$, was dann die Existenz einer bijektiven Abbildung $f:A\rightarrow B$ mit $N_{r}^{\mathfrak {A}}(a)\cong N_{r}^{\mathfrak {A}}(f(a))$ für alle $a\in A$ bedeutet.

Hanf-Lokalität

Eine $k$-stellige Eigenschaft $Q$ von relationalen $\sigma$-Strukturen heißt Hanf-lokal, falls es $r\geq 0$ gibt, so dass folgendes gilt:

Sind ${\mathfrak {A}}=(A,I)$ und ${\mathfrak {B}}=(B,J)$ $\sigma$-Strukturen, ${\vec {a}}\in A^{k}$, ${\vec {b}}\in B^{k}$ mit $({\mathfrak {A}},{\vec {a}})\,\leftrightarrows _{r}\,({\mathfrak {B}},{\vec {b}})$, so folgt ${\vec {a}}\in Q({\mathfrak {A}})\,\Leftrightarrow \,{\vec {b}}\in Q({\mathfrak {B}})$.

Das kleinste $r\geq 0$, für das dies gilt, heißt der Rang der Hanf-Lokalität und wird mit $hlr(Q)$ bezeichnet. $hlr$ steht für die englische Bezeichnung Hanf local rank.

Zwei Strukturen stimmen also bzgl. der Eigenschaft $Q$ bereits dann überein, wenn sie bzgl. aller $hlr(Q)$-Kugeln ihrer Gaifman-Graphen übereinstimmen.

Gaifman-Lokalität

Eine $k$-stellige Eigenschaft $Q$ von relationalen $\sigma$-Strukturen heißt Gaifman-lokal, falls es $r\geq 0$ gibt, so dass folgendes gilt:

Ist ${\mathfrak {A}}=(A,I)$ eine $\sigma$-Struktur und sind ${\vec {a}},{\vec {b}}\in A^{k}$ mit $N_{r}^{\mathfrak {A}}({\vec {a}})\cong N_{r}^{\mathfrak {A}}({\vec {b}})$ so folgt ${\vec {a}}\in Q({\mathfrak {A}})\,\Leftrightarrow \,{\vec {b}}\in Q({\mathfrak {A}})$.

Das kleinste $r\geq 0$, für das dies gilt, heißt der Rang der Gaifman-Lokalität und wird mit $lr(Q)$ bezeichnet.

Gaifman-Lokalität ist der schwächere Begriff, es besteht die Beziehung $lr(Q)\leq 3\cdot hlr(Q)+1$. Beachte, dass sich Gaifman-Lokalität auf eine Struktur bezieht, während Hanf-Lokalität zwei Strukturen vergleicht.

Anwendungen

In den Anwendungen weist man zunächst nach, dass alle durch bestimmte logische Ausdrücke definierten Eigenschaften Hanf- bzw. Gaifman-lokal sind, aber gewisse Eigenschaften $Q$ nicht diese Lokalitätsbedingung erfüllen. Daraus folgt dann, dass $Q$ nicht durch einen solchen logischen Ausdruck beschrieben werden kann, was eine Grenze der Ausdrucksstärke der betrachteten Logik markiert.

Lokalität der Prädikatenlogik erster Stufe

Bezeichnet man mit $FO[k]$ alle logischen Ausdrücke der Prädikatenlogik erster Stufe, deren Quantoren eine Verschachtelungstiefe von höchstens $k$ haben, so gilt

$hlr(Q)\leq {\frac {3^{k}-1}{2}}$

für alle Eigenschaften $Q$, die durch einen $FO[k]$-Ausdruck definiert werden können.

FO steht hierbei als Abkürzung für die englische Bezeichnung first order logic. Da jeder Ausdruck der Prädikatenlogik erster Stufe ein $FO[k]$-Ausdruck für irgendein $k$ ist, sind alle durch Ausdrücke der Prädikatenlogik erster Stufe definierten Eigenschaften Hanf-lokal.

Die Graphen $G_{i}$ mit grün dargestellten $N_{3}^{G_{i}}(a)$-Umgebungen, $a$ jeweils in rot

Zusammenhang von Graphen

Es sei $Q$ die boolesche Eigenschaft eines Graphen, das heißt einer $\{E\}$-Struktur, zusammenhängend zu sein. Um zu zeigen, dass sich Zusammenhang auch für als endlich vorausgesetzte Graphen nicht in der Prädikatenlogik erster Stufe formulieren lässt, genügt es zu zeigen, dass $Q$ nicht Hanf-lokal ist. Wäre $Q$ Hanf-lokal, etwa mit $hlr(Q)=r$, so wähle ein $m>2r+1$ und betrachte den zyklischen Graphen $G_{1}=C_{2m}$ mit $2m$ Knoten und den Graphen $G_{2}=C_{m}+C_{m}$, der aus der disjunkten Vereinigung zweier zyklischer Graphen mit je $m$ Knoten besteht. Die Gaifman-Graphen dieser Strukturen sind die Graphen selbst. In jedem dieser Graphen $G_{i}$ besteht eine $r$-Kugel $N_{r}^{G_{i}}(a)$ nach Wahl von $m$ aus einer Kette der Länge $2r+1$ mit Mittelpunkt $a$, und die sind als Untergraphen mit vorgegebenem Mittelpunkt alle untereinander isomorph. Jede Bijektion $f:G_{1}\rightarrow G_{2}$ (beide Graphen haben $2m$ Knoten) zeigt daher $G_{1}\leftrightarrows _{r}G_{2}$ und aus der angenommenen Hanf-Lokalität folgte $Q(G_{1})=Q(G_{2})$. Das kann aber nicht sein, denn $G_{1}$ ist zusammenhängend, $G_{2}$ aber nicht.

Transitive Hülle

Gaifman-Graph G zur Nachfolgerrelation, die grün dargestellten $N_{2}^{G}((a_{1},a_{2}))$ und $N_{2}^{G}((a_{2},a_{1}))$ sind als Mengen gleich.

Nun beschreibe $Q$ die transitive Hülle einer $\{R\}$-Struktur, das heißt $Q({\mathfrak {A}})$ ist die Menge aller Paare $(a,b)\in A^{2}$, so dass es $m\geq 1$ und $a_{0},a_{1},\ldots ,a_{m}\in A$ gibt mit $(a_{i-1},a_{i})\in R$ für alle $i=1,\ldots ,m$ und $a_{0}=a,a_{m}=b$. Um zu zeigen, dass die transitive Hülle nicht durch einen Ausdruck der Prädikatenlogik erster Stufe beschrieben werden kann, genügt es zu zeigen, dass $Q$ nicht Gaifman-lokal ist. Wäre $Q$ Gaifman-lokal, etwa mit $lr(Q)=r$, so betrachte als $\{R\}$-Struktur eine Kette ${\mathfrak {A}}=(\{0,\ldots ,m\},I)$ mit $m>4r+1$. Kette bedeutet, dass die Relation als $\{(0,1),\ldots ,(m-1,m)\}$ interpretiert wird. Die transitive Hülle dieser Relation ist dann nichts anderes als die natürliche Ordnung < auf $\{0,1,\ldots ,m\}$. Der Gaifman-Graph $G=G({\mathfrak {A}})$ ist ein linearer Graph der Länge $m+1$. Auf Grund der Wahl von $m$ kann man zwei Knoten $a_{1},a_{2}\in \{0,1,\ldots ,m\}$ wählen, die von den Rändern den Abstand $r$ und untereinander den Abstand $\geq 2r+1$ haben. Dann bestehen $N_{r}^{G}((a_{1},a_{2}))$ und $N_{r}^{G}((a_{2},a_{1}))$ beide aus je zwei disjunkten Teilketten der Länge $2r$ mit Mittelpunkten $a_{i}$. Daraus folgt $N_{r}^{G}((a_{1},a_{2}))\cong N_{r}^{G}((a_{2},a_{1}))$ und aus der angenommenen Gaifman-Lokalität ergäbe sich $(a_{1},a_{2})\in Q({\mathfrak {A}})\Leftrightarrow (a_{2},a_{1})\in Q({\mathfrak {A}})$. Das kann aber nicht sein, denn von den Relationen $a_{1}<a_{2}$ und $a_{2}<a_{1}$ ist genau eine wahr.

Weitere Logiken

Im Lichte obiger Beispiele stellt sich die Frage, ob es Erweiterungen der Prädikatenlogik erster Stufe gibt, für die jeder Ausdruck ebenfalls eine lokale Eigenschaft definiert. Derartige Erweiterungen wären immer noch nicht ausdrucksstark genug, um Graphenzusammenhang oder die transitive Hülle in endlichen Strukturen zu beschreiben.

Das Universum einer endlichen Struktur kann immer als linear geordnet angenommen werden. Diese Ordnung sei mit < bezeichnet, sie ist nicht Bestandteil der Signatur. Man kann zeigen, dass es von dieser Ordnung unabhängige Eigenschaften gibt, die sich aber mittels dieser Ordnung beschreiben lassen. Die Menge dieser Eigenschaften nennt man $(FO+<)_{inv}$, das heißt $FO$ wird um < erweitert und man beschränkt sich dann auf Eigenschaften, die nicht von < abhängen, was durch den Index inv (invariant) angedeutet wird. Dadurch erhält man eine echt größere Menge von Eigenschaften (Satz von Gurewich) und man kann zeigen, dass jede $(FO+<)_{inv}$-Eigenschaft Gaifman-lokal ist (Satz von Grohe-Schwentick).

Bestimmte Ausdrücke infinitärer Logiken, die um Möglichkeiten des Zählens erweitert sind, können ebenfalls als Hanf- bzw. Gaifman-lokal nachgewiesen werden.

Siehe auch

• Satz von Gaifman