Kőnigovo lemma - Kőnig's lemma

Kőnigovo lema nebo Königovo lema nekonečna je teorém v teorii grafů kvůli maďarskému matematikovi Dénesovi Kőnigovi, který jej publikoval v roce 1927. Poskytuje dostatečnou podmínku, aby nekonečný graf měl nekonečně dlouhou cestu. Aspekty vypočítatelnosti této věty byly důkladně prozkoumány vědci v matematické logice , zejména v teorii vypočítatelnosti . Tato věta má také důležité role v konstruktivní matematice a teorii důkazů .

Prohlášení o lemmatu

Nechť G je připojený , lokálně konečný , nekonečný graf (to znamená: libovolné dva vrcholy lze spojit cestou, graf má nekonečně mnoho vrcholů a každý vrchol sousedí pouze s konečně mnoha jinými vrcholy). Pak G obsahuje paprsek : jednoduchá cesta (cesta bez opakovaných vrcholů), která začíná na jednom vrcholu a pokračuje od něj nekonečně mnoha vrcholy.

Běžným zvláštním případem je to, že každý nekonečný strom obsahuje buď vrchol nekonečného stupně, nebo nekonečnou jednoduchou cestu.

Důkaz

Začněte s jakýmkoli vrcholem v ₁ . Každý z nekonečně mnoha vrcholů G lze dosáhnout z v ₁ jednoduchou cestou a každá taková cesta musí začínat jedním z konečně mnoha vrcholů sousedících s v ₁ . Musí existovat jeden z těch sousedních vrcholů, kterými lze dosáhnout nekonečně mnoho vrcholů, aniž bychom museli projít v ₁ . Pokud by neexistovaly, pak by celý graf byl spojením konečně mnoha konečných množin, a tedy konečných, což je v rozporu s předpokladem, že graf je nekonečný. Můžeme tedy vybrat jeden z těchto vrcholů a nazvat jej v ₂ .

Nyní lze nekonečně mnoho vrcholů G dosáhnout z v ₂ jednoduchou cestou, která nezahrnuje vrchol v ₁ . Každá taková cesta musí začínat jedním z konečně mnoha vrcholů sousedících s v ₂ . Argument podobný tomu výše uvedenému ukazuje, že musí existovat jeden z těch sousedních vrcholů, kterými lze dosáhnout nekonečně mnoho vrcholů; vyberte jednu a nazvěte ji v ₃ .

Pokračováním tímto způsobem lze vytvořit nekonečnou jednoduchou cestu pomocí matematické indukce a slabé verze axiomu závislé volby . V každém kroku indukční hypotéza uvádí, že existuje nekonečně mnoho uzlů dosažitelných jednoduchou cestou z konkrétního uzlu v _i, který neprochází jedním z konečné sady vrcholů. Indukční argument je, že jeden z vrcholů sousedících s v _i splňuje indukční hypotézu, i když je v _i přidáno do konečné množiny.

Výsledkem tohoto indukčního argumentu je, že pro všechna n je možné zvolit vrchol v _n, jak popisuje konstrukce. Sada vrcholů zvolených v konstrukci je potom řetězcem v grafu, protože každý byl vybrán tak, aby sousedil s předchozím, a konstrukce zaručuje, že stejný vrchol nebude nikdy zvolen dvakrát.

Aspekty vypočítatelnosti

Aspekty spočitatelnosti Kőnigova lematu byly důkladně prozkoumány. Forma Kőnigova lemu, která je pro tento účel nejvhodnější, je ta, která uvádí, že jakýkoli nekonečný konečně větvící podstrom má nekonečnou cestu. Zde označuje množinu přirozených čísel (považovaných za pořadové číslo ) a strom, jehož uzly jsou všechny konečné posloupnosti přirozených čísel, kde se rodič uzlu získá odstraněním posledního prvku ze sekvence. Každá konečná sekvence může být identifikována s částečnou funkcí od sebe a každou nekonečnou cestu lze identifikovat s celkovou funkcí. To umožňuje analýzu pomocí technik teorie vypočítatelnosti. ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega}$${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega}$

Podstrom, ve kterém má každá sekvence jen konečně mnoho okamžitých rozšíření (to znamená, že strom má konečný stupeň při pohledu jako graf), se nazývá konečně větvení . Ne každý nekonečný podstrom má nekonečnou cestu, ale Kőnigovo lemma ukazuje, že každý konečně větvící podstrom musí mít takovou cestu. ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega ^ {<\ omega}}$

Pro každý podstromu T o zápisu Ext ( T ) označuje soubor uzlů T prostřednictvím kterých je nekonečná dráha. I když je T vypočítatelné, nemusí být nastavitelná Ext ( T ) vypočítatelná. Každý podstromu T o , že má cesta má cesta vypočitatelný z Ext ( T ). ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega ^ {<\ omega}}$

Je známo, že existují neomezeně rozvětvitelné vypočítatelné podstromy , které nemají aritmetickou cestu a skutečně žádnou hyperaritmetickou cestu. Každý vypočítatelný podstrom s cestou však musí mít cestu vypočítatelnou z Kleeneova O , kanonické úplné sady. Je to proto, že množina Ext ( T ) je vždy (viz analytická hierarchie ), když T je vypočítatelná. ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ Pi _ {1} ^ {1}}$${\ displaystyle \ Sigma _ {1} ^ {1}}$

U vypočítatelně ohraničených stromů byla provedena jemnější analýza. Podstrom z se nazývá vypočítatelně ohraničený nebo rekurzivně ohraničený, pokud existuje vypočítatelná funkce f od do takové, že pro každou sekvenci ve stromu a každé n je n- tý prvek sekvence nanejvýš f ( n ). F tedy dává hranici toho, jak „široký“ je strom. Následující základní věty platí pro nekonečné, vypočítatelně ohraničené a vypočítatelné podstromy . ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega}$${\ displaystyle \ omega}$${\ displaystyle \ omega ^ {<\ omega}}$

• Každý takový strom má cestu, kterou lze vypočítat z kanonické Turingovy úplné sady, která může rozhodnout o problému zastavení . ${\ displaystyle 0 '}$
• Každý takový strom má cestu, která je nízká . Toto je známé jako věta o nízké bázi .
• Každý takový strom má cestu, která je hyperimunní zdarma . To znamená, že jakékoli funkci vypočítatelné z cesty dominuje vypočítatelná funkce.
• Pro jakékoliv noncomputable podmnožina X o stromu má cestu, která nepočítá  X . ${\ displaystyle \ omega}$

Slabá forma König lemma který říká, že každý nekonečný binární strom má nekonečnou větev slouží k definování podsystému WKL ₀ z druhého řádu aritmetiky . Tento subsystém hraje důležitou roli v reverzní matematice . Zde je binární strom takový, ve kterém je každý člen každé sekvence ve stromu 0 nebo 1, což znamená, že strom je vypočítatelně ohraničen pomocí konstantní funkce 2. Plná forma Kőnigova lematu není ve WKL ₀ dokázatelná , ale je ekvivalentní silnějšímu subsystému ACA ₀ .

Vztah ke konstruktivní matematice a kompaktnosti

Důkaz uvedený výše se obecně nepovažuje za konstruktivní , protože v každém kroku používá důkaz rozporem k prokázání, že existuje sousední vrchol, ze kterého lze dosáhnout nekonečně mnoho dalších vrcholů, a kvůli spoléhání se na slabou formu axiom výběru . Fakta o výpočetních aspektech lemmatu naznačují, že nelze poskytnout žádný důkaz, který by hlavní školy konstruktivní matematiky považovaly za konstruktivní .

Věta fanouška LEJ Brouwera  ( 1927 ) je z klasického hlediska kontrapozitivem formy Kőnigova lematu. Podmnožina S z se nazývá bar , pokud některý z funkce k sadě má určitý počáteční segment v S . Lišta je oddělitelná, pokud je každá sekvence buď v liště, nebo ne v liště (tento předpoklad je vyžadován, protože věta je obvykle brána v úvahu v situacích, kdy se nepředpokládá zákon vyloučeného prostředku ). Lišta je jednotná, pokud existuje nějaké číslo N, takže jakákoli funkce od do má počáteční segment v pruhu délky ne více než . Brouwerova věta o fanoušcích říká, že každá odnímatelná lišta je uniformní. ${\ displaystyle \ {0,1 \} ^ {<\ omega}}$${\ displaystyle \ omega}$${\ displaystyle \ {0,1 \}}$${\ displaystyle \ omega}$${\ displaystyle \ {0,1 \}}$${\ displaystyle N}$

To lze dokázat v klasickém prostředí tím, že lištu považujeme za otevřenou krytinu kompaktního topologického prostoru . Každá sekvence v pruhu představuje základní otevřenou množinu tohoto prostoru a tyto základní otevřené množiny pokrývají prostor podle předpokladu. Díky kompaktnosti má tento kryt konečnou podobu. N teorému ventilátoru může být vzat být délka nejdelší sekvenci jehož základní otevřené sada je v konečné subcover. Tento topologický důkaz lze použít v klasické matematice k prokázání, že platí následující forma Kőnigova lematu: pro jakékoli přirozené číslo k má nekonečný směr jakýkoli nekonečný podstrom stromu . ${\ displaystyle \ {0,1 \} ^ {\ omega}}$${\ displaystyle \ {0, \ ldots, k \} ^ {<\ omega}}$

Vztah k axiomu volby

Kőnigovo lema lze považovat za princip volby; první důkaz nahoře ilustruje vztah mezi lemmatem a axiomem závislé volby . V každém kroku indukce musí být vybrán vrchol s určitou vlastností. I když je prokázáno, že existuje alespoň jeden vhodný vrchol, pokud existuje více než jeden vhodný vrchol, nemusí existovat žádná kanonická volba. Ve skutečnosti není nutná plná síla axiomu závislé volby; jak je popsáno níže, postačuje axiom spočetné volby .

Pokud je graf spočítatelný, vrcholy jsou dobře uspořádané a lze kanonicky zvolit nejmenší vhodný vrchol. V tomto případě je Kőnigovo lemma prokazatelné v aritmetice druhého řádu s aritmetickým porozuměním a tím spíše v teorii množin ZF (bez volby).

Kőnigovo lemma je v podstatě omezení axiomu závislé volby na celé vztahy R tak, že pro každé x existuje pouze konečně mnoho z takových, že xRz . Ačkoli je axiom volby obecně silnější než princip závislé volby, toto omezení závislé volby je ekvivalentní omezení axiomu volby. Zejména když se větvení v každém uzlu provádí na konečné podmnožině libovolné množiny, která se nepředpokládá jako spočetná, forma Kőnigova lematu, která říká: „Každý nekonečně konečně větvící strom má nekonečnou cestu“, je ekvivalentní principu, že každý spočítatelná množina konečných množin má funkci volby, to znamená axiom spočitatelné volby pro konečné množiny. Tato forma axiomu volby (a tedy Königova lemmatu) není v teorii množin ZF prokazatelná.

Zobecnění

V kategorii množin je inverzní limit libovolného inverzního systému neprázdných konečných množin neprázdný. To lze považovat za zobecnění Kőnigova lemmatu a lze to dokázat Tychonoffovou větou , prohlížením konečných množin jako kompaktních diskrétních prostorů a následným použitím charakterizace kompaktnosti vlastností konečné křižovatky .

Viz také

• Aronszajnův strom , pro možnou existenci protikladů při zobecnění lemmatu na vyšší kardinality.
• Stupeň PA

Poznámky

Reference

• Brouwer, LEJ (1927), O doménách definice funkcí . publikováno v van Heijenoort, Jean, ed. (1967), Od Frege po Gödel
• Franchella, Miriam (1997), „K počátkům lemu nekonečna Dénesa Königa“, Archiv pro dějiny přesných věd (51 (1) 3: 2-3): 3–27, doi : 10,1007 / BF00376449
• Howard, Paul; Rubin, Jean (1998), Consequences of the Axiom of Choice , Mathematical Surveys and Monographs, 59 , Providence, RI: American Mathematical Society CS1 maint: discouraged parameter ( link )
• Kőnig, D. (1927), „Über eine Schlussweise aus dem Endlichen ins Unendliche“ , Acta Sci. Matematika. (Szeged) (v němčině) (3 (2-3)): 121–130, archivovány od originálu dne 2014-12-23 , vyvoláno 2014-12-23 CS1 maint: discouraged parameter ( link )
• Lévy, Azriel (1979), The Basic Set Theory , Springer, ISBN   3-540-08417-7 , MR   0533962 ; dotisk, Dover, 2002, ISBN   0-486-42079-5 .
• Rogers, Hartley, Jr. (1967), Teorie rekurzivních funkcí a efektivní vypočítatelnost , McGraw-Hill, MR   0224462
• Truss, J. (1976), „Some cases of König's lemma“, Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej (eds.), Teorie množin a teorie hierarchie: pamětní pocta Andrzejovi Mostowskému , Lecture Notes in Mathematics, 537 , Springer, str. 273–284, doi : 10,1007 / BFb0096907 , MR   0429557

Další čtení

• Cenzer, Douglas (1999), „ classes in computability theory“, Handbook of Computability Theory , Elsevier, str.  37–85 , doi : 10,1016 / S0049-237X (99) 80018-4 , ISBN${\ displaystyle \ Pi _ {1} ^ {0}}$  0-444-89882-4 , MR   1720779
• Kőnig, D. (1926), „Sur les korespondences multivoques des ensembles“ (PDF) , Fundamenta Mathematicae (ve francouzštině) (8): 114–134 CS1 maint: discouraged parameter ( link )
• Kőnig, D. (1936), Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (v němčině), Lipsko: Akad. Verlag
• Simpson, Stephen G. (1999), Subsystems of Second Order Arithmetic , Perspectives in Mathematical Logic, Springer, ISBN   3-540-64882-8 , MR   1723993
• Soare, Robert I. (1987), Rekurzivně vyčíslitelné množiny a stupně: Studie vypočítatelných funkcí a vypočítatelně generovaných množin , Perspectives in Mathematical Logic, Springer, ISBN   3-540-15299-7 , MR   0882921 CS1 maint: discouraged parameter ( link )

externí odkazy

• Stanfordská encyklopedie filozofie: konstruktivní matematika
• Projekt Mizar zcela formalizoval a automaticky zkontroloval důkaz verze Königova lematu v souboru TREES_2 .