En matemáticas , el axioma de determinación (abreviado como AD ) es un posible axioma para la teoría de conjuntos introducido por Jan Mycielski y Hugo Steinhaus en 1962. Se refiere a ciertos juegos topológicos de dos personas de longitud ω . AD establece que cada juego de un cierto tipo está determinado ; es decir, uno de los dos jugadores tiene una estrategia ganadora .
La motivación de Steinhaus y Mycielski para AD fueron sus interesantes consecuencias, y sugirieron que AD podría ser cierto en el modelo natural más pequeño L(R) de una teoría de conjuntos, que acepta solo una forma débil del axioma de elección (AC) pero contiene todos los números reales y ordinales . Algunas consecuencias de AD se desprendían de teoremas demostrados anteriormente por Stefan Banach y Stanisław Mazur y Morton Davis. Mycielski y Stanisław Świerczkowski contribuyeron con otra: AD implica que todos los conjuntos de números reales son medibles según Lebesgue . Más tarde, Donald A. Martin y otros demostraron consecuencias más importantes, especialmente en la teoría descriptiva de conjuntos . En 1988, John R. Steel y W. Hugh Woodin concluyeron una larga línea de investigación. Asumiendo la existencia de algunos números cardinales incontables análogos a ℵ 0 , demostraron la conjetura original de Mycielski y Steinhaus de que AD es cierto en L(R).
El axioma de determinación se refiere a juegos de la siguiente forma específica: Considérese un subconjunto A del espacio de Baire ω ω de todas las sucesiones infinitas de números naturales . Dos jugadores eligen alternativamente números naturales.
Esto genera la secuencia ⟨ n i ⟩ i ∈ω después de una cantidad infinita de movimientos. El jugador que elige primero gana el juego si y solo si la secuencia generada es un elemento de A . El axioma de determinación es la afirmación de que todos esos juegos están determinados.
No todos los juegos requieren el axioma de determinación para demostrar que están determinados. Si el conjunto A es clopen , el juego es esencialmente un juego finito y, por lo tanto, está determinado. De manera similar, si A es un conjunto cerrado , entonces el juego está determinado. Por el teorema de determinación de Borel , los juegos cuyo conjunto ganador es un conjunto de Borel están determinados. De la existencia de cardinales suficientemente grandes se deduce que AD se cumple en L(R) y que un juego está determinado si tiene un conjunto proyectivo como su conjunto ganador (ver Determinación proyectiva ).
El axioma de determinabilidad implica que para cada subespacio X de los números reales , el juego de Banach-Mazur BM( X ) está determinado y, en consecuencia, que todo conjunto de reales tiene la propiedad de Baire .
Partiendo del supuesto del axioma de elección, presentamos dos construcciones separadas de contraejemplos del axioma de determinación. De ello se desprende que el axioma de determinación y el axioma de elección son incompatibles.
El conjunto S 1 de todas las estrategias del primer jugador en un ω-juego G tiene la misma cardinalidad que el continuo . Lo mismo es cierto para el conjunto S 2 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 gane el primer jugador. Con el axioma de elección podemos ordenar bien el continuo, y podemos hacerlo de tal manera que cualquier porción inicial propia tenga menor cardinalidad que el continuo. Usamos el conjunto bien ordenado obtenido J para indexar tanto S 1 como S 2 , y construimos A de tal manera que sea un contraejemplo.
Empezamos con los conjuntos vacíos A y B. Sea α ∈ J el índice de las estrategias en S 1 y S 2. Necesitamos considerar todas las estrategias S 1 = {s 1 ( α )} α ∈ J del primer jugador y todas las estrategias S 2 = {s 2 ( α )} α ∈ J del segundo jugador para asegurarnos de que para cada estrategia existe una estrategia del otro jugador que le gana. Para cada estrategia del jugador considerado generaremos una secuencia que le dé una victoria al otro jugador. Sea t el tiempo cuyo eje tiene longitud ℵ 0 y que se utiliza durante cada secuencia de juego. Creamos el contraejemplo A por recursión transfinita en α :
Una vez hecho esto, prepárese para un ω-juego G . Para una estrategia dada s 1 del primer jugador, existe un α ∈ J tal que s 1 = s 1 ( α ), y se ha construido A de modo que s 1 ( α ) falla (en ciertas elecciones ⟨ b 2 , b 4 , b 6 , ...⟩ del segundo jugador). Por lo tanto, s 1 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 Axioma de elección#Citas .
En un juego ω, los dos jugadores generan la secuencia ⟨ a 1 , b 2 , a 3 , b 4 , ...⟩, un elemento en ω ω , donde nuestra convención es que 0 no es un número natural, por lo tanto, ningún jugador puede elegirlo. Defina 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 ejecuciones (ver codificación de longitud de ejecución ) es igual a r. (Se puede demostrar que una f de este tipo 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 .)
Obsérvese la relación de equivalencia en {0, 1} ω tal que dos sucesiones 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 (tal que T tiene la cardinalidad del continuo). Defina {0, 1} ω → T que lleva una sucesión a su clase de equivalencia. Defina el complemento de cualquier sucesión s en {0, 1} ω como la sucesión s 1 que difiere en cada término. Defina la función h : T → T tal que para cualquier sucesión 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 tales 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, tal que t ∈ U si y solo si h ( t ) ∉ U.
A continuación, definimos el subconjunto A ⊆ ω ω en el que 1 gana: A es el conjunto de todos los r tales que g ( f ( r )) ∈ U. Ahora afirmamos que ningún jugador tiene una estrategia ganadora, utilizando un argumento de robo de estrategia . Denotamos el estado actual del juego mediante una secuencia finita de números naturales (de modo que si la longitud de esta secuencia es par, entonces 1 es el siguiente en jugar; de lo contrario, 2 es el siguiente en jugar).
Supongamos que q es una estrategia ganadora (determinista) para 2. El jugador 1 puede construir una estrategia p que supere 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 = 1 + b 1. (A grandes rasgos, 1 ahora está jugando 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, y esto es una contradicción. Sin embargo, continuamos de manera más formal).
Supongamos que la respuesta de 2 (siempre según q ) a ⟨1 + b 1 ⟩ es b 2 , y la respuesta de 2 a ⟨1, b 1 , b 2 ⟩ es b 3 . Construimos p para 1 , solo pretendemos vencer a q y, por lo tanto, solo tenemos que manejar la respuesta b 2 al primer movimiento de 1. Por lo tanto, establecemos que la respuesta de 1 a ⟨1 + b 1 , b 2 ⟩ es b 3 . En general, para n par, denotamos la respuesta de 2 a ⟨1 + b 1 , ..., b n −1 ⟩ por b n y la respuesta de 2 a ⟨1 , b 1 , ..., b n ⟩ por b n +1 . Entonces 1 especifica en p que la respuesta de 1 a ⟨1 + b 1 , b 2 , ..., b n ⟩ es b n +1 . Se supone que la estrategia q es ganadora, y el resultado del juego r en ω ω dado por ⟨1, b 1 , ...⟩ 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 1 , b 2 , ...⟩ 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 todo excepto en el primer término (por 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 complementarias equivalentes, por lo que g ( f ( r )), g ( f ( r ')) no pueden estar ambos en U, lo que contradice el supuesto 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 al permitir que un número finito arbitrario de términos difirieran. 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 , 1, a 2 , ..., a n−1 ⟩ por a n y la respuesta de 1 a ⟨ a 1 , 1 + a 2 , ... a n ⟩ por a n +1 . Entonces el resultado del juego r dado por ⟨ a 1 , 1, a 2 , a 3 , ...⟩ está permitido por p de modo que g ( f ( r )) debe estar en U ; Además, el resultado del juego r ' dado por ⟨ a 1 , 1 + a 2 , a 3 , ...⟩ 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 los términos excepto en el primero a 1 + 1 , por lo que están en clases complementarias equivalentes, por lo tanto, g ( f ( r )) y g ( f ( r ')) no pueden estar ambos en U, lo que contradice que p es una estrategia ganadora.
La consistencia del axioma de determinación está estrechamente relacionada con la cuestión de la consistencia de los axiomas de grandes cardinales . Por un teorema de Woodin , la consistencia de la teoría de conjuntos de Zermelo-Fraenkel sin elección (ZF) junto con el axioma de determinación es equivalente a la consistencia de la teoría de conjuntos de Zermelo-Fraenkel con elección (ZFC) junto con la existencia de infinitos cardinales de Woodin . Dado que los cardinales de Woodin son fuertemente inaccesibles , si AD es consistente, entonces también lo son una infinidad de cardinales inaccesibles.
Además, si a la hipótesis de un conjunto infinito de cardinales de Woodin se añade la existencia de un cardinal medible mayor que todos ellos, surge una teoría muy fuerte de conjuntos medibles de reales de Lebesgue, pues entonces es demostrable que el axioma de determinabilidad es verdadero en L(R) , y por tanto que todo conjunto de números reales en L(R) está determinado.
Yiannis Moschovakis introdujo los ordinales δ1
n, que es el límite superior de la longitud de Δ1
n-normas (inyecciones de un Δ1
nestablecido en los ordinales), donde Δ1
nes un nivel de la jerarquía proyectiva . Suponiendo AD, todos los δ1
nson ordinales iniciales y tenemos δ1
2 n + 2= (δ1
2 n + 1) + , y para n < ω, el 2 n -ésimo cardinal de Suslin es igual a δ1
2 n −1. [1]