En matemáticas , el axioma de determinabilidad (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 bipersonales de longitud ω . AD afirma que cada juego de un determinado tipo está determinado ; es decir, uno de los dos jugadores tiene una estrategia ganadora .
La motivación de Steinhaus y Mycielski para desarrollar 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 sólo una forma débil del axioma de elección (AC) pero contiene todos los elementos reales. y todos los números ordinales . Algunas consecuencias de AD se derivaron de teoremas demostrados anteriormente por Stefan Banach , Stanisław Mazur y Morton Davis. Mycielski y Stanisław Świerczkowski contribuyeron con otro: AD implica que todos los conjuntos de números reales son medibles según Lebesgue . Posteriormente, 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. Suponiendo la existencia de algunos números cardinales incontables análogos a ℵ , demostraron la conjetura original de Mycielski y Steinhaus de que AD es cierto en L(R).
El axioma de determinabilidad se refiere a juegos de la siguiente forma específica: Considere un subconjunto A del espacio de Baire ω ω de todas las sucesiones infinitas de números naturales . Dos jugadores, 1 y 2 , eligen alternativamente números naturales.
Eso genera la secuencia ⟨ n i ⟩ i ∈ω después de infinitos movimientos. El jugador 1 gana el juego si y sólo si la secuencia generada es un elemento de A. El axioma de determinabilidad es la afirmación de que todos estos 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 abierto , el juego es esencialmente finito y, por tanto, está determinado. De manera similar, si A es un conjunto cerrado , entonces el juego está determinado. Donald A. Martin demostró en 1975 que 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 se determina si tiene un conjunto proyectivo como 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 por tanto que todo conjunto de reales tiene la propiedad de Baire ).
Bajo el supuesto del axioma de elección, presentamos dos construcciones separadas de contraejemplos del axioma de determinabilidad. De ello se deduce 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 ocurre con 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 el continuo, y podemos hacerlo de tal manera que cualquier porción inicial adecuada tenga una cardinalidad menor que el continuo. Usamos el conjunto J bien ordenado obtenido para indexar tanto S 1 como S 2 , y construimos A de 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 hay una estrategia del otro jugador que le gana. Por cada estrategia del jugador considerada generaremos una secuencia que le dará 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 mediante recursividad 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 A se ha construido de modo que s 1 ( α ) falla (en ciertas elecciones ⟨ b 2 , b 4 , b 6 , ...⟩ del segundo jugador). Por 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 indica 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 secuencia única de longitud ω con valores en {0, 1} cuyo primer término es igual a 0, y cuya secuencia de ejecuciones (ver ejecución -codificación de longitud ) es igual a r. ( Se puede demostrar que tal f es inyectiva. La imagen es el subconjunto de {0, 1} ω de secuencias que comienzan con 0 y que eventualmente no son 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 sólo 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 tenga la cardinalidad del continuo). Defina {0, 1} ω → T que lleve una secuencia a su clase de equivalencia. Defina el complemento de cualquier secuencia s en {0, 1} ω como la secuencia s 1 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, tal que t ∈ U sif 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 ninguno de los jugadores tiene una estrategia ganadora, usando una estrategia de robo de estrategias. argumento . Denota 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 . (Aproximadamente, 1 ahora juega como 2 en un segundo juego paralelo; el set ganador de 1 en el segundo juego es igual al set 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, establezca la respuesta de 1 en ⟨1 + b 1 , b 2 ⟩ es b 3 . En general, para n par, denota 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 norte +1 . Entonces especifico 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 estar ganando 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 todos los términos excepto en el primero (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 equivalentes en 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 finito arbitrariamente grande de términos difieran. Sea un 1 el primer movimiento de 1 . En general, para n par, denota la respuesta de 1 a ⟨ a 1 , 1⟩ (si n = 2) o ⟨ a 1 , 1, a 2 , ..., a n−1 ⟩ por a n y 1 ' s respuesta 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 ; también 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 el primero a 1 + 1, por lo que están en clases equivalentes en complemento, 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 coherencia del axioma de determinabilidad está estrechamente relacionada con la cuestión de la coherencia de los grandes axiomas cardinales . Según un teorema de Woodin , la consistencia de la teoría de conjuntos de Zermelo-Fraenkel sin elección (ZF) junto con el axioma de determinabilidad 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 cardenales de Woodin son fuertemente inaccesibles , si AD es consistente, también lo son una infinidad de cardenales inaccesibles.
Además, si a la hipótesis de un conjunto infinito de cardinales de Woodin se le suma la existencia de un cardenal mensurable mayor que todos ellos, surge una teoría muy fuerte de los conjuntos mensurables de reales de Lebesgue, ya que entonces es demostrable que el axioma de determinabilidad es cierto en L(R) y, por tanto, que todo conjunto de números reales en L(R) está determinado.
Yiannis Moschovakis introdujo los ordinales δ1
norte, que es el límite superior de la longitud de Δ1
norte-normas (inyecciones de un Δ1
nortepuesto en los ordinales), donde Δ1
nortees un nivel de la jerarquía proyectiva . Suponiendo AD, todos δ1
norteson ordinales iniciales y tenemos δ1
2 norte +2= (δ1
2 norte +1) + , y para n < ω, el 2 n -ésimo cardinal de Suslin es igual a δ1
2 norte −1. [1]