Twierdzenie o determinacji Borela

W opisowej teorii mnogości twierdzenie Borela o determinacji stwierdza, że każda gra Gale'a-Stewarta , której zestaw wypłat jest zbiorem Borela , jest określona , co oznacza, że jeden z dwóch graczy będzie miał zwycięską strategię w grze. Gra Gale-Stewart to prawdopodobnie nieskończona gra dla dwóch graczy, w której obaj gracze mają doskonałe informacje i nie ma w tym przypadku przypadkowości.

Twierdzenie jest daleko idącym uogólnieniem twierdzenia Zermelo o determinacji gier skończonych. Zostało to udowodnione przez Donalda A. Martina w 1975 roku i jest stosowane w opisowej teorii mnogości do wykazania, że zbiory borelowskie w polskich przestrzeniach mają własności regularności, takie jak własność zbioru doskonałego i własność Baire'a .

Twierdzenie jest również znane ze swoich właściwości metamatematycznych . W 1971 roku, zanim twierdzenie zostało udowodnione, Harvey Friedman wykazał, że każdy dowód twierdzenia w teorii mnogości Zermelo-Fraenkla musi wielokrotnie wykorzystywać aksjomat zastępowania . Późniejsze wyniki pokazały, że silniejszych twierdzeń o determinacji nie można udowodnić w teorii mnogości Zermelo-Fraenkla, chociaż są one z nią względnie zgodne , jeśli pewne duże liczby kardynalne są spójne.

Tło

Gry Gale'a-Stewarta

Gale -Stewart to gra dla dwóch graczy z doskonałą informacją. Gra jest zdefiniowana za pomocą zbioru A i oznaczona G _A . Dwaj gracze naprzemiennie tur, a każdy gracz jest świadomy wszystkich ruchów przed wykonaniem następnego. W każdej turze każdy gracz wybiera jeden element A do zagrania. Ten sam element można wybrać więcej niż jeden raz bez ograniczeń. Grę można zobrazować na poniższym diagramie, na którym ruchy są wykonywane od lewej do prawej, z ruchami gracza I powyżej i graczami II poniżej.

${\ Displaystyle {\ rozpocząć {macierz} \ operatorname {I} & a_ {1} & \ quad & a_ {3} & \ quad & a_ {5} & \quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots \end{macierz}}}$

Gra trwa bez końca, tak że pojedyncza gra określa nieskończoną sekwencję ${\ Displaystyle \ langle a_ {1}, a_ {2}, a_ {3} \ ldots \rangle }$ elementów A . Zbiór wszystkich takich ciągów oznaczamy A ^ω . Gracze od początku gry są świadomi ustalonego zestawu wypłat (tzw. zestawu wygrywającego ), który zadecyduje o tym, kto wygra. Zbiór wypłat jest podzbiorem A ω ^. Jeśli nieskończona sekwencja utworzona w wyniku gry jest w zbiorze wypłat, wygrywa gracz I. W przeciwnym razie wygrywa gracz II; nie ma więzi.

Wydaje się, że ta definicja początkowo nie obejmuje tradycyjnych gier z doskonałą informacją, takich jak szachy, ponieważ zestaw ruchów dostępnych w takich grach zmienia się co turę. Jednak tego rodzaju przypadki można rozwiązać, oświadczając, że gracz, który wykonuje nielegalny ruch, natychmiast przegrywa, tak więc koncepcja gry Gale'a-Stewarta w rzeczywistości uogólnia koncepcję gry zdefiniowaną przez drzewo gry .

Zwycięskie strategie

Zwycięska strategia dla gracza to funkcja, która mówi graczowi, jaki ruch wykonać z dowolnej pozycji w grze, tak że jeśli gracz zastosuje się do funkcji, z pewnością wygra. Mówiąc dokładniej, zwycięską strategią dla gracza I jest funkcja f , która przyjmuje jako dane wejściowe sekwencje elementów A o parzystej długości i zwraca element A , tak że gracz I wygra każdą grę postaci

${\ Displaystyle {\ rozpocząć {macierz} \ operatorname {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{macierz}}}$

Zwycięską strategią dla gracza II jest funkcja g , która pobiera sekwencje elementów A o nieparzystej długości i zwraca elementy A , tak że gracz II wygra każdą grę postaci

${\ Displaystyle {\ rozpocząć {macierz} \ operatorname {I} & a_ {1} & \ quad & a_ {3} & \ quad & a_ {5} & \ quad & \ cdots \\\ operatorname {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{macierz}}}$

Co najwyżej jeden gracz może mieć zwycięską strategię; gdyby obaj gracze mieli zwycięskie strategie i grali je przeciwko sobie, tylko jedna z dwóch strategii mogłaby wygrać tę partię gry. Jeśli jeden z graczy ma zwycięską strategię dla określonego zestawu wypłat, mówi się, że ten zestaw wypłat jest określony .

Topologia

Dla danego zbioru A to, czy zostanie określony podzbiór A ^{ω , zależy w pewnym stopniu od jego struktury topologicznej.} Na potrzeby gier Gale-Stewart zbiór A jest wyposażony w topologię dyskretną , a A ^ω w wynikową topologię produktu , gdzie A ^ω jest postrzegane jako policzalnie nieskończony iloczyn topologiczny A z samym sobą. W szczególności, gdy A jest zbiorem {0,1}, topologia zdefiniowana na A ^ω jest dokładnie topologią zwyczajną w przestrzeni Cantora , a gdy A jest zbiorem liczb naturalnych, jest to topologia zwyczajna w przestrzeni Baire'a .

Zbiór A ^ω można postrzegać jako zbiór ścieżek przechodzących przez pewne drzewo , co prowadzi do drugiej charakterystyki jego topologii. Drzewo składa się ze wszystkich skończonych ciągów elementów A , a dzieci danego węzła σ drzewa są dokładnie tymi ciągami, które wydłużają σ o jeden element. Zatem jeśli A = { 0, 1 }, pierwszy poziom drzewa składa się z sekwencji ⟨ 0 ⟩ i ⟨ 1 ⟩; drugi poziom składa się z czterech sekwencji ⟨ 0, 0 ⟩, ⟨ 0, 1 ⟩, ⟨ 1, 0 ⟩, ⟨ 1, 1 ⟩; i tak dalej. Dla każdego ze skończonych ciągów σ w drzewie zbiór wszystkich elementów A ^ω zaczynających się na σ jest podstawowym zbiorem otwartym w topologii na A . Zbiory otwarte A ^ω są właśnie zbiorami dającymi się wyrazić jako sumy tych podstawowych zbiorów otwartych . Zbiory domknięte , jak zwykle, to te, których dopełnienie jest otwarte.

Zbiory borelowskie A ^ω to najmniejsza klasa podzbiorów A ^ω , która zawiera zbiory otwarte i jest domknięta na dopełnienie i przeliczalną sumę . Oznacza to, że zbiory Borela są najmniejszą σ-algebrą podzbiorów A ^ω zawierającą wszystkie zbiory otwarte. Zbiory borelowskie są klasyfikowane w hierarchii borelowskiej na podstawie tego, ile razy operacje dopełnienia i sumy przeliczalnej są wymagane do wytworzenia ich ze zbiorów otwartych.

Poprzednie wyniki

Gale i Stewart (1953) udowodnili, że jeśli zbiór wypłat jest otwartym lub zamkniętym podzbiorem A ^ω , to gra Gale-Stewart z tym zbiorem wypłat jest zawsze określona. W ciągu następnych dwudziestu lat zostało to rozszerzone na nieco wyższe poziomy hierarchii Borela poprzez coraz bardziej skomplikowane dowody. Doprowadziło to do pytania, czy gra musi być ustalona, gdy zbiór wypłat jest podzbiorem borelowskim A ^ω . Wiadomo było, że za pomocą aksjomatu wyboru można skonstruować podzbiór {0,1} ^ω , który nie jest określony (Kechris 1995, s. 139).

Harvey Friedman (1971) udowodnił, że każdy dowód na to, że wszystkie podzbiory borelowskie przestrzeni Cantora ({0,1} ^ω ) zostały określone, wymagałby wielokrotnego użycia aksjomatu zamiany , aksjomatu zwykle nie wymaganego do udowodnienia twierdzeń o „małych” obiektach, takich jak jako przestrzeń Cantora.

Determinacja Borela

Donald A. Martin (1975) udowodnił, że dla dowolnego zbioru A wszystkie podzbiory borelowskie A ^ω są określone. Ponieważ oryginalny dowód był dość skomplikowany, Martin opublikował w 1982 r. krótszy dowód, który nie wymagał tak wielu urządzeń technicznych. W swojej recenzji artykułu Martina Drake opisuje drugi dowód jako „zaskakująco prosty”.

Dziedzina opisowej teorii mnogości bada właściwości polskich przestrzeni (zasadniczo kompletnych rozdzielnych przestrzeni metrycznych). Twierdzenie o determinacji Borela zostało użyte do ustalenia wielu ^{[ potrzebne źródło ]} właściwości podzbiorów borelowskich tych przestrzeni. Na przykład wszystkie borelowskie podzbiory przestrzeni polskich mają własność zbioru doskonałego i własność Baire'a .

Aspekty teorii mnogości

Twierdzenie Borela o determinacji jest interesujące ze względu na jego właściwości metamatematyczne , a także konsekwencje w opisowej teorii mnogości.

Wyznaczalność zbiorów domkniętych A ^ω dla dowolnego A jest równoważna aksjomatowi wyboru nad ZF (Kechris 1995, s. 139). Pracując w systemach teorii mnogości, w których nie zakłada się aksjomatu wyboru, można to obejść, rozważając uogólnione strategie znane jako quasistrategie (Kechris 1995, s. 139) lub rozważając tylko gry, w których A jest zbiorem liczb naturalnych, jak w aksjomat determinacji .

Teoria mnogości Zermelo ( Z ) to teoria mnogości Zermelo – Fraenkla bez aksjomatu zastępowania. Różni się od ZF tym, że Z nie dowodzi, że zbioru potęg można powtarzać niezliczoną ilość razy, zaczynając od dowolnego zbioru. W szczególności V _{ω + ω} , szczególny policzalny poziom skumulowanej hierarchii , jest modelem teorii mnogości Zermelo. Z drugiej strony aksjomat zastępowania jest spełniony tylko przez V _κ dla znacznie większych wartości κ, na przykład gdy κ jest silnie niedostępnym kardynałem . Twierdzenie Friedmana z 1971 roku wykazało, że istnieje model teorii mnogości Zermelo (z aksjomatem wyboru), w którym determinacja Borela zawodzi, a zatem teoria mnogości Zermelo nie może udowodnić twierdzenia Borela o determinacji.

Istnienie wszystkich liczb beth indeksu policzalnego jest wystarczające, aby udowodnić twierdzenie Borela o determinacji.

Silniejsze formy determinacji

W opisowej teorii mnogości bada się kilka zasad teorii mnogości dotyczących determinacji silniejszej niż determinacja Borela. Są blisko spokrewnione z dużymi aksjomatami kardynalnymi .

Aksjomat determinacji rzutowej mówi, że wszystkie podzbiory rzutowe polskiej przestrzeni są określone. Wiadomo, że jest nie do udowodnienia w ZFC, ale jest z nim stosunkowo zgodny i implikowany przez pewne duże aksjomaty kardynalne. Istnienie mierzalnego kardynała wystarczy, aby zasugerować nad ZFC, że wszystkie analityczne podzbiory polskich przestrzeni są określone.

Aksjomat wyznaczalności mówi, że wszystkie podzbiory wszystkich polskich przestrzeni są określone. Jest to niezgodne z ZFC, ale w ZF + DC (teoria mnogości Zermelo-Fraenkela plus aksjomat zależnego wyboru ) jest jednakowo zgodne z pewnymi dużymi aksjomatami kardynalnymi.

Friedmana, Harveya (1971). „Teoria wyższych zbiorów i praktyka matematyczna” . Roczniki logiki matematycznej . 2 (3): 325–357. doi : 10.1016/0003-4843(71)90018-0 .
- L. Bukovský, recenzent, Recenzje matematyczne , MR 284327 .
Gale, D. i FM Stewart (1953). „Nieskończone gry z doskonałymi informacjami” . Składki do teorii gier, tom. 2 . Annals of Mathematical Studies, tom. 28. Cz. 28. Princeton University Press. s. 245–266.
- S. Sherman, recenzent, recenzje matematyczne , MR 54922 .
Aleksander Kechris (1995). Klasyczna opisowa teoria mnogości . Absolwent Teksty z matematyki . Tom. 156. ISBN 0-387-94374-9 .
Martin, Donald A. (1975). „Determinacja Borela”. Roczniki matematyki . Druga seria. 102 (2): 363–371. doi : 10.2307/1971035 .
- John Burgess, recenzent. Recenzje matematyczne , MR 403976 .
Martin, Donald A. (1982). „Czysto indukcyjny dowód determinacji Borela”. Teoria rekurencji . proc. sympozja. Pure Math (Materiały letniego instytutu AMS – ASL, które odbyły się w Ithaca, wyd. Nowy Jork). s. 303–308.
- FR Drake, recenzent, recenzje matematyczne , MR 791065 .

Linki zewnętrzne

Determinacja Borela i metamatematyka . Rossa Bryanta. Praca magisterska, University of North Texas, 2001.
„Wielcy kardynałowie i determinacja” w Stanford Encyclopedia of Philosophy