Teorema de determinación de Borel

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 . Un juego de Gale-Stewart es un juego de dos jugadores, posiblemente infinito, donde ambos jugadores tienen información perfecta y no interviene el azar.

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 mostrar que los conjuntos de Borel en espacios polacos tienen propiedades de regularidad tales 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 un uso repetido de instancias del esquema axiomático de reemplazo . Resultados posteriores demostraron que no se pueden demostrar teoremas de determinatividad más fuertes en la teoría de conjuntos de Zermelo-Fraenkel, aunque son relativamente consistentes con ella, si ciertos cardinales grandes 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 mediante un conjunto A y se denota como G _A. Los dos jugadores se turnan y cada uno 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 restricciones. El juego se puede visualizar mediante el siguiente diagrama, en el que los movimientos se realizan de izquierda a derecha, con los movimientos del jugador I arriba y los del jugador II abajo.

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots \end{matrix}}$

El juego continúa sin fin, de modo que una sola jugada determina una secuencia infinita. $\langle a_{1},a_{2},a_{3}\ldots \rangle$ de elementos de A. El conjunto de todas estas secuencias se denota A ^ω . Los jugadores conocen, desde el inicio del juego, un conjunto de pagos fijo (también llamado 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 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 puede resolverse declarando que un jugador que realiza un movimiento ilegal pierde inmediatamente, de modo que la noción de juego de Gale-Stewart generaliza el concepto de juego definido por un árbol de juego .

Estrategias ganadoras

Una estrategia ganadora para un jugador es una función que le indica qué movimiento realizar 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

${\begin{matrix}\mathrm {I} &a_{1}=f(\langle \rangle )&\quad &a_{3}=f(\langle a_{1},a_{2}\rangle )&\quad &a_{5}=f(\langle a_{1},a_{2},a_{3},a_{4}\rangle )&\quad &\cdots \\\mathrm {II} &\quad &a_{2}&\quad &a_{4}&\quad &a_{6}&\cdots .\end{matrix}}$

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 tal manera que el jugador II ganará cada jugada de la forma

${\begin{matrix}\mathrm {I} &a_{1}&\quad &a_{3}&\quad &a_{5}&\quad &\cdots \\\mathrm {II} &\quad &a_{2}=g(\langle a_{1}\rangle )&\quad &a_{4}=g(\langle a_{1},a_{2},a_{3}\rangle )&\quad &a_{6}=g(\langle a_{1},a_{2},a_{3},a_{4},a_{5}\rangle )&\cdots .\end{matrix}}$

Como máximo, un jugador puede tener una estrategia ganadora; si ambos jugadores tuvieran estrategias ganadoras y las usaran 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 determinado, se dice que ese conjunto de pagos 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 producto resultante , donde A ^ω se considera 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 los 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 lleva 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 precisamente 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 ⟩ ; 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 de A. Los conjuntos abiertos de A ^ω son precisamente los conjuntos que se pueden expresar 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 es cerrada bajo el complemento y la unión numerable. Es decir, los conjuntos de Borel son el á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 según la cantidad de veces que se requieren las operaciones de complemento y unión numerable para generarlos 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 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 mediante demostraciones cada vez más complejas. Esto llevó a la cuestión de si el juego debe estar determinado 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 de instancias del esquema axiomático de reemplazo , un axioma que normalmente no se requiere para probar teoremas sobre estructuras "pequeñas" como el espacio de Cantor que no son explícitamente "conjuntistas" (es decir, construidas con el propósito de explorar la teoría axiomática de conjuntos).

Determinación de Borel

Donald A. Martin (1975) demostró que para cualquier conjunto A , todos los subconjuntos de Borel de A ^ω están determinados. Debido a que la demostración original era bastante compleja, Martin publicó una demostración más breve en 1982 que no requería tantos conocimientos técnicos. En su reseña del artículo de Martin, Drake describe la segunda demostración 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 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 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. ${\mathcal {A}}$ .

Aspectos de la teoría de conjuntos

El teorema de determinatividad de Borel resulta interesante tanto por sus propiedades metamatemáticas como por sus consecuencias en la teoría descriptiva de conjuntos.

La determinación de conjuntos cerrados de A ^ω para un 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 eludir considerando estrategias generalizadas conocidas como cuasi-estrategias (Kechris 1995, p. 139) o considerando solo juegos donde A es el conjunto de los números naturales, como en el axioma de determinación .

La teoría de conjuntos de Zermelo (Z) es (aproximadamente) la teoría de conjuntos de Zermelo-Fraenkel sin el esquema axiomático de reemplazo. Una forma en que difiere de ZF es que Z no prueba que la operación de conjunto potencia pueda iterarse infinitas veces comenzando con un conjunto infinito arbitrario. En particular, V _{ω + ω} , un nivel particular de la jerarquía acumulativa con rango numerable , es un modelo de la teoría de conjuntos de Zermelo. El esquema axiomático de reemplazo, por otro lado, solo se satisface con V _κ para valores de κ significativamente mayores, como cuando κ es un cardinal fuertemente inaccesible . El teorema de Friedman de 1971 demostró que existe un modelo de la teoría de conjuntos de Zermelo (con el axioma de elección) en el que falla la determinabilidad de Borel, y por lo tanto la teoría de conjuntos de Zermelo por sí sola no puede probar el teorema de determinabilidad de Borel. ^{[ 1 ]}

La existencia de todos los números beth de índice contable es suficiente para probar el teorema de determinación de Borel. ^{[ 2 ]}

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 determinabilidad, más fuertes que la determinabilidad de Borel. Estos principios están estrechamente relacionados con los axiomas cardinales grandes .

El axioma de la determinabilidad proyectiva establece que todos los subconjuntos proyectivos de un espacio polaco están determinados. Se sabe que es indemostrable en ZFC, pero es relativamente consistente con él y se deduce de ciertos axiomas de cardinales grandes . La existencia de un cardinal medible es suficiente para implicar, sobre ZFC, que todos los subconjuntos analíticos de los espacios polacos están determinados, lo cual es más débil que la determinabilidad proyectiva completa.

El axioma de determinatividad 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 axiomas cardinales grandes.

Referencias

↑ H. Friedman, "Teoría de conjuntos superiores y práctica matemática", Anales de lógica matemática 2 (1971). págs. 326-357.
↑ Leinster, Tom (23 de julio de 2021). "La determinación de Borel no requiere reemplazo" . The n-Category Café . Universidad de Texas en Austin . Recuperado el 25 de agosto de 2021 .

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 , MR 0284327 .
Gale, D. y FM Stewart (1953). «Juegos infinitos con información perfecta». Contribuciones a la teoría de juegos, vol. 2. Anales de Estudios Matemáticos , vol. 28. Princeton University Press, pp. 245-266 .
- S. Sherman, revisor, Mathematical Reviews , MR 0054922 .
Alexander Kechris (1995). Teoría clásica descriptiva de conjuntos . Textos de posgrado en matemáticas . Vol. 156. ISBN 0-387-94374-9.
Martin, Donald A. (1975). "Determinación de Borel". Anales de Matemáticas . Segunda Serie. 102 (2): 363– 371. doi : 10.2307/1971035 . JSTOR 1971035 .
- John Burgess, revisor. Mathematical Reviews , MR 0403976 .
Martin, Donald A. (1982). "Una demostración puramente inductiva de la determinabilidad de Borel". Teoría de la recursión . Actas del Simposio de Matemáticas Puras (Actas del Instituto de Verano AMS - ASL celebrado en Ithaca, Nueva York ). págs. 303-308 .
- FR Drake, revisor, Mathematical Reviews , MR 0791065 .

Enlaces externos

Determinación de Borel y metamatemáticas . Ross Bryant. Tesis de maestría, Universidad del Norte de Texas, 2001.
"Los cardenales grandes y la determinación" en la Enciclopedia de Filosofía de Stanford.

[1] H. Friedman, "Teoría de conjuntos superiores y práctica matemática", Anales de lógica matemática 2 (1971). págs. 326-357.

[2] Leinster, Tom (23 de julio de 2021). "La determinación de Borel no requiere reemplazo" . The n-Category Café . Universidad de Texas en Austin . Recuperado el 25 de agosto de 2021 .

[ 1 ]

[ 2 ]