Rado-Graph

Der Rado-Graph (auch als Erdős-Rényi-Graph oder Zufallsgraph bezeichnet) ist ein spezieller abzählbar unendlicher Graph, der fast sicher entsteht, wenn jedes Knotenpaar unabhängig und mit Wahrscheinlichkeit $\frac{1}{2}$ durch eine Kante verbunden wird.

Eine wichtige Erkenntnis ist, dass ein Satz $\phi$ in der Prädikatenlogik erster Stufe genau dann für fast alle endlichen Graphen gilt, wenn $\phi$ vom Rado-Graphen erfüllt wird.

Er ist aufgrund von Arbeiten in den 1960er-Jahren nach Richard Rado bzw. Rado, Paul Erdős und Alfréd Rényi benannt, taucht aber schon 1937 bei Wilhelm Ackermann auf.

Definition

Ein Ausschnitt des Rado-Graphen mit den ersten acht Knoten.

Der Rado-Graph $ℛ𝒢$ ist definiert als der (ungerichtete) Graph $(\mathbb{N},E),$ wobei zwei Zahlen $i,j\in \mathbb{N}$ mit $j<i$ genau dann durch eine Kante verbunden sind, also $E(i,j)$ gilt, wenn $\mathrm{B}\mathrm{I}\mathrm{T}(i,j)=1,$ d. h. wenn das $j$-te Bit in der Binärdarstellung von $i$ gleich $1$ ist. Zum Beispiel hat $35$ die Binärdarstellung $100011,$ die an den Stellen $0,1$ und $5$ einen Einser hat; also gilt im Rado-Graphen $E(35,0),E(35,1)$ und $E(35,5).$

Es gibt zahlreiche äquivalente Möglichkeiten, den Rado-Graphen zu definieren, unter anderem durch eine probabilistische Konstruktion: Man nimmt die natürlichen Zahlen $\mathbb{N}$ als Knotenmenge und verbindet jedes Zahlenpaar $\{i,j\}$ mit $i\ne j$ unabhängig und mit Wahrscheinlichkeit $\frac{1}{2}$ mit einer Kante. Diese Konstruktion liefert fast sicher den Rado-Graphen.

Eigenschaften

Erweiterungseigenschaft

Der Rado-Graph hat die Erweiterungseigenschaft: Für je zwei disjunkte, endliche Teilmengen $U$ and $V$ gibt es einen Knoten $x,$ der zu allen Knoten in $U$ und zu keinem Knoten in $V$ adjazent ist.

Der Rado-Graph besitzt folgende bemerkenswerte Eigenschaft, die sogenannte Erweiterungseigenschaft: Zu je zwei disjunkten, endlichen Knotenmengen $U$ und $V$ gibt es stets einen Knoten $z,$ der zu allen Knoten in $U$ und zu keinem Knoten in $V$ adjazent ist. Formal erfüllt $ℛ𝒢$ für alle $n,m\in \mathbb{N}$ mit $m\le n$ die Formel

$$E{A}_{n,m}\equiv \mathrm{\forall }{x}_1,...,x_n((\underset{i\ne j}{\bigwedge }{x}_i\ne x_j)\to \mathrm{\exists }z(\underset{i=1}{\overset{n}{\bigwedge }}z\ne x_i\wedge \underset{i\le m}{\bigwedge }E(z,x_i)\wedge \underset{i>m}{\bigwedge }\mathrm{\neg }E(z,x_i))).$$

Das kann man wie folgt leicht einsehen: Seien $U=\{x_1,...,x_m\}$ und $Y=\{x_{m+1},...,x_n\}$ disjunkt, dann sei $z$ jene Zahl, die $\mathrm{B}\mathrm{I}\mathrm{T}(z,x_i)=1$ für alle $i\in \{1,...,m\}\cup \{\mathrm{m}\mathrm{a}\mathrm{x}(U\cup V)+1\}$ erfüllt und deren andere Bits alle $0$ sind. Weil $U$ und $V$ disjunkt sind, ist $z$ wohldefiniert. Nach Konstruktion gilt $ℛ𝒢\models E(z,x_i)$ für alle $i\in \{1,...,m\}$ und $ℛ𝒢\models \mathrm{\neg }E(z,x_j)$ für alle $j\in \{m+1,...,n\}.$

Betrachte hierzu folgendes Beispiel: Sei $U=\{0,2,3,5\}$ und $V=\{1,4,7\},$ dann hat $z$ die Binärdarstellung $100101101,$ d. h. $\mathrm{B}\mathrm{I}\mathrm{T}(z,0)=\mathrm{B}\mathrm{I}\mathrm{T}(z,2)=\mathrm{B}\mathrm{I}\mathrm{T}(z,3)=\mathrm{B}\mathrm{I}\mathrm{T}(z,5)=\mathrm{B}\mathrm{I}\mathrm{T}(z,8)=1,$ wobei $8=\mathrm{m}\mathrm{a}\mathrm{x}(U\cup V)+1.$

Eindeutigkeit

Der Rado-Graph ist bis auf Isomorphie der einzige abzählbare Graph, der die Erweiterungseigenschaft besitzt. Um das zu zeigen, seien $𝒜$ und $ℬ$ zwei abzählbare Graphen mit Knotenmengen $A=\{a_i\mid i\in \mathbb{N}\}$ bzw. $B=\{b_j\mid j\in \mathbb{N}\},$ die die Erweiterungseigenschaft haben. Dann kann man wie folgt einen Isomorphismus $h:𝒜\to ℬ$ mit einer Back-and-forth-Konstruktion bauen: Seien ${𝒜}_n$ und ${ℬ}_n$ zwei endliche, zueinander vermöge eines Isomorphismus $h_n:{𝒜}_n\to B_n$ isomorphe Subgraphen von $𝒜$ bzw. $ℬ$ und sei $a_i$ jenes Element von $A$ mit kleinstem Index, das nicht in $A_n$ vorkommt. Weil $ℬ$ die Erweiterungseigenschaft hat, gibt es ein Element $b_j\in B\mathrm{\setminus }{B}_n$, das zu den Elementen von $B_n$ genau dieselben Kanten hat, wie $a_i$ zu den entsprechenden Elementen (bezüglich $h_n$) in $A_n.$ Ergo kann man $h_n$ zu einem Isomorphismus $h_{n+1}:{𝒜}_{n+1}\to {ℬ}_{n+1}$ durch die Vorschrift $h_{n+1}(a_i):=b_j$ erweitern, wobei ${𝒜}_{n+1}:={𝒜}_n\cup \{a_i\}$ und ${ℬ}_{n+1}:={ℬ}_n\cup \{b_j\}.$ Anschließend verfährt man völlig analog, um zum Element $b_k\in B\mathrm{\setminus }{B}_{n+1}$ mit kleinstem Index ein entsprechendes Element $a_l\in A\mathrm{\setminus }{A}_{n+1}$ zu finden und $h_{n+1}$ zu einem Isomorphismus $h_{n+2}:{𝒜}_{n+1}\cup \{a_l\}\to B_{n+1}\cup \{b_k\}$ zu erweitern.

Wird abwechselnd jeweils das noch nicht verwendete Element aus $A$ bzw. $B$ mit kleinstem Index auf diese Art hinzufügt, ist schließlich $\bigcup _{n\in \mathbb{N}}{h}_n$ ein Isomorphismus zwischen $𝒜$ und $ℬ$.

Logische Theorie

Offensichtlich folgt die Erweiterungseigenschaft bereits aus der Formelmenge $EA:=\{E{A}_{2k,k}\mid k\in \mathbb{N}\}.$ Wie im vorigen Abschnitt gezeigt, ist $EA$ (zusammen mit der Formel $\mathrm{\forall }x(\mathrm{\neg }E(x,x))\wedge \mathrm{\forall }y\mathrm{\forall }z(E(y,z)\leftrightarrow E(z,y))$, die besagt, dass die Kantenrelation $E$ irreflexiv und symmetrisch ist) ω-kategorisch, d. h. hat bis auf Isomorphie nur ein abzählbares Modell (nämlich den Rado-Graphen). Aus dem Satz von Löwenheim-Skolem folgt daraus unmittelbar, dass $EA$ eine vollständige Theorie ist. Weil sie des Weiteren axiomatisierbar ist (d. h. rekursiv aufzählbar), ist ihr deduktiver Abschluss aufgrund ihrer Vollständigkeit sogar entscheidbar.

Des Weiteren hat $EA$ Quantorenelimination.

Null-Eins-Gesetz der Prädikatenlogik erster Stufe

Eng verwandt mit dem Rado-Graphen ist das Null-Eins-Gesetz der Prädikatenlogik erster Stufe:

Für jedes $n\in \mathbb{N}$ sei $G_n$ die Menge aller nummerierten ungerichteten Graphen mit Knotenmenge $\{1,...,n\}.$ Betrachte eine Gleichverteilung auf $G_n$. Für einen Satz $\phi$ in der Sprache $\{E\}$ der Graphen sei ${\mu }_n(\phi )$ die Wahrscheinlichkeit, dass $\phi$ in einem zufällig ausgewählten Graphen aus $G_n$ gilt, d. h.

$${\mu }_n(\phi )=\frac{|\{G\in G_n:G\models \phi \}|}{|G_n|}.$$

Das Null-Eins-Gesetz besagt nun, dass

$$\mu (\phi ):=\underset{n\to \mathrm{\infty }}{\lim }{\mu }_n(\phi )\in \{0,1\}.$$

Für den Beweis überlegt man sich zuerst Folgendes: Haben zwei Graphen $𝒜$ und $ℬ$ die Erweiterungseigenschaft $E{A}_{2k,k}$, so folgt daraus unmittelbar, dass der Duplikator das $k$-Runden-Ehrenfeucht-Fraïssé-Spiel auf $𝒜$ und $ℬ$ gewinnt. Nach dem Satz von Ehrenfeucht-Fraïssé bedeutet das, dass in $𝒜$ und $ℬ$ dieselben Sätze vom Quantorenrang $k$ gelten. Nun kann man mit einfachen kombinatorischen Überlegungen und Abschätzungen nachweisen, dass $\mu (E{A}_{2k,k})=1$ für alle $k\in \mathbb{N}$ gilt. Also gelten für jedes $k\in \mathbb{N}$ in fast allen Graphen dieselben Sätze vom Quantorenrang $k.$ Daraus folgt sofort das Null-Eins-Gesetz, denn jeder Satz hat einen solchen Quantorenrang.

Weil insbesondere der Rado-Graph selbst für jedes $k\in \mathbb{N}$ die Erweiterungseigenschaft $E{A}_{2k,k}$ hat, gilt für jeden Satz $\phi$

$$ℛ𝒢\models \phi ⟺\mu (\phi )=1.$$

Da die Theorie von $ℛ𝒢$ entscheidbar ist, ist also auch das Berechnungsproblem, welche Sätze in fast allen Graphen gelten, entscheidbar.

Das Null-Eins-Gesetz lässt sich leicht auf beliebige relationale Sprachen verallgemeinern.

Literatur

• Vorlage:Anker Leonid Libkin: Elements of Finite Model Theory, Springer Verlag, 2004, ISBN 9783662070031.
• Vorlage:Anker Wilfrid Hodges: Model Theory (Encyclopedia of Mathematics and its Applications), Cambridge University Press, 1993, ISBN 9780511551574.