Determinatezza

In teoria degli insiemi, una branca della matematica, la determinatezza è lo studio delle condizioni che permettono ad uno dei due giocatori di un gioco di avere una strategia vincente, e delle conseguenze dell'esistenza di tale strategia.

Nozioni di base

Giochi

Il primo tipo di giochi che andiamo a considerare è il gioco a due giocatori di informazione perfetta e lunghezza ω, nel quale i giocatori giocano numeri naturali.

In questo tipo di gioco consideriamo due giocatori, spesso chiamati I e II, che si alternano giocando numeri naturali, con I che inizia. Il gioco dura per sempre; o meglio, le giocate dei giocatori sono indicizzate dai numeri naturali. Quando il gioco è finito, una condizione predeterminata sancisce quale giocatore ha vinto. Questa condizione non deve essere necessariamente una regola; può semplicemente essere una lista (infinitamente lunga) che dice chi vince per ogni sequenza di gioco.

Più formalmente, possiamo considerare un sottoinsieme A di uno Spazio di Baire; ricordiamo che quest'ultimo consiste di tutte le ω-sequenze di numeri naturali. Nel gioco G_A, I sceglie un numero naturale a₀, poi II sceglie a₁, poi I sceglie a₂, e così via. I vince il gioco se e solo se

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

altrimenti II vince. A è chiamato il payoff set di G_A.

Si assume che ogni giocatore possa vedere tutte le mosse precedenti alle sue, e che conosca la condizione vincente.

Strategie

Informalmente, una strategia per un giocatore è un modo di giocare nel quale le sue scelte sono totalmente determinate dalle scelte precedenti. Di nuovo, tale strategia non deve essere necessariamente seguire una "regola", ma può semplicemente essere una lista di scelte.

Più formalmente una strategia per il giocatore I (per un gioco come spiegato nella precedente sottosezione) è una funzione che ha come argomento sequenze finite di numeri naturali, di lunghezza pari, e restituisce un numero naturale. Se σ è una tale strategia e <a₀,…,a_2n-1> è una sequenza di giocate, allora σ(<a₀,…,a_2n-1>) è la prossima giocata che I farà, se sta seguendo la strategia σ. Strategie per II sono sostanzialmente le stesse, sostituendo "dispari" al posto di "pari".

Notare che non abbiamo detto nulla, ancora, riguardo a quando considerare se una data strategia sia da considerare buona. Una strategia può indurre un giocatore a giocare mosse cattive, ma rimane una strategia. Di fatto non è necessario sempre conoscere la condizione vincente per un gioco, ma sapere quali strategie esistono per il gioco.

Strategie vincenti

Una strategia si dice vincente se il giocatore che la segue vincerà sicuramente, qualunque siano le giocate dell'avversario. Per esempio se σ è una strategia per I, allora σ è una strategia vincente per I nel gioco G_A se, per ogni sequenza di naturali <a₁,a₃,a₅,…> scelta da II, la sequenza di giocate $\langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle$ prodotte da σ, quando II gioca così, è un elemento di A.

Giochi determinati

Un gioco (o una classe di giochi) è detto determinato se per ogni situazione di gioco esiste una strategia vincente per uno dei giocatori(non necessariamente lo stesso per ogni situazione). Notare che non possiamo avere una strategia vincente per entrambi i giocatori per lo stesso gioco, se ci fosse, le due strategie verrebbero giocate da entrambi l'uno contro l'altro. Ne risulterebbe, per ipotesi, una vittoria per entrambi i giocatori, che è impossibile.

Bibliografia

• Gale, D. and F. M. Stewart, Infinite games with perfect information, in Ann. Math. Studies, vol. 28, 1953, pp. 245–266.
• Harrington, Leo, Analytic determinacy and 0#, in The Journal of Symbolic Logic, vol. 43, n. 4, Jan., 1978, pp. 685–693, DOI:10.2307/2273508, JSTOR 2273508.
• Hjorth, Greg, Π¹₂ Wadge degrees, in Annals of Pure and Applied Logic, vol. 77, Jan., 1996, pp. 53–74.
• Jech, Thomas, Set theory, third millennium edition (revised and expanded), Springer, 2002, ISBN 3-540-44085-2.
• Martin, Donald A., Borel determinacy, in Annals of Mathematics. Second Series, vol. 102, n. 2, 1975, pp. 363–371, DOI:10.2307/1971035.
• Martin, Donald A. and John R. Steel, A Proof of Projective Determinacy, in Journal of the American Mathematical Society, vol. 2, n. 1, Jan., 1989, pp. 71–125, DOI:10.2307/1990913, JSTOR 1990913.
• Moschovakis, Yiannis N., Descriptive Set Theory, North Holland, 1980, ISBN 0-444-70199-0.
• Woodin, W. Hugh, Supercompact cardinals, sets of reals, and weakly homogeneous trees, in Proceedings of the National Academy of Sciences of the United States of America, vol. 85, n. 18, 1988, pp. 6587–6591, DOI:10.1073/pnas.85.18.6587, PMC 282022, PMID 16593979.
• Martin, Donald A., A simple proof that determinacy implies Lebesgue measurability, in Rend. Sem. Mat. Univ. Pol. Torino, vol. 61, n. 4, 2003, pp. 393–399. (PDF)
• Wolfe, P., The strict determinateness of certain infinite games, in Pacific J. Math., vol. 5, 1955, pp. Supplement I:841–847.