Email  zurück zur Homepage eine Stufe zurück
Königs 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
königs lemmaDénes König
königs lemmaKönig's lemma: MathWorld
königs lemmaKönig's lemma: Wikipedia, the free encyclopedia
königs lemmaKönig's lemma
königs lemmaA. James Humphreys, Stephen G. Simpson: "Separation and Weak König's Lemma"
königs lemmaruv.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.

Königs Lemma
Email  zurück zur Homepage eine Stufe zurück
© by Herbert Huber, Am Fröschlanger 15, 83512 Wasserburg, Germany, 17.12.2004