Determinacja - Determinacy

Determinacja to poddziedzina teorii mnogości , dział matematyki , który bada warunki, w których jeden lub drugi gracz w grze ma strategię wygrywającą, oraz konsekwencje istnienia takich strategii. Alternatywnie i podobnie „determinacja” jest własnością gry, w której istnieje taka strategia.

Gry badane w teorii mnogości to zazwyczaj gry Gale – Stewart – dwuosobowe gry z doskonałą informacją, w których gracze wykonują nieskończoną sekwencję ruchów i nie ma remisów. Dziedzina teorii gier zajmuje się bardziej ogólnymi rodzajami gier, w tym grami z remisami, takimi jak kółko i krzyżyk , szachy lub nieskończone szachy , lub gry z niedoskonałymi informacjami, takie jak poker .

Podstawowe pojęcia

Gry

Pierwszym rodzajem gry, który rozważymy, jest gra dwuosobowa z doskonałą informacją o długości ω , w której gracze grają w liczby naturalne . Te gry są często nazywane grami Gale-Stewart.

W tego rodzaju grze jest dwóch graczy, często nazywanych I i II , którzy na zmianę grają w liczby naturalne, a ja idę pierwszy. Grają „na zawsze”; to znaczy, że ich sztuki są indeksowane przez liczby naturalne. Kiedy skończą, z góry określony warunek decyduje o tym, który gracz wygra. Warunek ten nie musi być określony żadną definiowalną regułą ; może to być po prostu arbitralna (nieskończenie długa) tabela przeglądowa mówiąca, kto wygrał w określonej kolejności rozgrywek.

Bardziej formalnie, za podzbiór A w przestrzeń baire'a ; Przypomnijmy, że ta ostatnia składa się ze wszystkich ciągów liczb naturalnych. Następnie w grze G _A , że odgrywa liczbą naturalną ₀ , a następnie II odgrywa ₁ , a następnie , że odtwarza się ₂ , i tak dalej. Wtedy ja wygrywa tylko wtedy, gdy

{\ Displaystyle \ langle a_ {0}, a_ {1}, a_ {2}, \ ldots \ rangle \ w A}

w przeciwnym razie II wygrywa. A nazywa się wtedy zbiorem wypłat G _A .

Zakłada się, że każdy gracz widzi wszystkie ruchy poprzedzające każdy z jego ruchów, a także zna warunek wygranej.

Strategie

Nieformalnie strategia dla gracza to sposób gry, w którym jego zagrania są całkowicie zdeterminowane przez powyższe zagrania. Ponownie, taka „droga” nie musi być możliwa do przechwycenia przez jakąkolwiek dającą się wytłumaczyć „regułę”, ale może być po prostu tabelą przeglądową.

Bardziej formalnie, strategia dla gracza I (dla gry w rozumieniu poprzedniego podrozdziału) to funkcja, która przyjmuje jako argument dowolny skończony ciąg liczb naturalnych o parzystej długości i zwraca liczbę naturalną. Jeśli σ jest taką strategią, a <a ₀ ,...,a _2n-1 > jest ciągiem zagrań, to σ (<a ₀ ,...,a _2n-1 >) jest kolejnym zagraniem , które zrobię jeśli I jest następująca strategia Ď . Strategie dla II są takie same, zastępując „parzysty” „nieparzysty”.

Zauważ, że jak dotąd nie powiedzieliśmy nic o tym, czy strategia jest w jakikolwiek sposób dobra . Strategia może nakazać graczowi wykonywanie agresywnie złych ruchów i nadal będzie to strategia. W rzeczywistości nie trzeba nawet znać warunku wygranej gry, wiedzieć, jakie strategie istnieją w tej grze.

Zwycięskie strategie

Strategia wygrywa, jeśli podążający za nią gracz musi koniecznie wygrać, bez względu na to, co gra jego przeciwnik. Na przykład, jeśli σ jest strategią dla I , to σ jest strategią wygrywającą dla I w grze G _A jeśli dla dowolnego ciągu liczb naturalnych , który ma grać II , powiedzmy <a ₁ ,a ₃ ,a ₅ ,. ..>, sekwencja zagrań wytwarzanych przez σ, gdy II gra w ten sposób, czyli

{\ Displaystyle \ langle \ sigma ( \ langle \ rangle ), a_ {1} \ sigma ( \ langle \ sigma ( \ langle \ rangle ), a_ {1} \ rangle ), a_ {3} \ ldots \ rangle }

jest elementem A .

Zdeterminowane gry

Gra (klasa) gier jest określana, jeśli dla wszystkich instancji gry istnieje strategia wygrywająca dla jednego z graczy (niekoniecznie tego samego gracza w każdym przypadku). Zwróć uwagę, że nie może być zwycięskiej strategii dla obu graczy w tej samej grze, ponieważ gdyby tak było, obie strategie mogłyby być rozgrywane przeciwko sobie. Wynikający z tego wynik byłby wówczas, zgodnie z hipotezą, wygraną dla obu graczy, co jest niemożliwe.

Determinacja z elementarnych rozważań

Wszystkie skończone gry o doskonałej informacji, w których nie dochodzi do remisów, są określane.

Gry w świecie rzeczywistym z doskonałą informacją, takie jak kółko i krzyżyk , szachy lub nieskończone szachy , zawsze kończą się skończoną liczbą ruchów (w grach szachowych zakłada się zastosowanie zasady 50 ruchów). Jeśli taka gra zostanie zmodyfikowana w taki sposób, że dany gracz wygrywa w dowolnych warunkach, w których gra zostałaby nazwana remisem, to zawsze jest to rozstrzygane. Warunek, że gra zawsze się kończy (tzn. wszystkie możliwe rozszerzenia skończonej pozycji prowadzą do wygranej tego samego gracza) w skończonej liczbie ruchów odpowiada topologicznemu warunkowi, że zbiór A dający warunek wygranej dla G _A jest zamknięty w topologii w przestrzeni Baire'a .

Na przykład modyfikacja zasad gry w szachy, aby remisowe partie były wygraną dla czarnych, czyni z szachów grę zdeterminowaną. Tak się składa, że szachy mają skończoną liczbę pozycji i zasady remis po powtórzeniu, więc przy tych zmodyfikowanych zasadach, jeśli gra będzie trwała wystarczająco długo, a białe nie wygrały, to czarne mogą ostatecznie wymusić wygraną (ze względu na modyfikację remisu). = wygrana dla czarnych).

Dowód na to, że takie gry są zdeterminowane, jest dość prosty: Gracz I po prostu gra, żeby nie przegrać ; to znaczy gracz , którym gram, aby upewnić się, że gracz II nie ma zwycięskiej strategii po moim ruchu. Jeśli gracz, którego ja nie mogę tego zrobić, oznacza to, że gracz II od początku miał zwycięską strategię. Z drugiej strony, jeśli gracz I może grać w ten sposób, to ja musi wygrać, bo gra zostanie zakończona po jakiejś skończonej liczbie ruchów, a gracz I nie stracił w tym punkcie.

Ten dowód w rzeczywistości nie wymaga, aby gra zawsze kończyła się w skończonej liczbie ruchów, tylko, aby była skończona w skończonej liczbie ruchów za każdym razem, gdy II wygrywa. Warunek ten, topologicznie, jest taki, że zbiór A jest domknięty . Ten fakt, że wszystkie zamknięte gry są zdeterminowane, nazywa się twierdzeniem Gale-Stewarta . Zauważ, że symetria określa również wszystkie otwarte gry. (Gra jest otwarta, jeśli mogę wygrać tylko poprzez wygraną w skończonej liczbie ruchów.)

Determinacja z ZFC

David Gale i FM Stewart udowodnili, że otwarte i zamknięte mecze są zdeterminowane. Determinację dla drugiego poziomu gier hierarchii borelowskiej wykazał Wolfe w 1955 roku. W ciągu następnych 20 lat dodatkowe badania przy użyciu coraz bardziej skomplikowanych argumentów ustaliły, że określony jest trzeci i czwarty poziom hierarchii borelowskiej.

W 1975 roku Donald A. Martin udowodnił, że wszystkie gry Borel są zdeterminowane; to znaczy, jeśli A jest podzbiorem borelowskim przestrzeni Baire'a, to G _A jest określane. Ten wynik, znany jako wyznaczenie Borela , jest najlepszym możliwym wynikiem wyznaczenia, który można udowodnić w ZFC, w tym sensie, że wyznaczenie następnej wyższej klasy Wadge nie jest możliwe do udowodnienia w ZFC.

W 1971 roku, przed Martin uzyskał dowód, Harvey Friedman pokazał, że każdy dowód Borel gry nieskończone muszą używać aksjomat zastępowania w istotny sposób, aby iteracyjne aksjomat PowerSet transfinitely często. Praca Friedmana daje wynik poziom po poziomie szczegółowo, jak wiele iteracji aksjomatu powerset jest koniecznych do zagwarantowania determinacji na każdym poziomie hierarchii Borel .

Dla każdej liczby całkowitej n ZFC\P dowodzi determinacji na n- tym poziomie różnicowej hierarchii zbiorów, ale ZFC\P nie dowodzi, że dla każdej liczby całkowitej n n- ty poziom różnicowej hierarchii zbiorów jest określony. Zobacz matematykę odwrotną dla innych relacji między określalnością a podsystemami arytmetyki drugiego rzędu . $\mathbf {\pi} _{3}^{0}$ ${\ Displaystyle \ Pi _ {3} ^ {0}}$

Determinacja i wielcy kardynałowie

Istnieje bliski związek między determinacją a wielkimi kardynałami . Na ogół silniejsze duże aksjomaty kardynalne dowodzą determinacji większych klas punktowych , wyższych w hierarchii Wadge'a , a determinacja takich klas punktowych z kolei dowodzi istnienia wewnętrznych modeli nieco słabszych dużych aksjomatów kardynalnych niż te, które służą do udowodnienia determinacji pointclass w pierwszej kolejności.

Mierzalni kardynałowie

Z istnienia mierzalnego kardynała wynika, że każda gra analityczna (zwana też grą Σ ¹₁ ) jest zdeterminowana, lub równoważnie, że każda gra koanalityczna (lub Π ¹₁ ) jest zdeterminowana. (Zobacz Hierarchia rzutowania dla definicji).

Właściwie wymierny kardynał w zupełności wystarczy. Słabsza zasada — istnienie 0 ^# wystarcza do udowodnienia determinacji koanalitycznej i trochę więcej: Dokładny wynik jest taki, że istnienie 0 ^# jest równoważne determinacji wszystkich poziomów hierarchii różnic poniżej poziomu ω ² , tj. ω·n- Π ¹₁ wyznaczenie dla każdego . ${\ Displaystyle n}$

Od mierzalnego kardynała możemy to bardzo nieznacznie poprawić do ω ² - Π ¹₁ determinacji. Z istnienia bardziej mierzalnych kardynałów można wykazać determinację większej liczby poziomów hierarchii różnic nad Π ¹₁ .

Dowód determinacji z ostrych narzędzi

Dla każdej liczby rzeczywistej r , gry nieskończone jest równoznaczne z istnieniem r ^# . Aby zilustrować, jak wielcy kardynałowie prowadzą do determinacji, oto dowód determinacji przy istnieniu r ^# . ${\ Displaystyle \ Sigma _ {1} ^ {1} (r)}$ ${\ Displaystyle \ Sigma _ {1} ^ {1} (r)}$

Niech A będzie podzbiorem przestrzeni Baire'a. A = p[ T ] dla pewnego drzewa T (konstruktywnego z r ) na (ω, ω). (To jest x∈A jeśli od pewnego y , jest ścieżką przez T .) ${\ Displaystyle \ Sigma _ {1} ^ {1} (r)}$ $((x_{0},y_{0}),(x_{1},y_{1}),...)$

Mając daną grę częściową s , niech będzie poddrzewem T zgodnym z s z zastrzeżeniem max(y ₀ ,y ₁ ,...,y _len(s)-1 )<len(s). Dodatkowy warunek zapewnia, że jest skończony. Spójność oznacza, że każda ścieżka ma formę, w której jest początkowym segmentem s . $T_{s}$ $T_{s}$ $T_{s}$ $((x_{0},y_{0}),(x_{1},y_{1}),...(x_{i},y_{i}))$ $(x_{0},x_{1},...,x_{i})$

Aby udowodnić, że A jest określone, zdefiniuj grę pomocniczą w następujący sposób:
Oprócz zwykłych ruchów, gracz 2 musi rozegrać odwzorowanie na liczby porządkowe (poniżej odpowiednio dużej liczby porządkowej κ ) w taki sposób, że $T_{s}$

każdy nowy ruch rozszerza poprzednie mapowanie i
kolejność porządków zgadza się z rozkazem Kleene-Brouwer z dnia . $T_{s}$

Przypomnijmy, że porządek Kleene-Brouwera jest jak porządek leksykograficzny z tą różnicą, że jeśli s prawidłowo rozciąga t, to s < t . Jest to dobrze uporządkowane, jeśli drzewo jest dobrze ugruntowane.

Gra pomocnicza jest otwarta. Dowód: Jeżeli gracz 2 nie przegra na skończonym etapie, to zjednoczenie wszystkich (które jest drzewem odpowiadającym grze) jest dobrze ugruntowane, a zatem wynik gry niepomocniczej nie znajduje się w A. $T_{s}$

W ten sposób określa się grę pomocniczą. Dowód: Poprzez indukcję nieskończoną, dla każdej porządkowej α oblicz zbiór pozycji, w których gracz 1 może wymusić wygraną w krokach α, gdzie pozycja z ruchem gracza 2 przegrywa (dla gracza 2) w krokach α iff dla każdego ruchu wynik pozycja przegrywa w mniej niż krokach α. Jedną ze strategii dla gracza 1 jest zmniejszenie α z każdą pozycją (powiedzmy wybranie najmniejszego α i zerwanie remisu poprzez wybranie najmniejszego ruchu), a jedną strategią dla gracza 2 jest wybranie najmniejszego (właściwie każdy zadziała) ruchu, który nie prowadzi do pozycji z przypisanym α. Zauważ, że L ( r ) zawiera zestaw wygrywających pozycji, jak również zwycięskie strategie podane powyżej.

Zwycięska strategia dla gracza 2 w oryginalnej grze prowadzi do zwycięskiej strategii w grze pomocniczej: poddrzewo T odpowiadające zwycięskiej strategii jest dobrze ugruntowane, więc gracz 2 może wybrać liczby porządkowe na podstawie kolejności Kleene-Brouwer drzewa. Ponadto, trywialnie, strategia wygrywająca dla gracza 2 w grze pomocniczej daje strategię wygrywającą dla gracza 2 w grze oryginalnej.

Pozostaje wykazać, że przy użyciu r ^# wspomniana powyżej strategia wygrywająca dla gracza 1 w grze pomocniczej może zostać przekształcona w strategię wygrywającą w grze oryginalnej. r ^# daje odpowiednią klasę I ( L ( r ), ∈, r ) nieodróżnialnych liczb porządkowych. Przez nierozróżnialność, jeśli κ i liczby porządkowe w odpowiedzi pomocniczej są w I , to ruchy gracza 1 nie zależą od ruchów pomocniczych (lub na κ ), a więc strategię można przekształcić w strategię dla oryginalnej gry ( ponieważ gracz 2 może wytrzymać z nieodróżnialnymi dla dowolnej skończonej liczby kroków). Załóżmy, że gracz 1 przegrywa w oryginalnej grze. Wtedy drzewo odpowiadające sztuce jest dobrze ugruntowane. Dlatego gracz 2 może wygrać grę pomocniczą, używając ruchów pomocniczych opartych na nieodróżnialnych (ponieważ rodzaj kolejności elementów nieodróżnialnych przekracza porządek Kleene-Brouwer drzewa), co przeczy wygraniu gry pomocniczej przez gracza 1.

Kardynałowie Woodin

Jeśli istnieje kardynał Woodin z mierzalną kardynała nad nim, a następnie Π ¹₂ gry nieskończone trzyma. Mówiąc ogólnie, jeśli istnieją n Cardinals obróbki drewna z mierzalną Cardinal nad nimi całość, następnie Π ¹_{n + 1} gry nieskończone ładowni. Z determinacji Π ¹_n+1 wynika, że istnieje przechodni model wewnętrzny zawierający n kardynałów Woodina.

${\ Displaystyle \ Delta _ {2} ^ {1}}$ (jasna twarz) determinacja jest równoważna z kardynałem Woodin. Jeśli zachodzi wyznaczenie, to dla stożka Turinga x (to znaczy dla każdego rzeczywistego x o wystarczająco wysokim stopniu Turinga ), L[ x ] spełnia wyznaczenie OD (to znaczy wyznaczalność gier na liczbach całkowitych o długości ω i porządkowo-definiowalnej wypłacie) , aw HOD ^L[^x^] jest kardynałem Woodina. ${\ Displaystyle \ Delta _ {2} ^ {1}}$ ${\ Displaystyle \ omega _ {2} ^ {L [x]}}$

determinacja projekcyjna

Jeśli jest nieskończenie wielu kardynałów Woodina, to obowiązuje determinacja projekcyjna; oznacza to, że określana jest każda gra, której warunkiem wygranej jest zestaw projekcyjny . Z determinacji rzutowej wynika, że dla każdej liczby naturalnej n istnieje przechodni model wewnętrzny, który potwierdza, że istnieje n kardynałów Woodina.

Aksjomat determinacji

Aksjomat determinacji lub AD , twierdzi, że każdy gra dla dwóch graczy doskonałego informacji Ohm długości, w której gracze Naturals, jest ustalona.

AD jest dowodem na fałsz z ZFC; posługując się aksjomatem wyboru można udowodnić istnienie gry nieokreślonej. Jednakże, jeśli jest nieskończenie wielu kardynałów Woodina z mierzalną ponad nimi wszystkimi, to L(R) jest modelem ZF, który spełnia AD.

Konsekwencje determinacji

Własności regularności dla zbiorów liczb rzeczywistych

Jeżeli A jest takim podzbiorem przestrzeni Baire'a, że gra Banacha–Mazura dla A jest określona, to albo II ma strategię wygrywającą, w tym przypadku A jest ubogi , albo ja ma strategię wygrywającą, w którym to przypadku A jest komercyjny na niektórych otwarte sąsiedztwo.

Nie oznacza to do końca, że A ma własność Baire , ale jest blisko: prosta modyfikacja argumentu pokazuje, że jeśli Γ jest odpowiednią klasą punktową taką, że każda gra w Γ jest określona, to każdy zbiór liczb rzeczywistych w Γ ma własność Baire.

W rzeczywistości wynik ten nie jest optymalny; Rozważając rozwiniętą grę Banacha–Mazura, możemy pokazać, że wyznaczenie Γ (dla Γ o wystarczających własnościach domknięcia) implikuje, że każdy zbiór liczb rzeczywistych będący rzutem zbioru w Γ ma własność Baire'a. Tak więc na przykład istnienie mierzalnego kardynała implikuje determinację Π ¹₁ , co z kolei implikuje, że każdy zbiór liczb rzeczywistych Σ ¹₂ ma własność Baire'a.

Rozważając inne gry, możemy pokazać, że z determinacji Π ¹_n wynika, że każdy zbiór liczb rzeczywistych Σ ¹_{n +1} ma własność Baire'a, jest mierzalny przez Lebesgue'a (w rzeczywistości mierzalny powszechnie ) i ma własność zbioru doskonałego .

Twierdzenia o okresowości

Pierwszy okresowość twierdzenie zakłada, że dla każdej liczby naturalnej n , jeśli Δ ¹_{2 n +1} gry nieskończone trzyma, a następnie Π ¹_{2 n +1} i Σ ¹_{2 n +2} mają właściwość prewellordering (a Σ ¹_{2 n +1} i Π ¹_{2 n + 2} są nie mają własność prewellordering, ale ma właściwości rozdzielania ).
Sekund okresowość twierdzenie zakłada, że dla każdej liczby naturalnej n , jeśli hemibursztynianu ¹_{2 n +1} gry nieskończone trzyma, a następnie Π ¹_{2 n +1} i Σ ¹_{2 n} mają właściwość skalę . W szczególności, jeśli zachodzi determinacja projekcyjna, to każda relacja projekcyjna ma uniformizację projekcyjną .
Trzecie twierdzenie okresowość daje wystarczający warunek gra mieć definiowalny strategię wygrywającą.

Zastosowania do rozstrzygania niektórych teorii drugiego rzędu

W 1969 roku Michael O. Rabin udowodnił, że drugiego rzędu teoria z n następców jest rozstrzygalne . Kluczowy element dowodu wymaga wykazania determinacji gier parzystości , które leżą na trzecim poziomie hierarchii borelowskiej .

Determinacja kija

Wadge determinity to stwierdzenie, że dla wszystkich par A , B podzbiorów przestrzeni Baire'a wyznaczana jest gra Wadge G( A , B ). Podobnie dla klasy punktowej Γ, Γ Wyznaczalność Wadge'a jest stwierdzeniem, że dla wszystkich zbiorów A , B w Γ jest wyznaczona gra Wadge'a G( A , B ).

Wadge gry nieskończone implikuje semilinear zasady zamawiania dla porządku Wadge . Inną konsekwencją determinacji Wadge'a jest właściwość zbioru doskonałego .

Ogólnie, wyznaczenie Γ Wadge'a jest konsekwencją determinacji boolowskich kombinacji zbiorów w Γ. W rzutowej hierarchii , Π ¹₁ Wadge gry nieskończone odpowiada Õ ¹₁ gry nieskończone, o czym świadczy Leo Harrington . Wynik ten został przedłużony przez Hjorth, aby udowodnić, że Π ¹₂ Wadge gry nieskończone (aw rzeczywistości semilinear zasada zamawianie Õ ¹₂ ) już implikuje Π ¹₂ gry nieskończone.

Więcej ogólnych gier

Gry, w których grane obiekty nie są liczbami naturalnymi

Wyznaczenie gier na liczbach porządkowych z liczbą porządkową definiowalną wypłatą i długością ω implikuje, że dla każdej liczby regularnej κ >ω nie istnieją żadne porządkowe definiowalne rozłączne stacjonarne podzbiory κ utworzone z liczb porządkowych kofinalności ω. Siła spójności hipotezy determinacji jest nieznana, ale oczekuje się, że będzie bardzo wysoka.

Gry rozgrywane na drzewach

Długie gry

Istnienie kardynałów ω ₁ Woodina implikuje, że dla każdej przeliczalnej liczby porządkowej α wyznaczane są wszystkie gry na liczbach całkowitych o długości α i wypłacie rzutowej. Z grubsza rzecz biorąc, kardynałowie α Woodina odpowiadają determinacji gier na rzeczywistych długościach α (z prostym zbiorem wypłat). Zakładając limit kardynałów Woodina κ z o( κ )= κ ⁺⁺ i ω kardynałów Woodina powyżej κ , gry o zmiennej policzalnej długości, w których gra kończy się, gdy tylko jej długość jest dopuszczalna względem linii gry i z rzutową wypłatą są określony. Zakładając, że pewna hipoteza iterowalności jest dowodliwa, istnienie mierzalnego kardynała Woodina implikuje determinację otwartych gier o długości ω ₁ i wypłatę projekcyjną. (W tych grach warunek wygranej dla pierwszego gracza jest uruchamiany na etapie policzalnym, więc wypłata może być zakodowana jako zestaw reali).

W odniesieniu do limitu Woodina liczby kardynałów Woodina i mierzalnej powyżej nich, jest zgodne, że każda gra na liczbach całkowitych o długości ω ₁ i liczbie porządkowej definiowalnej wypłaty jest określana. Przypuszcza się, że hipoteza determinacji jest równoznaczna z granicą Woodina kardynałów Woodina. ω ₁ jest maksymalna w tym sensie, że istnieją nieoznaczone gry na liczbach całkowitych o długości ω ₁ + ω i wypłatach porządkowych definiowalnych.

Gry z niedoskonałymi informacjami

W każdej interesującej grze z niedoskonałymi informacjami strategia wygrywająca będzie strategią mieszaną , to znaczy da pewne prawdopodobieństwo różnych reakcji w tej samej sytuacji. Jeśli optymalne strategie obu graczy są strategiami mieszanymi, wynik gry nie może być z pewnością determinujący (tak jak w przypadku czystych strategii , ponieważ są one deterministyczne ). Ale można obliczyć rozkład prawdopodobieństwa wyników dla przeciwstawnych strategii mieszanych. Gra, która wymaga strategii mieszanych, jest definiowana jako określona, jeśli istnieje strategia, która zapewnia minimalną oczekiwaną wartość (poza możliwymi strategiami kontr), która przekracza daną wartość. Wbrew tej definicji wszystkie skończone gry dla dwóch graczy o sumie zerowej są wyraźnie określone. Jednak determinacja nieskończonych gier niedoskonałych informacji (gry Blackwell) jest mniej jasna.

W 1969 David Blackwell udowodnił, że pewne „nieskończone gry z niedoskonałą informacją” (obecnie nazywane „grami Blackwella”) są określone, a w 1998 Donald A. Martin udowodnił, że zwykła (doskonała gra informacyjna) determinacja dla klasy punktowej pogrubioną czcionką implikuje determinację Blackwella dla klasa punktów. To, w połączeniu z twierdzeniem Martina o wyznaczeniu Borela , sugeruje, że wszystkie gry Blackwella z funkcjami wypłaty Borela są zdeterminowane. Martin przypuszczał, że determinacja zwykła i determinacja Blackwella dla gier nieskończonych są równoważne w silnym sensie (tj. determinacja Blackwella dla klasy punktowej pogrubionej z kolei implikuje zwykłą determinację dla tej klasy punktowej), ale od 2010 roku nie udowodniono, że determinacja Blackwella implikuje determinacja w doskonałej grze informacyjnej.

Quasistrategie i quasideterminacyjność

Zobacz też

Przypisy

^ Zakłada to,żestaram się, aby skrzyżowanie odtwarzanych sąsiedztw było singletonem, którego unikalnym elementem jest elementA. Niektórzy autorzy stawiają na cel zamiast dla graczaII; zastosowanie wymaga odpowiedniej modyfikacji powyższych uwag.

Bibliografia

Gale, David i Stewart, FM (1953). Kuhn, HW; Tucker, AW (wyd.). Nieskończone gry z doskonałymi informacjami . Składki do teorii gier, tom II . Roczniki studiów matematycznych 28. Princeton University Press. s. 245-266. Numer ISBN 9780691079356.CS1 maint: wiele nazwisk: lista autorów ( link )
Harrington, Lew (styczeń 1978). „Wyznaczanie analityczne i 0 #”. Dziennik logiki symbolicznej . 43 (4): 685–693. doi : 10.2307/2273508 . JSTOR 2273508 .
Hjorth, Greg (styczeń 1996). " Π ¹₂ stopnie Wadge" . Roczniki logiki czystej i stosowanej . 77 : 53–74. doi : 10.1016/0168-0072(95)00011-9 .
Jech, Tomasz (2002). Teoria mnogości, wydanie trzecie tysiąclecie (poprawione i rozszerzone) . Skoczek. Numer ISBN 978-3-540-44085-7.
Martin, Donald A. (1975). „Determinacja borelowska”. Roczniki Matematyki . Druga seria. 102 (2): 363-371. doi : 10.2307/1971035 . JSTOR 1971035 .
Martin, Donald A. i John R. Steel (styczeń 1989). „Dowód determinacji projekcyjnej” . Dziennik Amerykańskiego Towarzystwa Matematycznego . 2 (1): 71–125. doi : 10.2307/1990913 . JSTOR 1990913 .
Moschovakis, Yiannis N. (1980). Opisowa teoria mnogości . Północna Holandia. Numer ISBN 978-0-444-70199-2.
Woodin, W. Hugh (1988). „Superkompaktowi kardynałowie, zbiory realne i słabo jednorodne drzewa” . Materiały Narodowej Akademii Nauk Stanów Zjednoczonych Ameryki . 85 (18): 6587–6591. Kod Bib : 1988PNAS...85.6587W . doi : 10.1073/pnas.85.18.6587 . PMC 282022 . PMID 16593979 .
Marcin, Donald A. (2003). „Prosty dowód, że determinacja implikuje mierzalność Lebesgue'a”. Rozdzierać. Sem. Mata. Uniw. Pol. Turyn . 61 (4): 393–399. ( PDF )
Wolfe, P. (1955). „Ścisła determinacja pewnych gier nieskończonych” . Pacific J. Matematyka . 5 (5): Suplement I: 841-847. doi : 10.2140/pjm.1955.5.841 .

Zewnętrzne linki

„Wielcy kardynałowie i determinacja” w Stanford Encyclopedia of Philosophy

Languages

In other projects