Gry nieskończone

matematyczny opis ponumerowanych wyborów

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.

DefinicjeEdytuj

Gry długości   o posunięciach z ustalonego zbioruEdytuj

Niech   będzie zbiorem o przynajmniej dwóch elementach oraz niech   będzie zbiorem, którego elementy są ciągami nieskończonymi   o wyrazach w   (tzn.   dla wszystkich liczb naturalnych  ). Określamy grę nieskończoną   dwóch graczy, I i II, na zbiór   o posunięciach ze zbioru   jako proces, w wyniku którego dwie osoby konstruują ciąg nieskończony   o wyrazach w   w taki sposób, że po tym, jak już   zostało wybrane, to

  • jeśli   jest parzyste, to gracz I wybiera  
  • jeśli   jest nieparzyste, to gracz II wybiera  

Po wykonaniu wszystkich   kroków, kiedy gracze zbudowali ciąg   powiemy, że gracz I wygrał partię  , jeśli  

Strategia dla gracza I to funkcja   której dziedziną jest zbiór wszystkich ciągów o parzystej długości i wyrazach w   i której wartości są elementami zbioru   tak więc   Powiemy, że ciąg   jest zgodny ze strategią  , jeśli   Strategia   dla gracza I jest strategią zwycięską gracza I w  , jeśli każdy ciąg   zgodny z   należy do zbioru  

Strategia dla gracza II to funkcja   której dziedziną jest zbiór wszystkich ciągów o nieparzystej długości i wyrazach w   i której wartości są elementami zbioru   tak więc   Powiemy, że ciąg   jest zgodny ze strategią  , jeśli   Strategia   dla gracza II jest strategią zwycięską gracza II w  , jeśli żaden ciąg   zgodny z   nie należy do zbioru  

Powiemy, że gra   jest zdeterminowana, jeśli jeden z graczy ma strategię zwycięską.

Bardziej skomplikowane gry długości  Edytuj

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   tak aby był on odpowiednio „duży”, a reguły gry zakodować w odpowiednim doborze zbioru   (utrzymując konwencję, że gracz który pierwszy złamie reguły przegrywa). Często jednak jest wygodnym użyć opisu gier za pomocą drzew (porównaj np. z artykułem Donalda Martina[1]).

Niech   będzie zbiorem, którego elementami są ciągi skończone i takim, że

  •  
  • jeśli   jest ciągiem długości   oraz   to  
  • dla każdego ciągu   długości   istnieje ciąg   długości   który wydłuża  

Połóżmy   jest ciągiem nieskończonym takim że   Niech   Określamy grę nieskończoną   dwóch graczy, I i II, na zbiór   o posunięciach w drzewie   jako proces w wyniku którego dwie osoby konstruują ciąg nieskończony   w taki sposób, że po tym jak już   zostało wybrane, to

  • jeśli   jest parzyste, to gracz I wybiera   tak że  
  • jeśli   jest nieparzyste, to gracz II wybiera   tak aby  

Po wykonaniu wszystkich   kroków, kiedy gracze zbudowali ciąg   powiemy, że gracz I wygrał partię   jeśli  

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

Gry długości pozaskończonejEdytuj

Rozważa się również gry długości większej niż   W takim przypadku często wprowadza się dodatkowy parametr   opisujący, 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   Niech   będzie zbiorem o przynajmniej dwóch elementach oraz niech   Określamy grę długości     dwóch graczy, I i II, na zbiór   o posunięciach ze zbioru   jako proces, w wyniku którego dwie osoby konstruują pozaskończony ciąg   o wyrazach w   w taki sposób, że po tym jak już   zostało wybrane, to:

jeśli   to gracz I wybiera   a
jeśli   to gracz II wybiera  

Po wykonaniu wszystkich   kroków, kiedy gracze zbudowali ciąg   powiemy, że gracz I wygrał partię  , jeśli  

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

PrzykładyEdytuj

Wszystkie przykłady gier podane poniżej mogą być przedstawione tak, że będą one pasować do ogólnych definicji przedstawionych powyżej.

Szachy są przykładem gry, w której dwóch graczy (Biała i Czarny) wykonuje 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   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   i w odpowiedzi podawać ruch Białej   Strategia dla Białej jest więc funkcją   której dziedziną jest zbiór wszystkich możliwych częściowych partii parzystej długości   a wartościami są posunięcia dozwolone przez reguły gry. Strategia   jest zwycięska dla Białej jeśli każda partia   spełniająca warunek

  dla wszystkich  

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 zwycięskie 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   że dla każdego posunięcia Czarnego   istnieje odpowiedź Białej   taka, że dla każdej odpowiedzi Czarnego   ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ istnieje odpowiedź Białej   taka, że dla każdej odpowiedzi Czarnego   Biała wygrała partię  

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

  (Biała wygrała partię  ).

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

  (Czarny wygrał partię  ).

Zatem   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 się od skończonego ciągu naprzemiennych kwantyfikatorów i że zawsze jeden z graczy ma strategię zwycięską (jeżeli 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

 

którego wyrazy są wybierane po kolei w taki sposób, że   jest określone przez Białą (po tym, jak już wybrano  ) a   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   tych wszystkich ciągów nieskończonych, które są „wygrane” przez Białą. Zbiór   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 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.

Gra Banacha-MazuraEdytuj

Pierwsza gra nieskończona była opisana w 1930 przez polskiego matematyka Stanisława Mazura w Problemie 43 w Księdze Szkockiej. Niech   Rozważmy następującą grę   dwóch graczy, których nazwiemy Graczem A i Graczem B. Gra składa się z nieskończenie wielu posunięć ponumerowanych liczbami naturalnymi   Oponenci zaczynają w ten sposób, że Gracz A wybiera niepusty przedział otwarty   a Gracz B odpowiada przez wskazanie niepustego otwartego przedziału   Kiedy gracze dochodzą do  -tego kroku w grze, to mają skontruowany zstępujący ciąg niepustych przedziałów otwartych   Na   tym etapie gry najpierw Gracz A wybiera niepusty przedział otwarty   a potem Gracz B wskazuje niepusty otwarty przedział  

Kiedy gracze wykonają już wszystkie posunięcia (jest ich nieskończenie wiele!), to decydujemy, że Gracz B wygrał partię   wtedy i tylko wtedy, gdy  

Mazur pytał, kiedy istnieją strategie zwycięskie w tej grze. Odpowiedź na to pytanie była dana przez Stefana Banacha w 1935. Okazuje się, że Gracz B ma strategię zwycięską w grze   wtedy i tylko wtedy, gdy   jest zbiorem pierwszej kategorii.

Gra DavisaEdytuj

Morton Davis[2] rozważał następującą grę  

Przypuśćmy, że   Definiujemy grę   długości   pomiędzy graczami I i II w sposób następujący: najpierw gracz I wybiera skończony ciąg   o wartościach w   potem gracz II odpowiada przez wybór jednej liczby   Ogólniej: na kroku   tej gry, najpierw gracz I wybiera ciąg skończony   o wartościach w   a potem gracz II decyduje wartość   Po   krokach gra jest zakończona, a gracze skonstruowali ciąg   Decydujemy, że gracz I wygrał tę partię wtedy i tylko wtedy, gdy

 

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

Strategiczna domkniętośćEdytuj

Niech   będzie pojęciem forsingu oraz niech λ będzie regularną liczbą kardynalną. Definiujemy następującą grę   długości λ pomiędzy graczami I i II. W czasie gry gracze budują ciąg   tak, że na kroku  

najpierw gracz I wybiera warunek   taki że
jeśli ciąg   ma ograniczenie dolne, to  
a potem gracz II wybiera warunek  

Po skończonej partii, gdy gracze skonstruowali ciąg   decydujemy, że gracz II wygrał tę partię wtedy i tylko wtedy, gdy ciąg ten jest malejący (tzn. gdy  ).

Mówimy, że pojęcie forsingu   jest  -strategicznie domknięte, jeśli gracz II ma strategię zwycięską w grze   Ta własność pojęć forsingu jest dość ważna w teorii forsingu, jako że

  •  -strategicznie domknięte pojęcia forsingu nie kolapsują liczb kardynalnych   oraz
  • iteracje z nośnikami mocy   pojęć forsingu, które są  -strategicznie domknięte są  -strategicznie domknięte.

DeterminacjaEdytuj

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   gra   jest zdeterminowana.

Aksjomaty determinacji były rozważane po raz pierwszy przez polskich matematyków Jana Mycielskiego i Hugo Steinhausa[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łębszego rozwinięcia tego tematu odsyłamy czytelnika do hasła o aksjomatach determinacji. Zauważmy tylko jeszcze, że jeśli   jest zbiorem borelowskim, to gra   jest zdeterminowana[8]. Jeśli istnieje liczba mierzalna oraz   jest zbiorem analitycznym, to gra   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].

Zobacz teżEdytuj

PrzypisyEdytuj

  1. 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.
  2. Davis, Morton: Infinite games of perfect information. „Advances in game theory”, Princeton Univ. Press, Princeton, N.J, 1964. s. 85–101.
  3. 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.
  4. Mycielski, Jan i Świerczkowski, Stanisław: On the Lebesgue measurability and the axiom of determinateness. „Fundamenta Mathematicae”. 54 (1964), s. 67–71.
  5. Mycielski, Jan: On the axiom of determinateness. „Fundamenta Mathematicae” 53 (1963/1964), s. 205–224.
  6. Mycielski, Jan: On the axiom of determinateness. II. „Fundamenta Mathematicae” 59 (1966), s. 203–212.
  7. 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​.
  8. Martin, Donald A.: Borel determinacy. „Ann. of Math.” (2) 102 (1975), nr 2, s. 363–371.
  9. Martin, Donald A.: Measurable cardinals and analytic games. „Fund. Math.” 66 (1969/1970), s. 287–291.
  10. Woodin, W. Hugh: Supercompact cardinals, sets of reals, and weakly homogeneous trees. „Proc. Nat. Acad. Sci. U.S.A.” 85 (1988), s. 6587–6591.
  11. Martin, Donald A., Steel, John R.: A proof of projective determinacy. „J. Amer. Math. Soc.” 2 (1989), s. 1, 71–125.