Ultrafiltros y aplicaciones

ULTRAFILTROS Y APLICACIONES Manuel Camúñez Triguero ULTRAFILTROS Y APLICACIONES Manuel Camúñez Triguero Memoria presentada como parte de los requisitos para la obtención del título de Máster Universitario en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. MªÁngeles Japón Pineda Índice general English Abstract 1 1. Generalidades 7 1.1. Aplicación y relaciones con la Topología . . . . . . . . . . . . . . . . 16 1.2. Comparación y relaciones con las redes . . . . . . . . . . . . . . . . . 25 2. Aplicación al Análisis 31 3. La compactificación de Stone-Čech 37 4. Algunas aplicaciones a la Teoría de Ramsey 47 5. Aplicación al Teorema de Arrow 53 English Abstract In this document, we present the notion of ultrafilter and study some of its properties and applications. Firstly, the manuscript begins with a general study of filters and ultrafilters, and compare them with some other more broadly extended mathematical concepts such as topology or nets. Next, ultrafilters are applied as relevant tools in some other areas of Mathematics, such as Analysis or Combinatorics. The last chapter consists of an application of ultrafilters to Social Sciencies and more particularly to the Arrow’s Imposibility Theorem. Introducción El concepto de ultrafiltro nace a principios del siglo XX introducido por Riesz, y su uso se extendió rápidamente entre los círculos matemáticos, de la mano de figuras como Banach, Tarski o Bourbaki. Los ultrafiltros formalizan una serie de ideas conceptuales, por ejemplo, dado un conjunto establecer cuáles de sus subconjuntos tienen mucho “peso”, o cuales son “muy grandes”. Pero la relevancia de los ultrafiltros puede ir mucho más allá. Los ultrafiltros también pueden usarse para generalizar nociones de convergencia topológica. Aquí la palabra topológica significa que dicha convergencia se expresa en términos cualitativos. Dígase, un objeto es convergente o no lo es. Aunque a primera vista parezca una limitación, permite el uso de dicha herramienta para el estudio matemático de “tendencias” en contextos donde no procede el concepto clásico de convergencia de una sucesión numérica. Este documento busca introducir al lector a los ultrafiltros (pasando previamente por los filtros), estudiando propiedades generales y comparándolos con otras estructuras matemáticas más extendidas, y posteriormente aplicarlos en ramas y problemas varios de la Matemática, justificando el interés de tal objeto. El desglose por capítulos es el siguiente: El capítulo primero es el de mayor extensión. Se definen los ultrafiltros, se demuestran las propiedades principales y se comparan con la topología y las redes. El capítulo segundo usa los ultrafiltros como herramienta para el estudio de di- 10 ultrafiltros y aplicaciones Un filtro principal basado en un conjunto Ano unitario no puede ser principal, puesto que si Ano es unitario existe Bcontenido estrictamente en Ay gracias a la Observación 1.1 F(B)es más fino que F(A). Como Bno puede ser un elemento del filtro F(A)pero es un elemento de F(B), la contención es estricta, contradiciendo la maximalidad del ultrafiltro. El siguiente resultado se le conoce como el Principio del Ultrafiltro, y es de mucha importancia en la rama de Fundamentos de la Matemática: Teorema 1.1 (Principio del Ultrafiltro). Todo filtro Fen un conjunto Xestá contenido en un ultrafiltro Gtambién en X. Para demostrarlo serán necesarias las siguientes herramientas algebraicas: Definición 1.8 (Orden parcial). en un conjunto Xun orden parcial es una relación ∼ ∼ ∼que verifica: 1. x∼x 2. x∼yey∼ximplica x=y 3. x∼yey∼zimplica x∼z. en tales condiciones se suele denotar por ≤a la relación ∼ ∼ ∼, y al par (X,≤)un conjunto parcialmente ordenado. Definición 1.9 (Cadena). En un conjunto parcialmente ordenado (X,≤)un subconjunto Cse dice una cadena si para cualesquiera x, y ∈ C se verifica x≤yóy≤x. Lema 1.1 (Lema de Zorn).Si (X,≤) es conjunto parcialmente ordenado tal que toda cadena Ctiene una cota superior, entonces existe un elemento maximal en X. Demostración (Teorema 1.1).Vamos a usar el Lema de Zorn. Consideremos el conjunto de los filtros más finos que Fy en dicho conjunto consideramos el orden parcial F1≤ F2si se verifican las contenciones F ⊆ F1⊆ F2⊆ P(X). Sea entonces una cadena C={Fα:α∈A}. Considérese el conjunto siguiente: G:= SαFα. Es obvio que Fα⊆ G para todo αy que F ⊆ G, por tanto sólo falta por probar que Ges efectivamente un filtro. 1. generalidades 11 1) ∅/∈ F porque por definición no es elemento de ningún filtro de la cadena y X∈ G porque es elementos de F ∈ C. 2) Sean AyBelementos de G, podemos suponer sin pérdida de generalidad que existen α1yα2índices tales que A∈ Fα1yB∈ Fα2con Fα1≤ Fα2. En particular se verifica que tanto Acomo Bson elementos de Fα2, y por ser este filtro se tiene A∩B∈ Fα2⊆ G. 3) Sean F∈ G yF′⊇F. Entonces existe αcon F∈ Fα, pero por ser filtro tenemos F′∈ Fα⊆ G. Por tanto Ges un filtro. Como toda cadena tiene un elemento maximal, existe un elemento maximal en el conjunto de los filtros más finos que F, y tal elemento es el ultrafiltro deseado. Lema 1.2.Si Fes un ultrafiltro las siguientes condiciones son equivalentes: a) Fes un ultrafiltro no principal b) Ningún conjunto finito es un elemento de F Demostración. El esquema de la demostración es probar no b) implica no a) seguido de no a) implica no b). Supongamos que Fcontiene algún conjunto finito S={s1, s2,· · · , sn}, entonces si {sn} ∈ F el ultrafiltro es principal de manera directa. En caso contrario Sy X\ {sn}son simultáneamente elementos del ultrafiltro y por tanto su intersección también. Como la intersección es el conjunto {s1, s2,· · · , sn−1}, aplicando el mismo argumento inductivamente llegamos a que algún conjunto unitario {si}debe ser un elemento del ultrafiltro, haciéndolo principal. Si Fes principal, gracias al Ejemplo 1.1 tiene que estar basado en un conjunto unitario, en particular uno de sus elementos es un conjunto unitario, negando la propiedad b). Teorema 1.2. Un filtro Fes un ultrafiltro en Xsi y sólo si para todo subconjunto E de Xse tiene E∈ F óX\E∈ F. 12 ultrafiltros y aplicaciones Demostración. Supongamos que Fes un ultrafiltro. Sea entonces Fun elemento de Fcualquiera (y por tanto ha de ser no vacío). Por ser no vacío tiene intersección no vacía con EóEc. Podemos suponer sin pérdida de generalidad que F∩E=∅. Consideremos entonces la familia G:= {F∩E:F∈ F}. Es un ejercicio sencillo comprobar que dicha familia verifica las condiciones de la Proposición 1.1, y por tanto es base de un filtro Gque claramente debe de ser más fino que F. Al ser Fun ultrafiltro necesariamente se tiene F=Gy con ello E∈ F. Continuemos con la implicación inversa. Supongamos por reducción al absurdo que existe Gun filtro estrictamente más fino que F. Entonces existe A∈Gtal que A /∈ F. Por la condición hipótesis tenemos Ac∈ F ⊆ G, pero en tal caso AyAcson simultáneamente elementos del filtro G, contradiciendo la propiedades a)yb)de la Definición 1.1. Observación 1.3 (Caracterización de ultrafiltros).Dada Funa familia no vacía de subconjuntos de algún espacio Stenemos que Fes un ultrafiltro si y sólo si verifica las siguientes tres condiciones: a) ∅/∈ F. b) Si F1yF2son elementos de Fentonces F1∩F2también lo es. c) Para todo E⊆So bien E∈ F o bien Ec∈ F. Corolario 1.1.Si A1, A2,· · · , Anes una familia de subconjuntos disjuntos de Stales que su unión es un elemento de un ultrafiltro Fen Sentonces existe exactamente un ien {1,2,· · · , n}tal que Ai∈ F. Demostración. En primer lugar, en tales condiciones, de existir un Aicon Ai∈ F debe de ser único, puesto que si fuesen AiyAjelementos diferentes del ultrafiltro, Aj⊆Ac ide donde AiyAc ison simultáneamente elementos del ultrafiltro, contradiciendo el Teorema 1.1. Nos queda por probar que existe al menos un Aique esté en el ultrafiltro. Procedamos por inducción. Para n= 1 el resultado es inmediato puesto que la afirmación la unión es un elemento del ultrafiltro se reduce a A1∈ F. Supóngase cierto el resultado para un cierto ny veamos que también es cierto para n+ 1. Sean A1, A2,· · · , An, An+1 tales que la unión de todos ellos es un ele- 1. generalidades 13 mento del ultrafiltro. Considérese A=⊔n i=1An. Se tiene entonces de forma inmediata A⊔An+1 ∈ F. Si fuese An+1 ∈ F se concluye la prueba. En caso contrario, debe darse Ac n+1 ∈ F por el Teorema 1.1. Se puede comprobar fácilmente la igualdad: A= n+1 [ i=1 Ai!∩Ac n+1. Y como son ambos objetos entre paréntesis elementos del ultrafiltro, su intersección Atambién lo es por el segundo apartado de la Definición 1.1. Aplicando la hipótesis de inducción a Ase concluye la tesis buscada. Una cuestión interesante es plantear si es posible caracterizar los ultrafiltros principales. Cuando el conjunto Ssobre el que se construye el ultrafiltro es finito es inmediato que todos los ultrafiltros son de la forma F(x)para algún xde S. Cuando el conjunto es infinito aparecen nuevos ultrafiltros “no triviales”. Observación 1.4.Si Ses infinito, entonces existen ultrafiltros no principales. Efectivamente, consideremos Fel filtro de Frechet. Por el Teorema 1.1 está contenido en un ultrafiltro G. Sea x∈S, entonces {x}/∈ G, ya que el conjunto S\ {x}es un elemento de Fy este está contenido en G. Lema 1.3.Un ultrafiltro es libre si y solo si contiene al filtro de Frechet. Demostración. La implicación a derecha se debe a que en caso contrario existiría un conjunto finito S={s1, s2,· · · , sn}tal que X\Sno es un elemento del ultrafiltro y gracias a la propiedad c)de la Observación 1.3 se sigue que Ssí es un elemento del ultrafiltro. Hemos llegado a una contradicción con el Lema 1.2 y la implicación a izquierda es inmediata. En general, conocer explícitamente un ultrafiltro no principal es difícil. Para ilustrar este hecho, existen resultados de matemática fundacional que establecen la imposibilidad de probar la existencia de ultrafiltros no principales en Nusando sólo la axiomática de Zermelo-Fraekel y el llamado axioma de elección dependiente. 14 ultrafiltros y aplicaciones Es más, en matemática fundacional se sabe que el principio del ultrafiltro es equivalente al axioma de elección, lo que ilustra que los ultrafiltros son “altamente no constructivos”. Dichos resultados se encuentran en [14], p.151. Para una demostración consúltese [11]. Observación 1.5.En general, los ultrafiltros quedan muy binariamente divididos en ultrafiltros “muy trivales” (los principales) y ultrafiltros “nada triviales” (los no principales). Sorprendentemente, a pesar de que los ultrafiltros no principales son difíciles de conocer explícitamente, se puede demostrar un resultado que nos da información muy precisa sobre “cuantos hay”: Teorema 1.3. Si Ses un conjunto infinito y βS es el conjunto de los ultrafiltros en S, entonces existe una biyección βS ←→ P(P(S)). Dicho resultado se referencia en [14] y se prueba en [3] además de en [1] p. 117. Dicho teorema presenta el siguiente sorprendente resultado como corolario: Teorema 1.4. Sean Sun conjunto infinito, βS el conjunto de los ultrafiltros en Sy ΩSel conjunto de los filtros en S. Entonces existe una biyección βS ←→ ΩS Será necesario el siguiente resultado: Teorema 1.5 (Teorema de Schöder-Bernstein:). Si AyBson conjuntos tales que existen aplicaciones inyectivas (también llamadas inyecciones) de Aen By de Ben A, entonces existe una biyección entre AyB. Demostración (Teorema 1.4).Se tiene de manera inmediata la siguiente cadena de inyecciones: βS i ,−−→ ΩSi ,−−→ P(P(X)) f ,−−→ βS donde ies la inclusión correspondiente y fes la inyección dada por el Teorema 1.3. Se concluye fácilmente que existen inyecciones de βS en ΩSy viceversa, por lo que gracias al Teorema de Berstein existe la biyección. 1. generalidades 15 Observación 1.6.El Teorema 1.4 no es cierto cuando Ses finito no vacío. En tal caso sabemos que |βS|=|S|, ya que todos los ultrafiltros son principales de manera inmediata. Para el caso de los filtros, sabemos que tenemos uno diferente por cada subconjunto de S, de donde |ΩS| ≥ |P(S)|= 2|S|>|S|. Para concluir la sección, vamos a enunciar dos resultados hermanos de los cuales solo demostraremos el segundo, puesto que como se verá posteriormente, los argumentos de la segunda demostración se pueden “rescatar” para la primera. Proposición 1.3.Sean dos conjuntos XeY, una aplicación f:X→YyFun filtro en X, entonces la familia: f(F) = {f(F) : F∈ F} define una base de un filtro en Y, al que en ocasiones nos referiremos como filtro imagen. Proposición 1.4.Sean dos conjuntos XeY, una aplicación f:X→YyFun ultrafiltro en X, entonces la familia: f(F) = {f(F) : F∈ F} define un ultrafiltro en f(X), al que en ocasiones nos referiremos como ultrafiltro imagen. Demostración. Usaremos la caracterización de la Observación 1.3. En primer lugar, se verifica fácilmente que X∈f(F)y∅/∈f(F). Seguidamente, sean G1yG2en f(F)y sean F1yF2dos elementos de Ftales que f(F1) = G1yf(F2) = G2. Entonces por ser Ffiltro F1∩F2es un elemento de Fy consecuentemente un elemento de f(F)es f(F1∩F2)⊆f(F1)∩f(F2) = G1∩G2, probando que la intersección G1∩G2es un elemento de f(F)por la propiedad b) de la Definición 1.1 Para el apartado final sea Aun subconjunto de f(X)y sea Ac:= f(X)\A. Definimos B:= f−1(A), teniendo de forma directa Bc:= X\B=f−1(Ac). Por ser Fultrafiltro o bien B∈ F o bien Bc∈ F. Debido a las igualdades f(B) = Ay f(Bc) = Acse tiene de forma inmediata A∈f(F)oAc∈f(F). 16 ultrafiltros y aplicaciones Observación 1.7.Observemos que en el resultado para filtros se ha afirmado que el conjunto filtro imagen define una base de filtros para el conjunto Yal completo mientras que en segundo resultado se ha afirmado que el filtro imagen es un filtro para la imagen de la aplicación. Dichas afirmaciones son intercambiables y los resultados son ciertos, pero se ha incluido “una de cada una” para enfatizar la libertad de elección. Proposición 1.5.Sean dos conjuntos XeY, una aplicación f:X−→ YyFun (ultra)filtro en X, entonces la familia: f(F) = {A⊆Y:f−1(A)∈ F} define un (ultra)filtro en Y, al que en ocasiones nos referiremos como (ultra)filtro imagen. Demostración. Probaremos el caso Ffiltro. Bastará con comprobar que dicha familia tiene por base la definida en la Proposición 1.3. Sea A∈f(F). Sea F=f−1(A), que por hipótesis es un elemento de F. Entonces f(F) = f(F−1(A)) ⊆A, luego Aes un elemento del filtro definido por la base de la Proposición 1.3. Sólo resta por comprobar que todo elemento del conjunto {f(F) : F∈ F} está en nuestro nuevo f(F). Sabemos F⊆f−1(f(F)), luego si F∈ F se sigue f−1(f(F)) ∈ F, de donde f(F)∈f(F), concluyendo la equivalencia. La demostración para el caso Fultrafiltro es totalmente análoga. Observación 1.8.Los argumentos dados en la demostración de la Proposición 1.5 en realidad demuestran que los filtros imagen de la Proposición 1.3 y la Proposición 1.5 son el mismo, y por tanto las definiciones son equivalentes. Lo mismo para el caso de los ultrafiltros imagen. 1.1 Aplicación y relaciones con la Topología Comenzaremos dando una introducción breve a los conceptos básicos de la Topología y algunos resultados fundamentales. 1. generalidades 17 Definición 1.10. Sea Xun conjunto. Una familia τde subconjuntos de Xse dice que es una topología sobre Xsi verifica las siguientes propiedades: 1. ∅, X ∈τ; 2. Si UyVson elementos de τentonces U∩Vtambién lo es; 3. Si {Ui}i∈Ies una colección arbitraria de elementos de τentonces ∪i∈IUitambién lo es. Si se dan tales condiciones a los elementos de τse les llama conjuntos abiertos de la topología, y a los complementarios en Xde dichos conjuntos de les llama los conjuntos cerrados de la topología. Al par (X, τ)se le llama espacio topológico. Si (X, τ)es un espacio topológico y el contexto no da lugar a confusión, se hará referencia al espacio como simplemente X. Algunas de las nociones importantes de la rama son las siguientes: Definición 1.11 (Conjunto compacto). Sean Xes un espacio topológico y Kun subconjunto suyo. Decimos que Kes compacto si para cualquier familia {Ui}i∈Ide abiertos de la topología con K⊆ ∪i∈IUiexiste una selección finita de elementos de la familia {Ui1, Ui2,· · · , Uin}tales que K⊆ ∪n k=1Uik. Definición 1.12 (Punto interior). Sea Xun espacio topológico y sea xun elemento del mismo. Decimos que un conjunto Ees un entorno de xsi existe un abierto Ucon x∈U⊆E. Al conjunto {x∈E:Ees entorno de x}se le denomina el interior de E, y se denota int(E). Definición 1.13. Si Xes un espacio topológico, denotamos por Uxa la familia de conjuntos que son entornos abiertos de x. Observación 1.9.La familia de los entornos de xes un filtro que tiene por base Ux. Definición 1.14. Sea Xun espacio topológico y Fun subconjunto cualquiera del mismo. Denotamos por Fy denoninamos por clausura de Fal conjunto: {x∈X:∀U∈ Ux, U ∩F=∅}. Un resultado importante de equivalencia de compacidad es el siguiente: Proposición 1.6.Sea Xun espacio topológico y Kun subconjunto suyo. Entonces Kes compacto si y solo si toda colección {Fi}i∈Ide cerrados contenidos en Kque verifica la propiedad de la intersección finita tiene intersección no vacía. 18 ultrafiltros y aplicaciones Una topología sobre un conjunto es habitualmente percibida como una de las estructura más generales posibles sobre la que estudiar nociones como la convergencia de sucesiones o la continuidad de una aplicación, que admiten la siguiente expresión en términos de la topología: Definición 1.15 (Límite de una sucesión). Sea Xun espacio topológico y sea {xn}n∈Nuna sucesión en dicho conjunto. Decimos que xes un límite de la sucesión si para cada Uentorno abierto de x, existe n0(que depende de U) tal que {xn}n≥n0está contenido en U. En tales condiciones se dice que la sucesión {xn}n∈Nconverge a x. Definición 1.16 (Aplicación continua). Sean (X, τX)e(Y, τY)espacios topológicos y sea f:X→Yuna aplicación entre ambos. Sea x∈X, decimos que fes continua en xsi para cada Vabierto de τYcon f(x)∈Vexiste U∈τXcon f(U)⊆V. Decimos que fes continua si para cada Vabierto de τYexiste U∈τXcon f(U)⊆V. Proposición 1.7.Sean (X, τX)e(Y, τY)espacios topológicos y sea f:X→Yuna aplicación entre ambos. Entonces fes continua en xsi y solo si para cada V∈τY con f(x)∈Vse verifica que f−1(V)es entorno abierto de x. Además, fes continua si y solo si para cada V∈τYse verifica f−1(V)∈τX. De ahora en adelante para referirnos a una aplicación continua haremos referencia a la definición que más cómoda resulte en el contexto. Finalmente, pasamos a definir nociones de convergencia usando filtros y ultrafiltros, para ilustrar las similitudes con la topología, e incluso se demostrarán algunos resultados de “paralelismo” entre ambas estructuras. Definición 1.17. Dado un filtro Fdecimos que Fconverge a x si Ux⊆ F. Cuando es así escribimos F → x. Un buen resultado para mostrar el interés de los ultrafiltros es la siguiente equivalencia de la compacidad, noción topológica de importancia difícil de exagerar: Teorema 1.6. Sea Xun espacio topológico, entonces las siguientes condiciones son equivalentes: a) Xes compacto; 1. generalidades 19 b) Todo ultrafiltro en Xes convergente. Demostración. Usaremos la caracterización proporcionada por la Proposición 1.6. Supongamos cierto a). Sea Fun ultrafiltro y sean A1, A2,· · · , Anelementos del mismo. Tenemos de forma directa ∩n i=1Ai⊇ ∩n i=1Ai=∅. Es decir, la familia AA∈F verifica la propiedad de la intersección finita, y por compacidad de X, tienen intersección no vacía. Sea x∈ ∩A∈F A. Por ser x∈Apara todo Adel ultrafiltro, para cada V entorno abierto de xse tiene A∩V=∅. Consecuentemente tiene sentido considerar la base de filtros: B={A∩V:A∈ F, V ∈ Ux} Debido a la inclusión F ⊆ B, el ultrafiltro debe de estar contenido en el filtro generado por la base, pero la condición de ser filtro maximal implica que han de coincidir, concluyendo B ⊆ F. Lo anterior justifica que todo abierto Ventorno de xverifica V=X∩V∈ B ⊆ F, probando la convergencia del ultrafiltro. Supóngase ahora que se verifica b). Sea {Ci}una familia de cerrados con la propiedad de la intersección finita. En particular se verifican las hipótesis de la Proposición 1.2, existe un filtro Fque contiene a la familia y en virtud del Teorema 1.1 podemos imponer que Fsea ultrafiltro. En particular cada Cide la familia es un elemento del ultrafiltro. La hipótesis b)nos asegura que existe x∈Xcon U∈ F para cada Uentorno de x. Se ha de verificar x∈Cipara cada Cide la familia. Si no fuese así, existiría Cicon x /∈Ci, es decir, x∈Cc i. Como los Cison cerrados, los Cc ison abiertos y por tanto entornos de x, lo que implicaría Cc i∈ F, contradiciendo Ci∈ F. Como x∈Cipara cada i, se sigue de forma directa que la familia tiene intersección no vacía. Definición 1.18 (Punto de acumulación). Dado un filtro Fen un conjunto S decimos que x∈Ses un punto de acumulación si ∀F∈ F y∀U∈ Uxse tiene F∩U=∅. Alternativamente: x∈\ F∈F F. 26 ultrafiltros y aplicaciones Cuando el contexto no dé lugar a confusión se denotará (xλ)para hacer referencia a la red (xλ)λ∈Λ. Definición 1.22 (Subred). Una subred asociada a una red f: Λ →Xes una aplicación g:M→Xtal que g=f◦φ, donde φ:M→Λes una aplicación con dominio un conjunto dirigido que es creciente y cofinal. Es decir: 1. φ(m1)≤φ(m2)en Λsi m1≤m2en M; 2. Para cada λ∈Λ, existe m∈Mcon λ≤φ(m). Normalmente, si µ∈Mse denotará por xλµpara denotar al elemento g(µ) = f(φ(µ)), y denotaremos a la subred per se como (xλµ)µ∈M. Cuando el contexto no dé lugar a confusión denotaremos (xλµ)para denotar a la subred (xλµ)µ∈M. El siguiente paso será definir una noción de convergencia en términos de redes: Definición 1.23 (Red convergente). Sea (xλ)una red en un espacio topológico Xy sea x∈X. Decimos que (xλ)es una red convergente a x, y lo denotamos por xλ→x, si para cada Uentorno abierto de xexiste un λ0∈Λtal que xλ∈Upara cada λ≥λ0. En estas circustancias se dice que tenemos una red residual en U. Definición 1.24 (Punto de acumulación de una red). Dada una red (xλ)en un espacio topológico Xyx∈X, decimos que xes un punto de acumulación de la red si para cada Uentorno abierto de xy para cada λ∈Λexiste λ0≥Λcon xλ0∈U. Finalmente, pasamos a enunciar una serie de resultados que exponen la similitud entre las redes y los filtros. Dichos resultados se enunciarán sin demostración, pero pueden encontrarse con prueba incluida en [15]. Teorema 1.11. Una red (xλ)un punto de acumulación en xsi y sólo si posee una subred convergente a x. 1. generalidades 27 Teorema 1.12. Si Ees un subconjunto de Xentonces: x∈E⇐⇒ [Existe una red (xλ)en Econ xλ→x]. Teorema 1.13. Sean XeYespacios topológicos y f:X→Yuna función del primero en el segundo. Entonces dado x0∈Xse tiene: fes continua en x0⇐⇒ [(xλ)λ∈Λconverge a x0implica que (f(xλ))λ∈Λconverge a f(x0)] . Proposición 1.12.Sea (xλ)λ∈Λuna red en un producto Πα∈AXα. Entonces la red converge al punto xsi y sólo si para cada αde Ala red proyección (πα(xλ))λ∈Λconverge aπα(x0). Definición 1.25. Una red (xλ)en un conjunto Xse dice una ultrared si para cada subconjunto Ede Xse tiene que la red es residual en Eo bien es residual en X\E. Teorema 1.14. Si (xλ)λ∈Λes una ultrared en Xy existe una aplicación f:X→Y entonces (f(xλ))λ∈Λes una ultrared en Y. Dadas las fuertes similitudes entre las redes y los filtros es natural preguntarse si existe una equivalencia entre ambos conceptos. La respuesta es parcialmente afirmativa y se expondrán relaciones explícitas entre ambos: Definición 1.26 (filtro generado por una red). Sea (xλ)λ∈Λuna red en un conjunto X. Definimos el filtro generado por la red a aquel que tiene por base el conjunto formado por los siguientes elementos: Bλ0={xλ:λ≥λ0}. Dicho conjunto se comprueba fácilmente que verifica las condiciones de la Proposición 1.1 simplemente recordando que Λes un conjunto dirigido. Por ejemplo, cuando la red consiste en una sucesión, el conjunto base consiste en las colas de la sucesión, y de hecho cuando la sucesión es la trivial (xn=n)el filtro que obtenemos es el filtro de Frechet. Existe una construcción “recíproca” por la cual dado un filtro obtenemos una red en algún conjunto dirigido, dada de la siguiente forma: Definición 1.27 (red basada en un filtro). Sea Fun filtro en un conjunto X. Definimos la red basa en el filtro como aquella construida sobre el conjunto dirigido 28 ultrafiltros y aplicaciones ΛF={(x, F) : x∈F∈ F} con la relación (x1, F1)≤(x2, F2)si y solo si F2⊆F1y definida mediante la aplicación: P: ΛF−→ X (x, F)7−→ x. Dichas definiciones verifican el siguiente resultado de “intercambio”: Teorema 1.15 (de equivalencia entre filtro y red). a) Un filtro Fconverge al punto xsi y solo si la red basada en el filtro converge a x. b) Una red (xλ)converge a xsi y solo si el filtro generado por la red converge a x. Demostración. Sea Fun filtro convergiendo a x. Sea entonces Uun entorno cualquiera de xypun punto cualquiera del entorno. El elemento (p, U)es parte del conjunto dirigido, y si (q, V )es tal que (p, U)≤(q, V )entonces q∈V⊆U, es decir, para todo elemento en el conjunto dirigido en la cola a partir de (p, U)se verifica P(q, V )∈U, lo que demuestra la convergencia. Sea ahora (xλ)una red que converge a x. Sea entonces Uun entorno de xcualquiera. Por la convergencia de la red existe λ0con xλ∈Upara todo λmayor o igual aλ0, lo que implica Bλ0⊆U, concluyendo que Ues un elemento del filtro y por tanto que el filtro converge a x. Dichas transformaciones no son arbitrarias, sino que son “casi inversas” en el siguiente sentido: Lema 1.5.Si Fes un filtro, el filtro generado por la red basada en Fes F. Demostración. Por comodidad vamos a denotar por Gal filtro generado por la red basada en F. F∈ G ⇔ ∃λ0con {xλ:λ≥λ0} ⊆ F ⇔ ∃(x0, F0)con x0∈F0∈ F y{˜x: (˜x, ˜ F)≥(x0, F0)} ⊆ F ⇔ ∃(x0, F0)con x0∈F0∈ F y{˜x: ˜x∈˜ F⊆F0} ⊆ F ⇔ ∃F0∈ F con F0⊆F ⇔F∈ F. 1. generalidades 29 Sin embargo, existen redes diferentes que generan el mismo filtro. Por ejemplo, las sucesiones (vistas como redes) (xn)n∈Ncon xn= 1/n e(ym)m≥2con ym= 1/m. Debido a que la condición dada por los Bλson una condición “en alguna cola” ese elemento inicial de diferencia se puede comprobar que no afecta a la construcción del filtro. Sabemos que existe una inyección de los filtros en Xen las redes en Xque no puede tener inversa, sin embargo, ello no implica que no exista una correspondencia unívoca entre filtros y redes. Pensemos en la siguiente inyección basada en el Hotel infinito de Hilbert: f:N−→ N n7−→ n+ 1, dicha aplicación es claramente inyectiva pero sabemos que no puede ser invertible, ya que no es sobreyectiva, sin embargo, claramente se ha de verificar que los naturales son biyectivos a sí mismos. El problema es que hemos hecho una mala elección de inyección. Lo mismo ocurre con la correspondencia entre filtros y redes. O bien existe una correspondencia inequívoca o bien se verifica que el cardinal de los filtros es estrictamente menor al de las redes (en el sentido algebraico formal). Para concluir la cuestión gracias al Teorema de Bernstein bastaría con encontrar una inyección del conjunto de las redes en el de los filtros o bien demostrar la imposibilidad de tal inyección, pero se desconoce cual de ambas opciones es cierta. 2 Aplicación al Análisis Un resultado clásico del Análisis es el llamado Teorema de Hahn-Banach, el cual presenta fuertes conexiones con los ultrafiltros por dos motivos principales. Comencemos enunciando dicho resultado: Teorema 2.1 (de Hahn-Banach). Sea Xun espacio vectorial sobre un cuerpo k, donde kdenotará o bien al cuerpo de los números reales o al de los números complejos. Sobre dicho espacio vectorial sea p:X−→ [0,+∞)una seminorma, y sean Mun subespacio vectorial de Xyf:M−→ kun funcional lineal tal que |f(m)| ≤ p(m) para cada m∈M. Entonces existe ˜ funa extensión del funcional a todo el espacio, que también es lineal y tal que |˜ f(x)| ≤ p(x)para cada x∈X. Observación 2.1.La aplicación definida sobre el subespacio de las sucesiones convergente, contenido en el espacio vectorial de las sucesiones acotadas, que a cada sucesión le asocia su límite es un funcional lineal de norma uno. Por tanto, gracias al Teorema de Hanh-Banach ha de existir una generalización del concepto de límite de una sucesión que se aplique a todas las sucesiones acotadas (pero no tiene por qué ser único). El Teorema de Hahn-Banach es usualmente demostrado usando el Lema de Zorn (ver por ejemplo [13, capítulo 3]), que recordemos es equivalente al Principio del Ultrafiltro como comentamos en el capítulo uno ([14, p.151], [11]). A continuación vamos a usar la existencia de ultrafiltros no principales como herramienta alternativa al Teorema de Hahn-Banach para la construcción de un límite generalizado invariante por traslaciones, y por tanto un Límite de Banach, concepto que pasamos a definir. Definición 2.1. Un límite de Banach se define como una aplicación lineal de ℓ∞en Rtal que si la sucesión es convergente con la definición estándar el límite de Banach de la sucesión coincide con el límite habitual, que sea invariante por traslaciones y que la 32 ultrafiltros y aplicaciones imagen de una sucesión de ℓ∞cuyos elementos sean no negativos sea no negativa a su vez. Denotaremos por l´ım∗a un límite generalizado. Es decir, una aplicación de ℓ∞en Rque verifique las siguientes propiedades: (A) Si {xn}es convergente entonces l´ım∗xn= l´ım xn; (B) l´ım∗(xn+yn) = l´ım∗xn+ l´ım∗yn; (C) l´ım∗(c xn) = cl´ım∗xn. Definamos ahora las siguientes tres propiedades: (D) |l´ım∗xn| ≤ Asi |xm| ≤ Apara cada m= 1,2,· · · . (E) |l´ım∗xn| ≤ supn|xn| (F) Si {xn}es una secuencia de números no negativos entonces l´ım∗xn≥0. A continuación probamos el siguiente lema técnico: Lema 2.1.En presencia de (A), (B) y (C) las propiedades (D), (E) y (F) son equivalentes entre sí. Demostración. Para probar probar (D) implica (E) basta con tomar A= supn|xn|. Supongáse ahora (E) y sea {xn}una sucesión de números reales no negativos acotados. Sea entonces Bun número real verificando simultáneamente: 1. B > l´ım∗xn, 2. B > xmpara todo m. Dicho Bexiste puesto que el límite de Banach siempre existe y es finito y la sucesión es acotada. Entonces aplicamos (E) a la sucesión {yn}={B−xn}: |l´ım∗yn| ≤ supn|B−xn|= supn(B−xn) = B−´ınf xn. 2. aplicación al análisis 33 Paralelamente, operando con el miembro más a la izquierda: |lím∗yn|=|lím∗(B−xn)| =|lím∗B+lím∗(−xn)|1 =|B+lím∗(−xn)|2 =|B−lím∗xn|3 =B−lím∗xn. En resumen, B−l´ım∗xn≤B−´ınf xn, lo que prueba 0≤´ınf xn≤l´ım∗xn, concluyendo el aserto. Para probar (F) implica (D), sea Aen las condiciones del enunciado y considérese yn=A−xn≥0. Entonces: 0≤l´ım∗yn= l´ım∗(A−xn) = l´ım∗A−l´ım∗xn=A−l´ım∗xn, de donde se sigue fácilmente l´ım∗xn≤A. Aplicando el mismo razonamiento a la sucesión yn=A+xnse comprueba la desigualdad −l´ım∗xn≤A, concluyendo (D). Recordemos que en el capítulo uno probamos que, dado un ultrafiltro no principal en los números naturales, toda sucesión de números reales acotada tiene límite por el ultrafiltro (véanse Corolario 1.2,Observación 1.15 yLema 1.4). Este límite será el candidato a ser límite generalizado como probaremos a continuación (nótese que el límite depende del ultrafiltro escogido). Teorema 2.2. Sea Fun ultrafiltro no principal definido en los naturales. Definimos la aplicación de ℓ∞en Rdada por: l´ım ∗xn= l´ım n→F xn si {xn}n∈ℓ∞. Entonces l´ım∗es un límite generalizado que además verifica (F). Obsérvese que l´ım∗xn=xsi y solo si para cada ϵpositivo se verifica: {n:|xn−x|< ϵ} ∈ F 1Aplicando la propiedad (B) 2Aplicando la propiedad (A) 3Aplicando la propiedad (C) 34 ultrafiltros y aplicaciones El Teorema 2.2 se demostrará valiéndonos de tal equivalencia, y dicha demostración se incluye a continuación como el Lema 2.2 y el Lema 2.3. Lema 2.2.La aplicación l´ım∗es lineal en las sucesiones. Demostración. Sean {xn}e{yn}sucesiones con límites xeyrespectivamente. Fijemos ϵpositivo. Queremos probar que cxx+cyyes un límite de {cxxn+cyyn}. En otras palabras, para cada ϵreal positivo buscamos probar que si Zes el conjunto {n:|(cxxn+cyyn)−(cxx+cyy)|< ϵ}entonces Z∈ F. Por convergencia de las sucesiones {xn}ne{yn}nsabemos que los conjuntos X= {n:|xn−x|< ϵ/2|cx|} eY={n:|yn−y|< ϵ/2|cy|} son elementos del ultrafiltro. Se sigue X∩Y∈ F. Veamos X∩Y⊆Z. Sea n∈X∩Y. Entonces |(cxxn+cyyn)−(cxx+cyy)| ≤ |cx||xn−x|+|cy||yn−y| ≤ ϵ, de donde n∈Z, como queríamos demostrar. Lema 2.3.La aplicación l´ım∗verifica (F) y por tanto (D) y (E). Demostración. Sea {xn}no negativa. Sea x < 0. Si ϵ=|x/2|se tiene |xn−x| ≥ ϵ para todo n, de donde Xϵ={n:|xn−x|< ϵ}=∅/∈ F. Como para un valor de ϵ el conjunto Xϵno es un elemento de F,xno puede ser límite de {xn}, probando que el límite generalizado tiene que ser no negativo. Observación 2.2.Los límites generalizados, si bien altamente satisfactorios, no tienen por qué ser invariantes por traslaciones, y por tanto no son límites de Banach en general. Por ejemplo, supongamos que el ultrafiltro considerado posee el conjunto {1,3,5,· · · } como elemento. Considérense entonces las sucesiones {xn}= {1,0,1,0,1,· · · } e{ym}={0,1,0,1,0,· · · }. Se comprueba fácilmente que l´ım∗xn= 1pero l´ım∗ym= 0. Para construir un límite de Banach, realizamos la siguiente modificación en el Teorema 2.2: Teorema 2.3 (Límite de Banach). Sea {xn}nuna sucesión de números reales acotadas. Sea {zn}nla sucesión definida por zn= (x1+x2+... +xn)/n. Definimos el Límite de Banach de la sucesión, notado l´ım∗∗ xncomo: l´ım∗∗ xn= l´ım∗zn, 2. aplicación al análisis 35 Demostración. Se comprueba fácilmente que dicha definición además de verificar las propiedades (A) a (D) verifica invariancia por traslaciones. Los límites de Banach no son la única aplicación de los ultrafiltros al Análisis, sino que además dar ultrafiltros en un conjunto está ampliamente relacionado con dar medidas finitamente aditivas. Más aún, tenemos el siguiente resultado de equivalencia: Lema 2.4.Si Xes un conjunto existe una biyección entre los ultrafiltros de Xy las medidas finitamente aditivas {0,1}-valuadas. A modo de recordatorio, incluimos a continuación la definición de medida finitamente aditiva {0,1}-valuada: Definición 2.2. Una aplicación µ:P(X)→ {0,1}se dice que es una medida finitamente aditiva {0,1}-valuada si se verifica: 1. µ(X)=1 2. Si A1, A2,· · · , Anson disjuntos dos a dos entonces µ(∪n 1Ai) = Pn 1µ(Ai). Demostración (Lema 2.4).Denotemos por βX al conjunto de los ultrafiltros en Xy γX al conjunto de las medidas finitamente aditivas {0,1}-valuadas en X. Consideremos las aplicaciones: F:βX −→ γX F 7−→ F(F) = µF G:γX −→ βX µ7−→ G(µ) = Fµ definidas por: µF(A) = (1si A∈ F 0si A /∈ F Fµ={A⊆X:µ(A) = 1}. Comprobemos que la aplicación Festá bien definida: Sea Fun filtro. Veamos que F(F) = µFverifica las condiciones de la Definición 2.2. 42 ultrafiltros y aplicaciones elemento de tal conjunto, probando que la aplicación es continua. Dichas propiedades topológicas no son lo único destacable de la Compactificación de Stone-Čech. Por ejemplo, es posible además dotar al conjunto βNde una operación binaria interna, asociativa y con un elemento idempotente. Es más, dicha operación es continua al fijar uno de los argumentos. Procedamos paso a paso. La definición de la operación es la siguiente: + : βN×βN−→ βN (F,G)7−→ F +G, donde F+Gviene dada por: {A⊆N:{n∈N:A−n∈ G} ∈ F}, y donde A−n={a−n:a∈A}. Ejemplo 3.1.Considérense dos ultrafiltros principales F(n)yF(m), entonces su suma es el ultrafiltro F(n+m). Efectivamente: A∈ F(n) + F(m)⇐⇒ {n∈N:A−n∈ F(m)}∈F(n) ⇐⇒ n∈ {n∈N:A−n∈ F(m)} ⇐⇒ A−n∈ F(m) ⇐⇒ m∈A−n ⇐⇒ n+m∈A ⇐⇒ A∈ F(n+m). El siguiente lema nos dicen que la operación está bien definida: Lema 3.5.Si FyGson ultrafiltros en Nentonces F+Gtambién lo es. Dicho de otra forma, la suma de ultrafiltros es un ultrafiltro en el mismo conjunto y por tanto la operación binaria es interna. Demostración. Comencemos demostrando que F+Ges una familia no vacía de subconjuntos de Ntal que ∅/∈ F +G. {n:N−n∈ G} ={n:N∈ G} =N∈ F, 3. la compactificación de stone-čech 43 de donde N∈ F +G. De manera similar: {n:∅ − n∈ G} ={n:∅ ∈ G} =∅/∈ F, de donde ∅/∈ F +G. Veamos ahora que la intersección de elementos de la familia está en la familia: Sean AyBelementos de F+G. Por definición A′:= {n:A−n∈ G} ∈ F y B′:= {n:B−n∈G}∈F. Tenemos de forma directa A′∩B′∈ F. Si probásemos A′∩B′⊆ {n: (A∩B−n)∈ G} hemos terminado. Efectivamente: m∈A′∩B′=⇒A−m, B −m∈ G =⇒((A∩B)−m)∈ G1 =⇒m∈ {n: ((A∩B)−n)∈ G}. Finalicemos el lema probando que si Ano es un elemento de la suma de ultrafiltros entonces Acsí lo es. Efectivamente, si A /∈ F +Gentonces X:= {n:A−n∈ G} /∈ F, de donde por ser Fultrafiltro X={n:A−n /∈ G} ∈ F. Valiéndonos de la propiedad (A−n)c=Ac−nconcluimos X={n:Ac−n∈G}∈F, lo que por definición significa Ac∈ F +G. Lema 3.6.La operación aditiva considerada es asociativa. Demostración. Sean tres ultrafiltros F,GyH. Observemos que por definición se tienen: A∈ F + (G+H)⇐⇒ {n:A−n∈(G+H)} ∈ F ⇐⇒ {n:A−n∈ {B⊆N:{n∈N:B−n∈H}∈G}∈F ⇐⇒ {n:{m: (A−n)−m∈H}∈G}∈F, así como: A∈(F+G) + H ⇐⇒ {m:A−m∈ H} ∈ (F+G) ⇐⇒ {n: ({m:A−m∈ H})−n∈G}∈F. 1Gracias a la igualdad de conjuntos (A−m)∩(B−m)=(A∩B)−m, que es fácil de comprobar. 44 ultrafiltros y aplicaciones En resumen, se tienen las siguientes equivalencias: A∈ F + (G+H)⇐⇒ {n:{m: (A−n)−m∈H}∈G}∈F, A∈(F+G) + H ⇐⇒ {n: ({m:A−m∈ H} − n)∈ G} ∈ F. Por tanto, los conjuntos coinciden si se da la igualdad {m:A−n−m∈ H} = {m:A−m∈ H} − n. Finalmente: x∈ {m:A−m∈ H} − n⇐⇒ x+n∈ {m:A−m∈ H} ⇐⇒ A−x−n∈ H ⇐⇒ x∈ {m:A−n−m∈ H}; concluyendo la demostración. Nuestra operación aditiva es “suave” en el siguiente sentido: Lema 3.7.Para cada Gfijado, la aplicación +G:βN−→ βNdada por +G(F) = F+Ges continua. Demostración. Para probar la continuidad será suficiente con probar que la anteimagen de un abierto básico es abierto básico. Efectivamente: +−1 G(A∗) = {F :F+G ∈ A∗} ={F :A∈ F +G} ={F :{n:A−n∈ G} ∈ F} ={n:A−n∈ G}∗. Lema 3.8 (de idempotencia).Existe un ultrafiltro idempotente, i.e existe F ∈ βN con F+F=F. Demostración. Sea Ael conjunto de los semigrupos topológicos compactos no vacíos que están contenidos en βN. Por ser βN∈ A se tiene que no es vacío. Aes un conjunto parcialmente ordenado cuyo orden parcial es la contención. Consideremos una cadena Cen A. Se comprueba de forma inmediata que Cverifica la propiedad de la intersección finita, y por ser βNcompacto la intersección ∩C∈CC 3. la compactificación de stone-čech 45 no es vacía gracias a la Proposición 1.6 (cada C∈ C es cerrado por ser un conjunto compacto en un espacio topológico de Hausdorff). Se verifica que tal intersección es cerrada por ser interesección arbitraria de conjuntos cerrados, y por tanto es compacta por estar contenida en un compacto. Además se verifica fácilmente que es semigrupo por serlo cada C∈ C y por ser cada elemento de la intersección elemento de todos los compactos de la cadena. Por el Lema de Zorn existe un elemento minimal A. Veamos que todo F ∈ Aes idempotente. En primer lugar, A+Fes compacto para cada Apor ser la operación +Fcontinua. Además es un semigrupo, ya que si F1+FyF2+Fson elementos de A+Fentonces: (F1+F)+(F2+F)=(F1+F2+F)+(F)∈A+F, por ser F1,F2yFelementos de A, un semigrupo. Por ser Agrupo se tiene A+F ⊆ A, y por la minimalidad de Ase sigue A+F=A. Considérese ahora B={G ∈ A:G+F=F}. Por ser F ∈ A=A+Fdebe de existir G ∈ Acon G+F=F, por tanto Bes no vacío. Bes semigrupo puesto que la suma de dos elementos del conjunto verifica: (G1+G2) + F=G1+ (G2+F) = G1+F=F. Como claramente B⊆A, por la minimalidad del segundo es B=A, y por tanto en particular F ∈ By con ello F+F=F. Una referencia general para el estudio del álgebra de βNy sus elementos idempotentes es [5]. Observación 3.2.Los argumentos usados para probar el Lema de Idempotencia son válidos para cualquier semigrupo topológico compacto cuya suma al fijar uno de los argumentos sea continua. Observación 3.3.Tal elemento Fidempotente ha de ser no principal, puesto que por el Ejemplo 3.1 si F=F(n)entonces F+F=F(2n)=F(n). 46 ultrafiltros y aplicaciones La existencia de elementos idempotentes y el hecho de que tal elemento no es un ultrafiltro principal se utilizará fuertemente en el siguiente capítulo, donde estudiaremos aplicaciones de los ultrafiltros a la Teoría de Ramsey en los números naturales. 4 Algunas aplicaciones a la Teoría de Ramsey En este capítulo se van a estudiar algunos resultados clásicos de Teoría de Ramsey cuya demostración puede ser dada he incluso simplificada usando ultrafiltros. La Teoría de Ramsey, en términos generales, estudia la aparición de estructuras “notables” para conjuntos lo suficientemente grandes. Nos centraremos en los números naturales y sus subconjuntos. Un ejemplo de los problemas a estudiar es el siguiente: supongamos que tenemos una propiedad de interés, y supongamos que coloreamos Ncon una cantidad finita de colores. ¿Existe algún subconjunto monocromático tal que todos sus elementos verifiquen dicha propiedad? Usando ultrafiltros no principales se demostrarán el Teorema de Schur (1912) y su generalización, el Teorema de Hindman [6]. Otros teoremas clásicos de Teoría de Ramsey sobre los números naturales pueden encontrarse por ejemplo en [9] y [12]. La idea en varios de dichos casos es valernos los ultrafiltros como herramienta de filtro literal, dígase, dado un conjunto potencialmente grande, considerar un ultrafiltro en dicho conjunto y usarlo para cribar elementos verificando propiedades “buenas”. Teorema 4.1 (de Ramsey). Sea Gun grafo infinito completo. Si sus aristas están coloreadas con un número finito de colores, entonces Gposee un subgrafo monocromático con un número infinito numerable de vértices y completo. Demostración. Denotemos por Val conjunto de vértices de G. Por comodidad vamos a denotar {1,2,· · · , r}al conjunto de los colores. Sea entonces Fun ultrafiltro no principal en V. Sea v∈Vun vértice cualquiera. Si denotamos por χ(x, y)al color de la arista {x, y}, para cada color kpodemos considerar los conjuntos asociados: Ak(v) = {w∈V:χ(v, w) = k}. 48 ultrafiltros y aplicaciones Los conjuntos de dicha familia son claramente disjuntos dos a dos y su unión es V\ {v} ∈ F. Al ser Fun ultrafiltro no principal, tenemos que {v}no puede ser un elemento suyo y como consecuencia V\ {v}∈F. Gracias al Corolario 1.1 existe exactamente un kvtal que Akv(v)es un elemento del ultrafiltro F. A continuación vamos a seguir una línea de razonamiento parecida para otra partición diferente. Para cada color kconsideramos el conjunto: Bk={v:Ak(v)∈ F} Sean k1yk2dos colores diferentes. Entonces Bk1yBk2son disjuntos entre ellos. Efectivamente, si existiese un vértice vcon v∈Bk1∩Bk2entonces serían Ak1(v)y Ak2(v)simultáneamente elementos del ultrafiltro, contradiciendo la discusión previa. Sigamos con la demostración probando que la unión de los Bkconsiderando todos los colores (que es un conjunto finito) es el espacio V. Sea v∈Vcualquiera. Gracias a lo demostrado al inicio, sabemos que existe un color kvcon Akv(v)∈ F, pero entonces v∈Bkv, es decir, pertenece a un elemento de la unión. En resumen, los Bkdefinen una partición disjunta de V∈ F, y por tanto existe exactamente un Bkcon Bk∈ F. A continuación vamos a construir explícitamente nuestro subgrafo objetivo coloreado con el color kmediante el siguiente algoritmo inductivo: escogemos v1∈Bk cualquiera. Vamos a razonar por inducción: supongamos escogidos v1, v2,· · · , vnde tal manera que Ak(vl)∈ F para todo 1≤l≤nyχ(vs, vt) = ksiempre que 1≤s=t≤n. Consideremos entonces el conjunto: S=Bk∩ n \ l=1 Ak(vl)! Entonces Ses una intersección finita de conjuntos de F, y por tanto, S∈ F. Como Fno es principal, Sha de ser infinito. En particular, debe de existir un elemento 4. algunas aplicaciones a la teoría de ramsey 49 en S\ {v1, v2,· · · , vn}, que será el que escojamos como vn+1. Para concluir falta probar Ak(vn+1)∈ F yχ(vl, vn+1) = kpara todo 1≤l≤n. La condición Ak(vn+1)∈ F se tiene por hipótesis, puesto que vn+1 ∈Simplica vn+1 ∈Bk. Sea 1≤l≤n, la condición χ(vl, vn+1) = kse tiene por ser vn+1 ∈Ak(vl), concluyendo la demostración. La conexión entre la Teoría de Ramsey y los ultrafiltros va más allá, con resultados como el siguiente: Lema 4.1.Sea Guna familia de subconjuntos no vacíos de X. Las siguientes condiciones son equivalentes: a) Dada una coloración de X, existe un G∈ G monocromático; b) Existe un ultrafiltro Fen Xcon la propiedad de que para cada A∈ F existe G∈ G con G⊆A. Demostración. En primer lugar, supóngase b)como hipótesis. Sea la partición finita de Xdada por la coloración, dígase, X=⊔n i=1Ai, donde Aies el conjunto de los elementos de Xcoloreados con el color i. Usando el Corolario 1.1 existe exactamente un Aicon Ai∈ F. Por ser cualquier G⊆Aimonocromático y existir un conjunto de Gverificando tal contención, se sigue el resultado. Para la implicación recíproca, sea la siguiente familia: B={A⊆X:A∩G=∅para cada G∈ G}. Sea entonces B+la familia formada por todas las intersecciones finitas de elementos de B. Se verifica claramente que si A, B ∈ B+entonces A∩B∈ B+yX∈ B+. Sólo resta probar ∅/∈ B+. Sean A1, A2,· · · Akelementos de Bcualesquiera. Construimos {CS}S⊆{1,2,··· ,k}una partición de Xen 2kconjuntos disjuntos dada por: x∈CS0⇔x∈∩i∈S0Ai∩∩i/∈S0Ac i. Por hipótesis existe CS0yG∈ G con G⊆CS0. Se verifica Ai∩G=∅para cada i, por lo que en particular S0={1,2,· · · , k}yG⊆ ∩k i=1Ai. Se deduce ∩k i=1Aino 50 ultrafiltros y aplicaciones puede ser vacía y con ello existe un ultrafiltro Fque extiende a B+. Fijemos A∈ F. Se sigue Ac/∈ F y por tanto Ac/∈ B. Por definición ha de existir G∈ G con Ac∩G=∅, lo que concluye G⊆A. Con tal equivalencia es posible probar el Teorema de Schur: Teorema 4.2 (Teorema de Schur). Dada cualquier partición de los naturales en un número finito de subconjuntos, es posible encontrar números naturales xeytales que x,yyz=x+yestán todos en el mismo conjunto de la partición. Demostración. Sea Xuna coloración de los naturales que defina la partición considerada. Podemos entonces construir una coloración de N2dada por X′(x, y) = X(|x−y|). Por el Teorema de Ramsey existe un subconjunto infinito {x1, x2,· · · } tal que X(|xi−xj|) = cpara cada i=jycprefijado. Podemos suponer sin pérdida de generalidad x1< x2< x3. Tomamos x=x3−x2ey=x2−x1, completando la demostración. Dicho resultado admite una generalización conocida como Teorema de Hindman. Dado Aun subconjunto infinito de los números naturales se define: FS(A) = (X x∈B x:B⊆A, |B|<∞) el conjunto de las sumas finitas de elementos de A. Se puede demostrar el siguiente resultado asociado: Teorema 4.3 (Teorema de Hindman). Dada una partición de los números naturales en un número finito de subconjuntos, existe Aun subconjunto infinito de los números naturales tal que FS(A)está contenido en uno de los elementos de tal partición. Demostración. Fijemos una coloración finita del grafo X. Vamos a construir dos secuencias: una de conjuntos no vacíos tales que A0⊇A1⊇A2⊇... y otra de elementos ai∈Aipara cada i≥1tales que ai+Ai⊆Ai−1para cada i≥1que además verifique Xes constante en A0. Fijemos un elemento idempontente Fen βN(podemos gracias al Lema 3.8 y que recordemos no es principal por la Observación 3.3). Existe A0infinito con Xconstante en A0. Por ser Fidempotente: F=F+F=B⊆N:{n∈N:B−n∈F}∈F, 4. algunas aplicaciones a la teoría de ramsey 51 es decir, que para cada B∈ F se sigue B′={n∈N:B−n∈ F} es también un elemento de F. Por tanto B∩B′∈ F. Sea a1∈A0∩A′ 0, y sea A1=A0∩(A0−a1)− {a1}. Se deduce A1⊆A0de manera directa y a1+A1⊆A0. Se verifica A1∈ F, puesto que en caso contrario {a1}∈Fpero Fno es principal. Repitiendo el argumento de manera inductiva, dado Anencontramos an+1 ∈An∩ A′ ntal que definiendo An+1 =An∩(An−an+1)− {an+1}se sigue An+1 ⊆An, an+1 +An+1 ⊆AnyAn+1 ∈ F. Tomamos A={a1, a2,· · · , an,· · · }. Para ver que Xes constante en FS(A)basta con comprobar FS(A)⊆A0, que será demostrado por inducción. Por construcción, si mes estrictamente mayor que nse verifica am+an∈Am−1+ an⊆An+an⊆An−1⊆A0. Sean an1,an2,· · · , ank+1 . Podemos suponer sin pérdida de generalidad que verifican n1> n2> ... > nk> nk+1. Por hipótesis de inducción an1+an2+... +ank∈ Ank−1. Se sigue por tanto an1+an2+... +ank+ank+1 ∈Ank−1+ank+1 ⊆Ank+1 + ank+1 ⊆Ank+1−1⊆A0, completando la inducción. Otros resultados clásicos de teoría de Ramsey en Ndonde la aplicación de los ultrafiltros ha permitido simplificar las pruebas originales puede encontrarse en [5, capítulo I.5]. Una fuente interesante de información puede consultarse en el siguiente enlace: https://joelmoreira.wordpress.com/2012/11/14/properties-of-ultrafilters-and-a-theorem- of-hindman-on-arithmetic-combinatorics/ 58 ultrafiltros y aplicaciones Demostración. Háganse dos observaciones: 1. Si M⊆Ves decisivo entonces todo N⊆Vcon M⊆Ntambién lo es. 2. Un subconjunto de votantes y su complementario no pueden ser simultáneamente decisivos. La primera observación es inmediata. La segunda es cierta puesto que en tal caso, si Des conjunto de votantes que es decisivo simultáneamente a su complementario, al presentar Duna votación que jerarquice cjsobre ciyDcuna votación que jerarquice cisobre cj,fdebe jerarquizar simultáneamente cjsobre ciycisobre cj. Usando el Lema 5.3 de manera inductiva, tenemos que dada una partición disjunta V=D1⊔D2⊔ · · · ⊔ Dnha de ser exactamente un Didecisivo. Consecuentemente, si hacemos la descomposición: V= (A∪B)c⊔(B\A)⊔(A\B)⊔(A∩B), exactamente uno de los cuatro conjuntos es decisivo. Hagamos un estudio de cada uno de los candidatos a conjunto decisivo por separado: 1. Gracias a la observación primera A⊆A∪Bimplica A∪Bdecisivo. Debido a la segunda observación (A∪B)cno es decisivo. 2. B\Atampoco puede ser decisivo pues A⊆(B\A)c, de donde (B\A)ces decisivo. 3. Análogamente A\Bno es decisivo. 4. Por descarte A∩Bes necesariamente decisivo. Lema 5.3.Si Fno es decisivo entonces Fclo es. Dicho de otra manera, para todo F⊆Vse tiene F∈ F óFc∈ F. Demostración. Comencemos suponiendo que existen al menos tres candidatos distintos. Considérese la siguiente expresión equivalente para F: F={D⊆V:D es decisivo por bloques}, validada por la Observación 5.2. Valiéndonos de dicha formulación de Fpodremos probar que si D /∈ F necesariamente Dc∈ F. 5. aplicación al teorema de arrow 59 La afirmación Fes decisivo por bloques equivale a la siguiente lista de propiedades para cada i, j, k tres índices de candidatos: 1. Dces ij-decisivo 2. Dces kj-decisivo para cada k=i, j 3. Dces ik-decisivo para cada k=i, j 4. Dces jk-decisivo para cada k=i, j 5. Dces ji-decisivo 6. Dces ki-decisivo para cada k=i, j Dno decisivo por bloques significa que existen i=jy dos votaciones πyτtales que πjerarquiza el candidato cisobre el candidato cjmientras que τjerarquiza el candidato cjsobre el candidato ciy si todos los votantes de Dpresentan πy todos los votantes de Dcpresentan τentonces la FBS jerarquiza el candidato cjsobre el candidato ci. Por AI siempre que todos los x∈Djerarquizan cisobre cjy todos los x∈Dcjerarquizan cjsobre ci, la salida por fjerarquiza cjsobre ci. Es decir, Dces ij-decisivo, lo que se resume en la siguiente tabla: Presentante Permutación Jerarquización D π cisobre cj Dcτ cjsobre ci Resultado - cjsobre ci Con lo anterior hemos probado la primera propiedad y pasamos a la segunda. Sea k=i, j cualquiera, entonces Dckj-decisivo. Efectivamente, si no fuese así, existirían votaciones πjerarquizando cjsobre ck, τjerarquizando cksobre cjtales que si todos los x∈Dcpresentan πy todos los x∈Dpresentan τentonces fpresenta cksobre cj. Por el mismo argumento que en el párrafo anterior, Des jk-decisivo. Veamos que hemos llegado a una contradicción: Supóngase que todos los x∈Dcpresentan una votación πque jerarquiza cjsobre cisobre cky que todos los x∈Dpresentan una votación τque jerarquiza cisobre ck sobre cj. En resumen, tenemos el siguiente esquema de votación: 60 ultrafiltros y aplicaciones Votantes Permutación Jerarquización D τ cisobre cksobre cj Dcπ cjsobre cisobre ck Entonces por ser D jk-decisivo tenemos que: (1) fpresenta cksobre cj. Paralelamente, por ser Dcij-decisivo: (2) fjerarquiza cjsobre ci. gracias a UL, al ser tanto πcomo τvotaciones que jerarquizan cisobre ck: (3) fjerarquiza cisobre ck. Concatenando los tres órdenes relativos: fjerarquiza cksobre cjpor (1),cjsobre cipor (2), y cisobre ckpor (3), lo que es una contradicción. Concluimos que Dces kj-decisivo para todo k=i, j. Hasta ahora hemos probado las primeras dos afirmaciones de la lista. Las siguientes propiedades, por similitud como las anteriores, se demostrarán con mucha más brevedad. Continuamos probando siguiente: Dces ik-decisivo. Si no fuese así, Dsería ki-decisivo y entonces, si se da la siguiente votación: 5. aplicación al teorema de arrow 61 Votantes Votación Jerarquización D π cisobre cksobre cj Dcτ cksobre cjsobre ci Por ser Dcij-decisivo se sigue que fjerarquiza cjsobre ci, por ser Dki-decisivo la FBS presenta cisobre cky por jerarquizar tanto πcomo τ cksobre cjel resultado de la votación también, llegando a contradicción. La siguiente propiedad de la lista afirma Dces jk-decisivo. Efectivamente, si no fuese así sería D kj-decisivo. Si se da la siguiente votación: Votantes Votación Jerarquización D π cisobre cjsobre ck Dcτ cksobre cisobre cj La FBS jerarquizaría cjsobre ckpor ser D kj-decisivo,cksobre cipor ser Dc ik-decisivo ycisobre cjpor presentar todos los votantes cisobre cj. Afirmamos Dces ji-decisivo. Efectivamente, si no fuese así, se comprueba que Dsería ij-decisivo. Sean entonces πuna votación que presente cjsobre cisobre cky τuna votación que presente cisobre cksobre cjy supongamos que todos los votantes de Dpresentan πy todos los votantes de Dcpresentan τ. Es decir, que tenemos el siguiente esquema de votación: Votantes Votación Jerarquización D π cjsobre cisobre ck Dcτ cisobre cksobre cj entonces por ser D ij-decisivo se tiene que (1),fpresenta cjsobre ci. Paralelamente, por presentar ambos una votación que jerarquiza cisobre cktenemos que (2) el resultado presenta cisobre ck. Finalmente, como ya sabemos que Dces jk-decisivo y τ presenta cksobre cj(3) la FBS presenta cksobre cj, llegando a una contradicción. Para acabar la demostración, al ser Dctanto ij-decisivo como ji-decisivo, tenemos que las variables iyjson mudas, y con ello los argumentos usados para demostrar las propiedades 1) a5) se adaptan fácilmente para probar la propiedad 6), concluyendo la demostración. 62 ultrafiltros y aplicaciones Entrando en el pantanoso terreno de las conclusiones e implicaciones, este último resultado tiene algunas de las más interesantes. Por ejemplo, el resultado rígido (hay un dictador absoluto) sólo es cierto las reglas del sistema democrático son igualmente rígidas. Esto podría explicar por qué en las democracias actuales nunca hay una correspondencia absoluta entre el número de diputados y el porcentaje de votos, llegando a darse el caso de que un partido con más votos pierda frente a otro con menos. Al flexibilizar las condiciones en el sistema de votación se flexibiliza la naturaleza dictatorial. También sabemos que en numerosos países occidentales ciertas regiones disfrutan de una mejor relación voto-representación que otras. Una posible explicación es que debido a la naturaleza de ultrafiltro de los conjuntos decisivos, al ser un sector de la población un conjunto que no es parte del ultrafiltro, se le añade un peso “artifialmente”. Más aún, la existencia de dictadores sólo es veraz en conjuntos de votantes finitos. Sin embargo, un sistema de votantes muy grande podría “falsear” su naturaleza finita para obtener resultados propios de sistemas de infinitos votantes. Algo similar al caso de los ordenadores y sus sistemas de cálculo real usando racionales de “muchos decimales”. Dicho argumento explica el porqué no ha sido hasta la viabilidad tecnológica de votaciones en masa que la humanidad ha vivido bajo dominio de regímenes absolutos. Al ser el número de votantes “pequeño” no se puede “trucar” la naturaleza del sistema de votantes, dando lugar de forma natural a figuras dictatoriales. Bibliografía [1] J. L. Bell, A. B. Slomson. Models and Ultraproducts: an introduction. North- Holland Publishing Company, (1969). [2] Tullio Ceccherini-Silberstein, Michael Coornaert. Cellular Automata and Groups. Springer, (2010). [3] W. Gähler. Grundstrukturen der Analysis I. Birkhäuser Verlag, Basel, 1977. [4] David Galvin. Ultrafilters, with applications to analysis, social choice and combinatorics. https://www3.nd.edu/ dgalvin1/pdf/ultrafilters.pdf [5] Neil Hindman and Dona Strauss. Algebra in the Stone-Cech Compactification. Walter de Gruyter &Co., 2012. [6] Neil Hindman. Finite Sums from Sequences Within Cells of a Partition of N. Journal of Combinatorial Theory (A) 17, 1-11 (1974). [7] Alan P. Kirman and Dieter Sondermann. Arrow’s Theorem, Many Agents, and Invisible Dictators. Journal of Economic Theory 5, 267-277 (1972). [8] Péter Komjáth &Vilmos Totik. Ultrafilters. The American Mathematical Monthly, 115:1, 33-44 (2018). [9] Bruce M. Landman, Aaron Robertson. Ramsey Theory on the Integers. American Mathematical Society, (2004). [10] W. A. J. Luxemburg Two Applications of the Method of Construction by Ultrapowers to Analysis. (1962) [11] David Pincus and Robert Solovay. Definability of measures and ultrafilters. J. Symbolic Logic 42 (1977), 179-190. 64 ultrafiltros y aplicaciones [12] Graham, Ronald L.,; Rothschild, Bruce L.,; Spencer, Joel H. Ramsey theory. New York : Wiley; 1990 [13] W. Rudin. Functional Analysis. Mc Graw Hill, (1991) [14] Eric Schechter. Handbook of Analysis and Its Foundations. Academic Press, (1997). [15] Stephen Willard. General Topology. Addison Wesley Publishing Company, (1970)