Rozhodnost - Determinacy

„Odhodlaný“ přeadresuje tady. Pro heavy metalovou píseň 2005 viz Determined (píseň) .
Další použití „neurčitosti“ viz Neurčitost .

Determinacy je podoblast teorie množin , obor matematiky , který zkoumá podmínky, za nichž má jeden nebo druhý hráč hry vítěznou strategii, a důsledky existence takových strategií. Alternativně a podobně je „rozhodnost“ vlastností hry, ve které taková strategie existuje.

Hry studované v teorii množin jsou obvykle hry Gale- Stewart-hry pro dva hráče s dokonalými informacemi, ve kterých hráči provádějí nekonečnou posloupnost tahů a nedochází k remízám. Oblast teorie her studuje obecnější druhy her, včetně her s remízami, jako jsou tic-tac-toe , šachy nebo nekonečné šachy , nebo her s nedokonalými informacemi, jako je poker .

Základní pojmy

Hry

První typ hry, kterou zvažujeme, je hra pro dva hráče s dokonalými informacemi o délce ω , ve které hráči hrají přirozená čísla . Tyto hry se často nazývají hry Gale – Stewart.

V tomto druhu hry jsou dva hráči, často jmenovaní I a II , kteří se střídají v hraní přirozených čísel, přičemž já jdu první. Hrají „navždy“; to znamená, že jejich hry jsou indexovány přirozenými čísly. Když jsou hotové, předem stanovená podmínka rozhodne, který hráč vyhrál. Tato podmínka nemusí být specifikována žádným definovatelným pravidlem ; může to být jednoduše libovolná (nekonečně dlouhá) vyhledávací tabulka , která říká, kdo vyhrál danou sekvenci her.

Více formálně, zvažte podmnožiny A v Baire prostoru ; připomeňme, že to druhé se skládá ze všech ω-sekvencí přirozených čísel. Potom ve hře G A , I hraje přirozené číslo 0 , pak II hraje 1 , pak jsem hraje na 2 , a tak dále. Pak jsem se vyhrává hru tehdy a jen tehdy, pokud

a jinak vítězí II . Se pak nazývá výplatní set G A .

Předpokládá se, že každý hráč může vidět všechny tahy předcházející každému z jeho tahů a také zná vítěznou podmínku.

Strategie

Neformálně je strategie hráče způsobem, ve kterém jsou jeho hry zcela určeny předchozími hrami. Opět platí, že takový „způsob“ nemusí být možné zachytit žádným vysvětlitelným „pravidlem“, ale může to být jednoduše vyhledávací tabulka.

Formálněji je strategie pro hráče I (pro hru ve smyslu předchozího pododdílu) funkcí, která jako argument přijímá jakoukoli konečnou posloupnost přirozených čísel, sudé délky, a vrací přirozené číslo. Pokud je σ taková strategie a <a 0 ,...,a 2n-1> je posloupnost her, pak σ (<a 0 ,...,a 2n-1> ) je další hra, kterou udělám pokud jsem se po strategie å . Strategie pro II jsou stejné, nahrazují „liché“ „sudými“.

Všimněte si toho, že jsme zatím neřekli nic o tom, zda je strategie vůbec dobrá . Strategie může hráče nasměrovat k agresivně špatným tahům a stále by to byla strategie. Ve skutečnosti není nutné ani znát vítěznou podmínku hry, vědět, jaké strategie pro hru existují.

Vítězné strategie

Strategie vyhrává, pokud hráč, který ji sleduje, musí nutně vyhrát, bez ohledu na to, co hraje jeho soupeř. Pokud je například σ strategie pro I , pak σ je vítěznou strategií pro I ve hře G A, jestliže pro jakoukoli sekvenci přirozených čísel, kterou má hrát II , řekněme <a 1 , a 3 , a 5 ,. ..>, sekvence her vytvořená σ, když II hraje takto, jmenovitě

je prvek A .

Odhodlané hry

Hra (třídy) je určena, pokud pro všechny instance hry existuje vítězná strategie pro jednoho z hráčů (ne nutně stejného hráče pro každou instanci). Všimněte si, že nemůže existovat vítězná strategie pro oba hráče pro stejnou hru, protože pokud by existovaly, obě strategie by se daly hrát proti sobě. Výsledný výsledek by pak, hypotézou, byl výhrou pro oba hráče, což je nemožné.

Odhodlání od elementárních úvah

Jsou určeny všechny konečné hry dokonalých informací, ve kterých nedochází k losování.

Hry s dokonalými informacemi v reálném světě, jako jsou tic-tac-toe , šachy nebo nekonečné šachy , jsou vždy zakončeny konečným počtem tahů (v šachových hrách to předpokládá pravidlo 50 tahů). Pokud je taková hra upravena tak, že konkrétní hráč vyhraje za jakýchkoli podmínek, kde by byla hra nazývána remízou, pak je vždy rozhodnuto. Podmínka, že hra vždy skončí (tj. Všechny možné prodloužení konečné pozice vedou k výhře pro stejného hráče) v konečném počtu tahů, odpovídá topologické podmínce, že množina A dávající vítěznou podmínku pro G A je clopen v topologii z Baire prostoru .

Například úprava šachových pravidel tak, aby tažené hry vyhrály pro černého, ​​činí ze šachu určenou hru. Jak se to stává, šachy mají konečný počet pozic a pravidla opakování remízy, takže pokud s těmito upravenými pravidly hra pokračuje dostatečně dlouho, aniž by bílý vyhrál, pak černý může nakonec vynutit výhru (kvůli úpravě remízy) = výhra pro černé).

Důkaz, že takové hry jsou určeny, je poměrně jednoduchý: Hráč, kterého hraji, prostě neprohrává ; to znamená, že hráč I hraje, aby se ujistil, že hráč II nemá vítěznou strategii po mém tahu. Pokud hráč mi nemůže udělat, pak to znamená, že hráč II měl vítěznou strategii od samého počátku. Na druhou stranu, pokud hráč I mohou hrát tímto způsobem, pak jsem se musí vyhrát, protože hra bude více než po nějakém konečném počtu tahů a hráč já nemůže být v tomto bodě ztraceny.

Tento důkaz ve skutečnosti nevyžaduje, aby hra vždy skončila v konečném počtu tahů, pouze aby skončila v konečném počtu tahů, kdykoli vyhraje II . Tato podmínka, topologicky, je to, že množina je uzavřen . Této skutečnosti - že jsou určeny všechny uzavřené hry - se říká Galeova – Stewartova věta . Všimněte si, že symetrií jsou určeny i všechny otevřené hry. (Hra je otevřená, pokud mohu vyhrát pouze vítězstvím v konečném počtu tahů.)

Odhodlání od ZFC

David Gale a FM Stewart dokázali, že otevřené a uzavřené hry jsou rozhodné. Odhodlání pro druhou úroveň hierarchie Borel ukázal Wolfe v roce 1955. Během následujících 20 let další výzkum využívající stále komplikovanější argumenty prokázal, že je určena třetí a čtvrtá úroveň Borelské hierarchie.

V roce 1975 Donald A. Martin dokázal, že všechny hry Borel jsou určeny; to znamená, že pokud A je Borelova podmnožina Baireova prostoru, pak je určena G A. Tento výsledek, známý jako Borelova determinovanost , je nejlepším možným výsledkem určitelnosti prokazatelným v ZFC, v tom smyslu, že určitelnost další vyšší třídy Wadge není v ZFC prokazatelná.

V roce 1971, než Martin získal svůj důkaz, Harvey Friedman ukázal, že jakýkoli důkaz borelovské determinace musí zásadním způsobem využívat axiom nahrazení , aby se axiom setu mocnin často nekonečně často opakoval . Friedmanova práce poskytuje výsledek po úrovni, který podrobně popisuje, kolik iterací axiomu množin je zapotřebí k zajištění determinity na každé úrovni borelské hierarchie .

Za každou celé číslo n , ZFC \ P dokazuje determinovanosti v n -té úrovni hierarchie rozdílové sad, ale ZFC \ P nedokazuje, že pro každé celé číslo n n -tého úrovni hierarchie rozdílové sad je určen. Další vztahy mezi determinantou a subsystémy aritmetiky druhého řádu viz reverzní matematika .

Odhodlanost a velcí kardinálové

Mezi rozhodností a velkými kardinály existuje úzký vztah . Obecně platí, že silnější velké kardinální axiomy dokazují určitelnost větších bodových tříd , vyšší v hierarchii Wadge , a determinita těchto bodových tříd zase dokazuje existenci vnitřních modelů o něco slabších velkých kardinálních axiomů, než jaké byly použity k prokázání determinantnosti bodová třída na prvním místě.

Měřitelní kardinálové

Hlavní článek: Měřitelný kardinál

Z existence měřitelného kardinála vyplývá, že je určena každá analytická hra (také nazývaná Σ 1 1 hra), nebo ekvivalentně, že je určena každá koanalytická (nebo Π 1 1 ) hra. ( Definice viz Projektivní hierarchie .)

Ve skutečnosti je měřitelný kardinál více než dost. Slabší princip - existence 0 # stačí k prokázání koanalytické determinace a ještě něco navíc: Přesným výsledkem je, že existence 0 # je ekvivalentní určitelnosti všech úrovní hierarchie rozdílů pod úrovní ω 2 , tj. ω · n- Π 1 1 určitelnost pro každého .

Od měřitelného kardinála to můžeme velmi mírně vylepšit na determinantnost ω 2 - Π 1 1 . Z existence více měřitelných kardinálů lze prokázat určitelnost více úrovní diferenční hierarchie nad Π 1 1 .

Důkaz determinace z ostrých předmětů

Pro každé skutečné číslo r je determinita ekvivalentní existenci r # . Pro ilustraci, jak velcí kardinálové vedou k determinitě, je zde důkaz determinity dané existence r # .

Nechť A je podmnožinou prostoru Baire. A = p [ T ] pro nějaký strom T (konstruovatelný z r ) na (ω, ω). (To je x∈Aff od některých y , je cesta skrz T. )

Vzhledem k částečné hře s , nechť je podstrom T v souladu s s s výhradou max (y 0 , y 1 , ..., y len (s) -1 ) <len (s). Dodatečná podmínka zajišťuje, že je konečný. Konzistence znamená, že každá cesta je ve formě, kde je počáteční segment s .

Chcete -li dokázat, že A je určeno, definujte pomocnou hru takto:
Kromě běžných tahů musí hráč 2 hrát mapování do pořadových čísel (pod dostatečně velkým pořadovým číslem κ ) tak, aby

  • každý nový tah rozšiřuje předchozí mapování a
  • objednávka ordinals souhlasí s objednávkou Kleene – Brouwer dne .

Připomeňme si, že Kleene – Brouwerův řád je jako lexikografický řád s tím rozdílem, že pokud s správně prodlužuje t, pak s < t . Je to dobře uspořádané, pokud je strom opodstatněný.

Pomocná hra je otevřená. Důkaz: Pokud hráč 2 ve konečné fázi neprohraje, pak je sjednocení všech (což je strom, který hře odpovídá) podložené, a proto výsledek pomocné hry není v A.

Tím je určena pomocná hra. Důkaz: Transfinitní indukcí pro každý řadový α spočítejte sadu pozic, kde si hráč 1 může vynutit výhru v α krocích, kde pozice s hráčem 2, který se má pohybovat, ztrácí (pro hráče 2) v α krocích, pro každý pohyb výsledný pozice ztrácí v méně než α krocích. Jednou strategií pro hráče 1 je snížit α s každou pozicí (řekněme výběrem nejméně α a přerušením vazeb výběrem nejmenšího tahu) a jednou strategií pro hráče 2 je vybrat nejmenší (vlastně jakýkoli by fungoval) tah, který nevede do polohy s přiřazenou α. Všimněte si, že L ( r ) obsahuje sadu vítězných pozic i vítězné strategie uvedené výše.

Vítězná strategie pro hráče 2 v původní hře vede k vítězné strategii v pomocné hře: podstrom T odpovídající vítězné strategii je dobře podložený, takže si hráč 2 může vybrat pořadové číslo podle pořadí Kleene-Brouwerova stromu. Triviálně také vítězná strategie pro hráče 2 v pomocné hře dává vítěznou strategii pro hráče 2 v původní hře.

Zbývá ukázat, že pomocí r # lze výše uvedenou výherní strategii pro hráče 1 v pomocné hře převést na vítěznou strategii v původní hře. r # dává správnou třídu I ( L ( r ), ∈, r ) nerozeznatelných pořadových čísel. Podle nerozeznatelnosti, pokud κ a pořadové číslo v pomocné odpovědi je v I , pak tahy hráče 1 nezávisí na pomocných tahech (nebo na κ ), a tak lze strategii převést na strategii pro původní hru ( protože hráč 2 může vydržet s nerozeznatelnými pro libovolný konečný počet kroků). Předpokládejme, že hráč 1 prohraje v původní hře. Potom je strom odpovídající hře podložený. Hráč 2 tedy může vyhrát pomocnou hru pomocí pomocných tahů založených na nerozeznatelných (protože typ pořadí nerozeznatelných překračuje pořadí Kleene – Brouwer stromu), což je v rozporu s tím, že hráč 1 vyhraje pomocnou hru.

Woodin kardinálové

Hlavní článek: Woodin kardinál

Pokud existuje Woodinův kardinál s měřitelným kardinálem nad ním, pak platí Π 1 2 determinance. Obecněji platí, že pokud existuje n Woodinových kardinálů s měřitelným kardinálem nad všemi, pak platí Π 1 n+1 determinance. Z determinance Π 1 n+1 vyplývá, že existuje tranzitivní vnitřní model obsahující n Woodinových kardinálů.

(lightface) určitelnost je ekvikonzistentní s Woodinovým kardinálem. Platí -li určitelnost, pak pro Turingův kužel x (to znamená pro každé skutečné x dostatečně vysokého Turingova stupně ) splňuje L [ x ] OD-určitelnost (to je určitelnost her na celá čísla o délce ω a ordinálně definovatelné výplatě) , a v HOD L [ x ] je Woodinův kardinál.

Projektivní determinace

Hlavní článek: Projektivní determinace

Pokud existuje nekonečně mnoho Woodinových kardinálů, pak platí projektivní determinace; to znamená, že je určena každá hra, jejíž vítěznou podmínkou je projektivní sada . Z projektivní determinace vyplývá, že pro každé přirozené číslo n existuje tranzitivní vnitřní model, který splňuje, že existuje n Woodinových kardinálů.

Axiom determinace

Hlavní článek: Axiom determinace

Axiom determinovanosti nebo AD , tvrdí, že každé dva hráče hra dokonalé informace o délce W, ve kterém hráči hrají Naturals, je určena.

AD je prokazatelně nepravdivý od ZFC; pomocí axiomu výběru lze prokázat existenci neurčené hry. Pokud však existuje nekonečně mnoho Woodinových kardinálů s měřitelnými nad všemi, pak L (R) je model ZF, který splňuje AD.

Důsledky determinace

Vlastnosti pravidelnosti pro sady realů

Pokud je podmnožina Baire prostoru, tak, že Banachova-Mazur hra pro A je určeno, pak buď II má vítěznou strategii, a v takovém případě je hubené , nebo I má vítěznou strategii, a v takovém případě je comeager na některých otevřené sousedství.

To zcela neznamená, že A má vlastnost Baire , ale blíží se: Jednoduchá modifikace argumentu ukazuje, že pokud Γ je adekvátní bodová třída taková, že je určena každá hra v Γ, pak každá sada realů v Γ má majetek Baire.

Ve skutečnosti tento výsledek není optimální; s ohledem na rozvinutou hru Banach – Mazur můžeme ukázat, že určitelnost Γ (pro Γ s dostatečnými uzavíracími vlastnostmi) znamená, že každá sada realů, která je projekcí množiny v Γ, má vlastnost Baire. Například například existence měřitelného kardinála implikuje determinantu Π 1 1 , což zase znamená, že každá Σ 1 2 sada realů má vlastnost Baire.

Když vezmeme v úvahu jiné hry, můžeme ukázat, že Π 1 n determinance znamená, že každá Σ 1 n +1 sada realů má vlastnost Baire, je Lebesgueova měřitelná (ve skutečnosti univerzálně měřitelná ) a má dokonalou sadu vlastností .

Věty o periodicitě

  • První periodicity věta znamená, že pro každé přirozené číslo n , pokud Δ 1 2 n 1 determinovanosti platí, pak Π 1 2 n 1 a Σ 1 2 n +2 mají prewellordering majetku (a to Σ 1 2 n 1 a Π 1 2 n 2 se nebude mít prewellordering vlastnost, ale spíše mají vlastnost separační ).
  • Druhý periodicity věta znamená, že pro každé přirozené číslo n , jestliže delta 1 2 n +1 determinovanosti platí, pak Π 1 2 n 1 a Σ 1 2 n mají vlastnost měřítko . Zejména platí -li projektivní determinance, pak každý projektivní vztah má projektivní uniformizaci .
  • Periodicity věta třetí dává dostačující podmínkou pro hru mít definovatelnou vítěznou strategii.

Aplikace na rozhodnutelnost určitých teorií druhého řádu

V roce 1969, Michael O. Rabin dokázal, že teorie druhého řádu z n nástupců je decidable . Klíčová složka důkazu vyžaduje prokázání určitelnosti paritních her , které leží na třetí úrovni borelské hierarchie .

Brodivost

Determinace Wadge je tvrzení, že pro všechny páry A , B podmnožin prostoru Baire je určena hra Wadge G ( A , B ). Podobně pro bodovou třídu Γ je Γ Wadgeová určitelnost tvrzení, že pro všechny sady A , B v Γ je určena Wadgeova hra G ( A , B ).

Determinace Wadge implikuje semilineární princip uspořádání pro Wadge order . Dalším důsledkem determinace Wadge je dokonalá sada vlastností .

Obecně platí, že Γ určitelnost brodivosti je důsledkem určitelnosti booleovských kombinací množin v Γ. V projektivní hierarchii , Π 1 1 Wadge determinovanosti je ekvivalentní n 1 1 determinovanosti, jak o tom svědčí Leo Harrington . Tento výsledek rozšířil Hjorth, aby dokázal, že Π 1 2 Wadgeova determinovanost (a ve skutečnosti princip semilineárního uspořádání pro Π 1 2 ) již implikuje determinantu Π 1 2 .

Obecnější hry

Hry, ve kterých hrané objekty nejsou přirozená čísla

Odhodlání her na pořadových číslech s ordinální definovatelnou výplatou a délkou ω znamená, že pro každý pravidelný kardinál κ > ω neexistují žádné ordinální definovatelné disjunktní stacionární podmnožiny κ vytvořené z ordinálů kofinality ω. Síla konzistence hypotézy determinace není známa, ale očekává se, že bude velmi vysoká.

Hry hrané na stromech

Dlouhé hry

Existence ω 1 Woodinových kardinálů znamená, že pro každé spočítatelné pořadové číslo α jsou určeny všechny hry na celá čísla o délce α a projektivní výplatě. Zhruba řečeno, a. Za předpokladu limitu Woodinových kardinálů κ s o ( κ ) = κ ++ a ω Woodinových kardinálů nad κ , hry s proměnnou počitatelnou délkou, kde hra končí, jakmile je její délka přípustná vzhledem k linii hry a s projektivní odměnou, jsou odhodlaný. Za předpokladu, že je jistá domněnka iterability prokazatelná, existence měřitelného Woodinova kardinála implikuje určení otevřených her o délce ω 1 a projektivní výplatě. (V těchto hrách je vítězná podmínka pro prvního hráče spuštěna v počitatelné fázi, takže výplata může být kódována jako sada realů.)

Ve vztahu k Woodinovu limitu Woodinových kardinálů a měřitelnému nad nimi je konzistentní, že je určena každá hra na celá čísla o délce ω 1 a ordinálně definovatelné výplatě. Předpokládá se, že hypotéza determinace je v souladu s Woodinovým limitem Woodinových kardinálů. ω 1 je maximální v tom, že existují neurčené hry na celá čísla o délce ω 1 +ω a ordinálně definovatelné výplatě.

Hry s nedokonalými informacemi

V každé zajímavé hře s nedokonalými informacemi bude vítěznou strategií smíšená strategie : to znamená, že poskytne určitou pravděpodobnost různých reakcí na stejnou situaci. Pokud jsou optimálními strategiemi obou hráčů smíšené strategie, pak výsledek hry nemůže být rozhodně určující (jak tomu může být u čistých strategií , protože tyto jsou deterministické ). Ale rozdělení pravděpodobnosti výsledků na protichůdné smíšené strategie lze vypočítat. Hra, která vyžaduje smíšené strategie, je definována jako určená, pokud existuje strategie, která poskytuje minimální očekávanou hodnotu (přes možné protistratégie), která přesahuje danou hodnotu. Proti této definici jsou všechny konečné hry pro dva hráče s nulovým součtem jasně určeny. Méně jasná je však určitelnost nekonečných her s nedokonalou informací (hry Blackwell).

V roce 1969 David Blackwell prokázal, že jsou určeny některé „nekonečné hry s nedokonalými informacemi“ (nyní nazývané „hry Blackwell“), a v roce 1998 Donald A. Martin dokázal, že běžná (dokonalá informační hra) určitelnost pro tučnou třídu bodů implikuje Blackwellovu determinaci pro bodová třída. To v kombinaci s Martinovou větou o Borelově determinitě znamená, že jsou určeny všechny hry Blackwell s Borelskými výplatními funkcemi. Martin se domníval, že běžná determinantnost a Blackwellova determinovanost pro nekonečné hry jsou v silném smyslu ekvivalentní (tj. Že Blackwellova determinovanost pro tučnou třídu bodových tříd zase implikuje běžnou determinantu pro tuto bodovou třídu), ale od roku 2010 nebylo prokázáno, že Blackwellova determinovanost implikuje určitelnost hry s dokonalými informacemi.

Kvazistrategie a kvazideterminovanost

Viz také

Poznámky pod čarou

  1. ^ To předpokládá, žejsemse snaží dostat průsečík čtvrtí hrál být singleton, jehož jedinečný prvek je prvkemA. Někteří autoři to považují za cíl pro hráčeII; že použití vyžaduje odpovídající úpravu výše uvedených poznámek.

Reference

externí odkazy