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 de dos jugadores posiblemente infinito, donde ambos jugadores tienen información perfecta y no hay aleatoriedad involucrada.
El teorema es una generalización de gran alcance del teorema de Zermelo sobre la determinación 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 de 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 uso repetido del axioma de reemplazo . Resultados posteriores mostraron que los teoremas de determinación más fuertes no pueden demostrarse en la teoría de conjuntos de Zermelo-Fraenkel, aunque son relativamente consistentes con ella, si ciertos cardinales grandes son consistentes.
Un juego 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 se turnan y cada jugador conoce todos los movimientos antes de realizar el siguiente. En cada turno, cada jugador elige un único elemento de A para jugar. El mismo elemento puede elegirse 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 del juego determina una secuencia infinita de elementos de A . El conjunto de todas esas secuencias se denota A ω . Los jugadores conocen, desde el comienzo del juego, un conjunto de pagos fijos (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, el jugador II gana; no hay empates.
Esta definición inicialmente 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 caso se puede 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 juegos .
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 modo que el jugador II ganará cada jugada de la forma
Como máximo, un jugador puede tener una estrategia ganadora; si ambos jugadores tuvieran estrategias ganadoras y las utilizaran entre sí, solo una de las dos estrategias podría ganar esa partida. 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 , el que un subconjunto de A ω sea determinado depende en cierta medida de su estructura topológica. Para los propósitos de los juegos de Gale–Stewart, el conjunto A está dotado de la topología discreta , y A ω está dotado de la topología de producto resultante , donde A ω se considera como un producto topológico infinito numerable 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 cierto á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. Por lo tanto, 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 ⟩; y así sucesivamente. 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 en 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á cerrada bajo complemento y unión contable. Es decir, los conjuntos de Borel son la σ-álgebra más pequeña de subconjuntos de A ω que contiene todos los conjuntos abiertos. Los conjuntos de Borel se clasifican en la jerarquía de Borel en función de 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 de 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 a través de 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 demostrar teoremas sobre objetos "pequeños" como el 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 tantos recursos técnicos. 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 requerida ] propiedades de los subconjuntos de Borel de estos espacios. Por ejemplo, todos los subconjuntos analíticos de los espacios polacos tienen la propiedad de conjunto perfecto , la propiedad de Baire , y son medibles según el método de Lebesgue . Sin embargo, las dos últimas propiedades se pueden demostrar más fácilmente sin utilizar la determinación de Borel, mostrando que las σ-álgebras de conjuntos medibles o conjuntos con la propiedad de Baire son cerradas bajo la operación de Suslin .
El teorema de determinación de Borel es de interés por sus propiedades metamatemáticas así como por sus consecuencias en la teoría de conjuntos descriptivos.
La determinación de conjuntos cerrados de A ω para un número arbitrario de A 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 supone el axioma de elección, esto se puede evitar considerando estrategias generalizadas conocidas como cuasiestrategias (Kechris 1995, p. 139) o considerando solo juegos donde A es el conjunto de números naturales, como en el axioma de determinación .
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 de conjuntos de potencia se pueda iterar un número incontable de 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 se satisface por V κ para valores significativamente mayores de κ, como cuando κ es un cardinal fuertemente inaccesible . El teorema de Friedman de 1971 mostró que existe un modelo de la teoría de conjuntos de Zermelo (con el axioma de elección) en el que la determinación de Borel falla y, por lo 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 determinación de Borel. [2]
En la teoría descriptiva de conjuntos se estudian varios principios de la teoría de conjuntos sobre la determinación 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 axiomas de cardinales grandes . La existencia de un cardinal medible es suficiente para implicar en ZFC que todos los subconjuntos analíticos de los espacios polacos están determinados.
El axioma de determinación establece que todos los subconjuntos de todos los espacios polacos están determinados. Es incompatible 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 axiomas cardinales importantes.
