Königs Lemma – König's Lemma

Königs Lemma – König's Lemma
Nach Dénes König ( 21. September 1884 Budapest – 19. Oktober 1944 Budapest), 1926, u.a.

Königs Lemma gibt es in verschiedenen Ausprägungen.
Wenn ein Baum (Graph) an jedem Verzweigungspunkt endlich viele Verzweigungen hat und die Äste (Teilpfade) willkürlich lang sind, so hat er einen unendlichen Ast (Pfad).
Oder
Wenn es keine obere Grenze für die Pfadlänge in einem endlich verzweigenden Baum gibt, dann gibt es mindestens einen unendlich langen Pfad im Baum.
Oder

"In a geometric tree with finitely many arrows leading from each vertex, if there are arbitrarily long finite partial paths, then there is an infinite path."
Kleene 1968, S. 302.

Oder mit veränderten Prämissen
Ein endlich-verzweigender nicht-endlicher Baum besitzt einen nicht-endlichen Ast.
Oder

"Jeder unendliche zusammenhängende Graph G endlichen Grades besitzt einen einseitig unendlichen Weg, wobei der Anfangspunkt P0 dieses Weges beliebig vorgeschrieben werden kann."
König 1986 [1936 S. 80; 1927, S. 122.], S. 96
"Laufen nach jedem Knotenpunkt eines Graphen eine endliche Anzahl von Kanten, so heißt der Graph von endlichem Grade"
König 1986 [1936 S. 3], S. 19

Dieses Lemma wird nicht direkt bewiesen, sondern indirekt: wenn es keinen unendlich langen Pfad im Baum gäbe, dann gäbe es eine längsten Pfad und damit eine endliche obere Pfadlänge. das wird mit der Prämisse, daß die Pfade willkürlich lang sein sollen, ausgeschlossen. Ein etwas ausführlicher Beweis ist bei Kleene 1968, S. 302-303, zu finden. Nach intuitionistischer Auffassung ist das Lemma nicht wahr.

Links

Dénes König

König's lemma: MathWorld

König's lemma: Wikipedia, the free encyclopedia

König's lemma

A. James Humphreys, Stephen G. Simpson: "Separation and Weak König's Lemma"

ruv.net Encylopedia Information Portal

Literatur

Gallai, Tibor 1986: "Dénes König – Ein biographischer Abriß". In: König 1986, S. 303-306
Gallai, Tibor 1986: "Verzeichnis der wissenschaftlichen Arbeiten von D. König". In: König 1986, S. 307-308
Humphreys, A. James, Stephen G. Simpson 1999: "Separation and Weak Konig's Lemma". The Journal of Symbolic Logic 64.1. 268-278.
Kleene, Stephen Cole 1968: Mathematical Logic. New York: Wiley, 1968.
König, Dénes 1927: "Über eine Schlußweise aus dem Endlichen ins Unendlichem (Punktmengen. – Kartenfärben. – Verwandtschaftsbeziehungen. – Schachspiel)". Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae. Sectio Scientiarum Mathematicarum 3. Szeged. S. 121-130
König, Dénes 1986: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Sachs, Horst, Hg. Leipzig: Teubner. 348 Seiten. Teubner-Archiv zur Mathematik Bd. 6. Fotomechanische Nachdrucke von: König, Denes: Theorie der endlichen und unendlichen Graphen. 1936 und anderen Aufsätzen
Kohlenbach, Ulrich 1999: On the uniform weak Königs's lemma. Aarhus : BRICS, Dept. of Computer Science, Univ. of Aarhus. 13 S.
Simpson, Stephen G., Kazuyuki Tanaka, Takeshi Yamazaki 2002: "Some conservation results on week König's lemma". Annals of Pure and Applied Logic 118.1-2. 87-114.