Axioma de determinación

El conjunto S ₁ de todas las estrategias del primer jugador en un juego ω G tiene la misma cardinalidad que el continuo . Lo mismo ocurre con el conjunto S ₂ de todas las estrategias del segundo jugador. Sea SG el conjunto de todas las secuencias posibles en G , y A el subconjunto de secuencias de SG que hacen que el primer jugador gane. Con el axioma de elección podemos ordenar bien el continuo, y podemos hacerlo de tal manera que cualquier porción inicial propia tenga una cardinalidad menor que el continuo. Usamos el conjunto bien ordenado J obtenido para indexar tanto S ₁ como S ₂ , y construimos A de tal manera que sea un contraejemplo.

Comenzamos con conjuntos vacíos A y B. Sea α  ∈ J el índice de las estrategias en S ₁ y S _2. Necesitamos considerar todas las estrategias S ₁ = {s ₁ ( α )} _{α ∈ J} del primer jugador y todas las estrategias S ₂ = {s ₂ ( α )} _{α ∈ J} del segundo jugador para asegurarnos de que para cada estrategia exista una estrategia del otro jugador que gane contra ella. Para cada estrategia del jugador considerado, generaremos una secuencia que le dé la victoria al otro jugador. Sea t el tiempo cuyo eje tiene longitud ℵ ₀ y que se utiliza durante cada secuencia de juego. Creamos el contraejemplo A mediante recursión transfinita sobre α :     

1. Consideremos la estrategia s ₁ ( α ) del primer jugador.
2. Aplique esta estrategia en un juego ω, generando (junto con la estrategia del otro jugador) s ₁ ( α )) una secuencia ⟨ a ₁ , b ₂ , a ₃ , b ₄ ,  ...,a _t , b _{t +1} ,  ...⟩, que no pertenece a A . Esto es posible, porque el número de opciones para ⟨ b ₂ , b ₄ , b ₆ ,  ...⟩ tiene la misma cardinalidad que el continuo, que es mayor que la cardinalidad de la porción inicial propia { β ∈ J | β < α } de J.       
3. Agregue esta secuencia a B para indicar que s ₁ ( α ) pierde (en ⟨ b ₂ , b ₄ , b ₆ ,  ...⟩).
4. Consideremos la estrategia s ₂ ( α ) del segundo jugador.
5. Aplique esta estrategia en un juego ω, generando (junto con la estrategia del otro jugador) s ₂ ( α )) una secuencia ⟨ a ₁ , b ₂ , a ₃ , b ₄ ,  ..., a _t , b _{t +1} ,  ...⟩, que no pertenece a B. Esto es posible porque el número de opciones para ⟨ a ₁ , a ₃ , a ₅ ,  ...⟩ tiene la misma cardinalidad que el continuo, que es mayor que la cardinalidad de la porción inicial propia { β ∈ J | β ≤ α } de J.       
6. Agregue esta secuencia a A para indicar que s ₂ ( α ) pierde (en ⟨ a ₁ , a ₃ , a ₅ ,  ...⟩).
7. Procese todas las estrategias posibles de S ₁ y S ₂ con inducción transfinita sobre α. Para todas las secuencias que no estén en A o B después de eso, decida arbitrariamente si pertenecen a A o a B, de modo que B sea el complemento de A.

Una vez hecho esto, prepárese para un juego ω G. Para una estrategia dada s ₁ del primer jugador, existe un α  ∈ J tal que s ₁ = s ₁ ( α ), y A se ha construido de tal manera que s ₁ ( α ) falla (en ciertas elecciones ⟨ b ₂ , b ₄ , b ₆ , ...⟩ del segundo jugador). Por lo tanto, s ₁ falla. De manera similar, cualquier otra estrategia de cualquiera de los jugadores también falla.    

En esta construcción, el uso del axioma de elección es similar a la elección de calcetines, como se afirma en la cita de Bertrand Russell .

En un juego ω, los dos jugadores generan la secuencia ⟨ a ₁ , b ₂ , a ₃ , b ₄ ,  ...⟩, un elemento en ω ^ω , donde nuestra convención es que 0 no es un número natural, por lo que ninguno de los jugadores puede elegirlo. Definimos la función f :  ω ^ω  →  {0,  1} ^ω tal que f ( r ) es la única secuencia de longitud ω con valores en {0, 1} cuyo primer término es igual a 0, y cuya secuencia de rachas (véase codificación de longitud de rachas ) es igual a r. ( Se puede demostrar que dicha f  es inyectiva. La imagen es el subconjunto de {0, 1} ^ω de secuencias que comienzan con 0 y que no son eventualmente constantes. Formalmente, f es la función de signo de interrogación de Minkowski , {0,  1} ^ω es el espacio de Cantor y ω ^ω es el espacio de Baire ).

Observe la relación de equivalencia en {0,  1} ^ω tal que dos secuencias son equivalentes si y solo si difieren en un número finito de términos. Esto divide el conjunto en clases de equivalencia. Sea T el conjunto de clases de equivalencia (de modo que T tenga la cardinalidad del continuo). Defina g :  {0,  1} ^ω  → T que asigna una secuencia a su clase de equivalencia. Defina el complemento de cualquier secuencia s en {0, 1} ^ω como la secuencia s ₁ que difiere en cada término. Defina la función h : T → T tal que para cualquier secuencia s en {0, 1} ^ω , h aplicada a la clase de equivalencia de s es igual a la clase de equivalencia del complemento de s (que está bien definida porque si s y s' son equivalentes, entonces sus complementos son equivalentes). Se puede demostrar que h es una involución sin puntos fijos, y por lo tanto tenemos una partición de T en subconjuntos de tamaño 2, de modo que cada subconjunto tiene la forma { t , h ( t )}. Usando el axioma de elección, podemos elegir un elemento de cada subconjunto. En otras palabras, estamos eligiendo la "mitad" de los elementos de T, un subconjunto que denotamos por U (donde U ⊆ T) tal que t ∈ U si y solo si h ( t ) ∉ U.             

A continuación, definimos el subconjunto A  ⊆  ω ^ω en el que gana 1 : A es el conjunto de todos los r tales que g ( f ( r ))  ∈ U. Ahora afirmamos que ninguno de los jugadores tiene una estrategia ganadora, utilizando un argumento de robo de estrategia . Denotamos el estado actual del juego por una secuencia finita de números naturales (de modo que si la longitud de esta secuencia es par, entonces le toca jugar al 1 ; de lo contrario, le toca jugar al 2 ). 

Supongamos que q es una estrategia ganadora (determinista) para 2. El jugador 1 puede construir una estrategia p que vence a q de la siguiente manera: Supongamos que la respuesta del jugador 2 ( según q ) a ⟨1⟩ es b _1. Entonces 1 especifica en p que a ₁ = 1 + b _1. (Aproximadamente, 1 está jugando ahora como 2 en un segundo juego paralelo; el conjunto ganador de 1 en el segundo juego es igual al conjunto ganador de 2 en el juego original, lo cual es una contradicción. Sin embargo, continuamos de forma más formal).    

Supongamos que la respuesta de 2 ( siempre según q ) a ⟨1 + b ₁ ⟩ es b ₂ , y la respuesta de 2 a ⟨1, b ₁ , b ₂ ⟩ es b ₃ . Al construir p para 1 , solo buscamos vencer a q, y por lo tanto solo tenemos que manejar la respuesta b ₂ al primer movimiento de 1. Por lo tanto, establecemos b ₃ como la respuesta de 1 a ⟨1 + b ₁ , b ₂ ⟩. En general, para n par, denotamos la respuesta de 2 a ⟨1 + b ₁ , ..., b _{n −1} ⟩ por b _n y la respuesta de 2 a ⟨1, b ₁ , ..., b _n ⟩ por b _{n +1} . Luego especificamos en p que la respuesta de 1 a ⟨1 + b ₁ , b ₂ , ..., b _n ⟩ es b _{n +1} . Se presume que la estrategia q es ganadora, y el resultado del juego r en ω ^ω dado por ⟨1, b ₁ , ...⟩ es una secuencia posible permitida por q, por lo que r debe ser ganador para 2 y g ( f ( r )) no debe estar en U. El resultado del juego r            ' en ω ^ω dado por ⟨1  + b ₁ , b ₂ , ...⟩ también es una secuencia permitida por q (específicamente, q jugando contra p ), por lo que g ( f ( r  ')) no debe estar en U. Sin embargo, f ( r ) y f ( r )') difieren en todos los términos excepto en el primero (debido a la naturaleza de la codificación de longitud de ejecución y un desplazamiento de 1), por lo que f ( r ) y f ( r )') están en clases equivalentes de complemento, por lo que g ( f ( r )), g ( f ( r )')) no pueden estar ambos en U, lo que contradice la suposición de que q es una estrategia ganadora.

De manera similar, supongamos que p es una estrategia ganadora para 1 ; el argumento es similar, pero ahora utiliza el hecho de que las clases de equivalencia se definieron permitiendo que un número arbitrariamente grande de términos difiriera. Sea a 1 _el primer movimiento de 1. En general, para n par, denotemos la respuesta de 1 a ⟨ a 1 , _1⟩ (si n = 2) o ⟨ a ₁ , 1, a ₂ , ..., a _n−1 ⟩ por a _n y la respuesta de 1 a ⟨ a ₁ , 1 + a ₂ , ... a _n ⟩ por a _{n +1} . Entonces, el resultado del juego r dado por ⟨ a ₁ , 1, a ₂ , a ₃ , ...⟩ está permitido por p de modo que g ( f ( r )) debe estar en U ; también el resultado del juego r       ' dado por ⟨ a ₁ , 1  + a ₂ , a ₃ , ...⟩ también está permitido por p de modo que g ( f ( r  ')) debe estar en U. Sin embargo, f ( r ) y f ( r )') difieren en todos excepto en los primeros a ₁  +  1 términos, por lo que están en clases equivalentes complementarias, por lo tanto g ( f ( r )) y g ( f ( r )')) no pueden estar ambos en U, lo que contradice que p sea una estrategia ganadora.