| dbo:abstract
|
- 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. (de)
- Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory. (en)
- En mathématiques, le lemme de Kőnig est un lemme de la théorie des graphes que l'on doit au mathématicien hongrois Dénes Kőnig en 1927. Il énonce que : « Tout arbre infini à branchement fini a une branche infinie. » Il a des applications en logique. (fr)
- 그래프 이론에서 쾨니그 보조정리(Kőnig補助定理, 영어: Kőnig’s lemma)는 어떤 그래프가 무한할 수 있는 방법들을 나열하는 정리다. (ko)
- グラフ理論におけるケーニヒの補題はデネス・ケーニヒ (1936)によって示された定理で、無限グラフが無限長の道をもつための十分条件を与える。この定理のcomputability aspectsは数理論理学の計算可能性理論の研究者によって調べられてきている。この定理はや証明論においても重要な役割をもつ。 (ja)
- Il Lemma di König in logica afferma che: Se un albero, in cui ogni nodo ha un numero finito di successori immediati, ha infiniti nodi allora in esso c'è anche un ramo infinito. Dimostrazione del lemma. Ogni nodo dell'albero avrà un'etichetta. Si dice che un nodo è prolungabile se e solo se da esso derivano rami di lunghezza finita e arbitraria, quindi la radice dell'albero è prolungabile. Supponiamo un nodo v prolungabile, implica che esiste un figlio di v prolungabile. Se f0 è prolungabile e se ogni nodo ha un figlio prolungabile esiste almeno un discendente che è prolungabile. (it)
- Lemat Königa to lemat mówiący o tym, że jeśli drzewo jest nieskończone,a każdy węzeł ma skończoną liczbę dzieci, to musi w tym drzewie istnieć nieskończona ścieżka prosta. (pl)
- O Lema de König ou Lema da Infinitude de König é um teorema da teoria dos grafos creditado a (1936). Ele fornece uma condição suficiente para que um grafo infinito tenha um ramo infinitamente longo. Os aspectos desse teorema relacionados à computabilidade têm sido minuciosamente estudados por pesquisadores da lógica matemática, especialmente na teoria da computabilidade. Tal teorema também desempenha papeis importantes na matemática construtiva e na teoria da prova. (pt)
- Лема Кеніга про нескінченний шлях — теорема, яка дає достатню умову існування нескінченного шляху в графі. Ця теорема відіграє важливу роль як приклад у конструктивній математиці і теорії доведень. Довів Денеш Кеніг 1927 року. (uk)
- 柯尼格引理（英語：König's lemma）为图论中的一个定理。 (zh)
- Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе.Эта теорема играет важную роль как пример в конструктивной математике и теории доказательства. Доказана Денешем Кёнигом в 1927 году. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 16687 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
|
- Luitzen Egbertus Jan Brouwer (en)
|
| dbp:first
| |
| dbp:last
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| rdfs:comment
|
- 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. (de)
- Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in mathematical logic, especially in computability theory. This theorem also has important roles in constructive mathematics and proof theory. (en)
- En mathématiques, le lemme de Kőnig est un lemme de la théorie des graphes que l'on doit au mathématicien hongrois Dénes Kőnig en 1927. Il énonce que : « Tout arbre infini à branchement fini a une branche infinie. » Il a des applications en logique. (fr)
- 그래프 이론에서 쾨니그 보조정리(Kőnig補助定理, 영어: Kőnig’s lemma)는 어떤 그래프가 무한할 수 있는 방법들을 나열하는 정리다. (ko)
- グラフ理論におけるケーニヒの補題はデネス・ケーニヒ (1936)によって示された定理で、無限グラフが無限長の道をもつための十分条件を与える。この定理のcomputability aspectsは数理論理学の計算可能性理論の研究者によって調べられてきている。この定理はや証明論においても重要な役割をもつ。 (ja)
- Il Lemma di König in logica afferma che: Se un albero, in cui ogni nodo ha un numero finito di successori immediati, ha infiniti nodi allora in esso c'è anche un ramo infinito. Dimostrazione del lemma. Ogni nodo dell'albero avrà un'etichetta. Si dice che un nodo è prolungabile se e solo se da esso derivano rami di lunghezza finita e arbitraria, quindi la radice dell'albero è prolungabile. Supponiamo un nodo v prolungabile, implica che esiste un figlio di v prolungabile. Se f0 è prolungabile e se ogni nodo ha un figlio prolungabile esiste almeno un discendente che è prolungabile. (it)
- Lemat Königa to lemat mówiący o tym, że jeśli drzewo jest nieskończone,a każdy węzeł ma skończoną liczbę dzieci, to musi w tym drzewie istnieć nieskończona ścieżka prosta. (pl)
- O Lema de König ou Lema da Infinitude de König é um teorema da teoria dos grafos creditado a (1936). Ele fornece uma condição suficiente para que um grafo infinito tenha um ramo infinitamente longo. Os aspectos desse teorema relacionados à computabilidade têm sido minuciosamente estudados por pesquisadores da lógica matemática, especialmente na teoria da computabilidade. Tal teorema também desempenha papeis importantes na matemática construtiva e na teoria da prova. (pt)
- Лема Кеніга про нескінченний шлях — теорема, яка дає достатню умову існування нескінченного шляху в графі. Ця теорема відіграє важливу роль як приклад у конструктивній математиці і теорії доведень. Довів Денеш Кеніг 1927 року. (uk)
- 柯尼格引理（英語：König's lemma）为图论中的一个定理。 (zh)
- Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе.Эта теорема играет важную роль как пример в конструктивной математике и теории доказательства. Доказана Денешем Кёнигом в 1927 году. (ru)
|
| rdfs:label
|
- Lemma von König (de)
- Lemme de König (fr)
- Lemma di König (it)
- Kőnig's lemma (en)
- 쾨니그 보조정리 (ko)
- ケーニヒの補題 (ja)
- Lemat Königa (pl)
- Lema de Konig (pt)
- Лемма Кёнига о бесконечном пути (ru)
- Лема Кеніга (uk)
- 柯尼格引理 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
