Hispanopedia Wiki
Articulo de referencia

Juego analítico Lightface

En la teoría descriptiva de conjuntos , un juego analítico lightface es un juego infinito de dos jugadores de información perfecta cuyo conjunto de pagos es un subconjunto analí...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría descriptiva de conjuntos , un juego analítico lightface es un juego infinito de dos jugadores de información perfecta cuyo conjunto de pagos es un subconjunto analítico lightface ( Σ 1 1 ) del espacio de Baire . La determinabilidad de todos los juegos analíticos lightface es equivalente, sobre ZFC , a la existencia de 0 # , un resultado conocido como el teorema de Martin-Harrington .

Fondo

Juegos infinitos

Los juegos que se estudian aquí son los juegos de Gale-Stewart . Dos jugadores, denominados convencionalmente Jugador I y Jugador II, se turnan para elegir números naturales, comenzando el Jugador I:

El jugador I elige un 0 , el jugador II elige un 1 , el jugador I elige un 2 , ...

Tras un número infinito de rondas, los dos jugadores han generado conjuntamente una secuencia infinita ( a₀ , a₁ , a₂ , ... ) en el espacio de Baire ω₁ , el conjunto de todas las secuencias infinitas de números naturales con el producto de la topología discreta. Se fija de antemano un conjunto de pagos A ⊆ ω₁ ; el jugador I gana si la secuencia resultante pertenece a A , y el jugador II gana en caso contrario.

Una estrategia para el Jugador I es una función σ que asigna a cada secuencia finita de longitud par (que representa los movimientos realizados hasta el momento) un número natural (el siguiente movimiento del Jugador I). Una estrategia para el Jugador II se define de forma análoga para secuencias de longitud impar. Una estrategia es ganadora si, al seguirla, se garantiza la victoria independientemente del juego del oponente. El resultado de una partida se determina si uno de los dos jugadores tiene una estrategia ganadora.

La jerarquía de determinación

No todos los juegos infinitos son determinados: utilizando el axioma de elección se puede construir un juego indeterminado. [ 1 ] Sin embargo, la determinabilidad se cumple para conjuntos de pagos de baja complejidad descriptiva. Los resultados clásicos forman una jerarquía:

Texto ligero versus texto en negrita

La distinción entre notación ligera y negrita es fundamental para este tema. Un conjunto A ⊆ ω ω es analítico en negrita ( Σ 1 1 ) si es la proyección de un conjunto cerrado en un espacio producto, equivalentemente si existe un árbol T en ω × ω tal que A es el conjunto de primeras coordenadas de ramas infinitas que pasan por T. La versión en notación ligera añade una restricción de efectividad: A es analítico en notación ligera ( Σ 1 1 ) si T puede tomarse como un subconjunto computable (recursivo) de ( ω × ω ) < ω . [ 2 ]

De forma equivalente, un conjunto es analítico ligero si es recursivamente enumerable sin referencia a ningún oráculo; es decir, puede describirse sin parámetros de números reales. Los conjuntos analíticos en negrita pueden requerir parámetros de números reales; la clase ligera es estrictamente más reducida.

Esta distinción tiene una consecuencia directa para la determinabilidad: la determinabilidad analítica en negrita se deriva de la existencia de un cardinal medible , una suposición relativamente fuerte de cardinal grande. La determinabilidad analítica en letra normal requiere solo la suposición más débil de que existe 0 # . Por el contrario, Leo Harrington demostró que la determinabilidad analítica en letra normal no puede probarse solo en ZFC, y de hecho implica la existencia de 0 # .

El teorema de Martin-Harrington

El resultado central del tema es:

Teorema (Martin–Harrington, 1978). Las siguientes expresiones son equivalentes sobre ZFC:

  1. Todos los juegos analíticos de Lightface están determinados.
  2. 0 # existe.

Dirección hacia adelante: 0 # implica determinación

Donald A. Martin demostró que si existe 0 # entonces todos los juegos analíticos lightface están determinados. [ 3 ] La herramienta clave es la secuencia de indiscernibles de Silver codificada por 0 # . Estos indiscernibles proporcionan una forma uniforme de construir estrategias ganadoras para juegos analíticos lightface: el árbol computable que define el conjunto de pagos puede analizarse utilizando los indiscernibles, y la estructura resultante permite determinar qué jugador gana y construir explícitamente una estrategia ganadora.

Dirección inversa: la determinación implica 0 #

Leo Harrington demostró lo contrario en 1978: si todos los juegos analíticos lightface están determinados, entonces existe 0 # . [ 4 ] Esta dirección es considerablemente más difícil. La demostración de Harrington utiliza la teoría de conjuntos admisibles y ordinales admisibles (en particular, la compacidad Barwise ) para mostrar que la determinabilidad de un cierto juego analítico lightface obliga a la existencia de un modelo de teoría de conjuntos con una incrustación elemental no trivial j  : L → L , lo cual es equivalente a la existencia de 0 # . Sami (1999) dio una demostración posterior sin forzamiento de esta dirección. [ 5 ]

0 # y el universo construible

0 # (cero agudo) es un número real —formalmente un subconjunto de ω— que codifica la teoría completa de primer orden del universo constructible L de Gödel con respecto a sus indiscernibles de Silver . Los indiscernibles de Silver son una clase de club de ordinales que son indistinguibles entre sí por cualquier fórmula de primer orden de la teoría de conjuntos con parámetros de orden inferior en la secuencia de indiscernibles.

La existencia de 0 # es independiente de ZFC. Si 0 # existe, entonces L ≠ V (el universo construible es un modelo interno propio del universo verdadero), y todo cardinal no numerable de V es un cardinal medible en L [0 # ]. La existencia de un cardinal medible implica que 0 # existe, pero no a la inversa; 0 # es una suposición estrictamente más débil.

Relativización

El teorema se relativiza a reales arbitrarios. Para cualquier real x , la determinabilidad Π 1 1 ( x ) — la determinabilidad de todos los juegos cuyo conjunto de pagos es coanalítico de cara ligera con respecto a x como oráculo — es equivalente a la existencia de x # , el valor agudo para el modelo interno L [ x ]. [ 6 ] El teorema original de Martin-Harrington es el caso especial x = ∅.

Véase también

Referencias

  1. ↑ Jech, Thomas (2003). Teoría de conjuntos (edición del tercer milenio  ). Springer. ISBN 3-540-44085-2.
  2. ↑ Moschovakis, Yiannis N. (2009). Teoría descriptiva de conjuntos (2.ª ed.). Sociedad Matemática Americana. ISBN  978-0-8218-4813-5.
  3. ↑ Martin, Donald A. (1970). "Cardinales medibles y juegos analíticos". Fundamenta Mathematicae . 66 : 287– 291. doi : 10.4064/fm-66-3-287-291 .
  4. ↑ Harrington, Leo A. (1978). "Determinación analítica y 0 # ". Journal of Symbolic Logic . 43 (4): 685– 693. doi : 10.2307/2273508 . JSTOR 2273508 . 
  5. ↑ Sami, Ramez L. (1999). "Determinación analítica y 0 # : una demostración sin forzamiento del teorema de Harrington". Fundamenta Mathematicae . 160 (2): 153– 159. doi : 10.4064/fm-160-2-153-159 .
  6. ^ Kanamori, Akihiro (2003). El infinito superior (2ª ed.). Saltador. ISBN  3-540-00384-3.

Lecturas adicionales

  • Moschovakis, Yiannis N. (2009). Teoría descriptiva de conjuntos (2.ª  ed.). Sociedad Matemática Americana. ISBN 978-0-8218-4813-5.
  • Kanamori, Akihiro (2003). El infinito superior (2ª  ed.). Saltador. ISBN 3-540-00384-3.
  • Ahmed, Shehzad (2014). Π 1 1 -Determinación y Sharps (PDF) (Tesis de maestría). Universidad Estatal de Boise.