Gry nieskończone

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Gra nieskończona – wyimaginowany proces, w którym dwie osoby podejmują szereg (zwykle naprzemiennych) wyborów ponumerowanych elementami pewnej nieskończonej liczby porządkowej. Po zakończeniu procesu pewne zadane z góry kryterium używane jest do rozstrzygnięcia, który z graczy odniósł zwycięstwo.

Język gier nieskończonych jest używany w szeregu dziedzin matematyki głównie dla opisu własności studiowanych obiektów. Większość zastosowań gier tego typu występuje w teorii mnogości i topologii.

Należy zauważyć, że samo pojęcie gry nieskończonej nie daje się w pełni sformalizować. W zastosowaniach jednak interesują nas strategie graczy, a te z kolei są po prostu funkcjami o własnościach, które można formalnie opisać w języku teorii mnogości.

[edytuj] Intuicje

Szachy są przykładem gry, w której mamy dwóch graczy (Biała i Czarny) wykonujących na przemian posunięcia. Możliwe posunięcia graczy są dokładnie opisane przez reguły gry. Z góry wiadomo też kiedy Biała wygrywa partię, a kiedy wygrywa jej oponent. Umówmy się, że zarówno pat jak i wieczny szach oznaczają wygraną Czarnego, oraz że partia nie zakończona do 10000 posunięcia również jest uznawana za wygraną przez Czarnego. Dla uproszczenia rozważań każdą pełną partię tej gry będziemy traktować jako ciąg 10000 posunięć (umawiając się, że jeśli na kroku $n$ jeden z graczy wygrywa, to dalsze posunięcia są nieistotne). Spróbujmy opisać co to znaczy że Biała ma doskonały przepis na grę (czyli strategię zwycięską). Taki przepis powinien brać jako daną wejściową historię partii do danego momentu reprezentowaną przez kolejne posunięcia $b_1,c_1,b_2,c_2,\ldots,b_n,c_n$ i w odpowiedzi podawać ruch Białej $b n + 1$ . Strategia dla Białej jest więc funkcją σ której dziedziną jest zbiór wszystkich możliwych częściowych partii parzystej długości $< 10000$ a wartościami są posunięcia dozwolone przez reguły gry. Strategia σ jest zwycięska dla Białej jeśli każda partia $\langle b_1,c_1,b_2,c_2,\ldots, b_{4999},c_{4999},b_{5000},c_{5000}\rangle$ spełniająca warunek

$b_n=\sigma(\langle b_1,c_1,\ldots,b_{n-1},c_{n-1}\rangle)$ dla wszystkich $n=1,\ldots,4999$

jest wygrana przez Białą. (O partiach spełniających powyższy warunek będziemy mówić, że są zgodne ze strategią σ.) Całkowicie analogicznie definiuje się strategie zwycieskie dla Czarnego.

Intrygującym pytaniem jest czy jeden z graczy ma strategię zwycięską i jaka ta strategia jest. Zwróćmy uwagę, że stwierdzenie "Biała ma strategię zwycięską" może być wyrażone w następujący sposób:

istnieje takie posunięcie Białej

b 1

, że dla każdego posunięcia Czarnego

c 1

, istnieje odpowiedż Białej

b 2

taka, że dla każdej odpowiedzi Czarnego

c 2

⋅ ⋅ ⋅ ⋅ ⋅ ⋅ istnieje odpowiedż Białej

b 5000

taka, że dla każdej odpowiedzi Czarnego

c 5000

Biała wygrała partię $\langle b_1,c_1,b_2,c_2,\ldots, b_{4999},c_{4999},b_{5000},c_{5000}\rangle$ .

Używając kwantyfikatorów możemy zapisać powyższe wyrażenie następująco:

$\Psi\equiv (\exists b_1)(\forall c_1)(\exists b_2)(\forall c_2)\ldots(\exists b_{5000})(\forall c_{5000})$ (Biała wygrała partię $\langle b_1,c_1,b_2,c_2,\ldots, b_{4999},c_{4999},b_{5000},c_{5000}\rangle$ ).

Ponieważ nasze reguły zostały tak ustalone, aby zawsze jeden z graczy wygrywał, możemy użyć praw De Morgana aby wykazać że zaprzeczenie zdania $Ψ$ to

$\neg\Psi\equiv (\forall b_1)(\exists c_1)(\forall b_2)(\exists c_2)\ldots(\forall b_{5000})(\exists c_{5000})$ (Czarny wygrał partię $\langle b_1,c_1,b_2,c_2,\ldots, b_{4999},c_{4999},b_{5000},c_{5000}\rangle$ ).

Zatem $\neg\Psi$ to stwierdzenie, że " Czarny ma strategię zwycięską". Możemy stąd wywnioskować, że jeden z graczy ma doskonały przepis na grę - tyle tylko że nie wiemy który. Możemy to uogólnić do stwierdzenia, że istnienie strategii zwycięskiej w grze skończonej jest wyrażalne przez zdanie zaczynające sie od skończonego ciągu naprzemiennych kwantyfikatorów i że zawsze jeden z graczy ma strategię zwycięską (o ile każda partia kończy się wygraną jednego z nich).

Schemat przedstawiony powyżej może być użyty do opisu gier nieskończonych. Na przykład, jeśli chcemy rozważać gry indeksowane liczbami naturalnymi, to możemy opisać je jako proces w którym gracze Biała i Czarny budują ciąg nieskończony

$\langle b_1,c_1,b_2,c_2,\ldots, b_{4999},c_{4999},b_{5000},c_{5000},b_{5001},c_{5001},\ldots b_n,c_n,\ldots\rangle$

którego wyrazy są wybierane po kolei w taki sposób, że $b n$ jest określone przez Białą (po tym jak już wybrano $b_1,c_1,b_2,c_2,\ldots, b_{n-1},c_{n-1}$ ) a $c n$ jest zadecydowane przez Czarnego w kolejnym posunięciu. Przy takim opisie musimy też podać regułę wygrywania, która może być opisana przez podanie zbioru A tych wszystkich ciągów nieskończonych które są "wygrane" przez Białą. Zwróćmy uwagę, że zbiór A może też zawierać w sobie opis szczególnych reguł gry - wystarczy wpisać w niego zasadę, że gracz który pierwszy złamie te reguły przegrywa. Pojęcia strategii i strategii zwycięskiej przenoszą się na przypadek takich gier naturalnie. Ważną różnicą jest jednak, że próbując zapisać zdanie " Biała ma strategię zwycięską" za pomocą kwantyfikatorów otrzymamy nieskończony ciąg naprzemiennych kwantyfikatorów. Nawet jeśli spróbujemy wprowadzić logikę pozwalającą na takie ciągi, prawa De Morgana nie będą stosowalne i istnienie strategii zwycięskiej dla jednego z graczy staje się poważnym (i interesującym) problemem.

W dalszej części tego artykułu będziemy używać powszechnie akceptowanej w teorii mnogości konwencji, że liczby naturalne to elementy pierwszej nieskończonej liczby porządkowej $\omega=\{0,1,2,3,4,5,\ldots\}$ .

[edytuj] Definicje

[edytuj] Gry długości ω o posunięciach z ustalonego zbioru

Niech ${\mathcal X}$ będzie zbiorem o przynajmniej dwóch elementach oraz niech $A\subseteq {\mathcal X}^\omega$ będzie zbiorem którego elementy są ciągami nieskończonymi $\eta=\langle\eta(n):n\in\omega\rangle$ o wyrazach w ${\mathcal X}$ (tzn $\eta(n)\in {\mathcal X}$ dla wszystkich liczb naturalnych $n\in\omega$ ). Określamy grę nieskończoną $\Game^{\mathcal X}(A)$ dwóch graczy, I i II, na zbiór A o posunięciach ze zbioru ${\mathcal X}$ jako proces w wyniku którego dwie osoby konstruują ciąg nieskończony $\eta=\langle\eta(n):n\in\omega\rangle\in {\mathcal X}^\omega$ o wyrazach w ${\mathcal X}$ w taki sposób, że po tym jak już $\eta\upharpoonright n=\langle\eta(k):k<n\rangle$ zostało wybrane, to

jeśli

n

jest parzyste, to gracz I wybiera

η(n)

, a

jeśli

n

jest nieparzyste, to gracz II wybiera

η(n)

Po wykonaniu wszystkich ω kroków, kiedy gracze zbudowali ciąg $\eta=\langle\eta(n):n\in\omega\rangle\in {\mathcal X}^\omega$ , powiemy że gracz I wygrał partię η jeśli $\eta\in A$ .

Strategia dla gracza I to funkcja σ której dziedziną jest zbiór wszystkich ciągów o parzystej długości i wyrazach w ${\mathcal X}$ i której wartości są elementami zbioru ${\mathcal X}$ ; tak więc $\sigma:\bigcup\limits_{k\in\omega} {\mathcal X}^{2k}\longrightarrow {\mathcal X}$ . Powiemy, że ciąg $\eta\in {\mathcal X}^\omega$ jest zgodny ze strategią σ jeśli $(\forall k\in\omega)(\eta(2k)=\sigma(\eta\upharpoonright 2k))$ . Strategia σ dla gracza I jest strategią zwycięską gracza I w $\Game^{\mathcal X}(A)$ jeśli każdy ciąg η zgodny z σ należy do zbioru A.

Strategia dla gracza II to funkcja τ której dziedziną jest zbiór wszystkich ciągów o nieparzystej długości i wyrazach w ${\mathcal X}$ i której wartości są elementami zbioru ${\mathcal X}$ ; tak więc $\tau:\bigcup\limits_{k\in\omega} {\mathcal X}^{2k+1}\longrightarrow {\mathcal X}$ . Powiemy, że ciąg $\eta\in {\mathcal X}^\omega$ jest zgodny ze strategią τ jeśli $(\forall k\in\omega)(\eta(2k+1)=\tau(\eta\upharpoonright (2k+1)))$ . Strategia τ dla gracza II jest strategią zwycięską gracza II w $\Game^{\mathcal X}(A)$ jeśli żaden ciąg η zgodny z τ nie należy do zbioru A.

Powiemy że gra $\Game^{\mathcal X}(A)$ jest zdeterminowana jeśli jeden z graczy ma strategię zwycięską.

[edytuj] Bardziej skomplikowane gry długości ω

W zasadzie większość gier nieskończonych (nawet tych z bardzo skomplikowanymi regułami) można zinterpretować w języku przedstawionym powyżej. Wystarczy dobrać zbiór ${\mathcal X}$ tak aby był on odpowiednio "duży" a reguły gry zakodować w odpowiednim doborze zbioru A (trzymając konwencję że gracz który pierwszy złamie reguły przegrywa). Często jednak jest wygodnym użyć opisu gier przy pomocy drzew (porównaj np z artykułem Donalda Martina^[1]).

Niech ${\mathcal T}$ będzie zbiorem którego elementami są ciągi skończone i takim że

$\langle\rangle\in {\mathcal T}$ ,
jeśli $\nu\in {\mathcal T}$ jest ciągiem długości $lh(ν) = n$ oraz $k < n$ , to $\nu\upharpoonright k\in {\mathcal T}$ ,
dla każdego ciągu $\nu\in {\mathcal T}$ długości $lh(ν) = n$ istnieje ciąg $\rho\in {\mathcal T}$ długości $lh(ρ) = n + 1$ który wydłuża ν.

Połóżmy $[{\mathcal T}]=\{\eta:\eta$ jest ciągiem nieskończonym takim że $(\forall n\in \omega)(\eta\upharpoonright n\in {\mathcal T})\}$ . Niech $A\subseteq [T]$ . Określamy grę nieskończoną $\Game_{\mathcal T}(A)$ dwóch graczy, I i II, na zbiór A o posunięciach w drzewie ${\mathcal T}$ jako proces w wyniku którego dwie osoby konstruują ciąg nieskończony $\eta\in [{\mathcal T}]$ w taki sposób, że po tym jak już $\eta\upharpoonright n=\langle\eta(k):k<n\rangle\in {\mathcal T}$ zostało wybrane, to

jeśli

n

jest parzyste, to gracz I wybiera

η(n)

tak że $\langle\eta(k):k\leq n\rangle\in {\mathcal T}$ , a

jeśli

n

jest nieparzyste, to gracz II wybiera

η(n)

tak aby $\langle\eta(k):k\leq n\rangle\in {\mathcal T}$ .

Po wykonaniu wszystkich ω kroków, kiedy gracze zbudowali ciąg $\eta\in [{\mathcal T}]$ , powiemy że gracz I wygrał partię η jeśli $\eta\in A$ .

Pojęcia strategii, strategii zwycięskiej i zdeterminowania gry wprowadza się analogicznie do przedstawionych wcześniej.

[edytuj] Gry długości pozaskończonej

Rozważa się również gry długości większej niż ω. W takim przypadku często wprowadza się dodatkowy parametr S który opisuje które posunięcia są wykonywane przez gracza I (pozostałe wybory są dokonywane przez gracza II).

Niech α będzie nieskończoną liczbą porządkową oraz $S\subseteq\alpha$ . Niech ${\mathcal X}$ będzie zbiorem o przynajmniej dwóch elementach oraz niech $A\subseteq {\mathcal X}^\alpha$ . Określamy grę długości α $\Game^{\mathcal X}_\alpha(A)$ dwóch graczy, I i II, na zbiór A o posunięciach ze zbioru ${\mathcal X}$ jako proces w wyniku którego dwie osoby konstruują pozaskończony ciąg $\eta=\langle\eta(\beta):\beta<\alpha\rangle\in {\mathcal X}^\alpha$ o wyrazach w ${\mathcal X}$ w taki sposób, że po tym jak już $\eta\upharpoonright \beta=\langle\eta(\gamma):\gamma<\beta\rangle$ zostało wybrane, to

jeśli $\beta\in S$ , to gracz I wybiera

η(β)

, a

jeśli $\beta\in\alpha\setminus S$ , to gracz II wybiera

η(β)

Po wykonaniu wszystkich α kroków, kiedy gracze zbudowali ciąg $\eta=\langle\eta(\beta):\beta<\alpha\rangle\in {\mathcal X}^\alpha$ , powiemy że gracz I wygrał partię η jeśli $\eta\in A$ .

Pojęcia strategii, strategii zwycięskiej i zdeterminowania gry wprowadza się analogicznie do przedstawionych wcześniej.

[edytuj] Przykłady

Wszystkie przykłady gier podane poniżej mogą być przedstawione tak, że będą one pasować do ogólnych definicji przedstawionych powyżej. Ponieważ opis gier staje się wtedy bardziej skomplikowany, zadanie takiego przedstawienia pozostawiamy czytelnikowi.

[edytuj] Gra Banacha-Mazura

Pierwsza gra nieskończona była opisana w 1930 przez polskiego matematyka Stanisława Mazura w Problemie 43 w Księdze Szkockiej. Niech $Z\subseteq {\mathbb R}$ . Rozważmy następującą grę $\Game^{\rm BM}(Z)$ dwóch graczy, których nazwiemy Graczem A i Graczem B. Gra składa się z nieskończenie wielu posunięć ponumerowanych liczbami naturalnymi $n=1,2,3,\ldots$ . Oponenci zaczynają w ten sposób, że Gracz A wybiera niepusty przedział otwarty $I 1$ a Gracz B odpowiada przez wskazanie niepustego otwartego przedziału $I_2\subseteq I_1$ . Kiedy gracze dochodzą do $n$ tego kroku w grze, to mają oni skontruowany zstępujący ciąg niepustych przedziałów otwartych $I_1\supseteq I_2\supseteq \ldots I_{2n-2}\supseteq I_{2n-1}$ . Na $n$ tym etapie gry najpierw Gracz A wybiera niepusty przedział otwarty $I_{2n}\subseteq I_{2n-1}$ , a potem Gracz B wskazuje niepusty otwarty przedział $I_{2n+1}\subseteq I_{2n}$ .

Kiedy gracze wykonają już wszystkie posunięcia (jest ich nieskończenie wiele!) , to decydujemy że Gracz B wygrał partię $\langle I_n:n=1,2,3,4,\ldots\rangle$ wtedy i tylko wtedy gdy $\bigcap\limits_{n=1}^\infty I_n\subseteq Z$ .

Mazur pytał się kiedy istnieją strategie zwycięskie w tej grze. Odpowiedź na pytanie Mazura była dana przez Stefana Banacha w 1935. Okazuje się, że Gracz B ma strategię zwycięską w grze $\Game^{\rm BM}(Z)$ wtedy i tylko wtedy gdy ${\mathbb R}\setminus Z$ jest zbiorem pierwszej kategorii.

[edytuj] Gra Davisa

Morton Davis^[2] rozważał następującą grę $\Game_D(A)$ .

Przypuśćmy, że $A\subseteq 2^\omega=\{0,1\}^\omega$ . Definiujemy grę $\Game_D(A)$ długości ω pomiędzy graczami I i II w sposób następujący. Najpierw gracz I wybiera skończony ciąg $ν 0$ o wartościach w ${0,1}$ , poczem gracz II odpowiada przez wybór jednej liczby $k_0\in \{0,1\}$ . Ogólniej, na kroku $n\in\omega$ tej gry, najpierw gracz I wybiera ciąg skończony $ν n$ o wartościach w ${0,1}$ , a potem gracz II decyduje wartość $k_n\in \{0,1\}$ . Po ω krokach gra jest zakończona a gracze skonstruowali ciąg $\langle\nu_n,k_n:n\in\omega\rangle$ . Decydujemy, że gracz I wygrał tę partię wtedy i tylko wtedy gdy

$\nu_0^\frown\langle k_0\rangle^\frown\nu_1^\frown\langle k_1\rangle^\frown\ldots \nu_n^\frown\langle k_n\rangle^\frown\ldots\in A.$

Okazuje się, że gracz I ma strategię zwycięską w $\Game_D(A)$ wtedy i tylko wtedy, gdy zbiór A zawiera podzbiór doskonały. Natomiast gracz II ma strategię zwycięską w $\Game_D(A)$ wtedy i tylko wtedy, gdy zbiór A jest przeliczalny.

[edytuj] Strategiczna domkniętość

Niech ${\mathbb P}=({\mathbb P},\leq)$ będzie pojęciem forsingu oraz niech λ będzie regularną liczbą kardynalną. Definijemy następującą grę $\Game_\lambda^{\mathbb P}$ długości λ pomiędzy graczami I i II. W czasie gry gracze budują ciąg $\langle p_\alpha,q_\alpha:\alpha<\lambda\rangle\subseteq {\mathbb P}$ tak, że na kroku $α < λ$ :

najpierw gracz I wybiera warunek $p_\alpha\in {\mathbb P}$ taki że

jeśli ciąg $\langle p_\beta,q_\beta:\beta<\alpha\rangle$ ma ograniczenie dolne, to $(\forall\beta<\alpha)(p_\beta\geq p_\alpha\ \wedge q_\beta\geq p_\alpha)$ ,

a potem gracz II wybiera warunek $q_\alpha\leq p_\alpha$ .

Po skończonej partii, gdy gracze skonstruowali ciąg $\langle p_\alpha,q_\alpha:\alpha<\lambda\rangle$ decydujemy że gracz II wygrał tę partię wtedy i tylko wtedy gdy ciąg ten jest malejący (tzn gdy $(\forall\beta<\alpha<\lambda)(p_\beta\geq q_\beta\geq p_\alpha\geq q_\alpha)$ ).

Mówimy, że pojęcię forsingu ${\mathbb P}$ jest $( < λ)$ -strategicznie domknięte jeśli gracz II ma strategię zwycięską w grze $\Game_\lambda^{\mathbb P}$ . Ta własność pojęć forsingu jest dość ważna w teorii forsingu jako, że

$( < λ)$ -strategicznie domknięte pojęcia forsingu nie kolapsują liczb kardynalnych $\leq\lambda$ , oraz
iteracje z nośnikami mocy λ pojęć forsingu które są $( < λ)$ -strategicznie domknięte są $( < λ)$ -strategicznie domknięte.

[edytuj] Determinacja

Aksjomaty determinacji to postulaty, że pewne gry nieskończone są zdeterminowane. Najbardziej popularnym aksjomatem tej postaci jest zdanie AD orzekające, że dla każdego zbioru $A\subseteq \omega^\omega$ gra $\Game^\omega(A)$ jest zdeterminowana.

Aksjomaty determinacji były rozważane po raz pierwszy przez polskich matematyków Jana Mycielskiego i Hugo Steinhuasa ^[3] i były one intensywnie studiowane na początku lat 60. XX wieku przez Mycielskiego i Stanisława Świerczkowskiego^[4]^[5]^[6]. W latach 90. XX wieku w wyniku szeregu spektakularnych rezultatów amerykańskiego matematyka Hugh Woodina znacznie wzrosło zainteresowanie aksjomatami tego typu^[7].

Dla głebszego rozwinięcia tego tematu odsyłamy czytelnika do hasła o aksjomatach determinacji. Zauważmy tylko jeszcze, że jeśli $A\subseteq \omega^\omega$ jest zbiorem borelowskim, to gra $\Game^\omega(A)$ jest zdeterminowana^[8]. Jeśli istnieje liczba mierzalna, oraz $A\subseteq \omega^\omega$ jest zbiorem analitycznym, to gra $\Game^\omega(A)$ jest zdeterminowana^[9]. Przy założeniu istnienia znacznie większych dużych liczb kardynalnych można wykazać, że gry na zbiory z wyższych klas rzutowych też są zdeterminowane^[10]^[11].

[edytuj] Bibliografia

↑ Martin, Donald A.: A purely inductive proof of Borel determinacy. "Recursion theory (Ithaca, N.Y., 1982)", Proc. Sympos. Pure Math., 42 (1985). s. 303-308.
↑ Davis, Morton: Infinite games of perfect information. "Advances in game theory", Princeton Univ. Press, Princeton, N.J, 1964. s. 85-101
↑ Mycielski, Jan; Steinhaus, H.: A mathematical axiom contradicting the axiom of choice. "Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys." 10 (1962), s. 1-3
↑ Mycielski, Jan i Świerczkowski, Stanisław: On the Lebesgue measurability and the axiom of determinateness. "Fundamenta Mathematicae". 54 (1964), s. 67-71.
↑ Mycielski, Jan: On the axiom of determinateness. "Fundamenta Mathematicae" 53 (1963/1964), s. 205-224.
↑ Mycielski, Jan: On the axiom of determinateness. II. "Fundamenta Mathematicae" 59 (1966), s. 203-212
↑ Woodin, W. Hugh: The axiom of determinacy, forcing axioms, and the nonstationary ideal. "de Gruyter Series in Logic and its Applications", 1. Walter de Gruyter & Co., Berlin, 1999. ISBN 3-11-015708-X
↑ Martin, Donald A.: Borel determinacy. "Ann. of Math." (2) 102 (1975), nr 2, s. 363-371.
↑ Martin, Donald A.: Measurable cardinals and analytic games. "Fund. Math." 66 (1969/1970), s. 287-291.
↑ Woodin, W. Hugh: Supercompact cardinals, sets of reals, and weakly homogeneous trees. "Proc. Nat. Acad. Sci. U.S.A." 85 (1988), s. 6587-6591.
↑ Martin, Donald A., Steel, John R.: A proof of projective determinacy. "J. Amer. Math. Soc." 2 (1989), s. 1, 71-125.

[edytuj] Zobacz też

przegląd zagadnień z zakresu matematyki,
teoria mnogości,
opisowa teoria mnogości,
aksjomat determinacji,
duże liczby kardynalne

Źródło: "http://pl.wikipedia.org../../../g/r/y/Gry_niesko%C5%84czone.html"

Kategoria: Teoria mnogości

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Gry nieskończone

Z Wikipedii

Spis treści

[edytuj] Intuicje

[edytuj] Definicje

[edytuj] Gry długości ω o posunięciach z ustalonego zbioru

[edytuj] Bardziej skomplikowane gry długości ω

[edytuj] Gry długości pozaskończonej

[edytuj] Przykłady

[edytuj] Gra Banacha-Mazura

[edytuj] Gra Davisa

[edytuj] Strategiczna domkniętość

[edytuj] Determinacja

[edytuj] Bibliografia

[edytuj] Zobacz też

Views

nawigacja

techniczne

zmiany

Szukaj

W innych językach