Borels bestämningssats

I beskrivande mängdteori anger Borels bestämningsteorem att alla Gale-Stewart-spel vars utdelning är en Borel-uppsättning bestäms , vilket betyder att en av de två spelarna kommer att ha en vinnande strategi för spelet . Ett Gale-Stewart-spel är ett möjligen oändligt spel för två spelare, där båda spelarna har perfekt information och ingen slumpmässighet är inblandad.

Satsen är en långtgående generalisering av Zermelos sats om bestämning av ändliga spel. Det bevisades av Donald A. Martin 1975 och tillämpas i beskrivande mängdteori för att visa att Borel-mängder i polska utrymmen har regularitetsegenskaper som den perfekta uppsättningsegenskapen och egenskapen Baire .

Teoremet är också känt för sina metamatematiska egenskaper. 1971, innan satsen bevisades, Harvey Friedman att alla bevis för satsen i Zermelo–Fraenkels mängdlära måste göra upprepad användning av axiomet om ersättning . Senare resultat visade att starkare determinitetsteorem inte kan bevisas i Zermelo–Fraenkels mängdlära, även om de är relativt konsekventa med den, om vissa stora kardinaler är konsekventa.

Bakgrund

Gale–Stewart-spel

Ett Gale–Stewart- spel är ett spel för två spelare med perfekt information. Spelet definieras med en uppsättning A och betecknas GA _. De två spelarna växlar om, och varje spelare är medveten om alla drag innan de gör nästa. Vid varje tur väljer varje spelare ett enda element av A att spela. Samma element kan väljas mer än en gång utan begränsning. Spelet kan visualiseras genom följande diagram, där dragen görs från vänster till höger, med rörelserna för spelare I ovan och dragen för spelare II nedan.

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}& \quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots \end{matrix}}$

Spelet fortsätter utan slut, så att ett enda spel av spelet bestämmer en oändlig sekvens $\langle a_{1},a_{2},a_{3}\ldots \rangle$ av element i A . Uppsättningen av alla sådana sekvenser betecknas A ^ω . Spelarna är medvetna, från början av spelet, om ett fast payoff-set (aka vinnande set ) som kommer att avgöra vem som vinner. Utdelningsmängden är en delmängd av A ^ω . Om den oändliga sekvensen som skapas av ett spel i spelet är i utdelningsuppsättningen, vinner spelare I. Annars vinner spelare II; det finns inga band.

Denna definition tycks initialt inte inkludera traditionella perfekta informationsspel som schack, eftersom uppsättningen av drag som finns tillgängliga i sådana spel ändras för varje tur. Men den här typen av fall kan hanteras genom att förklara att en spelare som gör ett olagligt drag förlorar omedelbart, så att Gale-Stewarts uppfattning om ett spel faktiskt generaliserar konceptet med ett spel som definieras av ett spelträd .

Vinnande strategier

En vinnande strategi för en spelare är en funktion som talar om för spelaren vilket drag som ska göras från valfri position i spelet, så att om spelaren följer funktionen kommer de säkert att vinna. Närmare bestämt är en vinnande strategi för spelare I en funktion f som tar som inmatningssekvenser av element av A med jämn längd och returnerar ett element av A , så att spelare I vinner varje spel i formen

${\begin{matrix}\mathrm {I} &a_{1}=f(\langle \rangle )&\quad &a_{3}=f(\langle a_{1},a_{2}\rangle ) &\quad &a_{5}=f(\langle a_{1},a_{2},a_{3},a_{4}\rangle )&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots .\end{matris}}$

En vinnande strategi för spelare II är en funktion g som tar sekvenser av udda längder av element av A och returnerar element av A , så att spelare II vinner varje spel i formen

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{ 2}=g(\langle a_{1}\rangle )&\quad &a_{4}=g(\langle a_{1},a_{2},a_{3}\rangle )&\quad &a_{6} =g(\langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )&\cdots .\end{matris}}$

Högst en spelare kan ha en vinnande strategi; om båda spelarna hade vinnande strategier och spelade strategierna mot varandra, kunde bara en av de två strategierna vinna det spelet i spelet. Om en av spelarna har en vinnande strategi för en viss utdelningsuppsättning, sägs den utdelningsuppsättningen vara bestämd .

Topologi

För en given mängd A beror huruvida en delmängd av A ^ω kommer att bestämmas till viss del på dess topologiska struktur. För Gale-Stewart-spelen är uppsättningen A utrustad med den diskreta topologin och A ^ω utrustad med den resulterande produkttopologin , där A ^ω ses som en countably oändlig topologisk produkt av A med sig själv. I synnerhet när A är mängden {0,1} är topologin som definieras på A ^ω exakt den vanliga topologin på Cantor-rymden, och när A är mängden naturliga tal är det den vanliga topologin på Baire-rymden .

Mängden A ^ω kan ses som en uppsättning vägar genom ett visst träd , vilket leder till en andra karaktärisering av dess topologi. Trädet består av alla ändliga sekvenser av element i A , och barnen i en viss nod σ i trädet är exakt de sekvenser som sträcker sig σ med ett element. Om A = { 0, 1 }, så består den första nivån i trädet av sekvenserna ⟨ 0 ⟩ och ⟨ 1 ⟩; den andra nivån består av de fyra sekvenserna ⟨ 0, 0 ⟩, ⟨ 0, 1 ⟩, ⟨ 1, 0 ⟩, ⟨ 1, 1 ⟩; och så vidare. För var och en av de finita sekvenserna σ i trädet är mängden av alla element i A ^ω som börjar med σ en grundläggande öppen mängd i topologin på A . De öppna mängderna av A ^ω är just de mängder som kan uttryckas som föreningar av dessa grundläggande öppna mängder. De slutna uppsättningarna är som vanligt de vars komplement är öppet.

Borelmängderna av A ^ω är den minsta klassen av delmängder av A ^ω som inkluderar de öppna mängderna och är sluten under komplement och räknebar förening . Det vill säga, Borel-mängderna är den minsta σ-algebra av delmängder av A ^ω som innehåller alla öppna mängder. Borel-uppsättningarna klassificeras i Borel-hierarkin baserat på hur många gånger operationerna med komplement och räkningsbar förening krävs för att producera dem från öppna uppsättningar.

Tidigare resultat

Gale och Stewart (1953) bevisade att om utdelningsmängden är en öppen eller sluten delmängd av A ^ω så bestäms alltid Gale–Stewart-spelet med den utdelningsmängden. Under de kommande tjugo åren utvidgades detta till något högre nivåer i Borelhierarkin genom allt mer komplicerade bevis. Detta ledde till frågan om spelet måste bestämmas när utdelningsmängden är en Borel-delmängd av A ^ω . Det var känt att med hjälp av valets axiom är det möjligt att konstruera en delmängd av {0,1} ^ω som inte är bestämd (Kechris 1995, s. 139).

Harvey Friedman (1971) bevisade att alla bevis för att alla Borel-delmängder av Cantor-rymden ({0,1} ^ω ) bestämdes skulle kräva upprepad användning av axiomet för ersättning , ett axiom som vanligtvis inte krävs för att bevisa satser om "små" objekt som t.ex. som kantorsutrymme.

Borel beslutsamhet

Donald A. Martin (1975) bevisade att för varje mängd A bestäms alla Borel-delmängder av A ^{ω .} Eftersom originalbeviset var ganska komplicerat publicerade Martin ett kortare bevis 1982 som inte krävde så mycket tekniskt maskineri. I sin recension av Martins tidning beskriver Drake det andra beviset som "förvånansvärt okomplicerat".

Området beskrivande mängdteori studerar egenskaperna hos polska utrymmen (i huvudsak kompletta separerbara metriska utrymmen). Borels bestämningssats har använts för att fastställa många ^{egenskaper hos Borels delmängder av dessa} utrymmen. Till exempel har alla Borel-undergrupper av polska utrymmen den perfekta uppsättningsegenskapen och Baires egendom .

Mängdteoretiska aspekter

Borels bestämningssats är av intresse för dess metamatematiska egenskaper såväl som dess konsekvenser i beskrivande mängdteori.

Bestämning av slutna uppsättningar av A ^ω för godtyckligt A är ekvivalent med valets axiom över ZF (Kechris 1995, s. 139). När man arbetar i mängdteoretiska system där valets axiom inte antas, kan detta kringgås genom att överväga generaliserade strategier som kallas kvasistrategier (Kechris 1995, s. 139) eller genom att endast betrakta spel där A är mängden naturliga tal, som i beslutsamhetens axiom .

Zermelo mängdlära (Z) är Zermelo–Fraenkels mängdlära utan axiomet ersättning. Den skiljer sig från ZF genom att Z inte bevisar att effektuppsättningsoperationen kan itereras oräkneligt många gånger med början med en godtycklig uppsättning. I synnerhet V _{ω + ω} , en speciell räknebar nivå i den kumulativa hierarkin , en modell av Zermelos mängdteori. Axiomet för ersättning, å andra sidan, uppfylls endast av V _κ för signifikant större värden på κ, som när κ är en starkt otillgänglig kardinal . Friedmans teorem från 1971 visade att det finns en modell av Zermelos mängdlära (med valets axiom) där Borels bestämning misslyckas, och Zermelos mängdlära kan därför inte bevisa Borels bestämningssats.

Förekomsten av alla beth-tal med räknebart index är tillräckligt för att bevisa Borels bestämningssats.

Starkare former av beslutsamhet

Flera mängdteoretiska principer om bestämning starkare än Borel bestämning studeras i deskriptiv mängdlära. De är nära besläktade med stora kardinalaxiom .

Axiomet för projektiv bestämning anger att alla projektiva delmängder av ett polskt rum bestäms. Det är känt för att vara omöjligt att bevisa i ZFC men relativt konsekvent med det och antydt av vissa stora kardinalaxiom . Förekomsten av en mätbar kardinal är tillräckligt för att antyda över ZFC att alla analytiska delmängder av polska utrymmen bestäms.

Axiomet för bestämning anger att alla delmängder av alla polska utrymmen bestäms. Det är inkonsekvent med ZFC men i ZF + DC (Zermelo–Fraenkel mängdteori plus axiomet för beroende val ) är det ekvikonsistent med vissa stora kardinalaxiom.

Friedman, Harvey (1971). "Högre mängdteori och matematisk praktik" . Annals of Mathematical Logic . 2 (3): 325–357. doi : 10.1016/0003-4843(71)90018-0 .
- L. Bukovský, granskare, Mathematical Reviews , MR 284327 .
Gale, D. och FM Stewart (1953). "Oändliga spel med perfekt information". Bidrag till teorin om spel, vol. 2 . Annals of Mathematical Studies, vol. 28. Vol. 28. Princeton University Press. s. 245–266.
- S. Sherman, granskare, Mathematical Reviews , MR 54922 .
Alexander Kechris (1995). Klassisk deskriptiv mängdlära . Graduate Texts in Mathematics . Vol. 156. ISBN 0-387-94374-9 .
Martin, Donald A. (1975). "Borel beslutsamhet". Annals of Mathematics . Andra serien. 102 (2): 363–371. doi : 10.2307/1971035 .
- John Burgess, recensent. Matematiska recensioner , MR 403976 .
Martin, Donald A. (1982). "Ett rent induktivt bevis på Borels beslutsamhet". Rekursionsteori . Proc. Sympos. Pure Math (Proceedings of the AMS–ASL summer institute som hölls i Ithaca, New York red.). s. 303–308.
- FR Drake, granskare, Mathematical Reviews , MR 791065 .

externa länkar

Borels bestämning och metamatematik . Ross Bryant. Magisteruppsats, University of North Texas, 2001.
"Large Cardinals and Determinacy" på Stanford Encyclopedia of Philosophy