Kőnig's lemma (original) (raw)

About DBpedia

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.

thumbnail

Property Value
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 wiki-commons:Special:FilePath/Denes_König_-_Über_ei...ndlichen_ins_Unendliche.png?width=300
dbo:wikiPageExternalLink http://plato.stanford.edu/entries/mathematics-constructive/ https://archive.org/details/handbookofcomput0140unse/page/37 http://mizar.org/JFM/Vol3/trees_2.html http://acta.fyx.hu/acta/showCustomerArticle.action%3Fid=5131&dataObjectType=article&returnAction=showCustomerVolume&sessionDataSetId=2b29ea26fa2c9ba&style= https://archive.today/20141223141608/http:/acta.fyx.hu/acta/showCustomerArticle.action%3Fid=5131&dataObjectType=article&returnAction=showCustomerVolume&sessionDataSetId=2b29ea26fa2c9ba&style= http://matwbn.icm.edu.pl/ksiazki/fm/fm8/fm815.pdf
dbo:wikiPageID 153788 (xsd:integer)
dbo:wikiPageLength 16687 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1112167039 (xsd:integer)
dbo:wikiPageWikiLink dbc:Axiom_of_choice dbr:Mizar_system dbc:Constructivism_(mathematics) dbr:Reverse_mathematics dbr:Degree_(graph_theory) dbr:Reductio_ad_absurdum dbc:Articles_containing_proofs dbr:Compact_space dbr:Connected_graph dbr:Contrapositive dbr:Analytical_hierarchy dbr:Mathematical_logic dbr:Glossary_of_graph_theory_terms dbc:Infinite_graphs dbr:Theorem dbr:Arithmetical_hierarchy dbr:Aronszajn_tree dbr:Basis_theorem_(computability) dbr:Zermelo–Fraenkel_set_theory dbr:Low_basis_theorem dbr:Path_(graph_theory) dbr:Category_of_sets dbr:Tree_(graph_theory) dbr:Dénes_Kőnig dbr:Finite_intersection_property dbr:Graph_theory dbr:Proof_theory dbr:Ray_(graph_theory) dbr:Halting_problem dbr:Inverse_limit dbc:Computability_theory dbc:Lemmas_in_graph_theory dbc:Wellfoundedness dbr:Axiom_of_choice dbr:Axiom_of_countable_choice dbr:Axiom_of_dependent_choice dbr:Pigeonhole_principle dbr:Ordinal_number dbr:Kleene's_O dbr:Second-order_arithmetic dbr:Tychonoff's_theorem dbr:Low_(computability) dbr:PA_degree dbr:Arithmetical_comprehension dbr:Mathematical_constructivism dbr:Recursion_theory dbr:Law_of_the_excluded_middle dbr:Constructive_mathematics dbr:File:Denes_König_-_Über_eine_Schlussweise_aus_dem_Endlichen_ins_Unendliche.png
dbp:authorlink Luitzen Egbertus Jan Brouwer (en)
dbp:first L. E. J. (en)
dbp:last Brouwer (en)
dbp:wikiPageUsesTemplate dbt:Citation dbt:More_footnotes dbt:Other_uses dbt:Reflist dbt:Short_description dbt:Isbn dbt:Harvs
dbp:year 1927 (xsd:integer)
dct:subject dbc:Axiom_of_choice dbc:Constructivism_(mathematics) dbc:Articles_containing_proofs dbc:Infinite_graphs dbc:Computability_theory dbc:Lemmas_in_graph_theory dbc:Wellfoundedness
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 wikidata:Kőnig's lemma dbpedia-de:Kőnig's lemma dbpedia-fr:Kőnig's lemma dbpedia-he:Kőnig's lemma dbpedia-hu:Kőnig's lemma dbpedia-it:Kőnig's lemma dbpedia-ja:Kőnig's lemma dbpedia-ko:Kőnig's lemma dbpedia-pl:Kőnig's lemma dbpedia-pt:Kőnig's lemma dbpedia-ru:Kőnig's lemma dbpedia-uk:Kőnig's lemma dbpedia-zh:Kőnig's lemma https://global.dbpedia.org/id/8VQh
prov:wasDerivedFrom wikipedia-en:Kőnig's_lemma?oldid=1112167039&ns=0
foaf:depiction wiki-commons:Special:FilePath/Denes_König_-_Über_ei..._aus_dem_Endlichen_ins_Unendliche.png
foaf:isPrimaryTopicOf wikipedia-en:Kőnig's_lemma
is dbo:wikiPageRedirects of dbr:König's_Lemma dbr:Konig's_lemma dbr:König's_lemma dbr:Koenig's_Lemma dbr:Koenig_lemma dbr:Konig's_Lemma dbr:König's_infinity_lemma dbr:König_infinity_lemma dbr:König_lemma dbr:Konig_lemma dbr:Lema_de_konig dbr:Koenig's_lemma
is dbo:wikiPageWikiLink of dbr:Mizar_system dbr:List_of_graph_theory_topics dbr:Reverse_mathematics dbr:Unbounded_nondeterminism dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:List_of_lemmas dbr:List_of_mathematical_proofs dbr:König's_Lemma dbr:Constructive_set_theory dbr:Cop-win_graph dbr:Thoralf_Skolem dbr:Aronszajn_tree dbr:Löwenheim–Skolem_theorem dbr:Kruskal's_tree_theorem dbr:Tree_(descriptive_set_theory) dbr:Tree_(set_theory) dbr:Heesch's_problem dbr:Truth-table_reduction dbr:Dénes_Kőnig dbr:Hahn–Banach_theorem dbr:Inverse_limit dbr:Konig's_lemma dbr:Ramsey's_theorem dbr:Second-order_arithmetic dbr:Unavoidable_pattern dbr:WKL dbr:König's_theorem dbr:König_(disambiguation) dbr:König's_lemma dbr:The_Art_of_Computer_Programming dbr:Koenig's_Lemma dbr:Koenig_lemma dbr:Konig's_Lemma dbr:Semi-deterministic_Büchi_automaton dbr:PA_degree dbr:S2S_(mathematics) dbr:König's_infinity_lemma dbr:König_infinity_lemma dbr:König_lemma dbr:Konig_lemma dbr:Lema_de_konig dbr:Koenig's_lemma
is foaf:primaryTopic of wikipedia-en:Kőnig's_lemma