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 $φ$ in der Prädikatenlogik erster Stufe genau dann für fast alle endlichen Graphen gilt, wenn $φ$ 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]

Definition

Der Rado-Graph $ℛ 𝒢$ ist definiert als der (ungerichtete) Graph $(ℕ, E),$ wobei zwei Zahlen $i, j \in ℕ$ mit $j < i$ genau dann durch eine Kante verbunden sind, also $E (i, j)$ gilt, wenn $B I 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 $ℕ$ als Knotenmenge und verbindet jedes Zahlenpaar ${i, j}$ mit $i \neq j$ unabhängig und mit Wahrscheinlichkeit $\frac{1}{2}$ mit einer Kante. Diese Konstruktion liefert fast sicher den Rado-Graphen.^[4]

Eigenschaften

Erweiterungseigenschaft

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 ℕ$ mit $m \leq n$ die Formel

$E A_{n, m} \equiv \forall x_{1}, ..., x_{n} ((\underset{i \neq j}{⋀} x_{i} \neq x_{j}) \to \exists z (⋀_{i = 1}^{n} z \neq x_{i} \land \underset{i \leq m}{⋀} E (z, x_{i}) \land \underset{i > m}{⋀} \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 $B I T (z, x_{i}) = 1$ für alle $i \in {1, ..., m} \cup {m a 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 $ℛ 𝒢 ⊨ E (z, x_{i})$ für alle $i \in {1, ..., m}$ und $ℛ 𝒢 ⊨ \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. $B I T (z, 0) = B I T (z, 2) = B I T (z, 3) = B I T (z, 5) = B I T (z, 8) = 1,$ wobei $8 = m a 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} ∣ i \in ℕ}$ bzw. $B = {b_{j} ∣ j \in ℕ},$ 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 ∖ 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 ∖ B_{n + 1}$ mit kleinstem Index ein entsprechendes Element $a_{l} \in A ∖ 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 $⋃_{n \in ℕ} h_{n}$ ein Isomorphismus zwischen $𝒜$ und $ℬ$ .

Logische Theorie

Offensichtlich folgt die Erweiterungseigenschaft bereits aus der Formelmenge $E A := {E A_{2 k, k} ∣ k \in ℕ} .$ Wie im vorigen Abschnitt gezeigt, ist $E A$ (zusammen mit der Formel $\forall x (\neg E (x, x)) \land \forall y \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 $E A$ 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 $E A$ Quantorenelimination.^[5]

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 ℕ$ sei $G_{n}$ die Menge aller nummerierten ungerichteten Graphen mit Knotenmenge ${1, ..., n} .$ Betrachte eine Gleichverteilung auf $G_{n}$ . Für einen Satz $φ$ in der Sprache ${E}$ der Graphen sei $μ_{n} (φ)$ die Wahrscheinlichkeit, dass $φ$ in einem zufällig ausgewählten Graphen aus $G_{n}$ gilt, d. h.

$μ_{n} (φ) = \frac{| {G \in G_{n} : G ⊨ φ} |}{| G_{n} |} .$

Das Null-Eins-Gesetz besagt nun, dass

$μ (φ) := lim_{n \to \infty} μ_{n} (φ) \in {0, 1} .$

Für den Beweis überlegt man sich zuerst Folgendes: Haben zwei Graphen $𝒜$ und $ℬ$ die Erweiterungseigenschaft $E A_{2 k, 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 $μ (E A_{2 k, k}) = 1$ für alle $k \in ℕ$ gilt. Also gelten für jedes $k \in ℕ$ 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 ℕ$ die Erweiterungseigenschaft $E A_{2 k, k}$ hat, gilt für jeden Satz $φ$

$ℛ 𝒢 ⊨ φ ⟺ μ (φ) = 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.^[6]

Literatur

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.

Einzelnachweise

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

[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.

[1]

[2]

[3]

[4]

[5]

[6]