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 de dos personas 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 verdadera 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, I y II , eligen alternativamente números naturales.
Después de infinitos movimientos, se genera una secuencia. El jugador I 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 todos los juegos con conjunto ganador son un conjunto proyectivo (ver Determinación proyectiva ), y que AD se cumple en L(R) .
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 S1 de todas las estrategias del primer jugador en un juego ω G tiene la misma cardinalidad que el continuo . Lo mismo ocurre con el conjunto S2 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 S1 como S2, y construimos A de manera que sea un contraejemplo.
Comenzamos con los conjuntos vacíos A y B. Sea α J el índice de las estrategias en S1 y S2. Necesitamos considerar todas las estrategias S1 = {s1(α)} del primer jugador y todas las estrategias S2 = {s2(α)} del segundo jugador para asegurarnos de que para cada estrategia haya una estrategia del otro jugador que gane. En contra. 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 s1 del primer jugador, existe un α J tal que s1 = s1(α), y A se ha construido de modo que s1(α) falla (en ciertas elecciones {b(2), b(4) , b(6), ...} del segundo jugador). Por tanto, s1 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 Axiom_of_choice#Quotations .
En un juego ω, los dos jugadores generan la secuencia , un elemento en ω ω , donde nuestra convención es que 0 no es un número natural, por lo tanto, ninguno de los jugadores puede elegirlo. Defina la función de modo que f(r) sea la secuencia única de longitud ω cuyos valores estén en {0, 1}, cuyo primer término sea igual a 0 y cuya secuencia de ejecuciones (consulte codificación de longitud de ejecución ) sea igual a r. (Se puede demostrar que f es inyectiva. La imagen es el subconjunto de secuencias que comienzan con 0 y que finalmente no son constantes. Formalmente, f es la función del signo de interrogación de Minkowski , es el espacio de Cantor y ω ω es el espacio de Baire . )
Observe la relación de equivalencia tal que dos sucesiones son equivalentes si y sólo si difieren en un número finito de términos. Esto divide el conjunto en clases de equivalencia, y sea T el conjunto de clases de equivalencia (de modo que T tenga la cardinalidad del continuo). Definir que lleva una secuencia a su clase de equivalencia. Defina el complemento de cualquier secuencia s en como la secuencia s 1 que difiere en cada término. Defina la función de modo que para cualquier secuencia s en , h aplicada a la clase de equivalencia de s sea 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. Uno podemos 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 elija 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 está en U si h(t) no está en U.
A continuación, definimos el subconjunto A de ω ω en el que gana el jugador 1: A es el conjunto de todos los r tales que g(f(r)) está en U. Ahora afirmamos que ninguno de los jugadores tiene una estrategia ganadora, usando una estrategia -argumento de robo . 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 el jugador 1 es el siguiente en jugar; de lo contrario, el jugador 2 es el siguiente en jugar).
Supongamos que q es una estrategia ganadora (determinista) para el jugador 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 el jugador 1 especifica en p que a(1) = 1 + b 1 . (A grandes rasgos, el jugador 1 ahora juega como segundo jugador en un segundo juego paralelo; el set ganador del jugador 1 en el segundo juego es igual al set ganador del jugador 2 en el juego original, y esto es una contradicción. Sin embargo, continuamos de manera más formal).
Supongamos que la respuesta del jugador 2 (siempre según q) a [1 + b 1 ] es b 2 , y la respuesta del jugador 2 a [1, b 1 , b 2 ] es b 3 . Cuando el jugador 1 está construyendo p, su único objetivo es vencer a q y, por tanto, sólo tiene que manejar la respuesta b 2 a su primer movimiento. El jugador 1 especifica que su respuesta a [1 + b 1 , b 2 ] es b 3 . En general, incluso para n, denota la respuesta del jugador 2 a [1 + b 1 , ..., b n-1 ] por b n y la respuesta del jugador 2 a [1, b 1 , ..., b n ] por b norte + 1 . Luego, el jugador 1 especifica en p que su respuesta 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 el jugador 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), entonces 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 ambas 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 el jugador 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 del jugador 1. En general, incluso para n, denota la respuesta del jugador 1 a [a 1 , 1] (si n = 2) o [a 1 , 1, a 2 , ... a n-1 ] por an y la respuesta del jugador 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; 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 que 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 de reales mensurables 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 , que es el límite superior de la longitud de las normas (inyecciones de un conjunto en los ordinales), donde es un nivel de la jerarquía proyectiva . Suponiendo AD, todos son ordinales iniciales , y tenemos , y para el cardinal Suslin es igual a . [1]
