Determinare

În teoria mulțimilor , o ramură a matematicii , determinarea este studiul condițiilor care permit unuia dintre cei doi jucători dintr-un joc să aibă o strategie câștigătoare și consecințele existenței unei astfel de strategii.

Noțiuni de bază

Jocuri

Primul tip de jocuri pe care urmează să îl luăm în considerare este jocul cu doi jucători de informații perfecte și lungime ω , în care jucătorii joacă numere naturale .

În acest tip de joc luăm în considerare doi jucători, numiți adesea I și II , care joacă pe rând numerele naturale, începând cu I. Jocul durează pentru totdeauna; sau mai bine zis, pariurile jucătorilor sunt indexate cu numere naturale. Când jocul s-a terminat, o condiție prestabilită dictează ce jucător a câștigat. Această condiție nu trebuie neapărat să fie o regulă ; poate fi pur și simplu o listă (infinit de lungă) cu cine câștigă pentru fiecare secvență de joc.

Mai formal, putem considera un subset A al unui spațiu Baire ; ne amintim că aceasta din urmă constă din toate secvențele of ale numerelor naturale. In joc G _A, am alege un număr natural de la _0, atunci II alege o _1, atunci alege un _2, și așa mai departe. Am câștigă jocul dacă și numai dacă

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

{\ displaystyle \ langle a_ {0}, a_ {1}, a_ {2}, \ ldots \ rangle \ în A}

{\ displaystyle \ langle a_ {0}, a_ {1}, a_ {2}, \ ldots \ rangle \ în A}

altfel câștigă II . A se numește setul de recompense al lui G _A.

Se presupune că fiecare jucător poate vedea toate mișcările înainte de ale sale și că cunoaște condiția de câștig.

Strategii

În mod informal, o strategie pentru un jucător este un mod de a juca în care alegerile sale sunt total determinate de alegerile sale anterioare. Din nou, o astfel de strategie nu trebuie neapărat să respecte o „regulă”, poate fi pur și simplu o listă de alegeri.

Mai formal, o strategie pentru jucătorul I (pentru un joc așa cum s-a explicat în subsecțiunea anterioară) este o funcție care are ca argument secvențe finite de numere naturale, de lungime pare, și returnează un număr natural. Dacă σ este o astfel de strategie și <a ₀ ,…,a _2n-1> este o succesiune de piese, atunci σ (<a ₀ ,…,a _2n-1> ) este următoarea piesă pe care o voi face, dacă _urmez strategia σ. Strategiile pentru II sunt în esență aceleași, înlocuind „impar” cu „pare”.

Rețineți că încă nu am spus nimic despre momentul în care trebuie să ne gândim dacă o anumită strategie este bună . O strategie poate determina un jucător să joace mișcări proaste, dar rămâne o strategie. De fapt, nu este întotdeauna necesar să cunoaștem condiția de câștig pentru un joc, ci să știm ce strategii există pentru joc.

Strategii câștigătoare

Se spune că o strategie câștigă dacă jucătorul care o urmează va câștiga cu siguranță, indiferent de jocul adversarului. De exemplu, dacă σ este o strategie I, atunci σ este o strategie câștigătoare pentru joc în G _A dacă, pentru fiecare secvență de ,a <a naturale ₁ ₃ ₅ ,a ,...> alegere II, secvența Joaca $\langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle$ ${\ displaystyle \ langle \ sigma (\ langle \ rangle), a_ {1}, \ sigma (\ langle \ sigma (\ langle \ rangle), a_ {1} \ rangle), a_ {3}, \ ldots \ rangle }$ ${\ displaystyle \ langle \ sigma (\ langle \ rangle), a_ {1}, \ sigma (\ langle \ sigma (\ langle \ rangle), a_ {1} \ rangle), a_ {3}, \ ldots \ rangle }$ produs de σ, când II joacă astfel, este un element al lui A.

Jocuri determinate

Se spune că un joc (sau o clasă de jocuri) este stabilit dacă pentru fiecare situație de joc există o strategie câștigătoare pentru unul dintre jucători (nu neapărat aceeași pentru fiecare situație). Rețineți că nu putem avea o strategie câștigătoare pentru ambii jucători pentru același joc, dacă ar exista una, cele două strategii ar fi jucate de ambii unul împotriva celuilalt. Acest lucru ar duce ipotetic la o victorie pentru ambii jucători, ceea ce este imposibil.

Bibliografie

Gale, D. și FM Stewart, jocuri Infinite cu informații perfecte , în Ann. Matematica. Studii , vol. 28, 1953, pp. 245-266.
Harrington, Leo, Determinarea analitică și 0 # , în Jurnalul de logică simbolică , vol. 43, nr. 4, ianuarie, 1978, pp. 685–693, DOI : 10.2307 / 2273508 , JSTOR 2273508 .
Hjorth, Greg , Π ¹ ₂ grade Wadge , în Annals of Pure and Applied Logic , vol. 77, ianuarie, 1996, pp. 53-74.
Jech, Thomas, Teoria seturilor, ediția mileniului III (revizuită și extinsă) , Springer, 2002, ISBN 3-540-44085-2 .
Martin, Donald A., determinarea Borel , în Annals of Mathematics. A doua serie , vol. 102, nr. 2, 1975, pp. 363–371, DOI : 10.2307 / 1971035 .
Martin, Donald A. și John R. Steel, A Proof of Projective Determinacy , în Journal of the American Mathematical Society , vol. 2, nr. 1, ianuarie 1989, pp. 71-125, DOI : 10.2307 / 1990913 , JSTOR 1990913 .
Moschovakis, Yiannis N., Teoria descriptivă a seturilor, Olanda de Nord, 1980, ISBN 0-444-70199-0 .
Woodin, W. Hugh , cardinali supercompacti, seturi de reali și copaci slab omogeni , în Proceedings of the National Academy of Sciences din Statele Unite ale Americii , vol. 85, nr. 18, 1988, pp. 6587–6591, DOI : 10.1073 / pnas.85.18.6587 , PMC 282022 , PMID 16593979 .
Martin, Donald A., O dovadă simplă că determinarea implică măsurabilitatea Lebesgue , în Rend. Sem. Mat. Univ. Pol. Torino , vol. 61, nr. 4, 2003, pp. 393–399. ( PDF )
Wolfe, P., Determinarea strictă a anumitor jocuri infinite , în Pacific J. Math. , vol. 5, 1955, pp. Suplimentul I: 841–847.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică