Lokalität (Logik)

Lokalität i​st ein Begriff a​us der mathematischen Logik, m​it dem Grenzen d​er Ausdrucksstärke gewisser Logiken aufgezeigt werden können. Die Grundidee besteht darin, d​ass gewisse Logiken w​ie die Prädikatenlogik erster Stufe n​ur lokale Eigenschaften v​on Strukturen beschreiben können, a​ber andere Eigenschaften solcher Strukturen d​iese Lokalitätseigenschaft n​icht haben, letztere s​ind also n​icht in dieser Logik formulierbar. Man unterscheidet z​wei Arten v​on Lokalität, d​ie nach William Hanf benannte Hanf-Lokalität u​nd die n​ach 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 ${\displaystyle E}$ auf dieser Menge. Das Bestehen der Relation ${\displaystyle E(x,y)}$ bedeutet, dass es eine Kante von ${\displaystyle x}$ nach ${\displaystyle y}$ gibt. Der Buchstabe E erinnert an das englische Wort edge für Kante. Damit lassen sich Graphen in der Prädikatenlogik ${\displaystyle L_{I}^{\sigma }}$ erster Stufe beschreiben, wobei die Signatur ${\displaystyle \sigma }$ nur aus der Relation ${\displaystyle E}$ besteht, also ${\displaystyle \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

${\displaystyle \forall x\forall yE(x,y)}$.

Interessanter i​st die Untersuchung v​on Wegen i​n einem Graphen:

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

${\displaystyle x=y}$

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

${\displaystyle (x=y)\lor E(x,y)}$

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

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

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

${\displaystyle (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 ${\displaystyle n}$ einen ${\displaystyle L_{I}^{\sigma }}$-Ausdruck ${\displaystyle \varphi _{n}(x,y)}$, der die Existenz eines Weges von ${\displaystyle x}$ nach ${\displaystyle y}$ der Länge ${\displaystyle \leq n}$ ausdrückt. Zu anderen Eigenschaften finden sich keine Ausdrücke der Prädikatenlogik erster Stufe:

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

Könnte man die Existenz eines Weges von ${\displaystyle x}$ nach ${\displaystyle y}$ durch einen Ausdruck ${\displaystyle \varphi (x,y)}$ ausdrücken, so würde ${\displaystyle \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 ${\displaystyle L_{I}^{\sigma }}$-Satz ${\displaystyle \psi }$ geben, der den Zusammenhang ausdrückt. Um das einzusehen, erweitern wir die Sprache um zwei Konstanten ${\displaystyle c_{1},c_{2}}$ und betrachten die unendlich vielen Sätze

${\displaystyle \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 ${\displaystyle \neg \varphi _{n}(c_{1},c_{2})}$ und damit keine Sätze ${\displaystyle \neg \varphi _{n}(c_{1},c_{2})}$ mit ${\displaystyle n\geq N}$ für ein geeignetes, endliches ${\displaystyle N}$. Daher ist diese endliche Teilmenge durch den zyklischen Graphen ${\displaystyle C_{2N}}$ erfüllbar, wenn man ${\displaystyle c_{1}}$ und ${\displaystyle 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 ${\displaystyle \psi }$ zusammenhängend ist und keinen Weg endlicher Länge von ${\displaystyle c_{1}}$ nach ${\displaystyle c_{2}}$ hat. Dieser Widerspruch zeigt, dass es einen ${\displaystyle L_{I}^{\sigma }}$-Satz ${\displaystyle \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 ${\displaystyle L_{I}^{\sigma }}$-Satz ${\displaystyle \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 ${\displaystyle \varphi _{n}(x,y)}$ aus, dass ${\displaystyle y}$ in einer gewissen Umgebung von ${\displaystyle x}$ liegt. Es scheint nun so zu sein, dass ${\displaystyle 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 ${\displaystyle {\mathfrak {A}}=(A,I)}$ zu einer Signatur ${\displaystyle \sigma }$ besteht bekanntlich aus einer Menge ${\displaystyle A}$, dem sogenannten Universum der Struktur, und einer Interpretation ${\displaystyle I}$ eines jeden Symbols aus ${\displaystyle \sigma }$. Einem k-stelligen Relationssymbol ${\displaystyle R\in \sigma }$ wird vermöge ${\displaystyle I}$ eine Teilmenge ${\displaystyle R^{\mathfrak {A}}\subset A^{k}}$ zugeordnet, das heißt eine k-stellige Relation über dem Universum. Ist wie in obiger Einführung ${\displaystyle \sigma =\{E\}}$ mit einer zweistelligen Relation ${\displaystyle E}$, so ist eine ${\displaystyle \sigma }$-Struktur nichts anderes als ein Graph. Ein Isomorphismus zwischen ${\displaystyle \sigma }$-Strukturen ist eine bijektive Abbildung zwischen den unterliegenden Universen, die die Interpretationen der Struktur erhält. Im Falle von Graphen, also ${\displaystyle \{E\}}$-Strukturen ${\displaystyle {\mathfrak {A}}=(A,I)}$ und ${\displaystyle {\mathfrak {B}}=(B,I)}$, heißt das einfach, dass die Abbildung, etwa ${\displaystyle f:A\rightarrow B}$, bijektiv ist, aus ${\displaystyle E^{\mathfrak {A}}(a_{1},a_{2})}$ stets ${\displaystyle E^{\mathfrak {B}}(f(a_{1}),f(a_{2}))}$ folgt und dass für die Umkehrabbildung ${\displaystyle f^{-1}:B\rightarrow A}$ dasselbe gilt. Hat die Struktur ein Konstanten-Symbol, etwa ${\displaystyle c}$, das in den Strukturen durch ${\displaystyle c^{\mathfrak {A}}\in A}$ bzw. ${\displaystyle c^{\mathfrak {B}}\in B}$ interpretiert ist, so bedeutet die Erhaltung der Struktur unter ${\displaystyle f}$ nichts anderes als ${\displaystyle 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[1], ordnet jeder Struktur ${\displaystyle {\mathfrak {A}}=(A,I)}$ eine Teilmenge ${\displaystyle Q({\mathfrak {A}})\subset A^{k}}$ zu, so dass für jeden Isomorphismus ${\displaystyle f:{\mathfrak {A}}\rightarrow {\mathfrak {B}}}$ gilt, dass ${\displaystyle (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 ${\displaystyle A^{2}}$ zuordnet.

Für ${\displaystyle k=0}$ setzt man ${\displaystyle A^{0}=\{0\}}$. Für eine 0-stellige Eigenschaft gibt es dann nur zwei Möglichkeiten, ${\displaystyle \emptyset }$ oder ${\displaystyle \{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 ${\displaystyle \varphi (x_{1},\ldots ,x_{k})}$ ein logischer Ausdruck mit ${\displaystyle k}$ freien Variablen ${\displaystyle x_{1},\ldots ,x_{k}}$, so ist durch

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

eine k-stellige Eigenschaft gegeben, ${\displaystyle 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 ${\displaystyle \varphi }$ als logischen Ausdruck definiert und statt ${\displaystyle Q({\mathfrak {A}})}$ schreibt man auch ${\displaystyle \varphi ({\mathfrak {A}})}$.

Es g​eht im Folgenden u​m die Frage, welche solcher Eigenschaften d​urch Ausdrücke gewisser Logiken n​icht definiert werden können. Das beschreibt Grenzen d​er 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 ${\displaystyle {\mathfrak {A}}=(A,I)}$ einer relationalen Signatur ${\displaystyle \sigma }$ einen Graphen ${\displaystyle G({\mathfrak {A}})}$, den sogenannten Gaifman-Graphen zu. Seine Punkte sind die Elemente aus dem zugehörigen Universum ${\displaystyle A}$. Zwei verschiedene Punkte ${\displaystyle a}$ und ${\displaystyle b}$ sind genau dann durch eine Kante verbunden, wenn sie in einer Relation zueinander stehen, genauer, wenn es ein n-stelliges ${\displaystyle R\in \sigma }$ und ${\displaystyle a_{1},\ldots ,a_{n}\in A}$ gibt mit ${\displaystyle R^{\mathfrak {A}}(a_{1},\ldots ,a_{n})}$ und ${\displaystyle a,b\in \{a_{1},\ldots ,a_{n}\}}$. Dabei ist ${\displaystyle R^{\mathfrak {A}}=I(R)}$ die Interpretation von ${\displaystyle R}$ in der Struktur ${\displaystyle {\mathfrak {A}}}$.[2]

In der in[3] gegebenen Definition werden alle Paare ${\displaystyle (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 ${\displaystyle \sigma =\{<\}}$ beispielsweise aus einer zweistelligen Relation < und ist ${\displaystyle {\mathfrak {A}}=(\{1,\ldots ,n\},I)}$, wobei ${\displaystyle I}$ die Relation als die übliche Größenrelation zwischen natürlichen Zahlen interpretiert, so ist ${\displaystyle G({\mathfrak {A}})}$ der vollständige Graph mit Punkten ${\displaystyle \{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 ${\displaystyle \sigma =\{E\}}$ mit einer zweistelligen Relation ${\displaystyle E}$, so dass jede endliche ${\displaystyle L_{I}^{\sigma }}$-Struktur ${\displaystyle {\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 ${\displaystyle {\mathfrak {A}}=(A,I)}$ ihren Gaifman-Graphen ${\displaystyle G({\mathfrak {A}})}$ zugeordnet haben, können wir vom Abstand zweier Elemente des zugehörigen Universums ${\displaystyle A}$ sprechen, wir setzen

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

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

${\displaystyle 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 ${\displaystyle \infty }$ annehmen kann, genügt es, ganzzahlige Radien ${\displaystyle 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 ${\displaystyle \sigma }$-Struktur auf den ${\displaystyle r}$-Kugeln betrachten. Da wir in ${\displaystyle \sigma }$ nur Relationen ${\displaystyle R}$ und keine Funktionen haben, ist das einfach die Einschränkung der Relationen ${\displaystyle R^{\mathfrak {A}}}$. Dabei sind folgende zwei Dinge zu beachten.

Enthält die Signatur Konstanten ${\displaystyle 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 ${\displaystyle 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

${\displaystyle 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 s​ich lediglich a​ls eine technische Ergänzung dieser Überlegungen.

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

Zweitens wollen wir die Zentren ${\displaystyle 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 ${\displaystyle \sigma }$ um neue Konstanten zu ${\displaystyle {\tilde {c}}_{1},\ldots ,{\tilde {c}}_{n}}$, die durch ${\displaystyle a_{1}\ldots ,a_{n}}$ zu interpretieren sind, und setzten ${\displaystyle \sigma _{n}:=\sigma \cup \{{\tilde {c}}_{1},\ldots ,{\tilde {c}}_{n}\}}$.

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

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

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

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

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

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

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

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

Hanf-Lokalität

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

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

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

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

Gaifman-Lokalität

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

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

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

Gaifman-Lokalität ist der schwächere Begriff, es besteht die Beziehung ${\displaystyle lr(Q)\leq 3\cdot hlr(Q)+1}$.[8] 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 ${\displaystyle Q}$ nicht diese Lokalitätsbedingung erfüllen. Daraus folgt dann, dass ${\displaystyle 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 ${\displaystyle FO[k]}$ alle logischen Ausdrücke der Prädikatenlogik erster Stufe, deren Quantoren eine Verschachtelungstiefe von höchstens ${\displaystyle k}$ haben, so gilt

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

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

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

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

Zusammenhang von Graphen

Es sei ${\displaystyle Q}$ die boolesche Eigenschaft eines Graphen, das heißt einer ${\displaystyle \{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 ${\displaystyle Q}$ nicht Hanf-lokal ist. Wäre ${\displaystyle Q}$ Hanf-lokal, etwa mit ${\displaystyle hlr(Q)=r}$, so wähle ein ${\displaystyle m>2r+1}$ und betrachte den zyklischen Graphen ${\displaystyle G_{1}=C_{2m}}$ mit ${\displaystyle 2m}$ Knoten und den Graphen ${\displaystyle G_{2}=C_{m}+C_{m}}$, der aus der disjunkten Vereinigung zweier zyklischer Graphen mit je ${\displaystyle m}$ Knoten besteht. Die Gaifman-Graphen dieser Strukturen sind die Graphen selbst. In jedem dieser Graphen ${\displaystyle G_{i}}$ besteht eine ${\displaystyle r}$-Kugel ${\displaystyle N_{r}^{G_{i}}(a)}$ nach Wahl von ${\displaystyle m}$ aus einer Kette der Länge ${\displaystyle 2r+1}$ mit Mittelpunkt ${\displaystyle a}$, und die sind als Untergraphen mit vorgegebenem Mittelpunkt alle untereinander isomorph. Jede Bijektion ${\displaystyle f:G_{1}\rightarrow G_{2}}$ (beide Graphen haben ${\displaystyle 2m}$ Knoten) zeigt daher ${\displaystyle G_{1}\leftrightarrows _{r}G_{2}}$ und aus der angenommenen Hanf-Lokalität folgte ${\displaystyle Q(G_{1})=Q(G_{2})}$. Das kann aber nicht sein, denn ${\displaystyle G_{1}}$ ist zusammenhängend, ${\displaystyle G_{2}}$ aber nicht.[10]

Transitive Hülle

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

Nun beschreibe ${\displaystyle Q}$ die transitive Hülle einer ${\displaystyle \{R\}}$-Struktur, das heißt ${\displaystyle Q({\mathfrak {A}})}$ ist die Menge aller Paare ${\displaystyle (a,b)\in A^{2}}$, so dass es ${\displaystyle m\geq 1}$ und ${\displaystyle a_{0},a_{1},\ldots ,a_{m}\in A}$ gibt mit ${\displaystyle (a_{i-1},a_{i})\in R}$ für alle ${\displaystyle i=1,\ldots ,m}$ und ${\displaystyle 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 ${\displaystyle Q}$ nicht Gaifman-lokal ist. Wäre ${\displaystyle Q}$ Gaifman-lokal, etwa mit ${\displaystyle lr(Q)=r}$, so betrachte als ${\displaystyle \{R\}}$-Struktur eine Kette ${\displaystyle {\mathfrak {A}}=(\{0,\ldots ,m\},I)}$ mit ${\displaystyle m>4r+1}$. Kette bedeutet, dass die Relation als ${\displaystyle \{(0,1),\ldots ,(m-1,m)\}}$ interpretiert wird. Die transitive Hülle dieser Relation ist dann nichts anderes als die natürliche Ordnung < auf ${\displaystyle \{0,1,\ldots ,m\}}$. Der Gaifman-Graph ${\displaystyle G=G({\mathfrak {A}})}$ ist ein linearer Graph der Länge ${\displaystyle m+1}$. Auf Grund der Wahl von ${\displaystyle m}$ kann man zwei Knoten ${\displaystyle a_{1},a_{2}\in \{0,1,\ldots ,m\}}$ wählen, die von den Rändern den Abstand ${\displaystyle r}$ und untereinander den Abstand ${\displaystyle \geq 2r+1}$ haben. Dann bestehen ${\displaystyle N_{r}^{G}((a_{1},a_{2}))}$ und ${\displaystyle N_{r}^{G}((a_{2},a_{1}))}$ beide aus je zwei disjunkten Teilketten der Länge ${\displaystyle 2r}$ mit Mittelpunkten ${\displaystyle a_{i}}$. Daraus folgt ${\displaystyle 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 ${\displaystyle (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 ${\displaystyle a_{1}<a_{2}}$ und ${\displaystyle a_{2}<a_{1}}$ ist genau eine wahr.[11]

Weitere Logiken

Im Lichte obiger Beispiele stellt s​ich die Frage, o​b es Erweiterungen d​er Prädikatenlogik erster Stufe gibt, für d​ie jeder Ausdruck ebenfalls e​ine lokale Eigenschaft definiert. Derartige Erweiterungen wären i​mmer noch n​icht ausdrucksstark genug, u​m Graphenzusammenhang o​der die transitive Hülle i​n endlichen Strukturen z​u 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 ${\displaystyle (FO+<)_{inv}}$, das heißt ${\displaystyle 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[12]) und man kann zeigen, dass jede ${\displaystyle (FO+<)_{inv}}$-Eigenschaft Gaifman-lokal ist (Satz von Grohe-Schwentick[13]).

Bestimmte Ausdrücke infinitärer Logiken, d​ie um Möglichkeiten d​es Zählens erweitert sind, können ebenfalls a​ls Hanf- bzw. Gaifman-lokal nachgewiesen werden.[14]

Siehe auch

• Satz von Gaifman

Einzelnachweise

1. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Definition 2.7
2. Heinz-Dieter Ebbinghaus, Jörg Flum: Finite Model Theory, Springer-Verlag 1999, ISBN 3-540-28787-6, Kapitel 2.4
3. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag 2004, ISBN 3-540-21202-7, Definition 4.1
4. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Definition 4.2
5. Grädel, Kolaitis, Libkin, Marx, Spencer, Vardi, Venema, Weinstein: Finite Model Theory and Its Applications, Springer-Verlag (2007), ISBN 978-3-540-00428-8, Definition 2.3.24, hier hat ${\displaystyle N_{r}}$ abweichend das Universum ${\displaystyle B_{r-1}}$.
6. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Definition 4.6
7. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Definition 4.7
8. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Theorem 4.11
9. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Theorem 4.12
10. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Seite 48
11. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Seite 49
12. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Theorem 5.2
13. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Theorem 5.8
14. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Theorem 8.4