Desarrollos Recientes en la Teoría de Particiones

Carlos Augusto Di Prisco

Instituto Venezolano de Investigaciones Científicas y Universidad Central de Venezuela

1 Introducción.

El origen de la teoría de particiones se puede situar en un teorema demostrado por F.P. Ramsey en 1930 para resolver un problema de decibilidad en lógica matemática (véase [22]). El teorema de Ramsey se puede considerar una generalización de la simple observación siguiente llamada el principio del casillero: Si debemos clasificar k objetos en m casillas, y m < k entonces en alguna casilla necesariamente habrá más de un objeto. Más aún, dado un número h, existe un número M tal que si clasificamos M objetos en k casillas, siempre habrá una casilla con al menos h objetos. El teorema de Ramsey generaliza este principio al considerar no solamente la clasificación de los elementos de un conjunto dado, sino la clasificación de sus subconjuntos que tienen exactamente dos elementos, o más generalmente, la clasificación de los subconjuntos que tienen un número dado n de elementos.

El estudio de una diversidad de variaciones del teorema de Ramsey ha dado lugar a una rama de la teoría combinatoria, llamada la teoría de particiones o cálculo de particiones, que presenta interesantes interrogantes, tanto en lo referente a particiones de conjuntos finitos como en lo referente a conjuntos infinitos. Debido a que las técnicas usadas en uno y otro caso tienden a ser totalmente diferentes, el área se muestra subdividida en dos campos; para conjuntos finitos se usan técnicas más bien clásicas de combinatoria, y hay una variedad de problemas abiertos que tienen que ver con computabilidad y eficiencia de algoritmos para hacer cálculos. En lo referente a particiones de conjuntos infinitos, al entrar en consideraciones de cardinalidad, se pasa inmediatamente al ámbito de los problemas indecidibles en la teoría de conjuntos por lo cual las técnicas de demostración de consistencia e independencia son de gran importancia.

Enunciaremos el teorema de Ramsey en la siguiente sección, pero antes conviene hacer algunas precisiones sobre la notación que usaremos. Denotaremos por ω al tipo de orden de los números naturales ℕ. Los cardinales infinitos son usualmente denotados usando la letra ℵ con el subíndice apropiado. Así ℵ_{0} es el primer cardinal infinito, la cardinalidad de ℕ; ℵ_{1} es el primer cardinal no numerable, ℵ_{2} el primer cardinal mayor que ℵ_{1}, y así sucesivamente; ℵ_{ω} es el supremo de los ℵ_{n} para n ∈ ω. El siguiente cardinal es ℵ_{ω+1}, etc.

Conviene definir los números cardinales como ordinales iniciales, es decir aquellos ordinales que no son equipotentes con ningún ordinal menor. El primer ordinal infinito es ω, el primer ordinal no numerable es llamado ω_{1}, el primer ordinal que no es equipotente con ω_{1} es ω_{2}, y así sucesivamente. Todos los ordinales infinitos numerables están entre ω_{0} y ω_{1}, y ω_{1} es precisamente el supremo de todos ellos. Análogamente ocurre con los ordinales mayores.

Identificamos entonces ℵ_{0} con ω y, en general, ℵ_{α} con el ordinal ω_{α}.

Usaremos |A| para denotar la cardinalidad del conjunto A, y si n es un número natural, [A]^{n} = {B ⊆ A : |B| = n}. Es decir, [A]^{n} denota la colección de los subconjuntos de A que tienen exactamente n elementos. Este notación se usa también cuando consideramos subconjuntos infinitos de un conjunto infinito, así [A]^{ω} denota la colección de subconjuntos infinitos numerables del conjunto A. Es común denotar a la colección de los subconjuntos finitos de A por [A]^{<ω}.

Dado un conjunto A, A^{α} es el producto cartesiano de A por sí mismo α veces, es decir, la colección de todas las funciones de α en A. La colección de todas las sucesiones finitas de elementos de A se denota por A^{<ω}.

Un árbol es un conjunto A parcialmente ordenado con un orden ≤ tal que para cada a ∈ A, el conjunto {b ∈ A : b ≤ a} está bien ordenado por ≤. Conviene recordar un resultado debido a D. König relativo a árboles infinitos.

Lema 1.1 (König) Un árbol infinito cuyos niveles son todos finitos tiene una rama infinita.

La demostración es muy fácil, la rama infinita se halla por inducción en los niveles. Como el primer nivel del árbol es finito, debe haber un elemento del primer nivel con una colección infinita de sucesores. Entre los sucesores inmediatos de ese elemento (hay una cantidad finita de éstos, ya que son miembros del segundo nivel del árbol) hay al menos uno que tiene infinitos sucesores, etc. Continuando este proceso se halla una rama infinita.

2 El Teorema de Ramsey

Teorema 2.1 (Ramsey, versión finita) Para todo k, n, h, ∈ ℕ, existe M ∈ ℕ tal que para todo conjunto A de M elementos y toda partición de [A]^{n} en k clases, existe un subconjunto H ⊆ A con h elementos tal que [H]^{n} está contenido en una de las clases.

Daremos una demostración de este teorema después de probar la versión infinita.

La función que para n y k fijos, a cada h le asigna el menor M que satisface el enunciado anterior se llama la función de Ramsey. Esta función crece muy rápidamente por lo que resulta muy difícil calcularla. (Ver [4], [12]).

El siguiente teorema de Erdös y Szekeres se puede considerar como una variación de carácter geométrico (ver [12]).

Teorema 2.2 (Erdös-Szekeres). Para cada n ∈ ℕ existe un N tal que todo conjunto de N puntos en el plano contiene tres puntos colineales o contiene n puntos que forman los vértices de un polígono convexo.

Algunos resultados con el mismo sabor combinatorio habían sido obtenidos con anterioridad al de Ramsey, por ejemplo se pueden mencionar los siguientes teoremas.

Hilbert (1892): Para todo k, n ∈ ℕ existe N tal que toda partición en k partes de P(X), el conjunto de partes de un conjunto de cardinalidad N, existen n subconjuntos de X, A_{1}, A_{2}, …, A_{n}, cuyas uniones no vacías están todas en la misma parte.

Schur (1916): Para todo k, n ∈ ℕ existe N tal que toda partición de {1, 2, …, N} en k partes, una de las partes contiene n números junto con sus sumas. (Este resultado surgió del estudio de congruencias x^{m} + y^{m} = z^{m} (mod p) ).

Van der Waerden (1927): : Para todo k, n ∈ ℕ existe N tal que toda partición de {1, 2, …, N} en k partes una de las partes contiene una progresión aritmética de longitud N.

Un resultado de este mismo tipo, pero mucho más reciente es el siguiente. Hales-Jewett (1963) : Para todo k, n ∈ ℕ existe N tal que toda partición de

{1, 2, …, n}^{N} en k partes una de las partes contiene una línea combinatoria. Sugerimos al lector consultar el texto [12] para obtener la definición de línea combinatoria y la demostración del resultado.

Kahn y Kalai ([13]) usaron ideas de la teoría de Ramsey para refutar la siguiente conjetura de Borsuk.

Conjetura (Borsuk):

Todo conjunto de ℝ^{n} de diámetro 1 se puede descomponer en n + 1 partes de diámetro menor.

Para n pequeño la conjetura vale, pero la función f(n) = el menor número k tal que cada conjunto de ℝ^{n} de diámetro 1 se puede descomponer en k subconjuntos de diámetro menor que 1, crece exponencialmente. A saber, f(d) > 1.1^{\sqrt{n}}. Para demostrar esto, Kahn y Kalai usaron cotas conocidas del crecimiento de la función R(n).

Ramsey demostró también un teorema de particiones relativas a conjuntos infinitos que se enuncia a continuación.

Teorema 2.3 (Ramsey, versión infinita) Dados n, k ∈ ℕ y un conjunto infinito A, para toda partición de [A]^{n} en k clases, existe un subconjunto infinito H ⊆ A tal que [H]^{n} está contenido en una de las clases.

Incluimos la demostración de este teorema para ilustrar el tipo de métodos que se usan en esta área.

R. Rado introdujo una notación que ha resultado muy conveniente para expresar relaciones de particiones. Esta notación es de gran versatilidad y ha sido ampliamente adoptada.

El símbolo

κ → (λ)_{k}^{n}

expresa que para toda partición de los subconjuntos de n elementos de un conjunto A de cardinalidad κ existe un conjunto H de A, de cardinalidad λ cuyos subconjuntos de n elementos están todos en la misma clase de la partición. Se dice entonces que H es un conjunto homogéneo para la partición. Con esta notación, el teorema el teorema de Ramsey en su versión infinita se puede enunciar así

ω → (ω)_{k}^{n}.

Demostración: Consideremos primero el caso k = 2 (el caso k = 1 es trivial). Para k = 2, demostraremos ω → (ω)_{2}^{n} por inducción en n. Si n = 1 es claro que el resultado vale, es una versión del principio del casillero. Supongamos que el teorema vale para n, y probemos ω → (ω)_{2}^{n+1}. Sea F : [w]^{n+1} → 2. Para encontrar el conjunto H homogéneo para F construiremos un árbol infinito de niveles finitos y extraeremos el conjunto homogéneo de una de sus ramas infinitas. Para cada nodo del árbol, definiremos un conjunto de sucesores potenciales. Los primeros n niveles del árbol están dados por 0, 1, 2, ..., n − 1 respectivamente. El conjunto de sucesores potenciales de n − 1 es ω \ n = {j ∈ ω : j ≥ n}. Dividimos este conjunto en dos clases: {j ≥ n : F ({0, 1, ..., n − 1, j}) = 0} y {j ≥ n : F ({0, 1, ..., n − 1, j}) = 1}. El nivel n + 1 del árbol estará formado por el menor elemento de cada una de esas clases (luego, n − 1 tiene a lo sumo dos sucesores) y el resto de la clase correspondiente es el conjunto de sucesores potenciales de cada elemento de ese nivel. Supongamos que hemos definido el nivel m del árbol, y para cada elemento de ese nivel, su conjunto de sucesores potenciales. Definimos ahora el nivel m+1 indicando cuales son los sucesores de cada elemento del nivel m. Dado t en el nivel m, sea C_{t} el conjunto formado por t y sus predecesores en el orden del árbol . C_{t} está bien ordenado por el orden del árbol, y tiene m elementos. Sea B_{t} el conjunto de sucesores potenciales de t. Dividiremos al conjunto B_{t} en varias clases, y para simplificar la notación haremos esto definiendo una relación de equivalencia en B_{t}: i es equivalente a j si y sólo si para todo x ∈ [C_{t}]^{n} tenemos F (x ∪ {i}) = F (x ∪ {j}). Es fácil verificar que ésta es, en efecto, una relación de equivalencia. Los sucesores inmediatos de t son determinados tomando el menor elemento de cada clase de equivalencia. Nótese que algunas veces puede ocurrir que el conjunto de sucesores potenciales de un nodo del árbol sea vacío. En cada nodo del nivel m tiene a lo sumo 2^{\binom{m}{n}} elementos (ya que para t del nivel m, \binom{m}{n} = |[C_{t}]^{n}| , y para cada x ∈ [C_{t}]^{n}, F (x∪{t}) puede ser 0 ó 1). Para cada sucesor inmediato de t, el conjunto de sus sucesores potenciales es el resto de la clase a la que pertenece. Así completamos la construcción inductiva de un árbol infinito a niveles finitos. El lema de König nos indica que existe una rama infinita R. Por construcción, esa rama tiene la siguiente propiedad: dado un x ∈ [R]^{n}, el valor F (x ∪ {j}) es el mismo para todo j que se encuentre en la rama por encima de x. Entonces para x ∈ [R]^{n} diremos que x es de tipo 0 si ese valor es 0, de lo contrario decimos que x es de tipo 1. Esto nos da una partición de [R]^{n} en dos clases, y por hipótesis inductiva existe un subconjunto infinito H ⊆ R tal que todos los elementos de [H]^{n} son del mismo tipo. Claramente H es homogéneo para F. Esto completa el caso k = 2. Si suponemos que para k ≤ r vale ω → (ω)_{k}^{n} para todo n, y F : [ω]^{n} → r + 1, podemos definir una partición auxiliar G : [ω]^{n} → r poniendo G(x) = 0 si F (x) = 0 y G(x) = 1 en caso contrario. Por hipótesis inductiva, existe un conjunto infinito H homogéneo para G, si G”[H]^{n} = {0}, H es homogéneo para F. Si G”[H]^{n} = {1}, entonces G ↾ [H]^{n} (G restringida a H) es una partición en r partes y por hipótesis inductiva hay un conjunto H′ ⊆ H infinito homogéneo. Este conjunto H′ es homogéneo para F. □

La versión finita del teorema se obtiene fácilmente de la versión infinita.

Demostración de 2.1:

Dados k, m, h supongamos que para todo M ≥ n, f_{M} : [M]^{n} → k es una partición de [M]^{n} en k partes para la que no hay conjunto homogéneo de h elementos. El conjunto A = {f_{M} ↾ [j]^{n} : j ≤ M, M ∈ ω}, con el orden dado por la extensión de funciones, es un árbol infinito. Pero cada nivel de A es finito, ya que para cada j, hay un número finito de funciones de [j]^{n} en k, por lo tanto, por el lema de König existe una rama infinita F en A. Si ponemos f = ∪F, es claro que f : [w]^{n} → k. Por la versión infinita del teorema de Ramsey, existe un conjunto H ⊆ ω infinito homogéneo para f. Sea J ⊆ H un subconjunto de H con h elementos. Si tomamos una función g de la rama F tal que J ⊆ dom(g), g = f_{M}|[j]^{n} para algún M y algún j ≥ M, y J es un conjunto homogéneo para f_{M}, lo que contradice la definición de f_{M}. □

Erdös y Rado [9] iniciaron durante la década de los 50 lo que ellos mismos llamaron el cálculo de particiones. En los libros [10] y [26] se presentan diversos aspectos de este cálculo.

Los resultados mencionados y muchos otros desarrollos recientes que extienden o generalizan estas ideas conforman lo que hoy en día se llama la Teoría de Ramsey. Este amplio cuerpo de conocimiento matemático tiene profundas conexiones con una gran variedad de áreas de la matemática: geometría, topología, teoría de grafos, teoría ergódica, teoría de números, lógica matemática, entre otras. El libro [20] reúne una serie de artículos sobre diversos aspectos de la teoría de Ramsey y sus variadas aplicaciones.

3 Extensiones o generalizaciones.

La versión infinita del teorema de Ramsey establece que para toda partición de los pares de elementos de un conjunto infinito A en un número finito de clases, existe un subconjunto infinito de A cuyos pares de elementos están todos en la misma clase, es decir, un subconjunto homogéneo. La demostración del teorema indica cómo obtener tal subconjunto. Si el conjunto A es no numerable, la demostración del teorema no da más que la existencia de un subconjunto homogéneo numerable.

Cabe entonces la siguiente pregunta. Si κ es un cardinal infinito no numerable, ¿ es cierto que para toda partición de los pares de elementos de un conjunto A de cardinalidad κ existe un subconjunto H ⊆ A también de cardinalidad κ homogéneo para la partición? La respuesta es, en general, negativa. Por ejemplo, es negativa para κ = ℵ_{1}, el primer cardinal no numerable.

Un cardinal no numerable κ satisface la relación κ → (κ)_{2}^{2} si para toda partición F : [κ]^{2} → 2 existe un conjunto H ⊆ κ tal que |H| = κ y F es constante en [H]^{2}.

La satisfacción de la relación κ → (κ)_{2}^{2} como propiedad de un cardinal no numerable κ es una propiedad muy fuerte que está enmarcada, como veremos más adelante, en la teoría de los grandes cardinales.

Otra manera de generalizar el teorema de Ramsey consiste en considerar particiones de la colección de subconjuntos infinitos de un conjunto dado. Esta idea da lugar al concepto de conjunto de Ramsey que también examinaremos luego.

a) Particiones y grandes cardinales.

Para motivar varias de las definiciones que daremos en esta sección, examinemos por un momento algunas propiedades del primer cardinal infinito ω. Por una parte, la unión de una colección finita de conjuntos finitos es finita. Como un cardinal es finito exactamente si es menor que ω, podemos refrasear esa propiedad diciendo “la unión de una colección de menos de ω conjuntos, cada uno de ellos de cardinalidad menor que ω es de cardinalidad menor que ω”. Un cardinal que tiene la propiedad análoga se llama un cardinal regular.

Definición 3.1 Un cardinal κ es regular si la unión de una colección de menos de κ conjuntos de cardinalidad menor que κ tiene cardinalidad menor que κ.

Por ejemplo, ω_{1}, el primer cardinal no numerable es regular, ya que una unión numerable de conjuntos numerables es numerable.

Es claro que si n es un cardinal finito, entonces 2^{n} es también un cardinal finito. Esta se puede expresar como una propiedad de ω diciendo que para todo n < ω se tiene que 2^{n} < ω. Un cardinal es un límite fuerte si tiene la propiedad análoga.

Definición 3.2 Un cardinal κ es un límite fuerte si para todo cardinal α < κ, se tiene que 2^{α} < κ.

Definición 3.3 Diremos que un cardinal κ es inaccesible si

1. ω < κ,

2. κ es regular, y

3. κ es límite fuerte.

La existencia de cardinales inaccesibles implica la existencia de modelos para la teoría de conjuntos, y por el teorema de incompletitud de Gödel, la existencia de cardinales inaccesibles no es demostrable en la teoría de conjuntos de Zermelo-Fraenkel con el Axioma de Elección ZF C. En este sentido, la inaccesibilidad es una propiedad de gran cardinalidad. El enunciado que afirma la existencia de cardinales inaccesibles puede ser visto entonces como una versión fuerte del axioma que postula la existencia de un conjunto infinito en la teoría ZF. Hay una gran variedad de propiedades que definen cardinales grandes, motivadas por conceptos diferentes, pero todas las nociones encajan en una teoría de gran armonía interna. Mencionaremos aquí algunas de estas nociones, en particular la de cardinal débilmente compacto y la de cardinal medible.

El estudio de los cardinales grandes ha sido muy fructífero, sobre todo por las conexiones que se han establecido entre problemas referentes a conjuntos de números reales y estas propiedades de gran cardinalidad. Una excelente referencia para obtener una visión panorámica del tema es la monografía [14].

Definición 3.4 Un cardinal no numerable κ se llama débilmente compacto si satisface la propiedad κ → (κ)_{2}^{2}.

Si un cardinal κ es débilmente compacto entonces es inaccesible; y además, existen κ cardinales inaccesible menores que κ. La compacidad débil es equivalente inaccesibilidad aunada a la siguiente propiedad:

Se dice que un cardinal κ tiene la propiedad de árbol si todo árbol de cardinalidad κ cuyos niveles tienen todos cardinalidad menor que κ, tiene una rama de cardinalidad κ.

El lema de König, mencionado anteriormente, dice que ω tiene la propiedad de árbol.

b) Conjuntos de Ramsey

Volvamos al teorema de Ramsey. Este establece que si tomamos subconjuntos de n elementos de un conjunto infinito A y los clasificamos en k clases, existe un conjunto homogéneo infinito, es decir, un conjunto infinito H ⊆ A tal que [H]^{n} está contenido en una de las clases. ¿Qué ocurre si tomamos particiones del conjunto de subconjuntos infinitos de ℕ? Conforme a nuestra notación, usaremos [ℕ]^{ω} para denotar al conjunto de los subconjuntos infinitos de ℕ. Nos estamos preguntando si la relación expresada por ω → (ω)_{2}^{ω} es válida. En otras palabras, queremos saber si es cierto que para toda partición de [ℕ]^{ω} en dos pedazos, existe un conjunto infinito H ⊆ ℕ tal que todos los subconjuntos infinitos de H están en la misma clase de la partición.

Esta relación es falsa. Se puede dar un contraejemplo con la ayuda del Axioma de Elección. Sin embargo, la relación vale para particiones definibles en forma sencilla. Haremos esta afirmación más precisa. Al conjunto [ℕ]^{ω} se le puede dotar de una topología que lo hace homeomorfo al conjunto de los números irracionales con la topología heredada de la recta real. Una base para la topología de [ℕ]^{ω} está dada por la colección de conjuntos de la forma {x ∈ [ℕ]^{ω} : s es un segmento inicial de x} donde s es un subconjunto finito de ℕ. Una vez que tenemos una topología en [ℕ]^{ω}, podemos hablar de subconjuntos abiertos, cerrados, borelianos, etc. de ese espacio topológico. Entonces una partición de [ℕ]^{ω} en dos pedazos es boreliana si estos pedazos son conjuntos borelianos.

Galvin y Prikry demostraron que la relación ω → (ω)_{2}^{ω} es cierta para particiones borelianas [11]. Es decir, si partimos ω → (ω)_{2}^{ω} en dos pedazos borelianos, existe un conjunto H ∈ [ℕ]^{ω} tal que todos sus subconjuntos infinitos están en el mismo pedazo de la partición.

Se puede demostrar algo todavía más fuerte. Un subconjunto de [ℕ]^{ω} es analítico si es la imagen de un boreliano por una función continua. Obviamente todo conjunto boreliano es analítico, pero existen conjuntos analíticos no borelianos, tal como fue demostrado por Suslin. El resultado de Galvin y Prikry fue extendido por Silver al caso de particiones analíticas [24]. [21] contiene una serie de aplicaciones de la teoría de Ramsey a la teoría de espacios de Banach. Como muestra, mencionamos la prueba del siguiente teorema que aparece en [2]:

Teorema 3.1 (Teorema de Rosenthal) Si {f_{n}} es una sucesión de funciones continuas (de un espacio polaco X en ℝ), entonces existe una subsucesión convergente o existe una subsucesión que no tiene subsucesiones convergentes.

Un subconjunto A de [ℕ]^{ω} determina una partición de [ℕ]^{ω} en dos, A y su complemento. Decimos que A tiene la propiedad de Ramsey, o simplemente que A es un conjunto de Ramsey, si existe un H ⊆ ℕ infinito homogéneo para la partición determinada por A, es decir, si [H]^{ω} está contenido en A o es disjunto de A. El resultado de Silver indica entonces que todo conjunto analítico es de Ramsey.

Los conjuntos cuyo complemento es analítico son llamados coanalíticos. Por los resultados de Suslin, la existencia de analíticos no borelianos es equivalente a la existencia de conjuntos analíticos no coanalíticos. Tomando imágenes de conjuntos coanalíticos mediante funciones continuas, obtenemos una clase todavía más amplia de conjuntos, y continuando de este modo, tomando complementos e imágenes por funciones continuas cualquier número de veces, obtenemos la clase de los conjuntos llamados proyectivos. Los conjuntos analíticos son medibles Lebesgue, y además tienen otras propiedades de regularidad como lo son la Propiedad de Baire y la Propiedad del subconjunto perfecto (ver más abajo la definición de esta última). Sin embargo, no es demostrable a partir de los axiomas de Zermelo-Fraenkel de la teoría de conjuntos que toda imagen continua de un coanalítico sea medible Lebesgue. Tampoco es demostrable que los conjuntos coanalíticos tengan la propiedad del subconjunto perfecto.

R. Solovay en un importante trabajo de 1970 ([25]) estudió la relación entre medibilidad Lebesgue (y otras propiedades de los conjuntos de números reales) y el Axioma de Elección. Como es bien conocido, la existencia de conjuntos no medibles Lebesgue sigue del Axioma de Elección. También se demuestra usando el axioma de elección que hay conjuntos que no tienen la propiedad de Baire y conjuntos no numerables que no contienen subconjuntos perfectos. Solovay estableció la posibilidad de que la medida de Lebesgue mida todo conjunto de números reales al construir un modelo de la teoría de conjuntos donde no vale el axioma de elección (aunque sí una versión más débil llamada axioma de elecciones dependientes) y donde todo conjunto de números reales es medible, tiene la propiedad de Baire y, si es no numerable, contiene un subconjunto perfecto. El resultado de Solovay requiere una hipótesis de consistencia fuerte, la consistencia de la existencia de cardinales inaccesibles con la teoría de Zermelo-Fraenkel.

También quedó establecido por Solovay que aún con el axioma de elección, es consistente que todos los conjuntos proyectivos tengan las propiedades de regularidad mencionadas (siempre que se suponga la consistencia de la teoría de Zermelo-Fraenkel junto con la existencia de cardinales inaccesibles).

Una introducción a los conjuntos proyectivos se puede encontrar en [8], una referencia muy completa la provee la obra [15].

El Teorema de Solovay, junto a resultados posteriores de Shelah [23], permite establecer una diferencia importante entre medida de Lebesgue y categoría de Baire, a saber, la consistencia de que todos los conjuntos de números reales son medibles Lebesgue con la teoría ZF es una hipótesis más fuerte que la que establece la consistencia de que todos los conjuntos de reales tengan la propiedad de Baire. La primera es equivalente a la consistencia de ZF C+“existe un cardinal inaccesible”, mientras la segunda es equivalente a la consistencia de ZF C.

Una diferencia similar se puede establecer entre la propiedad de subconjunto perfecto y la propiedad de Bernstein que mencionaremos más adelante.

El Axioma de Elección implica la existencia de conjuntos que no tienen la propiedad de Ramsey (en efecto, los conjuntos totalmente imperfectos, definidos más adelante no pueden ser de Ramsey). A. Mathias [18] demostró que en el modelo de Solovay, todo conjunto de números reales es de Ramsey. Por lo tanto, la consistencia de ZF C+“Existe un cardinal inaccesible” implica la consistencia de ZF + DC+“Todo conjunto de números reales es de Ramsey”. No se sabe si la hipótesis sobre cardinales inaccesibles es necesaria en este caso.

4 Avances recientes.

a) Particiones de conjuntos de sucesiones finitas.

Si en vez de considerar particiones del conjunto de subconjuntos de n elementos de un conjunto dado consideramos particiones de la colección de sucesiones de longitud n formadas por elementos de ese conjunto, la situación cambia drásticamente.

Consideremos por ejemplo lo que ocurre con particiones del producto cartesiano ℕ × ℕ. Conociendo el teorema de Ramsey, estaríamos tentados a decir que para cada partición de ℕ × ℕ en dos pedazos, existe un conjunto infinito H ⊆ ℕ tal que H × H está contenido en uno de los pedazos. Esto no es verdad, para la partición ℕ × ℕ = A ∪ B definida por (n, m) ∈ A si y sólo si a < b, no existen conjuntos infinitos H y J tales que el producto H × J está contenido en una de las partes. Lo que si es cierto es que para cada partición ℕ × ℕ = A ∪ B y para cada n ∈ ℕ existe un conjunto infinito H y un conjunto N con al menos n elementos tales que H × N está contenido en uno de los pedazos.

Usaremos la siguiente notación para expresar propiedades de particiones polarizadas. Si α, β, γ, δyλ son cardinales,

(\begin{matrix}α \\ β \end{matrix}) ⟶ (\begin{matrix}γ \\ δ \end{matrix})_{λ}

significa que para toda partición de α × β en λ pedazos, existe un subconjunto H_{1} ⊆ α de cardinalidad γ y un subconjunto H_{2} ⊆ β de cardinalidad δ tales que H_{1} × H_{2} esta contenido en uno de los pedazos de la partición. Estas son las llamadas particiones polarizadas. Una introducción al caso de productos de dos factores y algunos resultados para productos de un número finito de factores se puede encontrar en [26].

Consideremos ahora el caso de particiones del conjunto de las sucesiones finitas de un conjunto dado. Esto es, particiones de la colección de todos los productos de cualquier número finito de factores. Dados conjuntos A_{i} (i ∈ ω), y dada una partición de cada producto ∏_{i=0}^{k} A_{i} queremos una sucesión H_{i} tal que para cada k, el producto ∏_{i=0}^{k} H_{i} es homogéneo.

Definición 4.1 El símbolo

(κ ; κ ; κ ; ⋮) ⟶^{<ω} (2 2 2 ⋮)_{λ} .

significa que para toda F : κ^{<ω} → λ, existe una sucesión H_{0}, H_{1}, … de subconjuntos de κ tal que para cada i |H_{i}| = 2 y para cada n, F es constante en Π_{i=0}^{n}H_{i}.

Este tipo de propiedad de partición fue estudiada en [1], allí se prueba en particular que ninguno de los ℵ_{n}, con n ∈ ω, satisface la propiedad para λ = 2, sin embargo, la existencia de ciertos cardinales grandes implica directamente la existencia de cardinales que tienen la propiedad. Esto sugiere preguntarse si la propiedad

(κ ; κ ; κ ; ⋮) ⟶^{<ω} (2 2 2 ⋮)_{2}

es una propiedad de gran cardinalidad para el cardinal κ.

En el mismo artículo [1] se demuestra el siguiente teorema.

Teorema 4.1 Suponiendo la Hipótesis Generalizada del Continuo, el menor cardinal κ que satisface la relación

(κ ; κ ; κ ; ⋮) ⟶^{<ω} (2 2 2 ⋮)_{2}

tiene cofinalidad ω o es inaccesible.

Este teorema deja abierta la posibilidad de que ℵ_{ω}, el supremo de los ℵ_{n} (n ∈ ω), sea precisamente el menor cardinal con la propiedad de partición mencionada. Este resultó un problema interesante, resuelto en [7]: el que ℵ_{ω} sea el menor cardinal con la propiedad es indecidible, y es equiconsistente con la existencia de cardinales medibles. De modo que no es posible determinar cuál es el primer cardinal con la propiedad que estamos considerando a menos que se añadan axiomas adicionales a la teoría ZF.

b) Productos infinitos (particiones de ℝ).

En vez de trabajar directamente con los números reales, conviene considerar varios espacios intimamente relacionados con el de los números reales. Uno de estos espacios es el espacio de Cantor que denotaremos por 2^{ω}. Este espacio es el obtenido dotando al conjunto de sucesiones infinitas de ceros y unos con la topología producto que resulta de dar a {0, 1} la topología discreta. Resulta sencillo verificar que esta topología está generada por los conjuntos de la forma

V_{s} = {x ∈ 2^{ω} : s ⊆ x},

donde s es una sucesión finita de ceros y unos. En otras palabras, dada una sucesiíon finita s de ceros y unos, la vecindad básica determinada pos s es la colección de todas las sucesiones infinitas de ceros y unos que comienzan con s. El espacio de Cantor es compacto y perfecto. Si miramos las sucesiones infinitas de ceros y unos como funciones características de subconjuntos del conjunto de los números naturales, podemos identificar estas sucesiones con subconjuntos de ℕ.

Otro espacio que conviene considerar es el llamado espacio de Baire. Este es el conjunto de todas las sucesiones infinitas de números naturales con la topología producto que se obtiene cuando se considera ℕ con la topología discreta. También en este caso es fácil describir los elementos de una base de la topología. Dada una sucesión finita s de números naturales, la vecindad básica determinada por s es

U_{s} = {x ∈ ℕ^{ℕ} : s ⊆ x}.

El espacio de Baire es homeomorfo al conjunto de los irracionales con la topología heredada de la recta real, y por lo tanto es también homeomorfo al espacio [ℕ]^{ω} que mencionamos anteriormente.

Todos estos espacios junto con ℝ, son espacios métricos completos y separables. Los espacios métricos que tienen todas estas propiedades son comunmente llamados espacios polacos.

Un subconjunto de un espacio polaco es perfecto si es cerrado, no vacío y no tiene puntos aislados. Es relativamente sencillo demostrar que un conjunto perfecto tiene cardinalidad 2^{ℵ_{0}}, la cardinalidad del continuo.

Teorema 4.2 (Cantor-Bendixon) Todo conjunto cerrado y no numerable de números reales contiene un subconjunto perfecto.

Este resultado vale para subconjuntos cerrados de cualquier espacio polaco. Se puede demostrar un resultado mucho más fuerte, a saber, todo conjunto analítico no numerable contiene un subconjunto perfecto.

Un conjunto A es totalmente imperfecto si todo conjunto perfecto tiene intersección no vacía tanto con A como con su complemento. Usando el axioma de elección se puede demostrar la existencia de conjuntos totalmente imperfectos en cualquier espacio polaco. Este resultado se debe a Bernstein, quien también notó que un conjunto totalmente imperfecto no puede ser medible Lebesgue ni puede tener la propiedad de Baire. Nótese que si existe un conjunto totalmente imperfecto, entonces existe un conjunto no numerable sin subconjuntos perfectos.

Diremos que un conjunto A tiene la propiedad de Bernstein si no es totalmente imperfecto, es decir, si contiene o es disjunto de un subconjunto perfecto.

Podemos ver la propiedad de Bernstein como una propiedad de partición, ya que dado un conjunto A, el que A tenga la propiedad de Bernstein quiere decir que para la partición del espacio en A y su complemento, existe un conjunto perfecto contenido en uno de los dos pedazos de la partición.

Solovay demostró en 1970 [25] que si ZF C+“Existe un cardinal inaccesible” es consistente entonces también lo es ZF + DC+“todo conjunto no numerable de números reales tiene un subconjunto perfecto”. DC es una versión débil del axioma de elección llamada axioma de elecciones dependientes. DC implica el axioma de elección para familias numerables de conjuntos.

La consistencia de ZF C no basta para probar la consistencia de “todo conjunto no numerable de números reales tiene un subconjunto perfecto” con ZF, sin embargo, se puede demostrar que a partir de la consistencia de ZF C si se puede demostrar la consistencia de ZF +DC+“todo conjunto tiene la propiedad de Bernstein”. Para ver esto último, conviene recordar un resultado de Shelah que establece la consistencia de ZF C+“todo conjunto de números reales tiene la propiedad de Baire” a partir de la consistencia de ZF C [23].

Teorema 4.3 Todo conjunto con la propiedad de Baire contiene un subconjunto perfecto o es disjunto de un conjunto perfecto.

Demostración. Aunque este resultado vale para cualquier espacio polaco, lo demostraremos en el caso del espacio de Cantor. Sea A ⊆ 2^{ℕ} un conjunto con la propiedad de Baire. Es decir, existe un abierto O y un conjunto magro M tales que A = OΔM. El conjunto M es una unión numerable de conjuntos nunca densos, M = ∪_{i}N_{i}. Si O ≠ ∅, sea V_{s} una vecindad básica contenida en O. Cada una de las sucesiones finitas s ⌢ 0 y s ⌢ 1 se puede extender para evitar N_{0}, es decir, existen sucesiones finitas s_{0} y s_{1} de ceros y unos tales que tanto V_{s⌢0⌢s_{0}} y V_{s⌢1⌢s_{1}} son vecindades disjuntas de N_{0}. Ahora extendemos cada una de las cuatro sucesiones s ⌢ 0 ⌢ s_{0} ⌢ 0, s ⌢ 0 ⌢ s_{0} ⌢ 1, s ⌢ 1 ⌢ s_{1} ⌢ 0 y s ⌢ 1 ⌢ s_{1} ⌢ 1 de modo de evitar N_{1}. Continuando de este modo, construimos un conjunto perfecto (las ramas de un árbol donde cada nodo tiene sucesores incomparables) disjunto de M y contenido en O, y por lo tanto contenido en A. Si O fuese vacío, este mismo proceso da como resultado un conjunto perfecto disjunto de A. □

Corolario 4.1 Si ZF C es consistente, entonces también lo es ZF +DC+“todo conjunto de números reales tiene la propiedad de Bernstein”.

Sabiendo que el axioma de elección implica la existencia de conjuntos totalmente imperfectos, resulta interesante preguntarse si se puede obtener esta misma conclusión a partir de versiones débiles del axioma de elección. Hemos mencionado que el axioma de elecciones dependientes no basta, ya que si ZF C es consistente entonces hay un modelo de ZF donde vale el axioma de elecciones dependientes y todo conjunto de números reales tiene la propiedad de Bernstein (además, en el modelo de Solovay vale el axioma de elecciones dependientes y todo conjunto no numerable de números reales contiene un subconjunto perfecto).

Una consecuencia del axioma de elección que interesa examinar en este contexto es la existencia de ultrafiltros en ℕ. Recordemos que un filtro F en ℕ es una colección de subconjuntos de ℕ con las siguientes propiedades.

1. ℕ ∈ F,

2. Para A, B ∈ ℕ, A ∈ F y A ⊆ B implica B ∈ F,

3. A, B ∈ F implica A ∩ B ∈ F.

Un filtro F es no trivial si ∅ ∉ F, y es un ultrafiltro si es un filtro maximal no trivial. Equivalentemente, U es un ultrafiltro en ℕ si es un filtro y para todo A ⊆ ℕ, A ∈ U si y solamente si ℕ \ A ∉ U.

Es fácil verificar que para cada a ⊆ ℕ, la colección {B ⊆ ℕ : A ⊆ B} es un filtro, y si A tiene un único elemento a, entonces es un ultrafiltro y se llama el ultrafiltro principal generado por a. La existencia de ultrafiltros no principales es una consecuencia del Lema de Zorn. En efecto, la coleccíon de subconjuntos de ℕ cuyo complemento es finito es un filtro, llamado el filtro de Frechet. Cualquier filtro maximal (no trivial) que extienda al filtro de Frechet es un ultrafiltro no principal.

Es bien conocido que lema de Zorn y el axioma de elección son equivalentes. La existencia de ultrafiltros no principales es estrictamente más débil que cualquiera de esos dos principios, es decir el lema de Zorn implica la existencia de ultrafiltros no principales en ℕ, pero no es implicado por ésta (ver, por ejemplo, [19]).

La existencia de ultrafiltros no principales no basta para demostrar la existencia de conjuntos totalmente imperfectos. En el artículo [3] se prueba la consistencia de “todo conjunto de números reales tiene la propiedad de Bernstein” con la existencia de ultrafiltros no principales en ℕ y ZF + DC (suponiendo la consistencia de ZF C y la existencia de cardinales inaccesibles).

Un estudio más amplio de varias propiedades relacionadas con conjuntos perfectos y la existencia de ultrafiltros no principales apareció posteriormente en [6].

Referencias

[1] M. Carrasco, C.A. Di Prisco y A. Millán, “Partitions of the set of finite sequences” Journal of Combinatorial Theory, Series A 71 (1995) 255-274.

[2] J. Diestel, Sequences y Series in Banach Spaces. Springer-Verlag (1984).

[3] C. A. Di Prisco, Partition properties y perfect sets. Notas de Lógica Matemática 38, Universidad Nacional del Sur, Bahía Blanca, Argentina (1993) 119-127.

[4] C. A. Di Prisco, Algunos aspectos de la teoría de particiones. Boletín de la Asociación Matemática Venezolana 1 (2) (1994) 43–55.

[5] C. A. Di Prisco, Una Introducción a la teoría de conjuntos. Coleçao CLE, Campinas (1997).

[6] C. A. Di Prisco y S. Todorcevic, Perfect-set properties in L(ℝ)[U]. Advances in Mathematics 139 (1998) 240-259.

[7] C. A. Di Prisco y S. Todorcevic, A cardinal defined by a polarized partition property. Israel Journal of Mathematics 109 (1999) 41-52.

[8] C. A. Di Prisco y C. E. Uzcátegui, Una introducción a la teoría descriptiva de conjuntos. Escuela Venezolana de Matemáticas. (1992)

[9] P. Erdös y R. Rado, A partition calculus inset theory. Bull. Amer. Math. Soc. 62 (1956) 427–489.

[10] P. Erdös, A. Hajnal, A. Máté y R. Rado, Combinatorial Set Theory. Partition Relations para Cardinals. North Holland, (1984).

[11] F. Galvin y K. Prikry, Borel sets y Ramsey’s Theorem. Journal of Symbolic Logic 38, (1973)193-198 [12] R. L. Graham, B. L. Rothschild y J. H. Spencer, Ramsey Theory. John

Wiley y Sons (1990).

[13] Kahn, J. y Kalai, G., A counterexample to Borsuk’s conjecture. Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 60–62.

[14] A. Kanamori, The higher infinite. Springer Verlag (1994)

[15] A. Kechris, Classical Descriptive Set Theory. Springer Verlag (1995).

[16] J. Llopis, A note on polarized partitions. Notas de Lógica Matemática INMABB-CONICET, Bahia Blanca, Argentina vol. 39 (1993).

[17] J. Llopis y S. Todorcevic, Borel partitions of products of finite sets. Acta Científica Venezolana vol.47 (1996).

[18] A.R.D. Mathias, “Happy Families” Annals of Math. Logic 12 (1977) 59-111.

[19] G. H. Moore, Zermelo’s Axiom of Choice. Springer Verlag, (1982).

[20] J. Nešteřil y V. Rödl (Eds.), Mathematics of Ramsey Theory. Springer Verlag (1990).

[21] E. Odell, Applications of Ramsey Theorems to Banach Space Theory. Austin, University of Texas Press (1981)

[22] F. P. Ramsey , On a problem of formal logic. Proc. of the London Mathematical Society, Ser. 2 30, Part 4 (1928) 338–384.

[23] S. Shelah, Can you take Solovay’s inaccessible away? Israel Journal of Mathematics 48 (1984) 1-47

[24] J. Silver Every analytic set is Ramsey. Journal of Symbolic Logic 35 (1970) 60-64.

[25] R. Solovay, A model of set theory in which every set of reals is Lebesgue measurable. Annals of Mathematics 92 (1970) 1-56.

[26] N. H. Williams, Combinatorial Set Theory. North Holland (1977).