Pořadová analýza - Ordinal analysis
v teorie důkazů, ordinální analýza přiřadí řadové (často velké počty řadových řádků ) k matematickým teoriím jako měřítko jejich síly. Pokud mají teorie stejný důkazně-teoretický ordinál, jsou často ekvikonzistentní, a pokud má jedna teorie větší teoreticko-teoretický ordinál než druhá, může často dokázat konzistenci druhé teorie.
Dějiny
Pole ordinální analýzy bylo vytvořeno, když Gerhard Gentzen v roce 1934 použit eliminace řezu dokázat moderně, že ordinální důkaz z Peano aritmetika je ε0. Vidět Gentzenův důkaz konzistence.
Definice
Ordinální analýza se týká pravdivých, efektivních (rekurzivních) teorií, které dokážou interpretovat dostatečnou část aritmetiky pro výroky o ordinálních zápisech.
The ordinální důkaz takové teorie je nejmenší pořadové číslo (nutně rekurzivní, viz další část), kterou teorie nemůže dokázat opodstatněné —Vrchol všech ordinálů pro které existuje a notace v Kleeneově smyslu takhle to dokazuje je pořadová notace. Ekvivalentně je to nadřazenost všech ordinálů takové, že existuje a rekurzivní vztah na (množina přirozených čísel) dobře objednávky to s pořadovým číslem a takhle dokazuje transfinitní indukce aritmetických příkazů pro .
Horní hranice
Existence rekurzivního ordinálu, který se teorii nepodařilo prokázat, je dobře uspořádaná, vyplývá z mezní věta, protože množina přirozených čísel, která se efektivní teorii ukazuje jako ordinální notace, je a sada (viz Hyperaritmetická teorie ). Důkazový teoretický ordinál teorie tedy bude vždy (počítatelný) rekurzivní pořadové číslo, tj. méně než Církev – Kleene ordinální .
Příklady
Teorie s důkazně-teoretickým pořadovým číslem ω
- Q, Robinsonova aritmetika (ačkoli definice důkazně-teoretického ordinálu pro takové slabé teorie musí být vylepšena).
- PA–, teorie prvního řádu nezáporné části diskrétně uspořádaného prstence.
Teorie s důkazně-teoretickým pořadovým číslem ω2
- RFA, základní funkce aritmetický.[1]
- IΔ0, aritmetika s indukcí na Δ0-predikáty bez jakéhokoli axiomu, který tvrdí, že umocňování je úplné.
Teorie s důkazem-teoretickým pořadovým číslem ω3
- EFA, aritmetika základních funkcí.
- IΔ0 + exp, aritmetika s indukcí na Δ0-predikáty rozšířené o axiom, který tvrdí, že umocňování je úplné.
- RCA*
0, formulář druhého řádu EFA, který se někdy používá v reverzní matematika. - WKL*
0, formulář druhého řádu EFA, který se někdy používá v reverzní matematika.
Friedmanova velký dohad naznačuje, že mnoho „obyčejné“ matematiky lze dokázat ve slabých systémech, které mají toto jako důkazně-teoretický ordinál.
Teorie s důkazně-teoretickým pořadovým číslem ωn (pro n = 2, 3, ... ω)
- IΔ0 nebo EFA rozšířené o axiom zajišťující, že každý prvek n-tá úroveň z Grzegorczykova hierarchie je celkem.
Teorie s důkazem-teoretickým pořadovým číslem ωω
- RCA0, rekurzivní porozumění.
- WKL0, slabé Königovo lemma.
- PRA, primitivní rekurzivní aritmetika.
- Já1, aritmetika s indukcí na Σ1- predikáty.
Teorie s důkazem-teoretickým ordinálem ε0
- PA, Peano aritmetika (zobrazeno podle Gentzen použitím eliminace řezu ).
- ACA0, aritmetické porozumění.
Teorie s důkazem-teoretickým ordinálem Feferman – Schütte ordinál Γ0
- ATR0, aritmetická transfinitní rekurze.
- Teorie typu Martin-Löf s libovolně mnoha vesmíry konečné úrovně.
Toto pořadové číslo se někdy považuje za horní hranici pro „predikativní“ teorie.
Teorie s důkazně-teoretickým ordinálem Bachmann – Howardovým ordinálem
- ID1, teorie indukčních definic.
- KP, Teorie množin Kripke – Platek s axiom nekonečna.
- CZF, Aczel's konstruktivní teorie množin Zermelo – Fraenkel.
- EON, slabá varianta Feferman Výslovný matematický systém T0.
Teorie množin Kripke-Platek nebo CZF jsou slabé teorie množin bez axiomů pro celou sadu sil danou jako sada všech podskupin. Místo toho mají tendenci buď mít axiomy omezené separace a formování nových množin, nebo poskytují existenci určitých funkčních prostorů (umocňování) místo toho, aby je vyřezávali z větších vztahů.
Teorie s většími teoreticko-teoretickými ordinály
- , Π11 pochopení má poměrně velký důkazně-teoretický ordinál, který popsal Takeuti ve smyslu „ordinálních diagramů“ a který je ohraničen ψ0(Ωω) v Buchholzova notace. Je také pořadovým řádem z , teorie konečně iterovaných indukčních definic. A také pořadový typ MLW, teorie typu Martin-Löf s indexovanými typy W Setzer (2004).
- T0„Fefermanova konstruktivní soustava explicitní matematiky má větší důkazově-teoretický ordinál, který je zároveň důkazně-teoretickým ordinálem teorie množin KPi, Kripke – Platek s iterovanými přípustnými a .
- KPM, rozšíření Teorie množin Kripke – Platek na základě a Mahlo kardinál, má velmi velký důkazně-teoretický ordinál ϑ, který popsal Rathjen (1990).
- MLM, rozšíření teorie typu Martin-Löf o jeden Mahlo-vesmír, má ještě větší důkazně-teoretický ordinál ψΩ1(ΩM + ω).
Většina teorií schopných popsat množinu přirozených čísel má důkazně-teoretické ordinály, které jsou tak velké, že dosud nebyl uveden explicitní kombinatorický popis. To zahrnuje aritmetika druhého řádu a nastavit teorie s množinami energií včetně ZF a ZFC (od roku 2019[Aktualizace]). Síla intuitivní ZF (IZF) se rovná ZF.
Viz také
- Rovnoměrnost
- Velký světový majetek
- Feferman – Schütte pořadové číslo
- Bachmann – Howard řadový
- Třída složitosti
Reference
- Buchholz, W .; Feferman, S .; Pohlers, W .; Sieg, W. (1981), Iterované indukční definice a subsystémy analýzy, Poznámky k přednášce v matematice., 897, Berlín: Springer-Verlag, doi:10.1007 / BFb0091894, ISBN 978-3-540-11170-2
- Pohlers, Wolfram (1989), Teorie důkazůPřednášky z matematiky, 1407, Berlín: Springer-Verlag, doi:10.1007/978-3-540-46825-7, ISBN 3-540-51842-8, PAN 1026933
- Pohlers, Wolfram (1998), "Teorie množin a teorie čísel druhého řádu", Příručka teorie důkazů„Studium logiky a základy matematiky, 137, Amsterdam: Elsevier Science B. V., s. 210–335, doi:10.1016 / S0049-237X (98) 80019-0, ISBN 0-444-89840-9, PAN 1640328
- Rathjen, Michael (1990), „Pořadové zápisy založené na slabě Mahlově kardinálovi.“, Oblouk. Matematika. Logika, 29 (4): 249–263, doi:10.1007 / BF01651328, PAN 1062729
- Rathjen, Michael (2006), „Umění ordinální analýzy“ (PDF), Mezinárodní kongres matematiků, II, Curych: Eur. Matematika. Soc., S. 45–69, PAN 2275588, archivovány od originálu dne 22.12.2009CS1 maint: BOT: stav původní adresy URL neznámý (odkaz)
- Rose, HE (1984), Subrekurze. Funkce a hierarchie, Oxford logičtí průvodci, 9, Oxford, New York: Clarendon Press, Oxford University Press
- Schütte, Kurt (1977), Teorie důkazůGrundlehren der Mathematischen Wissenschaften, 225, Berlín-New York: Springer-Verlag, str. Xii + 299, ISBN 3-540-07911-4, PAN 0505313
- Setzer, Anton (2004), "Důkazová teorie teorie Martin-Löf. Přehled", Mathématiques et Sciences Humaines. Matematika a sociální vědy (165): 59–99
- Takeuti, Gaisi (1987), Teorie důkazů„Studium logiky a základy matematiky, 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9, PAN 0882549
- ^ Krajíček, Jan (1995). Omezená aritmetika, výroková logika a teorie složitosti. Cambridge University Press. str.18–20. ISBN 9780521452052. definuje základní množiny a základní funkce a dokazuje jejich ekvivalent k Δ0-predikáty na přírodních zdrojích. Ordinální analýzu systému najdete v Rose, H. E. (1984). Subrekurze: funkce a hierarchie. University of Michigan: Clarendon Press. ISBN 9780198531890.