Indeterminaci on y eleccionEl axioma de elecci on El axioma de eleccion tambi en es equivalente al teorema de Gale y Stewart. Si Xes bien-ordenado, que los juegos G X(A) con Aabierto

JuegosDeterminación

El juego contable-finitoDicotoḿıas

Indeterminación y elección

Andrés Eduardo Caicedo

Department of MathematicsBoise State University

XVII Congreso Colombiano de MatemáticasCali, Agosto 3–6, 2009

Caicedo Indeterminación y elección



Juegos

En teoŕıa de conjuntos analizamos ciertos juegos, formalizados dela siguiente forma: Hay un conjunto X fijo; los elementos de Xson las jugadas posibles.

Dos jugadores I y II juegan por turnos, con I jugando primero. Lasreglas determinan qué jugadas son válidas. En cada turno, eljugador correspondiente escoge un elemento de X que sea unajugada válida y, si no hay, pierde. Si el juego continua por unnúmero infinito de jugadas, el ganador se decide de acuerdo con lasucesión en XN que se ha producido.

Ambos jugadores conocen las reglas del juego, pueden ver loselementos de X, y a cada momento saben qué jugadas se hanhecho hasta entonces. Estos juegos se denominan de informaciónperfecta.




Juegos finitos




Juegos finitos

I x0 x2 . . .

II x1 x3

Si X es finito y el juego siempre termina en un número finito dejugadas, decimos que el juego es finito.

Un ejemplo t́ıpico es ajedrez. Juegos de azar no forman parte deeste marco.

Otra restricción es que el juego no puede terminar en empate. Estoelimina el juego de ajedrez de nuestro análisis, pero podemosincluirlo si decretamos que las negras “ganan” si el juego terminaempatado.




Juegos finitos

Formalmente, una estrategia es una función que asigna a cadasucesión finita de elementos de X un elemento de X,

σ : X



Juegos finitos

Similarmente, II sigue σ si sus jugadas son dictadas por σ y lasjugadas de I:

I x0 x2 . . .

II σ(〈x0〉) σ(〈x0, x2〉)

Decimos que σ es una estrategia ganadora para I en un juego

G

si Igana cada vez que sigue σ. Similarmente, σ es una estrategiaganadora para II si II gana cada vez que sigue σ. Un juego esdeterminado si uno de los jugadores tiene una estrateǵıa ganadora.

El análisis matemático de juegos comenzó con Zermelo (1913),acerca del ajedrez. Se sigue de sus argumentos que todos losjuegos finitos son determinados.




Bengt Ekeroth y Max von Sydow en The Seventh Seal, 1957. c©Svensk Filmindustri; Ingmar Bergman (director), Gunnar Fischer(director de fotograf́ıa).




Juegos finitos

En particular, o bien las blancas tienen una estrategia ganadora, obien las negras tienen una estrategia “no perdedora”.Curiosamente, aun no sabemos cuál de los dos casos ocurre.

Gale y Stewart observaron que la demostración de que los juegosfinitos son determinados se aplica fácilmente a ciertos juegosinfinitos.




Carse, James P. Finite and Infinite Games. New York: BallantineBooks. ISBN: 0-345-34184-8.




Juegos infinitos

Decimos que un juego

G

es abierto para el jugador I si cada vezque I gana, al cabo de un número finito de jugadas se sab́ıa queiba a ganar.

Dado A ⊆ Xω, el juego

G

X(A) se define de modo que no hayrestricciones en qué elementos de X pueden jugarse a cadamomento, y el jugador I gana si y sólo si la sucesiónx = 〈x0, x1, . . . 〉 que se obtiene, es un elemento del conjunto A.

Teorema (Gale-Stewart, 1953).

Suponga que X tiene la topoloǵıa discreta, y Xω la topoloǵıaproducto. Si A es un conjunto abierto en Xω, entonces

G

X(A) esdeterminado.




Juegos infinitos

Teorema (Martin, 1975).

Si A es un conjunto de Borel en Xω, entonces

G

X(A) esdeterminado.

Por otro lado, tenemos el siguiente resultado, que es parte delfolklore:

Observación.

Hay un conjunto A ⊂ ωω1 tal que

G

X(A) no es determinado.

Algunas observaciones acerca de estos resultados son necesarias.




El axioma de elección

Axiom of Choice. Niyayesh (2002) Narada Records. Ganadores delpremio NAV por mejor álbum de música contemporánea.





El axioma de elección es parte de la teoŕıa básica de conjuntos.Una de sus formulaciones más populares es que todo conjuntopuede bien-ordenarse, es decir, hay una biyección entre el conjuntoy un ordinal.

El sistema básico de axiomas de la teoŕıa de conjuntos es ZFC. Lateoŕıa que resulta cuando no se incluye al axioma de elección esZF, por Zermelo y Fraenkel.

En ZF se puede demostrar que elección es equivalente al teoremade Tychonoff, al lema de Zorn, al hecho de que todo espaciovectorial admite una base, etc.





El axioma de elección también es equivalente al teorema de Gale yStewart.

Si X es bien-ordenado, que los juegosG

X(A) con A abierto sondeterminados puede demostrarse sin elección.

Por otro lado, el hecho de que hay un juego

G

ω1(A) indeterminadopuede demostrarse en ZF.




Determinación

Mudvayne. Determined, en Lost and Found (2005) Epic Records.




El axioma de determinación, AD, (Mycielski-Steinhaus, 1962)afirma que si A ⊂ ωω, entonces

G

ω(A) es determinado.Usualmente, se dice que A es determinado.

Como ωω es homeomorfo al conjunto R \Q de irracionales, enteoŕıa de conjuntos se acostumbra a llamar reales a los elementosde ωω.

Una de las consecuencias de determinación es la propiedad delconjunto perfecto, la siguiente versión de la hipótesis del continuo:Si A ⊆ ωω entonces o bien A es contable, o si no, contiene unsubconjunto perfecto.

Si ω1 puede inyectarse en ωω, entonces hay un conjunto de reales

para el cual la propriedad del conjunto perfecto falla. Por tanto,AD contradice al axioma de elección.




Modelos naturales

Como AD habla de la existencia de estrategias ganadoras, quepueden codificarse con reales, un modelo de ZF que es uncandidato natural a ser modelo de AD es la clase L(R), el universoconstruible a partir de los reales. Éste es el menor modelotransitivo de ZF que contiene a todos los reales y ordinales. En elmismo sentido en que L (el universo construible de Gödel) es elmenor modelo de ZF, L(R) seŕıa el menor modelo de ZF + AD.




Modelos naturales

Si AD vale, entonces vale en L(R).

Gracias a resultados de Foreman-Magidor-Shelah, Martin-Steel, yShelah-Woodin, en 1985, Woodin demostró que si asumimos laexistencia de ciertos cardinales grandes (una hipótesis natural enteoŕıa moderna de conjuntos) entonces, aśı valga elección en eluniverso V de todos los conjuntos, en el modelo interno L(R) valeAD.




AD se refiere a conjuntos de reales. Decimos que un modelotransitivo M (que contiene todos los ordinales) es un modelonatural de AD si M satisface V = L(P(R)).

Por ejemplo, L(R) es de esta forma, pero hay muchos otrosmodelos naturales.

Si AD vale y M es un modelo natural, entonces AD vale en M .




AD+

Usando resultados de Solovay, Martin-Steel,Kechris-Moschovakis-Woodin-Kleinberg, Kechris, y Woodin, unopuede demostrar que en L(R) valen los resultados siguientes,asumiendo ZF + AD:

DCR, el axioma de escogencias dependientes para relacionesde reales.

Todo conjunto de reales es ∞-Borel.

< Θ-determinación ordinal.

Estas nociones necesitan una explicación.




AD+

Definición (DCR).

Si R ⊆ R2 es una relación tal que para todo real x hay un real ycon xRy, entonces hay una sucesión de reales x0, x1, . . . tal que,para todo n, xnRxn+1.

DCR es suficiente para desarrollar el análisis clásico, pero no bastapara demostrar que hay conjuntos de reales que no son medibles enel sentido de Lebesgue. En cierto sentido, tenemos entonces todala estructura con la que el análisis nos provee, sin las patoloǵıascorrespondientes.




AD+

Definición.

Decimos que S, ϕ es un código ∞-Borel si y sólo si S es unconjunto de ordinales y ϕ(x, Z) es una fórmula.

La idea es que S, ϕ codifica la construcción de un conjunto dereales AS,ϕ:

x ∈AS,ϕ ⇔ L[S, x] |= ϕ(x, S),

donde L[S, x] es el menor modelo de ZF que contiene al conjuntoS y al real x.




AD+

Woodin definió que A ⊆ R es ∞-Borel si y sólo si hay un códigoS, ϕ tal que A = AS,ϕ.

Por ejemplo, todo conjunto Borel es ∞-Borel, y podemos escogerS ⊂ ω.




AD+

Θ es el menor ordinal α tal que no hay una función sobreyectiva deR en α.

Como mencionamos antes, hay juegos

G

ω1(A) que sonindeterminados. Sin embargo, hay una clase significativa de juegosordinales para los que es posible asumir determinación.

Definición (< Θ-determinación ordinal).

Supongamos que λ es un ordinal, λ < Θ, y que f : λω → ωω escontinua (donde λ tiene la topoloǵıa discreta). Entonces

G

λ(f−1[A]) es determinado para todo A ⊆ ωω.




AD+

Hugh Woodin definió AD+, una extensión de AD, y desarrolló suteoŕıa básica. AD+ es la conjunción de las tres consecuencias deAD en L(R) que acabamos de definir:

Definición (AD+).

DCR.

Todo conjunto de reales es ∞-Borel.

< Θ-determinación ordinal.




AD+

En ZFC, todos los modelos naturales de AD que conocemos son dehecho modelos de AD+.

Es posible que AD implique AD+, éste es el problema abierto mássignificativo en la teoŕıa de determinación.




El juego contable-finito

Marion Scheepers definió el juego contable-finito. Dado unconjunto S, el juego CF (S) se define como sigue: I y II alternan,con I jugando subconjuntos contables de S, y con II jugandosubconjuntos finitos:

CF (S)

I U0 U1 . . .

II D0 D1

El jugador II gana si y sólo si⋃n Un =

⋃nDn.





Por supuesto, con elección, para todo S, II tiene una estrategiaganadora.

Si S es contable (o Dedekind-finito), elección no se necesita parademostrar esto.

Scheepers ha investigado qué tanto puede restringirse la noción deestrategia, reemplazándola con la de táctica.

Si k ∈ N, una k-táctica sólo recuerda las últimas k movidas deloponente.





Scheepers demostró que si S es infinito, entonces II no tiene una1-táctica ganadora.

Por otro lado, Koszmider demostró que si |S| < ℵω, entonces IItiene una 2-táctica ganadora.

Koszmider también demostró que, en L, el jugador II tiene una2-táctica ganadora para todo S.





Es natural preguntar si es realmente necesario asumir elección paraver que II siempre gana.

En efecto, tal es el caso. Por ejemplo, Feferman y Levydemostraron en 1963 que es consistente con ZF que los reales sonuna unión contable de conjuntos contables. En tal caso, es I el quetiene una estrategia ganadora en CF (R).





Si asumimos determinación, R no es una unión contable deconjuntos contables, y uno puede preguntarse si hay otra manerade demostrar que CF (R) es determinado.




Los resultados que quiero mencionar son trabajo conjunto conRichard Ketchersid.




CF (S) en modelos naturales de AD+

Teorema (C-Ketchersid).

Sea M un modelo natural de AD+. Entonces, en M , si S es unconjunto no contable, el juego CF (S) es no determinado.

Éste es un resultado curioso: Aunque determinación está enconflicto con elección, hemos identificado una clase de juegos queson determinados si asumimos elección, y son indeterminados enlos modelos naturales de determinación.





Para demostrar el teorema, primero identificamos tres casos en losque es posible demostrar que uno de los jugadores no tieneestrategias ganadoras.

Después, demostramos nuestro resultado principal, identificandouna dicotoḿıa en la estructura de los conjuntos en modelosnaturales de determinación.

Usando esto, el teorema se sigue de los tres casos especiales.





Los primeros dos lemas se refieren al jugador II.

Lemma (ZF).

Si ω1 6≤ |R|, y ω1 ≤ |S|, entonces II no tiene una estrategiaganadora en CF (S),

Lemma (AD).

Si |R| ≤ |S|, entonces II no tiene una estrategia ganadora enCF (S).





El tercer lema se refiere al jugador I, y muestra que el ejemplo delmodelo de Feferman y Levy es básicamente la única forma en que Ipuede ganar.

Lemma (ZF).

Si todo conjunto no contable contiene un conjunto no contableque admite un orden lineal, y si toda unión contable de conjuntoscontables es contable, entonces I no tiene una estrategia ganadoraen CF (S) para ningún S no contable.




Una dicotoḿıa en modelos naturales de AD+

Usando los tres lemas, el resultado se sigue de la siguientedicotoḿıa:


Sea M un modelo natural de AD+. Entonces, en M , vale quetodo conjunto o bien es bien-ordenable, o contiene una copia de R.

En particular, esto vale en L(R) si asumimos determinación. Estaversión se conoce desde hace unos años, y es debida a Woodin.




Una dicotoḿıa en modelos naturales de AD+

Dos consecuencias immediatas de este resultado son las siguientes,con lo que completamos la demostración del teorema acerca deljuego contable-finito:

Corolario.

Sea M un modelo natural de AD+. Entonces, en M , todoconjunto infinito contiene una copia de N, y todo conjunto nocontable contiene una copia de ω1 o de R.

Corolario.

Sea M un modelo natural de AD+. Entonces, en M , toda unióncontable de conjuntos contables es contable.




Una dicotoḿıa para grafos

Es posible demostrar versiones de la dicotoḿıa no sólo paraconjuntos, sino también para ciertas estructuras. Por ejemplo:


Sea M un modelo natural de AD+. En M , si (X,≤) es un ordenparcial, y no es posible inyectar R en X de modo que cualesquierados reales tengan imágenes ≤-incomparables, entonces X se puedeescribir como una unión bien ordenada de ≤-cadenas.

Hay también una versión para grafos, que requiere unasdefiniciones preliminares.





Definición (E0).

E0 es la relación de equivalencia en 2N definida de modo que

x ∼ y ⇔ ∃n ∀m ≥ n (x(m) = y(m)).

E0 es una relación muy importante en teoŕıa descriptiva deconjuntos. El siguiente resultado es bien conocido:

Lema (AD).

1 2N/E0 no admite un orden lineal.2 ω1 no se puede inyectar en 2N/E0.3 |R| < |2N/E0|.





Definición (G0).

El grafo G0 en 2N se define como sigue: Primero, fijamos unasucesión (sn : n ∈ N) tal que sn ∈ 2n para toda n, y para todox ∈ 2N hay un n tal que sn es un segmento inicial de x.Dados x, y ∈ 2N, hay un arco en el grafo G0 entre x y y si y sólo si

∃n ∃i ∈ {0, 1} ∃t ∈ 2N (x = sn_(i)_t y y = sn_(0− i)_t).

Un coloreo de un grafo (X,G) es una función f con dominio X talque si xGy entonces f(x) 6= f(y).

Un homomorfismo de un grafo (X,G) en un grafo (Y,H) es unafunción f : X → H tal que si xGy entonces f(x)Hf(y).






Sea M un modelo natural de AD+. Entonces, en M , dado ungrafo (X,G), o bien G se puede colorear con ordinales, o hay unhomomorfismo de G0 en G.

Hay varias versiones más detalladas de este resultado. Concluyocon dos consecuencias de estas versiones:





El primer corolario, en el caso particular en que M = L(R) y ≤= ∅se debe a Hjorth (1995):

Corolario.

Sea M es un modelo natural de AD+. Entonces, en M , todoorden parcial (X,≤) o bien se puede extender a un orden lineal,subconjunto de un (2α,≤lex) para algún ordinal α, o hay unainyección de 2ω/E0 en X tal que las imágenes de cualesquiera dosclases distintas son ≤-incomparables.





El argumento del segundo corolario fue sugerido por BenjaminMiller, quien también es responsable por habernos informado delgrafo G0 y su conexión con la relación E0.

Corolario.

AD+ implica que 2ω/E0 es un sucesor de R, es decir, no haycardinales intermedios entre |R| y |2ω/E0|.




Para resumir: Hemos mostrado que en modelos naturales de AD+,

ω es el menor cardinal infinito.

ω tiene exactamente dos sucesores: ω1 y R.ω1 tiene exactamente dos sucesores: ω2 y ω1 ∪ R.R tiene al menos dos sucesores: ω1 ∪ R y 2ω/E0.

Sabemos que hay otros sucesores de R, pero aun no se sabecuántos, ni si forman una base para los cardinales mayores que R,ni si pueden clasificarse en algún sentido.




(Imagen encontrada en http://anonymusings.blogsome.com)

Fin.


JuegosDeterminaciónEl juego contable-finitoDicotomías

Documents

Indeterminaci on y eleccionEl axioma de elecci on El axioma de eleccion tambi en es equivalente al teorema de Gale y Stewart. Si Xes bien-ordenado, que los juegos G X(A) con Aabierto