Determinación

El primer tipo de juego que consideraremos es el juego de dos jugadores de información perfecta de longitud ω , en el que los jugadores juegan números naturales . Estos juegos se denominan a menudo juegos de Gale - Stewart. ^{[ 2 ]}

En este tipo de juego hay dos jugadores, a menudo llamados I y II , que se turnan para jugar números naturales, comenzando I. Juegan indefinidamente; es decir, sus jugadas se indexan mediante números naturales. Al finalizar, una condición predeterminada decide quién ganó. Esta condición no tiene por qué estar especificada por ninguna regla definible; puede ser simplemente una tabla de consulta arbitraria (de longitud infinita) que indique quién ha ganado según una secuencia de jugadas determinada.

De manera más formal, consideremos un subconjunto A del espacio de Baire ; recordemos que este último consta de todas las secuencias ω de números naturales. Entonces, en el juego G _A , I juega un número natural a ₀ , luego II juega a ₁ , luego I juega a ₂ , y así sucesivamente. Entonces I gana el juego si y solo si

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

y de lo contrario II gana. A se denomina entonces el conjunto de pagos de G _A .

Se supone que cada jugador puede ver todos los movimientos que preceden a cada uno de los suyos, y también conoce la condición de victoria.

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).

En realidad, un cardinal medible es más que suficiente. Un principio más débil —la existencia de 0 ^# es suficiente para probar la determinabilidad coanalítica, y un poco más: el resultado preciso es que la existencia de 0 ^# es equivalente a la determinabilidad de todos los niveles de la jerarquía de diferencias por debajo del nivel ω ² , es decir, determinabilidad ω·n- Π ¹ ₁ para cada${\displaystyle n}$.

A partir de un cardinal medible podemos mejorar esto muy ligeramente a la determinabilidad de ω ² - Π ¹ _1. A partir de la existencia de más cardinales medibles, se puede probar la determinabilidad de más niveles de la jerarquía de diferencias sobre Π ¹ ₁ .

Si existe un cardinal de Woodin con un cardinal medible por encima, entonces se cumple la determinación Π ¹ _2. De forma más general, si existen n cardinales de Woodin con un cardinal medible por encima de todos ellos, entonces se cumple la determinación Π ^{1 n} ₊₁ . De la determinación Π ¹ _n+1 se deduce que existe un modelo interno transitivo que contiene n cardinales de Woodin.

${\displaystyle \Delta _ {2}^{1}}$La determinabilidad (de cara clara) es equiconsistente con un cardinal de Woodin. Si${\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 .

La determinación de Wadge es la afirmación de que para todos los pares A , B de subconjuntos del espacio de Baire , el juego de Wadge G( A , B ) está determinado. De manera similar, para una clase de puntos Γ, la determinación de Wadge es la afirmación de que para todos los conjuntos A , B en Γ, el juego de Wadge G( A , B ) está determinado.

La determinación de Wadge implica el principio de ordenación semilineal para el orden de Wadge . Otra consecuencia de la determinación de Wadge es la propiedad de conjunto perfecto .

En general, la determinación de Wadge en Γ es consecuencia de la determinación de combinaciones booleanas de conjuntos en Γ. En la jerarquía proyectiva , la determinación de Wadge en Π ¹ ₁ es equivalente a la determinación en Π ¹ ₁ , como demostró Leo Harrington . Este resultado fue extendido por Hjorth para demostrar que la determinación de Wadge en Π ¹ ₂ (y de hecho el principio de ordenación semilineal para Π ¹ ₂ ) ya implica la determinación en Π ¹ ₂ .

La determinismo de los juegos sobre ordinales con recompensa definible ordinalmente y longitud ω implica que para cada cardinal regular κ > ω no existen subconjuntos estacionarios disjuntos definibles ordinalmente de κ formados por ordinales de cofinalidad ω. Se desconoce la fuerza de consistencia de la hipótesis de determinismo, pero se espera que sea muy alta.

La existencia de cardinales de Woodin ω ₁ implica que, para cada ordinal numerable α, todos los juegos sobre enteros de longitud α y pago proyectivo están determinados. En términos generales, los cardinales de Woodin α corresponden a la determinabilidad de los juegos sobre reales de longitud α (con un conjunto de pagos simple). Suponiendo un límite de cardinales de Woodin κ con o( κ )= κ ⁺⁺ y cardinales de Woodin ω por encima de κ , se determinan los juegos de longitud numerable variable donde el juego termina tan pronto como su longitud es admisible con respecto a la línea de juego y con pago proyectivo. Suponiendo que cierta conjetura de iterabilidad es demostrable, la existencia de un cardinal de Woodin medible implica la determinabilidad de los juegos abiertos de longitud ω ₁ y pago proyectivo. (En estos juegos, una condición de victoria para el primer jugador se activa en una etapa numerable, por lo que el pago puede codificarse como un conjunto de reales).

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 ]}