En la teoría descriptiva de conjuntos , el teorema de determinación de Borel establece que cualquier juego de Gale-Stewart cuyo conjunto de pagos sea un conjunto de Borel está determinado , lo que significa que uno de los dos jugadores tendrá una estrategia ganadora para el juego. Un juego de Gale-Stewart es un juego posiblemente infinito para dos jugadores, donde ambos jugadores tienen información perfecta y no hay aleatoriedad.
El teorema es una generalización de gran alcance del teorema de Zermelo sobre la determinabilidad de los juegos finitos. Fue demostrado por Donald A. Martin en 1975 y se aplica en la teoría descriptiva de conjuntos para demostrar que los conjuntos de Borel en espacios polacos tienen propiedades de regularidad como la propiedad del conjunto perfecto .
El teorema también es conocido por sus propiedades metamatemáticas . En 1971, antes de que se demostrara el teorema, Harvey Friedman demostró que cualquier demostración del teorema en la teoría de conjuntos de Zermelo-Fraenkel debe hacer un uso repetido del axioma de sustitución . Resultados posteriores mostraron que no se pueden probar teoremas de determinabilidad más fuertes en la teoría de conjuntos de Zermelo-Fraenkel, aunque son relativamente consistentes con ella, si ciertos cardinales grandes son consistentes.
Un juego de Gale-Stewart es un juego de información perfecta para dos jugadores. El juego se define utilizando un conjunto A y se denota G A . Los dos jugadores alternan turnos y cada jugador es consciente de todos los movimientos antes de realizar el siguiente. En cada turno, cada jugador elige un único elemento de A para jugar. El mismo elemento podrá ser elegido más de una vez sin restricción. El juego se puede visualizar a través del siguiente diagrama, en el que los movimientos se realizan de izquierda a derecha, con los movimientos del jugador I arriba y los movimientos del jugador II abajo.
El juego continúa sin fin, de modo que una sola jugada determina una secuencia infinita de elementos de A. El conjunto de todas esas secuencias se denota como A ω . Los jugadores son conscientes, desde el comienzo del juego, de un conjunto de pagos fijo (también conocido como conjunto ganador ) que determinará quién gana. El conjunto de pagos es un subconjunto de A ω . Si la secuencia infinita creada por una jugada del juego está en el conjunto de pagos, entonces el jugador I gana. De lo contrario, gana el jugador II; no hay ataduras.
Inicialmente, esta definición no parece incluir los juegos tradicionales de información perfecta, como el ajedrez, ya que el conjunto de movimientos disponibles en dichos juegos cambia en cada turno. Sin embargo, este tipo de casos se pueden manejar declarando que un jugador que realiza un movimiento ilegal pierde inmediatamente, de modo que la noción de juego de Gale-Stewart de hecho generaliza el concepto de juego definido por un árbol de juego .
Una estrategia ganadora para un jugador es una función que le dice al jugador qué movimiento hacer desde cualquier posición en el juego, de modo que si el jugador sigue la función seguramente ganará. Más específicamente, una estrategia ganadora para el jugador I es una función f que toma como entrada secuencias de elementos de A de longitud par y devuelve un elemento de A , de modo que el jugador I ganará cada jugada de la forma
Una estrategia ganadora para el jugador II es una función g que toma secuencias de longitud impar de elementos de A y devuelve elementos de A , de manera que el jugador II ganará cada jugada de la forma
Como máximo un jugador puede tener una estrategia ganadora; Si ambos jugadores tenían estrategias ganadoras y las jugaban entre sí, solo una de las dos estrategias podría ganar esa jugada del juego. Si uno de los jugadores tiene una estrategia ganadora para un conjunto de pagos en particular, se dice que ese conjunto de pagos está determinado .
Para un conjunto dado A , la determinación de un subconjunto de A ω depende en cierta medida de su estructura topológica. A los efectos de los juegos de Gale-Stewart, el conjunto A está dotado de la topología discreta y A ω está dotado de la topología del producto resultante , donde A ω se considera un producto topológico contablemente infinito de A consigo mismo. En particular, cuando A es el conjunto {0,1}, la topología definida en A ω es exactamente la topología ordinaria en el espacio de Cantor , y cuando A es el conjunto de números naturales, es la topología ordinaria en el espacio de Baire .
El conjunto A ω puede verse como el conjunto de caminos a través de un determinado árbol , lo que conduce a una segunda caracterización de su topología. El árbol consta de todas las secuencias finitas de elementos de A , y los hijos de un nodo particular σ del árbol son exactamente las secuencias que extienden σ en un elemento. Así, si A = { 0, 1 }, el primer nivel del árbol consta de las secuencias ⟨ 0 ⟩ y ⟨ 1 ⟩; el segundo nivel consta de las cuatro secuencias ⟨ 0, 0 ⟩, ⟨ 0, 1 ⟩, ⟨ 1, 0 ⟩, ⟨ 1, 1 ⟩; etcétera. Para cada una de las secuencias finitas σ en el árbol, el conjunto de todos los elementos de A ω que comienzan con σ es un conjunto abierto básico en la topología de A. Los conjuntos abiertos de A ω son precisamente los conjuntos expresables como uniones de estos conjuntos abiertos básicos. Los conjuntos cerrados , como es habitual, son aquellos cuyo complemento es abierto.
Los conjuntos de Borel de A ω son la clase más pequeña de subconjuntos de A ω que incluye los conjuntos abiertos y está cerrado bajo complemento y unión contable. Es decir, los conjuntos de Borel son el σ-álgebra más pequeño de subconjuntos de A ω que contiene todos los conjuntos abiertos. Los conjuntos de Borel se clasifican en la jerarquía de Borel según cuántas veces se requieren las operaciones de complemento y unión contable para producirlos a partir de conjuntos abiertos.
Gale y Stewart (1953) demostraron que si el conjunto de pagos es un subconjunto abierto o cerrado de A ω, entonces el juego Gale-Stewart con ese conjunto de pagos siempre está determinado. Durante los siguientes veinte años, esto se extendió a niveles ligeramente superiores de la jerarquía de Borel mediante pruebas cada vez más complicadas. Esto llevó a la pregunta de si el juego debe determinarse siempre que el conjunto de pagos sea un subconjunto de Borel de A ω . Se sabía que, utilizando el axioma de elección , es posible construir un subconjunto de {0,1} ω que no está determinado (Kechris 1995, p. 139).
Harvey Friedman (1971) demostró que cualquier prueba de que todos los subconjuntos de Borel del espacio de Cantor ({0,1} ω ) estaban determinados requeriría el uso repetido del axioma de reemplazo , un axioma que normalmente no se requiere para probar teoremas sobre objetos "pequeños" como como espacio de Cantor.
Donald A. Martin (1975) demostró que para cualquier conjunto A , todos los subconjuntos de Borel de A ω están determinados. Como la prueba original era bastante complicada, Martin publicó una prueba más corta en 1982 que no requería tanta maquinaria técnica. En su reseña del artículo de Martin, Drake describe la segunda prueba como "sorprendentemente sencilla".
El campo de la teoría descriptiva de conjuntos estudia las propiedades de los espacios polacos (esencialmente, espacios métricos separables completos). El teorema de determinación de Borel se ha utilizado para establecer muchas [ cita necesaria ] propiedades de los subconjuntos de Borel de estos espacios. Por ejemplo, todos los subconjuntos analíticos de espacios polacos tienen la propiedad de conjunto perfecto , la propiedad de Baire , y son medibles según Lebesgue . Sin embargo, las dos últimas propiedades se pueden demostrar más fácilmente sin utilizar la determinación de Borel, demostrando que las σ-álgebras de conjuntos medibles o conjuntos con la propiedad de Baire son cerradas bajo la operación de Suslin .
El teorema de determinabilidad de Borel es de interés por sus propiedades metamatemáticas así como por sus consecuencias en la teoría descriptiva de conjuntos.
La determinación de conjuntos cerrados de A ω para A arbitrario es equivalente al axioma de elección sobre ZF (Kechris 1995, p. 139). Cuando se trabaja en sistemas de teoría de conjuntos donde no se asume el axioma de elección, esto se puede evitar considerando estrategias generalizadas conocidas como cuasiestrategias (Kechris 1995, p. 139) o considerando únicamente juegos donde A es el conjunto de números naturales, como en el axioma de determinabilidad .
La teoría de conjuntos de Zermelo (Z) es la teoría de conjuntos de Zermelo-Fraenkel sin el axioma de reemplazo. Se diferencia de ZF en que Z no prueba que la operación del conjunto de potencias pueda repetirse incontablemente muchas veces comenzando con un conjunto arbitrario. En particular, V ω + ω , un nivel contable particular de la jerarquía acumulativa , es un modelo de la teoría de conjuntos de Zermelo. El axioma de reemplazo, por otro lado, solo lo satisface V κ para valores significativamente mayores de κ, como cuando κ es un cardinal fuertemente inaccesible . El teorema de Friedman de 1971 demostró que existe un modelo de teoría de conjuntos de Zermelo (con el axioma de elección) en el que falla la determinabilidad de Borel y, por tanto, la teoría de conjuntos de Zermelo no puede probar el teorema de determinación de Borel. [1]
La existencia de todos los números Beth de índice contable es suficiente para demostrar el teorema de determinabilidad de Borel. [2]
En la teoría descriptiva de conjuntos se estudian varios principios de la teoría de conjuntos sobre la determinabilidad más fuertes que la determinación de Borel. Están estrechamente relacionados con los grandes axiomas cardinales .
El axioma de determinación proyectiva establece que todos los subconjuntos proyectivos de un espacio polaco están determinados. Se sabe que no es demostrable en ZFC, pero es relativamente consistente con él y está implícito en ciertos grandes axiomas cardinales . La existencia de un cardinal mensurable es suficiente para implicar sobre ZFC que todos los subconjuntos analíticos de espacios polacos están determinados.
El axioma de determinabilidad establece que todos los subconjuntos de todos los espacios polacos están determinados. Es inconsistente con ZFC pero en ZF + DC (teoría de conjuntos de Zermelo-Fraenkel más el axioma de elección dependiente ) es equiconsistente con ciertos grandes axiomas cardinales.
