Lemma von König

Das Lemma von König oder Königs Unendlichkeitslemma (englisch König’s infinity lemma) ist ein mathematischer Lehrsatz, welcher sowohl dem Gebiet der Ramseytheorie als auch dem der Graphentheorie zuzurechnen ist. Das Lemma geht auf den ungarischen Mathematiker Dénes Kőnig und dessen klassische Monographie Theorie der endlichen und unendlichen Graphen von 1936 zurück. Es spielt nicht zuletzt in der Berechenbarkeitstheorie eine wichtige Rolle und wurde daher auch in der Mathematischen Logik erforscht.

Aussage des Lemmas

Sei $G$ ein zusammenhängender Graph mit unendlich vielen Knoten, so dass jeder Knoten endlichen Grad hat, also nur zu endlich vielen anderen Knoten benachbart ist. Von einem beliebigen Startknoten ausgehend gibt es dann stets einen unendlich langen Pfad in $G$, auf welchem jeder Knoten höchstens einmal besucht wird.

Ein gebräuchlicher Spezialfall ist, dass jeder Baum bestehend aus unendlich vielen Knoten endlichen Grades einen unendlichen Pfad besitzt.

Zu beachten ist, dass der Knotengrad endlich, allerdings nicht beschränkt sein muss. Es ist möglich, einen Knoten mit Grad 10, einen mit Grad 100, den dritten mit Grad 1000 usw. zu haben.

Beweis

Angenommen, der Graph sei zusammenhängend und besitze unendlich viele Knoten $v_{i}$.

Angefangen mit einem beliebigen Knoten $v_{1}$, kann jeder Knoten von $G$ vom Knoten $v_{1}$ aus durch einen Pfad erreicht werden. Ein solcher Pfad muss an einem der endlich vielen zu $v_{1}$ adjazenten Knoten beginnen. Es muss einen der adjazenten Knoten geben, durch den unendlich viele Knoten erreicht werden können. Gäbe es keinen solchen Knoten, dann wäre der gesamte Graph eine Vereinigung von endlich vielen endlichen Knotenmegen und stände daher im Widerspruch zur Annahme des unendlichen Graphen.

Sei $v_{2}$ einer dieser Knoten. Damit können unendlich viele Knoten aus $G$ von $v_{2}$ aus durch einen Pfad erreicht werden, der nicht $v_{1}$ enthält. Jeder solche Pfad muss an einem der endlich vielen zu $v_{2}$ adjazenten Knoten beginnen. Ein ähnliches Argument wie oben zeigt uns, dass es einen adjazenten Knoten geben muss, durch den unendlich viele Knoten erreicht werden können; dieser sei $v_{3}$.

Auf diese Art und Weise kann induktiv ein unendlicher Pfad konstruiert werden. Bei jedem Schritt besagt die Induktionsvoraussetzung, dass es unendlich viele Knoten gibt, die mittels eines Pfades von $v_{i}$ aus erreicht werden können, wobei dieser Pfad eine endliche Menge von Knoten nicht enthalten darf. Der Induktionsschritt wird mit dem Argument vollzogen, dass einer der zu $v_{i}$ adjazenten Knoten die Induktionsvoraussetzung erfüllt, selbst wenn $v_{i}$ zu jener endlichen Menge gehört.

Dieser Beweis gilt als nicht konstruktiv, weil bei jedem Schritt ein Beweis durch Widerspruch geschieht, um zu zeigen, dass es einen adjazenten Knoten gibt, von dem aus unendlich viele andere Knoten erreicht werden können. Rechnerische Analysen deuten darauf hin, dass es keinen konstruktiven Beweis gibt.

Berechenbarkeit

Die Berechenbarkeit des Lemmas von König wurde gründlich erforscht. Die Formulierung des Lemmas, nämlich dass jeder unendliche, endlich verzweigte Teilbaum von $\omega ^{<\omega }\,$ einen unendlichen Pfad hat, ist für diesen Zweck sehr günstig. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} steht hier für eine Menge natürlicher Zahlen, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} die kanonische Aufzählung aller endlichen, nach Zwischenergebnis sortierten Folgen von natürlichen Zahlen ist. Jede endliche Folge kann mittels einer partiellen Funktion von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} in sich selbst bestimmt werden. Jeder unendliche Pfad kann mit einer totalen Funktion bestimmt werden. Daher ist die Analyse mit Hilfe der Berechenbarkeitstheorie möglich.

Ein Teilbaum von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} , in dem jede Folge nur endlich viele direkte Nachfolger hat, d. h. der entsprechende Baum hat endlichen Grad an allen Knoten, heißt endlich verzweigt. Nicht jeder unendliche Teilbaum von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} besitzt einen unendlichen Pfad, aber das Lemma zeigt, dass jeder endlich verzweigte Teilbaum einen unendlichen Pfad haben muss.

Für alle Teilbäume Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} bezeichnet die Notation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Ext(T)} die Menge an Knoten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} , durch die ein unendlicher Pfad führt. Selbst wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} berechenbar ist, ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Ext(T)} nicht zwangsläufig berechenbar. Jeder Teilbaum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} , der einen unendlichen Pfad hat, hat auch einen unendlichen Pfad, der aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Ext(T)} berechenbar ist.

Es existieren endlich verzweigte, berechenbare Teilbäume von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} , die keinen arithmetischen und keinen hyperarithmetischen Pfad haben. Jeder berechenbare Teilbaum von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} mit Pfad muss einen Pfad haben, der von Kleenes O, der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Pi^1_1} vollständigen Menge, berechenbar ist. Das liegt daran, dass die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Ext(T)} immer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^1_1} ist und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T} somit berechenbar ist.

Eine genauere Analyse wurde für berechenbare beschränkte Bäume durchgeführt. Ein Teilbaum von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{<\omega}\,} heißt berechenbar beschränkt oder rekursiv beschränkt, wenn es eine berechenbare Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} gibt, so dass für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} es keine Folge im Baum gibt, dessen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -tes Element größer als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(n)} ist. Somit gibt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} eine Schranke für die "Breite" des Baums an. Die folgenden Basissätze gelten für unendliche berechenbar beschränkte, endlich verzweigte berechenbare Teilbäume von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega^{< \omega}\,} .

• Jeder solche Baum hat einen berechenbaren Pfad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0'} , der kanonischen und Turing-vollständigen Menge, die das Halteproblem entscheiden kann.
• Jeder solche Baum hat einen niedrigen Pfad. D. h. der Turing-Sprungoperator des Pfades hat denselben Turinggrad wie das Halteproblem.
• Jeder solche Baum hat einen Pfad, der hyperimmun frei ist. D. h. jede vom Pfad aus berechenbare Funktion wird durch eine berechenbare Funktion dominiert.
• Für alle nicht berechenbaren Teilmengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} hat der Baum einen Pfad, der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} nicht berechnet.

Eine schwächere Form des Lemmas von König wird bei der Definition des Subsystems Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{WKL}_0} der Arithmetik zweiter Ordnung benutzt. Dieses Subsystem hat eine wichtige Rolle in der reversen Mathematik.

Beziehung zur konstruktiven Mathematik und Kompaktheit

Das Fan Theorem von Brouwer ist vom klassischen Standpunkt her Gegenposition des Lemmas von König. Eine Teilmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{0,1\}^{<\omega}\,} heißt Bar, wenn jede Funktion von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} in die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{0,1\}} ein erstes Segment in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S} besitzt. Ein Bar heißt lösbar, wenn jede Folge entweder im Bar oder nicht im Bar liegt. Diese Prämisse ist notwendig. Ein Bar ist uniform, wenn es eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gibt, so dass von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \omega} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{0,1\}} ein erstes Segment im Bar mit einer Länge von maximal Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} existiert. Brouwers Fan Theorem besagt, dass jeder lösbare Bar uniform ist.

Beziehung zum Auswahlaxiom

Das Lemma von König beinhaltet das Auswahlprinzip; der erste Beweis oben zeigt die Beziehung zwischen dem Lemma und dem Axiom der abhängigen Auswahl. Bei jedem Induktionsschritt muss ein Knoten mit einer bestimmten Eigenschaft gewählt werden. Zwar wird bewiesen, dass mindestens ein geeigneter Knoten existiert; wenn es aber mehrere passende Knoten gibt, gibt es möglicherweise keine kanonische Auswahl. Dieser Fall kann nicht aufkommen, wenn der Graph als abzählbar angenommen wird.

Das Lemma ist hauptsächlich eine Einschränkung des Axiom der abhängigen Auswahl auf die vollständigen Relationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} , so dass es für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} endlich viele Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle xRz} gibt. Die Form des Lemmas, die aussagt, dass jeder unendliche endlich verzweigte Baum einen unendlichen Pfad hat, ist äquivalent zum Grundsatz, dass jede Folge endlicher Mengen eine Auswahlfunktion besitzt (vgl. Levy [1979, Exercise IX.2.18]). Somit gibt es Modelle der Zermelo-Fraenkel-Mengenlehre ohne Auswahl, in der diese Form des Lemmas von König nicht zutrifft.

Literatur

• Reinhard Diestel: Graphentheorie. 2. Auflage. Springer Verlag, Berlin / Heidelberg / New York (und weitere) 2000, ISBN 3-540-67656-2. 
• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6. 
• Dénes König: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Hrsg.: H. Sachs (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4. 
• A. Levy: Basic Set Theory. Springer, 1979 (Neudruck: Dover 2002, ISBN 0-486-42079-5). 
• S. Simpson: Subsystems of Second Order Arithmetic. Springer, 1999, ISBN 3-540-64882-8. 
• R. Soare: Recursively Enumerable Sets and Degrees. Springer, 1987, ISBN 0-387-15299-7. 

Weblinks

• Konstruktive Mathematik Stanford Encyclopedia of Philosophy (englisch)
• Das Mizar Projekt hat den Beweis einer Abwandlung des Lemmas von König komplett formalisiert und automatisch überprüft. mizar.org (englisch)