Věta o stromu Kruskals - Kruskals tree theorem - Wikipedia
v matematika, Kruskalova věta o stromu uvádí, že množina konečných stromy přes dobře kvazi objednané sada štítků je sama o sobě dobře kvazi objednaná homeomorfní vkládání. Věta byla domněnkou Andrew Vázsonyi a prokázáno Joseph Kruskal (1960 ); krátký důkaz poskytl Nash-Williams (1963 ). Od té doby se stal prominentním příkladem v reverzní matematika jako prohlášení, které nelze v rámci ATR prokázat0 (forma aritmetická transfinitní rekurze ), a konečná aplikace věty dává existenci notoricky rychle rostoucí Funkce TREE.
V roce 2004 byl výsledek zobecněn ze stromů na grafy jako Věta Robertson – Seymour Výsledek, který se osvědčil také v reverzní matematice a vede k ještě rychlejšímu růstu Funkce SSCG.
Prohlášení
Uvádíme verzi, kterou prokázal Nash-Williams; Kruskalova formulace je poněkud silnější. Všechny stromy považujeme za konečné.
Dostal strom T s kořenem a danými vrcholy proti, w, volání w nástupce proti pokud je jedinečná cesta od kořene k w obsahuje protia zavolat w bezprostřední nástupce proti pokud navíc cesta z proti na w neobsahuje žádný další vrchol.
Vzít X být a částečně objednaná sada. Li T1, T2 jsou zakořeněné stromy s vrcholy označenými v X, říkáme to T1 je integrovatelný do T2 a piš T1 ≤ T2 pokud existuje injektivní mapa F z vrcholů T1 k vrcholům T2 takhle
- Pro všechny vrcholy proti z T1, štítek proti předchází označení F(proti),
- Li w je jakýkoli jeho nástupce proti v T1, pak F(w) je nástupcem F(proti), a
- Li w1, w2 jsou dva zřetelní bezprostřední nástupci proti, pak cesta z F(w1) na F(w2) v T2 obsahuje F(proti).
Kruskalova věta o stromu pak uvádí:
Li X je dobře kvazi objednané, pak sada kořenových stromů se štítky X je dobře kvazi objednaný ve výše uvedeném inf-embeddable pořadí. (To znamená, vzhledem k jakékoli nekonečné posloupnosti T1, T2, … kořenových stromů označených v X, některé jsou i < j aby Ti ≤ Tj.)
Slabá funkce stromu
Definovat strom(n), funkce slabého stromu, jako délka nejdelší sekvence stromů označených 1 (tj. X = {1}) takové, že:
- Strom na pozici k v pořadí nemá více než k + n vrcholy, pro všechny k.
- Žádný strom není homeomorfně zabudovatelný do žádného stromu, který jej sleduje v pořadí.
Je známo, že strom (1) = 1, strom (2) = 5 a strom (3) ≥ 844424930131960,[1] ale STROM (3) (viz níže) je větší než
Friedmanova práce
Pro spočetnou sadu štítků , Kruskalův větu lze vyjádřit a dokázat pomocí aritmetika druhého řádu. Nicméně, jako Goodsteinova věta nebo Paříž – Harringtonova věta, některé speciální případy a varianty věty lze vyjádřit v subsystémech aritmetiky druhého řádu mnohem slabších než v subsystémech, kde je lze dokázat. Toto bylo poprvé pozorováno uživatelem Harvey Friedman na začátku 80. let, raný úspěch tehdy rodícího se oboru reverzní matematiky. V případě, že jsou výše uvedené stromy považovány za neoznačené (tj. V případě, že má objednávku jedna), Friedman zjistil, že výsledek byl neprokázatelný v ATR0,[2] tedy dává první příklad a predikativní výsledek s prokazatelně neprokazatelným důkazem.[3] Tento případ věty je stále dokázatelný v Π1
1-CA0, ale přidáním „podmínky mezery“[4] k definici řádu na stromech výše shledal přirozenou variaci věty v tomto systému neprokazatelnou.[5][6] Mnohem později by věta Robertson-Seymour poskytla další teorém, který by se uvnitř Π nedal dokázat1
1-CA0.
Pořadová analýza potvrzuje sílu Kruskalovy věty, přičemž důkazně-teoretický ordinál věty se rovná malý Veblen pořadový (někdy zaměňována s menší Ackermann pořadový ).
STROM (3)
Předpokládejme to P(n) je prohlášení:
- Některé jsou m takové, že pokud T1,...,Tm je konečná posloupnost neoznačených kořenových stromů, kde Tk má n+k vrcholy, pak Ti ≤ Tj pro některé i < j.
Všechna prohlášení P(n) jsou pravdivé jako důsledek Kruskalovy věty a Kőnigovo lemma. Pro každého n, Peano aritmetika může to dokázat P(n) je pravda, ale Peanoova aritmetika nemůže dokázat tvrzení „P(n) platí pro všechny n".[7] Navíc délka nejkratšího důkazu P(n) v Peano aritmetika roste fenomenálně rychle jako funkce n, mnohem rychlejší než kdokoli jiný primitivní rekurzivní funkce nebo Ackermannova funkce například. Nejméně m pro který P(n) drží podobně roste extrémně rychle s n.
Začleněním štítků definoval Friedman mnohem rychlejší funkci.[8] Pro kladné celé číslo n, vzít STROM(n)[*] být největší m takže máme následující:
- Existuje sekvence T1,...,Tm zakořeněných stromů označených ze sady n štítky, kde každý Ti má nanejvýš i vrcholy, takové, že Ti ≤ Tj neplatí pro žádné i < j ≤ m.
The STROM sekvence začíná STROM(1) = 1, STROM(2) = 3, pak najednou STROM(3) exploduje na hodnotu tak nesmírně velkou, že mnoho dalších „velkých“ kombinatorických konstant, jako je Friedmanova n(4),[**] ve srovnání jsou extrémně malé. Ve skutečnosti je mnohem větší než nn(5)(5). Dolní mez pro n(4), a tedy an velmi slabá dolní mez pro STROM(3), je AA(187196)(1),[9] kde A() je verze Ackermannova funkce: . Grahamovo číslo například je přibližně A64(4), která je mnohem menší než dolní mez AA(187196)(1). Je možné ukázat, že rychlost růstu funkce TREE je minimálně v rychle rostoucí hierarchie. AA(187196)(1) je přibližně , kde GX je Grahamova funkce.
Viz také
Poznámky
- ^ * Friedman tuto funkci původně označil TR[n].
- ^ ** n(k) je definována jako délka nejdelší možné sekvence, kterou lze zkonstruovat pomocí a k- abeceda písmen tak, že žádný blok písmen xi,...,X2i je subsekvence kteréhokoli pozdějšího bloku xj,...,X2j.[10] .
Reference
- Citace
- ^ "Sekvence STROMU". Googology Wiki | Fandom. Citováno 9. července 2020.[je zapotřebí lepší zdroj ]
- ^ Simpson 1985, Věta 1.8
- ^ Friedman 2002, s. 60
- ^ Simpson 1985, definice 4.1
- ^ Simpson 1985, Věta 5.14
- ^ Marcone 2001, s. 8–9
- ^ Smith 1985, s. 120
- ^ Friedman, Harvey (28. března 2006). „273: Sigma01 / optimální / velikost“. Ohio State University Katedra matematiky. Citováno 8. srpna 2017.
- ^ Friedman, Harvey M. (1. června 2000). „Obrovská celá čísla v reálném životě“ (PDF). Ohio State University. Citováno 8. srpna 2017.
- ^ Friedman, Harvey M. (8. října 1998). „Long Finite Sequences“ (PDF). Katedra matematiky na Ohio State University. str. 5, 48 (Thm. 6,8). Citováno 8. srpna 2017.
- Bibliografie
- Friedman, Harvey M. (2002), Vnitřní vložení konečných stromů. Úvahy o základech matematiky (Stanford, CA, 1998), Přednáška. Protokol poznámek, 15, Urbana, IL: Doc. Symbol. Logic, str. 60–91, PAN 1943303
- Gallier, Jean H. (1991), „Co je tak zvláštního na Kruskalově větě a ordinálu?“0? Průzkum některých výsledků v teorii důkazů “ (PDF), Ann. Pure Appl. Logika, 53 (3): 199–260, doi:10.1016 / 0168-0072 (91) 90022-E, PAN 1129778
- Kruskal, J. B. (Květen 1960), „Dobře kvazi-objednávání, věta o stromu a Vazsonyiho domněnka“ (PDF), Transakce Americké matematické společnostiAmerická matematická společnost, 95 (2): 210–225, doi:10.2307/1993287, JSTOR 1993287, PAN 0111704
- Marcone, Alberto (2001). "Teorie WQO a BQO v subsystémech aritmetiky druhého řádu" (PDF). Reverzní matematika. 21: 303–330.
- Nash-Williams, C. St.J. A. (1963), „O dobře kvazi-objednávajících konečných stromech“, Proc. Camb. Phil. Soc., 59 (4): 833–835, doi:10.1017 / S0305004100003844, PAN 0153601
- Rathjen, Michael; Weiermann, Andreas (1993). „Důkazně-teoretická vyšetřování Kruskalovy věty“. Annals of Pure and Applied Logic. 60 (1): 49–88. doi:10.1016 / 0168-0072 (93) 90192-g.
- Simpson, Stephen G. (1985), „Neprokázatelnost určitých kombinatorických vlastností konečných stromů“, Harrington, L. A .; Morley, M .; Scedrov, A .; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics„Studies in Logic and the Foundations of Mathematics, North-Holland, s. 87–117
- Smith, Rick L. (1985), „Silnosti konzistence některých konečných forem Higmanových a Kruskalových vět“, Harrington, L. A .; Morley, M .; Scedrov, A .; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics„Studies in Logic and the Foundations of Mathematics, North-Holland, s. 119–136