Determinacy

The first sort of game we shall consider is the two-player game of perfect information of length ω, in which the players play natural numbers. These games are often called Gale–Stewart games.^[2]

In this sort of game there are two players, often named I and II, who take turns playing natural numbers, with I going first. They play "forever"; that is, their plays are indexed by the natural numbers. When they're finished, a predetermined condition decides which player won. This condition need not be specified by any definable rule; it may simply be an arbitrary (infinitely long) lookup table saying who has won given a particular sequence of plays.

More formally, consider a subset A of Baire space; recall that the latter consists of all ω-sequences of natural numbers. Then in the game G_A, I plays a natural number a₀, then II plays a₁, then I plays a₂, and so on. Then I wins the game if and only if

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

and otherwise II wins. A is then called the payoff set of G_A.

It is assumed that each player can see all moves preceding each of his moves, and also knows the winning condition.

De manera informal, una estrategia para un jugador es una forma de jugar en la que sus jugadas están completamente determinadas por las jugadas anteriores. Nuevamente, dicha "forma" no tiene por qué poder ser descrita mediante ninguna "regla" explicable, sino que puede ser simplemente una tabla de consulta.

De forma más formal, una estrategia para el jugador I (para un juego en el sentido de la subsección anterior) es una función que acepta como argumento cualquier secuencia finita de números naturales, de longitud par, y devuelve un número natural. Si σ es dicha estrategia y < a ₀ ,...,a _2n-1 > es una secuencia de jugadas, entonces σ ( < a ₀ ,...,a _2n-1 > ) es la siguiente jugada que I realizará, si I sigue la estrategia σ . Las estrategias para II son exactamente iguales, sustituyendo "par" por "impar".

Cabe señalar que, hasta el momento, no hemos dicho nada sobre si una estrategia es buena o no . Una estrategia podría llevar a un jugador a realizar movimientos agresivamente malos, y aun así seguiría siendo una estrategia. De hecho, ni siquiera es necesario conocer la condición de victoria de un juego para saber qué estrategias existen para él.

Una estrategia es ganadora si el jugador que la sigue necesariamente debe ganar, sin importar lo que juegue su oponente. Por ejemplo, si σ es una estrategia para I , entonces σ es una estrategia ganadora para I en el juego G _A si, para cualquier secuencia de números naturales que II vaya a jugar , digamos < a ₁ ,a ₃ ,a ₅ ,... > , la secuencia de jugadas producida por σ cuando II juega de esta manera, es decir

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

es un elemento de A.

Se determina que un juego (o clase de juego) pertenece a una clase si, para todas las instancias del juego, existe una estrategia ganadora para uno de los jugadores (no necesariamente el mismo jugador en cada instancia). ^{[ 3 ]} No puede haber una estrategia ganadora para ambos jugadores en el mismo juego, pues si la hubiera, las dos estrategias podrían enfrentarse entre sí. El resultado resultante sería, por hipótesis, una victoria para ambos jugadores, lo cual es imposible. ^{[ 4 ]}

De la existencia de un cardinal medible se deduce que todo juego analítico (también llamado juego Σ ¹ ₁ ) está determinado, o, equivalentemente, que todo juego coanalítico (o Π ¹ ₁ ) está determinado. (Véase Jerarquía proyectiva para definiciones).

Actually a measurable cardinal is more than enough. A weaker principle — the existence of 0^# is sufficient to prove coanalytic determinacy, and a little bit more: The precise result is that the existence of 0^# is equivalent to the determinacy of all levels of the difference hierarchy below the ω² level, i.e. ω·n-Π¹₁ determinacy for every ${\displaystyle n}$.

From a measurable cardinal we can improve this very slightly to ω²-Π¹₁ determinacy. From the existence of more measurable cardinals, one can prove the determinacy of more levels of the difference hierarchy over Π¹₁.

If there is a Woodin cardinal with a measurable cardinal above it, then Π¹₂ determinacy holds. More generally, if there are n Woodin cardinals with a measurable cardinal above them all, then Π¹_n+1 determinacy holds. From Π¹_n+1 determinacy, it follows that there is a transitiveinner model containing n Woodin cardinals.

${\displaystyle \Delta _{2}^{1}}$ (lightface) determinacy is equiconsistent with a Woodin cardinal. If ${\displaystyle \Delta _{2}^{1}}$Si se cumple la determinación, entonces para un cono de Turing de x (es decir, para cada x real de grado de Turing suficientemente alto ), L[ x ] satisface la determinación OD (es decir, la determinación de juegos en enteros de longitud ω y pago definible ordinalmente), y en HOD ^{L[ x ]}${\displaystyle \omega _{2}^{L[x]}}$es un cardenal de Woodin.

Si existen infinitos cardinales de Woodin, entonces se cumple la determinismo proyectivo; es decir, todo juego cuya condición de victoria sea un conjunto proyectivo está determinado. De la determinismo proyectivo se deduce que, para cada número natural n , existe un modelo interno transitivo que satisface la existencia de n cardinales de Woodin.

El axioma de determinatividad , o AD , afirma que todo juego de dos jugadores de información perfecta de longitud ω, en el que los jugadores juegan números naturales, está determinado.

AD es demostrablemente falso a partir de ZFC; utilizando el axioma de elección se puede probar la existencia de un juego no determinado. Sin embargo, si existen infinitos cardinales de Woodin con una magnitud medible por encima de todos ellos, entonces L(R) es un modelo de ZF que satisface AD.

Si A es un subconjunto del espacio de Baire tal que el juego de Banach-Mazur para A está determinado, entonces o bien II tiene una estrategia ganadora, en cuyo caso A es meager , o bien I tiene una estrategia ganadora, en cuyo caso A es comeager en algún entorno abierto..

Esto no implica exactamente que A tenga la propiedad de Baire , pero se acerca bastante: una simple modificación del argumento muestra que si Γ es una clase de puntos adecuada tal que todo juego en Γ está determinado, entonces todo conjunto de números reales en Γ tiene la propiedad de Baire.

De hecho, este resultado no es óptimo; al considerar el juego de Banach-Mazur desplegado, podemos demostrar que la determinabilidad de Γ (para Γ con propiedades de cierre suficientes) implica que todo conjunto de números reales que es la proyección de un conjunto en Γ tiene la propiedad de Baire. Así, por ejemplo, la existencia de un cardinal medible implica la determinabilidad Π ¹ ₁ , lo que a su vez implica que todo conjunto Σ ¹ ₂ de números reales tiene la propiedad de Baire.

Al considerar otros juegos, podemos demostrar que la determinabilidad de Π ¹ _n implica que todo conjunto Σ ¹ _{n +1} de números reales tiene la propiedad de Baire, es medible según Lebesgue (de hecho, universalmente medible ) y tiene la propiedad de conjunto perfecto .

• El primer teorema de periodicidad implica que, para cada número natural n , si se cumple la determinación Δ ¹ _{2 n +1} , entonces Π ¹ _{2 n +1} y Σ ¹ _{2 n +2} tienen la propiedad de preordenamiento (y que Σ ¹ _{2 n +1} y Π ¹ _{2 n +2} no tienen la propiedad de preordenamiento, sino que tienen la propiedad de separación ).
• El segundo teorema de periodicidad implica que, para cada número natural n , si se cumple la determinación Δ ¹ _{2 n +1} , entonces Π ¹ _{2 n +1} y Σ ¹ _{2 n} tienen la propiedad de escala . ^{[ 7 ]} En particular, si se cumple la determinación proyectiva, entonces toda relación proyectiva tiene una uniformización proyectiva .
• El tercer teorema de periodicidad proporciona una condición suficiente para que un juego tenga una estrategia ganadora definible.

En 1969, Michael O. Rabin demostró que la teoría monádica de segundo orden de n sucesores ( S2S para n = 2) es decidible . ^{[ 8 ]} Un componente clave de la demostración requiere mostrar la determinabilidad de los juegos de paridad , que se encuentran en el tercer nivel de la jerarquía de Borel .

Wadge determinacy is the statement that for all pairs A, B of subsets of Baire space, the Wadge game G(A, B) is determined. Similarly for a pointclass Γ, Γ Wadge determinacy is the statement that for all sets A, B in Γ, the Wadge game G(A, B) is determined.

Wadge determinacy implies the semilinear ordering principle for the Wadge order. Another consequence of Wadge determinacy is the perfect set property.

In general, Γ Wadge determinacy is a consequence of the determinacy of Boolean combinations of sets in Γ. In the projective hierarchy, Π¹₁ Wadge determinacy is equivalent to Π¹₁ determinacy, as proved by Leo Harrington. This result was extended by Hjorth to prove that Π¹₂ Wadge determinacy (and in fact the semilinear ordering principle for Π¹₂) already implies Π¹₂ determinacy.

Determinacy of games on ordinals with ordinal definable payoff and length ω implies that for every regular cardinal κ>ω there are no ordinal definable disjoint stationary subsets of κ made of ordinals of cofinality ω. The consistency strength of the determinacy hypothesis is unknown but is expected to be very high.

Existence of ω₁ Woodin cardinals implies that for every countable ordinal α, all games on integers of length α and projective payoff are determined. Roughly speaking, α Woodin cardinals corresponds to determinacy of games on reals of length α (with a simple payoff set). Assuming a limit of Woodin cardinals κ with o(κ)=κ⁺⁺ and ω Woodin cardinals above κ, games of variable countable length where the game ends as soon as its length is admissible relative to the line of play and with projective payoff are determined. Assuming that a certain iterability conjecture is provable, existence of a measurable Woodin cardinal implies determinacy of open games of length ω₁ and projective payoff. (In these games, a winning condition for the first player is triggered at a countable stage, so the payoff can be coded as a set of reals.)

En relación con un límite de Woodin de cardinales de Woodin y una magnitud medible por encima de ellos, es consistente que todo juego sobre enteros de longitud ω ₁ y pago definible ordinalmente esté determinado. Se conjetura que la hipótesis de determinabilidad es equiconsistente con un límite de Woodin de cardinales de Woodin. ω ₁ es máximo en el sentido de que existen juegos indeterminados sobre enteros de longitud ω ₁ +ω y pago definible ordinalmente.

En cualquier juego interesante con información imperfecta , una estrategia ganadora será una estrategia mixta : es decir, dará cierta probabilidad de respuestas diferentes ante la misma situación. Si las estrategias óptimas de ambos jugadores son estrategias mixtas, el resultado del juego no puede ser ciertamente determinante (como sí lo es para las estrategias puras , ya que estas son deterministas ). Pero la distribución de probabilidad de los resultados de estrategias mixtas opuestas puede calcularse. Un juego que requiere estrategias mixtas se define como determinado si existe una estrategia que produce un valor esperado mínimo (sobre posibles contraestrategias) que supera un valor dado. Según esta definición, todos los juegos finitos de suma cero para dos jugadores están claramente determinados. Sin embargo, la determinación de los juegos infinitos de información imperfecta (juegos de Blackwell) es menos clara. ^{[ 9 ]}

En 1969, David Blackwell demostró que algunos "juegos infinitos con información imperfecta" (ahora llamados "juegos de Blackwell") están determinados, y en 1998, Donald A. Martin demostró que la determinabilidad ordinaria (juego de información perfecta) para una clase de puntos en negrita implica la determinabilidad de Blackwell para esa clase de puntos. Esto, combinado con el teorema de determinabilidad de Borel de Martin, implica que todos los juegos de Blackwell con funciones de pago de Borel están determinados. ^{[ 10 ] [ 11 ]} Martin conjeturó que la determinabilidad ordinaria y la determinabilidad de Blackwell para juegos infinitos son equivalentes en un sentido fuerte (es decir, que la determinabilidad de Blackwell para una clase de puntos en negrita implica a su vez la determinabilidad ordinaria para esa clase de puntos), pero hasta 2010, no se había demostrado que la determinabilidad de Blackwell implicara la determinabilidad de juegos de información perfecta. ^{[ 12 ]}