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 ${\displaystyle {\tfrac {1}{2}}}$ durch eine Kante verbunden wird.

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

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

Der Rado-Graph ${\displaystyle {\mathcal {RG}}}$ ist definiert als der (ungerichtete) Graph ${\displaystyle (\mathbb {N} ,E),}$ wobei zwei Zahlen ${\displaystyle i,j\in \mathbb {N} }$ mit ${\displaystyle j<i}$ genau dann durch eine Kante verbunden sind, also ${\displaystyle E(i,j)}$ gilt, wenn ${\displaystyle \mathrm {BIT} (i,j)=1,}$ d. h. wenn das ${\displaystyle j}$-te Bit in der Binärdarstellung von ${\displaystyle i}$ gleich ${\displaystyle 1}$ ist. Zum Beispiel hat ${\displaystyle 35}$ die Binärdarstellung ${\displaystyle 100011,}$ die an den Stellen ${\displaystyle 0,1}$ und ${\displaystyle 5}$ einen Einser hat; also gilt im Rado-Graphen ${\displaystyle E(35,0),E(35,1)}$ und ${\displaystyle 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 ${\displaystyle \mathbb {N} }$ als Knotenmenge und verbindet jedes Zahlenpaar ${\displaystyle \{i,j\}}$ mit ${\displaystyle i\neq j}$ unabhängig und mit Wahrscheinlichkeit ${\displaystyle {\tfrac {1}{2}}}$ mit einer Kante. Diese Konstruktion liefert fast sicher den Rado-Graphen.^[4]

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

$${\displaystyle EA_{n,m}\equiv \forall x_{1},...,x_{n}\left(\left(\bigwedge \limits _{i\neq j}x_{i}\neq x_{j}\right)\rightarrow \exists z\left(\bigwedge \limits _{i=1}^{n}z\neq x_{i}\land \bigwedge \limits _{i\leq m}E(z,x_{i})\land \bigwedge \limits _{i>m}\neg E(z,x_{i})\right)\right).}$$

Das kann man wie folgt leicht einsehen: Seien ${\displaystyle U=\{x_{1},...,x_{m}\}}$ und ${\displaystyle Y=\{x_{m+1},...,x_{n}\}}$ disjunkt, dann sei ${\displaystyle z}$ jene Zahl, die ${\displaystyle \mathrm {BIT} (z,x_{i})=1}$ für alle ${\displaystyle i\in \{1,...,m\}\cup \{\mathrm {max} (U\cup V)+1\}}$ erfüllt und deren andere Bits alle ${\displaystyle 0}$ sind. Weil ${\displaystyle U}$ und ${\displaystyle V}$ disjunkt sind, ist ${\displaystyle z}$ wohldefiniert. Nach Konstruktion gilt ${\displaystyle {\mathcal {RG}}\models E(z,x_{i})}$ für alle ${\displaystyle i\in \{1,...,m\}}$ und ${\displaystyle {\mathcal {RG}}\models \neg E(z,x_{j})}$ für alle ${\displaystyle j\in \{m+1,...,n\}.}$

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

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

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

Offensichtlich folgt die Erweiterungseigenschaft bereits aus der Formelmenge ${\displaystyle EA:=\{EA_{2k,k}\mid k\in \mathbb {N} \}.}$ Wie im vorigen Abschnitt gezeigt, ist ${\displaystyle EA}$ (zusammen mit der Formel ${\displaystyle \forall x\,(\neg E(x,x))\land \forall y\forall z\,(E(y,z)\leftrightarrow E(z,y))}$, die besagt, dass die Kantenrelation ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle EA}$ Quantorenelimination.^[5]

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

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

$${\displaystyle \mu _{n}(\varphi )={\frac {|\{G\in G_{n}\colon G\models \varphi \}|}{|G_{n}|}}.}$$

Das Null-Eins-Gesetz besagt nun, dass

$${\displaystyle \mu (\varphi ):=\lim _{n\rightarrow \infty }\mu _{n}(\varphi )\in \{0,1\}.}$$

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

Weil insbesondere der Rado-Graph selbst für jedes ${\displaystyle k\in \mathbb {N} }$ die Erweiterungseigenschaft ${\displaystyle EA_{2k,k}}$ hat, gilt für jeden Satz ${\displaystyle \varphi }$

$${\displaystyle {\mathcal {RG}}\models \varphi \iff \mu (\varphi )=1.}$$

Da die Theorie von ${\displaystyle {\mathcal {RG}}}$ 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.^[6]

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

1. ↑ Rado, Universal graphs and universal functions, Acta Arithmetica, Band 9, 1964, S. 331–340.
2. ↑ Paul Erdős, Alfred Rényi, Asymmetric graphs, Acta Mathematica Academiae Scientiarum Hungaricae, Band 14, 1963, S. 295–315
3. ↑ Ackermann, Die Widerspruchsfreiheit der allgemeinen Mengenlehre, Mathematische Annalen, Band 114, 1937, S. 305–315
4. ↑ Hodges, S. 351 f.
5. ↑ Hodges, S. 350
6. ↑ Libkin, S. 240 f.