La determinación es un subcampo de la teoría de conjuntos , una rama de las matemáticas , que examina las condiciones bajo las cuales uno u otro jugador de un juego tiene una estrategia ganadora, y las consecuencias de la existencia de tales estrategias. De manera alternativa y similar, la "determinación" es la propiedad de un juego en el que existe tal estrategia. La determinación fue introducida por Gale y Stewart en 1950, bajo el nombre de "determinación". [1]
Los juegos estudiados en la teoría de conjuntos suelen ser juegos de Gale -Stewart: juegos de información perfecta para dos jugadores en los que los jugadores realizan una secuencia infinita de movimientos y no hay empates. El campo de la teoría de juegos estudia tipos de juegos más generales, incluidos juegos con tablas como el tres en raya , el ajedrez o el ajedrez infinito , o juegos con información imperfecta como el póquer .
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 con números naturales . Estos juegos suelen denominarse juegos de Gale-Stewart. [2]
En este tipo de juego hay dos jugadores, a menudo llamados I y II , que se turnan para jugar con números naturales, siendo I el primero. Juegan "para siempre"; es decir, sus jugadas están indexadas por los números naturales. Cuando terminan, una condición predeterminada decide qué jugador ganó. Esta condición no necesita ser especificada por ninguna regla definible ; puede ser simplemente una tabla de búsqueda arbitraria (infinitamente larga) que dice quién ganó dada una secuencia particular de jugadas.
Más formalmente, consideremos un subconjunto A del espacio de Baire ; Recuerde que este último consta de todas las secuencias ω de números naturales. Luego, en el juego G A , juego un número natural un 0 , luego II juego un 1 , luego juego un 2 , y así sucesivamente. Entonces gano el juego si y sólo si
y en caso contrario II gana. Entonces A se llama conjunto de pagos de G A .
Se supone que cada jugador puede ver todos los movimientos que preceden a cada uno de sus movimientos y también conoce la condición ganadora.
Informalmente, una estrategia para un jugador es una forma de jugar en la que sus jugadas están enteramente determinadas por las jugadas anteriores. Una vez más, dicha "forma" no tiene por qué poder ser capturada por ninguna "regla" explicable, sino que puede ser simplemente una tabla de búsqueda.
Más formalmente, 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 tal estrategia y <a 0 ,...,a 2n-1 > es una secuencia de jugadas, entonces σ ( <a 0 ,...,a 2n-1 > ) es la próxima jugada que haré , si estoy siguiendo la estrategia σ . Las estrategias para II son exactamente las mismas, sustituyendo "par" por "impar".
Tenga en cuenta que hasta el momento no hemos dicho nada sobre si una estrategia es buena en algún sentido . Una estrategia podría dirigir a un jugador a realizar movimientos agresivos y malos, y seguiría siendo una estrategia. De hecho, ni siquiera es necesario conocer las condiciones para ganar un juego, saber qué estrategias existen para el juego.
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 vaya a jugar II , digamos <a 1 ,a 3 ,a 5 ,. ..>, la secuencia de jugadas producidas por σ cuando II juega así, es decir
es un elemento de A .
Una (clase de) juego(s) se determina si para todas las instancias del juego hay una estrategia ganadora para uno de los jugadores (no necesariamente el mismo jugador para cada instancia). [3] No puede haber una estrategia ganadora para ambos jugadores en un mismo juego, ya que si la hubiera, las dos estrategias podrían jugarse entre sí. El resultado resultante sería entonces, por hipótesis, una victoria para ambos jugadores, lo cual es imposible. [4]
Se determinan todos los juegos finitos de información perfecta en los que no se producen empates.
Los juegos del mundo real de información perfecta, como el tres en raya , el ajedrez o el ajedrez infinito , siempre terminan en un número finito de movimientos (en los juegos de ajedrez infinitos esto supone que se aplica la regla de los 50 movimientos). Si dicho juego se modifica para que un jugador en particular gane en cualquier condición en la que el juego se hubiera considerado empate, entonces siempre se determina. [4] La condición de que el juego siempre termine (es decir, todas las posibles extensiones de la posición finita resultan en una victoria para el mismo jugador) en un número finito de movimientos corresponde a la condición topológica de que el conjunto A que da la condición ganadora para G A es abierto en la topología del espacio de Baire .
Por ejemplo, modificar las reglas del ajedrez para que las partidas empatadas sean una victoria para las negras hace que el ajedrez sea un juego determinado. [5] Da la casualidad de que el ajedrez tiene un número finito de posiciones y reglas de empate por repetición, por lo que con estas reglas modificadas, si el juego continúa el tiempo suficiente sin que las blancas hayan ganado, entonces las negras pueden eventualmente forzar una victoria (debido a la modificación del empate = victoria para las negras).
La prueba de que tales juegos están determinados es bastante simple: el jugador I simplemente juega para no perder ; es decir, el jugador I juega para asegurarse de que el jugador II no tenga una estrategia ganadora después del movimiento I. Si el jugador I no puede hacer esto, significa que el jugador II tuvo una estrategia ganadora desde el principio. Por otro lado, si el jugador puedo jugar de esta manera, entonces debo ganar , porque el juego terminará después de un número finito de movimientos, y el jugador no puede haber perdido en ese momento.
Esta prueba en realidad no requiere que el juego termine siempre en un número finito de movimientos, sólo que termine en un número finito de movimientos siempre que II gane. Esa condición, topológicamente, es que el conjunto A sea cerrado . Este hecho (que todos los juegos cerrados están determinados) se denomina teorema de Gale-Stewart . Tenga en cuenta que, por simetría, todos los juegos abiertos también están determinados. (Un juego está abierto si puedo ganar sólo ganando en un número finito de movimientos).
David Gale y FM Stewart demostraron que los juegos abiertos y cerrados están determinados. Wolfe demostró la determinación para el segundo nivel de los juegos de la jerarquía de Borel en 1955. Durante los siguientes 20 años, investigaciones adicionales que utilizaron argumentos cada vez más complicados establecieron que el tercer y cuarto nivel de la jerarquía de Borel están determinados. [ especificar ]
En 1975, Donald A. Martin demostró que todos los juegos de Borel están determinados; es decir, si A es un subconjunto de Borel del espacio de Baire, entonces G A está determinado. Este resultado, conocido como determinación de Borel , es el mejor resultado de determinación posible demostrable en ZFC, en el sentido de que la determinación de la siguiente clase Wadge superior no es demostrable en ZFC.
En 1971, antes de que Martin obtuviera su prueba, Harvey Friedman demostró que cualquier prueba de la determinabilidad de Borel debe utilizar el axioma de reemplazo de manera esencial, para iterar el axioma del conjunto de potencias con una frecuencia transfinita . El trabajo de Friedman ofrece un resultado nivel por nivel que detalla cuántas iteraciones del axioma del conjunto de potencias son necesarias para garantizar la determinación en cada nivel de la jerarquía de Borel .
Para cada número entero n , ZFC\P demuestra determinabilidad en el n- ésimo nivel de la jerarquía de diferencias de conjuntos, pero ZFC\P no prueba que para cada número entero n se determina el n -ésimo nivel de la jerarquía de diferencias de conjuntos. Véase matemáticas inversas para conocer otras relaciones entre determinabilidad y subsistemas de aritmética de segundo orden .
Existe una relación íntima entre la determinación y los grandes cardenales . En general, los axiomas cardinales grandes más fuertes prueban la determinabilidad de clases de puntos más grandes , más altas en la jerarquía de Wadge , y la determinación de tales clases de puntos, a su vez, prueba la existencia de modelos internos de axiomas cardinales grandes ligeramente más débiles que los utilizados para probar la determinación de la clase de puntos en primer lugar.
De la existencia de un cardinal medible se deduce que todo juego analítico (también llamado juego Σ 1 1 ) está determinado o, de manera equivalente, que todo juego coanalítico (o Π 1 1 ) está determinado. (Consulte Jerarquía proyectiva para obtener definiciones).
En realidad, un cardenal mensurable es más que suficiente. Un principio más débil: la existencia de 0 # es suficiente para demostrar la determinación coanalítica, y un poco más: el resultado preciso es que la existencia de 0 # es equivalente a la determinación de todos los niveles de la jerarquía de diferencias por debajo del nivel ω 2 , es decir, ω·n- Π 1 1 determinación para cada .
Desde un cardinal mensurable podemos mejorar esto muy ligeramente a ω 2 - Π 1 1 determinación. A partir de la existencia de más cardinales mensurables, se puede probar la determinación de más niveles de la jerarquía de diferencias sobre Π 1 1 .
Para cada número real r , la determinabilidad es equivalente a la existencia de r # . Para ilustrar cómo los cardinales grandes conducen a la determinación, aquí hay una prueba de determinación dada la existencia de r # .
Sea A un subconjunto del espacio de Baire. A = p[ T ] para algún árbol T (construible a partir de r ) en (ω, ω). (Es decir, x∈A si y sólo si de algún y , es un camino a través de T ).
Dado un juego parcial s , sea el subárbol de T consistente con s sujeto a max(y 0 ,y 1 ,...,y len(s)-1 )<len(s). La condición adicional asegura que sea finita. Consistencia significa que cada camino tiene la forma donde hay un segmento inicial de s .
Para demostrar que A está determinado, defina el juego auxiliar de la siguiente manera:
además de los movimientos ordinarios, el jugador 2 debe realizar una asignación de en ordinales (por debajo de un ordinal suficientemente grande κ ) tal que
Recuerde que el orden de Kleene-Brouwer es como el orden lexicográfico excepto que si s extiende adecuadamente t entonces s < t . Es un buen ordenamiento si el árbol está bien fundamentado.
El juego auxiliar está abierto. Prueba: Si el jugador 2 no pierde en una etapa finita, entonces la unión de todos (que es el árbol que corresponde a la jugada) está fundada, por lo que el resultado de la jugada no auxiliar no está en A.
Así, se determina el juego auxiliar. Prueba: Por inducción transfinita, para cada ordinal α, calcule el conjunto de posiciones donde el jugador 1 puede forzar una victoria en α pasos, donde una posición con el jugador 2 para moverse es perder (para el jugador 2) en α pasos si y así por cada movimiento el resultado la posición está perdiendo en menos de α pasos. Una estrategia para el jugador 1 es reducir α con cada posición (digamos, elegir el menor α y romper empates eligiendo el menor movimiento), y una estrategia para el jugador 2 es elegir el menor movimiento (en realidad, cualquiera funcionaría) que no conduzca a una posición con un α asignado. Tenga en cuenta que L ( r ) contiene el conjunto de posiciones ganadoras, así como las estrategias ganadoras indicadas anteriormente.
Una estrategia ganadora para el jugador 2 en el juego original conduce a una estrategia ganadora en el juego auxiliar: el subárbol de T correspondiente a la estrategia ganadora está bien fundamentado, por lo que el jugador 2 puede elegir ordinales según el orden de Kleene-Brouwer del árbol. Además, trivialmente, una estrategia ganadora para el jugador 2 en el juego auxiliar proporciona una estrategia ganadora para el jugador 2 en el juego original.
Queda por demostrar que usando r # , la estrategia ganadora mencionada anteriormente para el jugador 1 en el juego auxiliar se puede convertir en una estrategia ganadora en el juego original. r # da una clase I adecuada de ( L ( r ),∈, r ) ordinales indiscernibles . Por indiscernibilidad, si κ y los ordinales en la respuesta auxiliar están en I , entonces los movimientos del jugador 1 no dependen de los movimientos auxiliares (o de κ ), por lo que la estrategia se puede convertir en una estrategia para el juego original ( ya que el jugador 2 puede aguantar con indiscernibles cualquier número finito de pasos). Supongamos que el jugador 1 pierde en el juego original. Entonces, el árbol correspondiente a una obra de teatro está bien fundamentado. Por lo tanto, el jugador 2 puede ganar el juego auxiliar utilizando movimientos auxiliares basados en los indiscernibles (ya que el tipo de orden de los indiscernibles excede el orden de Kleene-Brouwer del árbol), lo que contradice que el jugador 1 gane el juego auxiliar.
Si hay un cardenal de Woodin con un cardenal mensurable encima, entonces se cumple la determinación Π 1 2 . De manera más general, si hay n cardinales de Woodin con un cardenal mensurable sobre todos ellos, entonces se cumple la determinabilidad Π 1 n+1 . De la determinabilidad Π 1 n+1 , se deduce que existe un modelo interno transitivo que contiene n cardinales de Woodin.
La determinación (cara clara) es equiconsistente con un cardenal de Woodin. Si se cumple la determinabilidad, 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 sobre números enteros de longitud ω y pago definible por ordinal) , y en HOD L[ x ] es un cardenal de Woodin.
Si hay infinitos cardenales de Woodin, entonces se cumple la determinación proyectiva; es decir, se determina todo juego cuya condición de victoria sea un conjunto proyectivo . De la determinabilidad proyectiva se deduce que, para cada número natural n , existe un modelo interno transitivo que satisface que haya n cardinales de Woodin.
El axioma de determinabilidad , o AD , afirma que todo juego de dos jugadores de información perfecta de longitud ω, en el que los jugadores juegan naturales, está determinado.
AD es demostrablemente falso de ZFC; utilizando el axioma de elección se puede demostrar la existencia de un juego no determinado. Sin embargo, si hay infinitos cardinales de Woodin con un mensurable 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 se determina el juego de Banach-Mazur para A , entonces II tiene una estrategia ganadora, en cuyo caso A es pobre , o I tiene una estrategia ganadora, en cuyo caso A es pobre en algún barrio abierto [1] .
Esto no implica del todo que A tenga la propiedad de Baire , pero se acerca: una simple modificación del argumento muestra que si Γ es una clase de puntos adecuada tal que cada juego en Γ está determinado, entonces cada conjunto de 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 suficientes propiedades de cierre) implica que todo conjunto de reales que es la proyección de un conjunto en Γ tiene la propiedad de Baire. Así, por ejemplo, la existencia de un cardinal mensurable implica determinación Π 1 1 , lo que a su vez implica que todo conjunto Σ 1 2 de reales tiene la propiedad de Baire.
Al considerar otros juegos, podemos demostrar que la determinabilidad Π 1 n implica que cada conjunto Σ 1 n +1 de reales tiene la propiedad de Baire, es medible según Lebesgue (de hecho, universalmente mensurable ) y tiene la propiedad del conjunto perfecto .
En 1969, Michael O. Rabin demostró que la teoría monádica de segundo orden de n sucesores ( S2S para n = 2) es decidible . [7] Un componente clave de la prueba requiere mostrar la determinación de los juegos de paridad , que se encuentran en el tercer nivel de la jerarquía de Borel .
La determinabilidad de Wadge es la afirmación de que para todos los pares A , B de subconjuntos del espacio de Baire , se determina el juego de Wadge G( A , B ). De manera similar, para una clase de puntos Γ, Γ La determinabilidad de Wadge es la afirmación de que para todos los conjuntos A , B en Γ, se determina el juego de Wadge G( A , B ).
La determinación de Wadge implica el principio de ordenamiento semilineal para el orden Wadge . Otra consecuencia de la determinación de Wadge es la propiedad del conjunto perfecto .
En general, la determinabilidad de Γ Wadge es una consecuencia de la determinabilidad de combinaciones booleanas de conjuntos en Γ. En la jerarquía proyectiva , la determinación de Π 1 1 Wadge es equivalente a la determinación de Π 1 1 , como lo demuestra Leo Harrington . Hjorth amplió este resultado para demostrar que la determinabilidad de Π 1 2 Wadge (y, de hecho, el principio de ordenamiento semilineal para Π 1 2 ) ya implica determinación de Π 1 2 .
La determinación de juegos sobre ordinales con pago ordinal definible y longitud ω implica que para cada cardinal regular κ > ω no hay subconjuntos estacionarios disjuntos ordinales definibles de κ hechos de ordinales de cofinalidad ω. Se desconoce la fuerza de consistencia de la hipótesis de la determinabilidad, pero se espera que sea muy alta.
La existencia de ω 1 cardinales de Woodin implica que para cada ordinal contable α, se determinan todos los juegos sobre números enteros de longitud α y pago proyectivo. En términos generales, los cardinales α Woodin corresponden a la determinación de juegos en reales de longitud α (con un conjunto de pagos simple). Suponiendo un límite de cardenales de Woodin κ con o( κ )= κ ++ y ω cardenales de Woodin por encima de κ , los juegos de longitud contable variable donde el juego termina tan pronto como su duración es admisible en relación con la línea de juego y con pago proyectivo son determinado. Suponiendo que una cierta conjetura de iterabilidad sea demostrable, la existencia de un cardinal de Woodin medible implica la determinación de juegos abiertos de longitud ω 1 y pago proyectivo. (En estos juegos, se activa una condición ganadora para el primer jugador en una etapa contable, 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 un mensurable por encima de ellos, es consistente que cada juego en números enteros de longitud ω 1 y pago ordinal definible esté determinado. Se conjetura que la hipótesis de la determinabilidad es equiconsistente con un límite de Woodin de cardinales de Woodin. ω 1 es máximo porque hay juegos indeterminados sobre números enteros de longitud ω 1 +ω y pago ordinal definible.
En cualquier juego interesante con información imperfecta , una estrategia ganadora será una estrategia mixta : es decir, dará cierta probabilidad de respuestas diferentes a la misma situación. Si las estrategias óptimas de ambos jugadores son estrategias mixtas, entonces el resultado del juego no puede ser ciertamente determinante (como puede serlo para las estrategias puras , ya que son deterministas ). Pero se puede calcular la distribución de probabilidad de los resultados de estrategias mixtas opuestas. Un juego que requiere estrategias mixtas se define como determinado si existe una estrategia que produce un valor mínimo esperado (sobre posibles contraestrategias) que excede un valor dado. Frente a esta definición, todos los juegos finitos de dos jugadores de suma cero están claramente determinados. Sin embargo, la determinación de los juegos infinitos de información imperfecta (juegos de Blackwell) es menos clara. [8]
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 determinación ordinaria (juego de información perfecta) para una clase de puntos en negrita implica la determinación de Blackwell para la clase de puntos. Esto, combinado con el teorema de determinación de Borel de Martin, implica que todos los juegos de Blackwell con funciones de pago de Borel están determinados. [9] [10] Martin conjeturó que la determinabilidad ordinaria y la determinabilidad de Blackwell para juegos infinitos son equivalentes en un sentido fuerte (es decir, que la determinación de Blackwell para una clase de puntos en negrita implica a su vez una determinación ordinaria para esa clase de puntos), pero a partir de 2010, no ha sido así. Se ha demostrado que la determinación de Blackwell implica una determinación del juego de información perfecta. [11]
![{\displaystyle \omega _ {2}^{L[x]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d8665f4b2ab841ded5224606126c655e3ea229a)
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite book}}: |journal=ignorado ( ayuda )CS1 maint: multiple names: authors list (link)