Teoría estructural de Ramsey

En matemáticas, la teoría estructural de Ramsey es una generalización categórica de la teoría de Ramsey , basada en la idea de que muchos resultados importantes de la teoría de Ramsey tienen estructuras lógicas "similares". La observación clave es que estos teoremas de tipo Ramsey pueden expresarse como la afirmación de que una determinada categoría (o clase de estructuras finitas) tiene la propiedad de Ramsey (definida a continuación).

La teoría estructural de Ramsey comenzó en la década de 1970 ^[1] con el trabajo de Nešetřil y Rödl , y está íntimamente relacionada con la teoría de Fraïssé . Recibió un renovado interés a mediados de la década de 2000 debido al descubrimiento de la correspondencia Kechris–Pestov–Todorčević , que conectaba la teoría estructural de Ramsey con la dinámica topológica .

Historia

A Leeb  [de] se le atribuye ^[2] la invención de la idea de una propiedad de Ramsey a principios de los años 70. La primera publicación de esta idea parece ser el artículo de 1972 de Graham , Leeb y Rothschild sobre el tema. ^[3] El desarrollo clave de estas ideas fue realizado por Nešetřil y Rödl en su serie de artículos de 1977 ^[4] y 1983 ^[5] , incluido el famoso teorema de Nešetřil-Rödl. Este resultado fue refutado independientemente por Abramson y Harrington [ ^6] y generalizado por Prömel  [de] . ^[7] Más recientemente, Mašulović ^{[8] [9] [10]} y Solecki ^{[11] [12] [13]} han realizado un trabajo pionero en el campo.

Motivación

En este artículo se utilizará la convención de la teoría de conjuntos según la cual cada número natural puede considerarse como el conjunto de todos los números naturales menores que él, es decir , . Para cualquier conjunto , una coloración de es una asignación de una de las etiquetas a cada elemento de . Esto se puede representar como una función que asigna cada elemento a su etiqueta en (que se utilizará en este artículo) o, equivalentemente, como una partición de en partes. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n=\{0,1,\ldots ,n-1\}}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle A}$ ${\displaystyle \Delta :A\to r}$ ${\displaystyle r=\{0,1,\ldots ,r-1\}}$ ${\displaystyle A=A_{0}\sqcup \cdots \sqcup A_{r-1}}$ ${\displaystyle r}$

A continuación se presentan algunos de los resultados clásicos de la teoría de Ramsey:

• Teorema de Ramsey (finito) : para cada , existe tal que para cada -coloración de todos los subconjuntos de -elementos de , existe un subconjunto , con , tal que es -monocromático. ${\displaystyle k\leq m,r\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle r}$ ${\displaystyle \Delta :[n]^{(k)}\to r}$ ${\displaystyle k}$ ${\displaystyle n=\{0,1,\ldots ,n-1\}}$ ${\displaystyle A\subseteq n}$ ${\displaystyle |A|=m}$ ${\displaystyle [A]^{(k)}}$ ${\displaystyle \Delta }$
• Teorema de van der Waerden (finito) : para cada , existe tal que para cada -coloración de , existe una progresión aritmética -monocromática de longitud . ${\displaystyle m,r\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle r}$ ${\displaystyle \Delta :n\to r}$ ${\displaystyle n}$ ${\displaystyle \Delta }$ ${\displaystyle \{a,a+d,a+2d,\ldots ,a+(m-1)d\}\subseteq n}$ ${\displaystyle m}$
• Teorema de Graham-Rothschild : fija un alfabeto finito . Una palabra con un parámetro de longitud sobre es un elemento , tal que todos los de aparecen, y sus primeras apariciones están en orden creciente. El conjunto de todas las palabras con un parámetro de longitud sobre se denota por . Dados y , formamos su composición reemplazando cada ocurrencia de en con la entrada n de . Entonces, el teorema de Graham-Rothschild establece que para cada , existe tal que para cada -coloración de todas las palabras con un parámetro de longitud , existe , tal que (es decir, todas las subpalabras con un parámetro de ) es -monocromática. ${\displaystyle L=\{a_{0},a_{1},\ldots ,a_{d-1}\}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle w\in (L\cup \{x_{0},x_{1},\ldots ,x_{k-1}\})^{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle \textstyle [L]{\binom {n}{k}}}$ ${\displaystyle \textstyle w\in [L]{\binom {n}{m}}}$ ${\displaystyle \textstyle v\in [L]{\binom {m}{k}}}$ ${\displaystyle \textstyle w\circ v\in [L]{\binom {n}{k}}}$ ${\displaystyle x_{i}}$ ${\displaystyle w}$ ${\displaystyle i}$ ${\displaystyle v}$
  ${\displaystyle k\leq m,r\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle r}$ ${\displaystyle \textstyle \Delta :[L]{\binom {n}{k}}\to r}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle \textstyle w\in [L]{\binom {n}{m}}}$ ${\displaystyle \textstyle w\circ [L]{\binom {m}{k}}=\{w\circ v:v\in [L]{\binom {m}{k}}\}}$ ${\displaystyle k}$ ${\displaystyle w}$ ${\displaystyle \Delta }$
• Teorema de Folkman (finito) : para cada , existe tal que para cada -coloración de , existe un subconjunto , con , tal que , y es -monocromático. ${\displaystyle m,r\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle r}$ ${\displaystyle \Delta :n\to r}$ ${\displaystyle n}$ ${\displaystyle A\subseteq n}$ ${\displaystyle |A|=m}$ ${\displaystyle \textstyle {\big (}\sum _{k\in A}k{\big )}<n}$ ${\displaystyle \textstyle \operatorname {FS} (A)=\{\sum _{k\in B}k:B\in {\mathcal {P}}(A)\setminus \varnothing \}}$ ${\displaystyle \Delta }$

Todos estos teoremas "tipo Ramsey" tienen una idea similar: fijamos dos números enteros y , y un conjunto de colores . Luego, queremos demostrar que hay algunos suficientemente grandes, de modo que para cada coloración de las "subestructuras" de tamaño dentro de , podemos encontrar una "estructura" adecuada dentro de , de tamaño , de modo que todas las "subestructuras" de con tamaño tengan el mismo color. ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle k}$

Los tipos de estructuras que se permiten dependen del teorema en cuestión, y ésta resulta ser prácticamente la única diferencia entre ellos. Esta idea de un "teorema de tipo Ramsey" conduce a la noción más precisa de la propiedad de Ramsey (abajo).

La propiedad de Ramsey

Sea una categoría . tiene la propiedad de Ramsey si para cada número natural , y todos los objetos en , existe otro objeto en , tal que para cada -coloración , existe un morfismo que es -monocromático, es decir, el conjunto ${\displaystyle \mathbf {C} }$ ${\displaystyle \mathbf {C} }$ ${\displaystyle r}$ ${\displaystyle A,B}$ ${\displaystyle \mathbf {C} }$ ${\displaystyle D}$ ${\displaystyle \mathbf {C} }$ ${\displaystyle r}$ ${\displaystyle \Delta :\operatorname {Hom} (A,D)\to r}$ ${\displaystyle f:B\to D}$ ${\displaystyle \Delta }$

${\displaystyle f\circ \operatorname {Hom} (A,B)={\big \{}f\circ g:g\in \operatorname {Hom} (A,B){\big \}}}$

es -monocromático. ^[10] ${\displaystyle \Delta }$

A menudo, se considera que es una clase de estructuras finitas sobre un lenguaje fijo , con incrustaciones como morfismos. En este caso, en lugar de colorear morfismos, se puede pensar en colorear "copias" de en y luego encontrar una copia de en , de modo que todas las copias de en esta copia de sean monocromáticas. Esto puede prestarse de manera más intuitiva a la idea anterior de un "teorema de tipo Ramsey". ${\displaystyle \mathbf {C} }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle A}$ ${\displaystyle D}$ ${\displaystyle B}$ ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle B}$

También existe una noción de propiedad dual de Ramsey; tiene la propiedad dual de Ramsey si su categoría dual tiene la propiedad de Ramsey como se indicó anteriormente. Más concretamente, tiene la propiedad dual de Ramsey si para cada número natural , y todos los objetos en , existe otro objeto en , tal que para cada -coloración , existe un morfismo para el cual es -monocromático. ${\displaystyle \mathbf {C} }$ ${\displaystyle \mathbf {C} ^{\mathrm {op} }}$ ${\displaystyle \mathbf {C} }$ ${\displaystyle r}$ ${\displaystyle A,B}$ ${\displaystyle \mathbf {C} }$ ${\displaystyle D}$ ${\displaystyle \mathbf {C} }$ ${\displaystyle r}$ ${\displaystyle \Delta :\operatorname {Hom} (D,A)\to r}$ ${\displaystyle f:D\to B}$ ${\displaystyle \operatorname {Hom} (B,A)\circ f}$ ${\displaystyle \Delta }$

Ejemplos

• Teorema de Ramsey: la clase de todas las cadenas finitas , con mapas que preservan el orden como morfismos, tiene la propiedad de Ramsey.
• Teorema de van der Waerden: en la categoría cuyos objetos son ordinales finitos , y cuyos morfismos son aplicaciones afines para , , la propiedad de Ramsey se cumple para . ${\displaystyle x\mapsto a+dx}$ ${\displaystyle a,d\in \mathbb {N} }$ ${\displaystyle d\neq 0}$ ${\displaystyle A=1}$
• Teorema de Hales-Jewett : sea un alfabeto finito y, para cada , sea un conjunto de variables. Sea la categoría cuyos objetos son para cada , y cuyos morfismos , para , son funciones que son rígidas y sobreyectivas en . Entonces, tiene la propiedad dual de Ramsey para (y , dependiendo de la formulación). ${\displaystyle L}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle X_{k}=\{x_{0},\ldots ,x_{k-1}\}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {GR} }$ ${\displaystyle A_{k}=L\cup X_{k}}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle A_{n}\to A_{k}}$ ${\displaystyle n\geq k}$ ${\displaystyle f:X_{n}\to A_{k}}$ ${\displaystyle X_{k}\subseteq A_{k}=\operatorname {codom} f}$ ${\displaystyle \mathbf {GR} }$ ${\displaystyle A=A_{0}}$ ${\displaystyle B=A_{1}}$
• Teorema de Graham-Rothschild: la categoría definida anteriormente tiene la propiedad dual de Ramsey. ${\displaystyle \mathbf {GR} }$

La correspondencia Kechris-Pestov-Todorčević

En 2005, Kechris , Pestov y Todorčević ^[14] descubrieron la siguiente correspondencia (en adelante denominada correspondencia KPT ) entre la teoría estructural de Ramsey, la teoría de Fraïssé y las ideas de la dinámica topológica.

Sea un grupo topológico . Para un espacio topológico , un -flujo (denotado ) es una acción continua de sobre . Decimos que es extremadamente dócil si cualquier -flujo en un espacio compacto admite un punto fijo , es decir, el estabilizador de es él mismo. ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle G\curvearrowright X}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G\curvearrowright X}$ ${\displaystyle X}$ ${\displaystyle x\in X}$ ${\displaystyle x}$ ${\displaystyle G}$

Para una estructura de Fraïssé , su grupo de automorfismos puede considerarse un grupo topológico, dada la topología de convergencia puntual o, equivalentemente, la topología del subespacio inducida por el espacio con la topología del producto . El siguiente teorema ilustra la correspondencia KPT: ${\displaystyle \mathbf {F} }$ ${\displaystyle \operatorname {Aut} (\mathbf {F} )}$ ${\displaystyle \operatorname {Aut} (\mathbf {F} )}$ ${\displaystyle \mathbf {F} ^{\mathbf {F} }=\{f:\mathbf {F} \to \mathbf {F} \}}$

Teorema (KPT). Para una estructura de Fraïssé , los siguientes son equivalentes: ${\displaystyle \mathbf {F} }$

1. El grupo de automorfismos de es extremadamente manejable. ${\displaystyle \operatorname {Aut} (\mathbf {F} )}$ ${\displaystyle \mathbf {F} }$
2. La clase tiene la propiedad Ramsey. ${\displaystyle \operatorname {Age} (\mathbf {F} )}$

Véase también

• Teoría de Ramsey
• Teorema de Fraïssé
• Edad (teoría de modelos)

Referencias

1. Van Thé, Lionel Nguyen (10 de diciembre de 2014). "Un estudio sobre la teoría estructural de Ramsey y la dinámica topológica teniendo en cuenta la correspondencia Kechris–Pestov–Todorcevic". arXiv : 1412.3254 [math.CO].
2. Larson, Jean A. (1 de enero de 2012), "Combinatoria infinita", en Gabbay, Dov M.; Kanamori, Akihiro; Woods, John (eds.), Manual de la historia de la lógica , Conjuntos y extensiones en el siglo XX, vol. 6, Holanda Septentrional, págs. 145–357, doi :10.1016/b978-0-444-51621-3.50003-7, ISBN 9780444516213, consultado el 30 de noviembre de 2019
3. Graham, RL; Leeb, K.; Rothschild, BL (1972). "Teorema de Ramsey para una clase de categorías". Avances en Matemáticas . 8 (3): 417–433. doi : 10.1016/0001-8708(72)90005-9 . ISSN  0001-8708.
4. Nešetřil, Jaroslav; Rödl, Vojtěch (mayo de 1977). "Particiones de sistemas relacionales y de conjuntos finitos". Journal of Combinatorial Theory, Serie A . 22 (3): 289–312. doi : 10.1016/0097-3165(77)90004-8 . ISSN  0097-3165.
5. Nešetřil, Jaroslav; Rödl, Vojtěch (1 de marzo de 1983). "Clases Ramsey de sistemas establecidos". Revista de teoría combinatoria, serie A. 34 (2): 183–201. doi : 10.1016/0097-3165(83)90055-9 . ISSN  0097-3165.
6. Abramson, Fred G.; Harrington, Leo A. (septiembre de 1978). "Modelos sin indiscernibles". The Journal of Symbolic Logic . 43 (3): 572. doi :10.2307/2273534. ISSN  0022-4812. JSTOR  2273534. S2CID  1101279.
7. Prömel, Hans Jürgen (julio de 1985). "Propiedades de partición inducidas de cubos combinatorios". Journal of Combinatorial Theory, Serie A . 39 (2): 177–208. doi : 10.1016/0097-3165(85)90036-6 . ISSN  0097-3165.
8. Masulovic, Dragan; Scow, Lynn (2017). "Equivalencia categórica y la propiedad de Ramsey para potencias finitas de un álgebra primal". Algebra Universalis . 78 (2): 159–179. arXiv : 1506.01221 . doi :10.1007/s00012-017-0453-0. S2CID  125159388.
9. Masulovic, Dragan (2018). "Preadjunciones y la propiedad de Ramsey". Revista Europea de Combinatoria . 70 : 268–283. arXiv : 1609.06832 . doi :10.1016/j.ejc.2018.01.006. S2CID  19216185.
10. Mašulović, Dragan (2020). "Sobre teoremas duales de Ramsey para estructuras relacionales". Revista matemática checoslovaca . 70 (2): 553–585. arXiv : 1707.09544 . doi :10.21136/CMJ.2020.0408-18. S2CID  125310940.
11. Solecki, Sławomir (agosto de 2010). "Un teorema de Ramsey para estructuras con relaciones y funciones". Journal of Combinatorial Theory, Serie A . 117 (6): 704–714. doi : 10.1016/j.jcta.2009.12.004 . ISSN  0097-3165.
12. Solecki, Slawomir (20 de abril de 2011). "Enfoque abstracto de la teoría finita de Ramsey y un teorema de Ramsey autodual". arXiv : 1104.3950 [math.CO].
13. Solecki, Sławomir (16 de febrero de 2015). "Teorema dual de Ramsey para árboles". arXiv : 1502.04442 [math.CO].
14. Kechris, AS; Pestov, VG; Todorcevic, S. (febrero de 2005). "Límites de Fraïssé, teoría de Ramsey y dinámica topológica de grupos de automorfismos" (PDF) . Análisis geométrico y funcional . 15 (1): 106–189. doi :10.1007/s00039-005-0503-1. ISSN  1016-443X. S2CID  6937893.