En la teoría de conjuntos descriptiva , el Borel determinación teorema afirma que cualquier juego de Gale-Stewart cuyo conjunto de recompensa es un conjunto de Borel está determinada , lo que significa que uno de los dos jugadores tendrá un ganador de la estrategia para el juego.
El teorema fue probado por Donald A. Martin en 1975 y se aplica en la teoría descriptiva de conjuntos para demostrar que los conjuntos de Borel en los espacios polacos tienen propiedades de regularidad, como la propiedad del conjunto perfecto y la propiedad de Baire .
El teorema también es conocido por sus propiedades metamatemáticas . En 1971, antes de que se probara 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 reemplazo . Los resultados posteriores mostraron que los teoremas de determinación más fuertes no se pueden probar en la teoría de conjuntos de Zermelo-Fraenkel, aunque son relativamente consistentes con ella, si ciertos grandes cardinales son consistentes.
Fondo
Juegos de Gale-Stewart
Un juego de Gale-Stewart es un juego de dos jugadores con información perfecta. El juego se define utilizando un conjunto A , y se denota G A . Los dos jugadores alternan turnos, y cada jugador está al tanto de todos los movimientos antes de realizar el siguiente. En cada turno, cada jugador elige un solo 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.
La jugada continúa sin fin, de modo que una sola jugada del juego determina una secuencia infinita. de los elementos de A . El conjunto de todas esas secuencias se denota 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, el jugador II gana; no hay ataduras.
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 tales juegos cambia en cada turno. Sin embargo, este tipo de caso puede manejarse declarando que un jugador que hace un movimiento ilegal pierde inmediatamente, de modo que la noción de juego de Gale-Stewart generaliza de hecho el concepto de juego definido por un árbol de juego .
Estrategias ganadoras
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 uniforme 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 elementos de A de longitud impar y devuelve elementos de A , de modo que el jugador II ganará todas las jugadas de la forma.
A lo sumo, un jugador puede tener una estrategia ganadora; si ambos jugadores tuvieran estrategias ganadoras, y jugaran las estrategias 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 recompensas en particular, se dice que ese conjunto de recompensas está determinado .
Topología
Para un conjunto A dado , la determinación de un subconjunto de A ω 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 del producto resultante , donde A ω se ve como un producto topológico numerablemente 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. Por 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í. Para cada una de las secuencias finitas sigma en el árbol, el conjunto de todos los elementos de un ω que comienzan con σ es un conjunto abierto básico en la topología de una . 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 está abierto.
Los conjuntos de Borel de A ω son la clase más pequeña de subconjuntos de A ω que incluye los conjuntos abiertos y se cierra bajo complemento y unión contable. Es decir, los conjuntos de Borel son el σ-álgebra más pequeño de los subconjuntos de A ω que contienen 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.
Resultados anteriores
Gale y Stewart (1953) demostraron que si el conjunto de pagos es un subconjunto abierto o cerrado de A ω, entonces siempre se determina el juego Gale-Stewart con ese conjunto de pagos. Durante los siguientes veinte años, esto se extendió a niveles ligeramente más altos de la jerarquía 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 Borel de A ω . Se sabía que, usando 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 se determinaron todos los subconjuntos de Borel del espacio de Cantor ({0,1} ω ) requeriría el uso repetido del axioma de reemplazo , un axioma que normalmente no se requiere para demostrar teoremas sobre objetos "pequeños" como como espacio Cantor.
Determinación borel
Donald A. Martin (1975) demostró que para cualquier conjunto A , se determinan todos los subconjuntos de Borel de A ω . Debido a que 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 revisión 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 completos separables). El teorema de la determinación de Borel se ha utilizado para establecer muchas propiedades [ cita requerida ] de los subconjuntos de Borel de estos espacios. Por ejemplo, todos los subconjuntos de Borel de espacios polacos tienen la propiedad de conjunto perfecto y la propiedad de Baire .
Aspectos de la teoría de conjuntos
El teorema de la determinación de Borel es de interés por sus propiedades metametematicas , 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 teóricos de conjuntos donde no se asume el axioma de elección, esto se puede eludir considerando estrategias generalizadas conocidas como cuasestrategias (Kechris 1995, p. 139) o solo considerando juegos donde A es el conjunto de números naturales, como en el axioma de la 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 conjunto de potencias pueda repetirse incontables 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 con V κ para valores significativamente mayores de κ, como cuando κ es un cardenal fuertemente inaccesible . El teorema de Friedman de 1971 mostró que existe un modelo de teoría de conjuntos de Zermelo (con el axioma de elección) en el que falla la determinación de Borel y, por lo tanto, la teoría de conjuntos de Zermelo no puede probar el teorema de determinación de Borel.
Formas más fuertes de determinación
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 determinante de Borel. Están estrechamente relacionados con los grandes axiomas cardinales .
El axioma de la determinación proyectiva establece que todos los subconjuntos proyectivos de un espacio polaco están determinados. Se sabe que no puede demostrarse en ZFC, pero es relativamente coherente con él y está implícito en ciertos axiomas cardinales grandes . La existencia de un cardinal mensurable es suficiente para implicar sobre 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 igual a ciertos axiomas cardinales grandes.
Referencias
- Friedman, Harvey (1971). "Teoría de conjuntos superiores y práctica matemática" . Anales de lógica matemática . 2 (3): 325–357. doi : 10.1016 / 0003-4843 (71) 90018-0 .
- L. Bukovský, revisor, Mathematical Reviews , MR284327 .
- Gale, D. y FM Stewart (1953). "Juegos infinitos con información perfecta". Contribuciones a la teoría de juegos, vol. 2 . Annals of Mathematical Studies, vol. 28. 28 . Prensa de la Universidad de Princeton. págs. 245-266.
- S. Sherman, revisor, Mathematical Reviews , MR54922 .
- Alexander Kechris (1995). Teoría de conjuntos descriptiva clásica . Textos de Posgrado en Matemáticas . 156 . ISBN 0-387-94374-9.
- Martin, Donald A. (1975). "Determinación Borel". Annals of Mathematics . Segunda Serie. 102 (2): 363–371. doi : 10.2307 / 1971035 .
- John Burgess, revisor. Reseñas de Matemáticas , MR403976 .
- Martin, Donald A. (1982). "Una prueba puramente inductiva de la determinación de Borel". Teoría de la recursividad . Proc. Simpos. Pure Math (Actas del instituto de verano AMS-ASL celebrado en Ithaca, Nueva York ed.). págs. 303-308.
- FR Drake, revisor, Mathematical Reviews , MR791065 .
enlaces externos
- Determinación borel y metamatemática . Ross Bryant. Tesis de maestría, Universidad del Norte de Texas, 2001.
- "Grandes cardenales y determinación" en la Enciclopedia de Filosofía de Stanford