Combinatoria infinita

En matemáticas, la combinatoria infinitaria , o teoría combinatoria de conjuntos , es una extensión de ideas de la combinatoria a conjuntos infinitos . Algunos de los temas estudiados incluyen grafos y árboles continuos , extensiones del teorema de Ramsey y el axioma de Martin . Los desarrollos recientes se refieren a la combinatoria del continuo ^{[ 1 ]} y a la combinatoria sobre sucesores de cardinales singulares ^{[ 2 ] .}

Escribir${\displaystyle \kappa,\lambda}$para ordinales, ${\displaystyle m}$para un número cardinal (finito o infinito) y${\displaystyle n}$para un número natural. Erdős y Rado (1956) introdujeron la notación

${\displaystyle \displaystyle \kappa \rightarrow (\lambda)_ {m}^{n}}$

como una forma abreviada de decir que cada partición del conjunto${\displaystyle [\kappa ]^{n}}$de${\displaystyle n}$subconjuntos de elementos de${\displaystyle \kappa }$en${\displaystyle m}$Las piezas tienen un conjunto homogéneo de tipos de orden.${\displaystyle \lambda }$. Un conjunto homogéneo es en este caso un subconjunto de${\displaystyle \kappa }$de tal manera que cada${\displaystyle n}$El subconjunto de elementos está en el mismo elemento de la partición. Cuando${\displaystyle m}$es 2, a menudo se omite. Estas afirmaciones se conocen como relaciones de partición.

Suponiendo el axioma de elección , no hay ordinales.${\displaystyle \kappa }$con${\displaystyle \kappa \rightarrow (\omega )^{\omega }}$, entonces${\displaystyle n}$se suele considerar finito. Una extensión donde${\displaystyle n}$casi se permite que sea infinito es la notación

${\displaystyle \displaystyle \kappa \rightarrow (\lambda )_{m}^{<\omega }}$

lo cual es una forma abreviada de decir que cada partición del conjunto de subconjuntos finitos de${\displaystyle \kappa }$en${\displaystyle m}$piezas tiene un subconjunto de tipo de orden${\displaystyle \lambda }$tal que para cualquier finito${\displaystyle n}$, todos los subconjuntos de tamaño${\displaystyle n}$están en el mismo elemento de la partición. Cuando${\displaystyle m}$es 2, a menudo se omite.

Otra variación es la notación

${\displaystyle \displaystyle \kappa \rightarrow (\lambda,\mu)^{n}}$

lo cual es una forma abreviada de decir que cada coloración del conjunto${\displaystyle [\kappa ]^{n}}$de${\displaystyle n}$subconjuntos de elementos de${\displaystyle \kappa }$con 2 colores tiene un subconjunto del tipo de orden${\displaystyle \lambda }$de tal manera que todos los elementos de${\displaystyle [\lambda ]^{n}}$tienen el primer color, o un subconjunto del tipo de orden${\displaystyle \mu }$de tal manera que todos los elementos de${\displaystyle [\mu ]^{n}}$tienen el segundo color. Una coloración de${\displaystyle [\kappa ]^{n}}$es una función${\displaystyle f:[\kappa ]^{n}\rightarrow p}$.

Algunas propiedades de esto incluyen: (en lo que sigue)${\displaystyle \kappa }$es un cardenal)

${\displaystyle \displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$para todos los finitos${\displaystyle n}$y${\displaystyle k}$( Teorema de Ramsey ).

${\displaystyle \displaystyle \beth _{n}^{+}\rightarrow (\aleph _{1})_{\aleph _{0}}^{n+1}}$(el teorema de Erdős-Rado ).

${\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (\kappa ^{+})^{2}}$(el teorema de Sierpiński)

${\displaystyle \displaystyle 2^{\kappa }\not \rightarrow (3)_{\kappa }^{2}}$

${\displaystyle \displaystyle \kappa \rightarrow (\kappa,\aleph _ {0})^{2}}$(el teorema de Erdős-Dushnik-Miller )

En universos sin elección, pueden cumplirse propiedades de partición con exponentes infinitos, y algunas de ellas se obtienen como consecuencia del axioma de determinatividad (AD). Por ejemplo, Donald A. Martin demostró que AD implica

${\displaystyle \displaystyle \aleph _{1}\rightarrow (\aleph _{1})_{2}^{\aleph _{1}}}$

Wacław Sierpiński demostró que el teorema de Ramsey no se extiende a conjuntos de tamaño${\displaystyle \aleph _{1}}$demostrando que${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$. Es decir, Sierpiński construyó una coloración de pares de números reales en dos colores tal que para cada subconjunto no numerable de números reales${\displaystyle X}$,${\displaystyle [X]^{2}}$toma ambos colores. Tomando cualquier conjunto de números reales de tamaño${\displaystyle \aleph _{1}}$y aplicándole la coloración de Sierpiński, obtenemos que${\displaystyle \aleph _{1}\not \rightarrow (\aleph _{1})_{2}^{2}}$Las coloraciones de este tipo se conocen como coloraciones fuertes ^{[ 3 ]} y se estudian en la teoría de conjuntos. Erdős, Hajnal y Rado (1965) introdujeron una notación similar a la anterior para esto.

Escribir${\displaystyle \kappa ,\lambda }$para ordinales, ${\displaystyle m}$para un número cardinal (finito o infinito) y${\displaystyle n}$para un número natural. Entonces

${\displaystyle \displaystyle \kappa \nrightarrow [\lambda ]_{m}^{n}}$

es una forma abreviada de decir que existe una coloración del conjunto${\displaystyle [\kappa ]^{n}}$de${\displaystyle n}$subconjuntos de elementos de${\displaystyle \kappa }$en${\displaystyle m}$piezas de tal manera que cada conjunto de tipo de orden${\displaystyle \lambda }$es un conjunto arcoíris. Un conjunto arcoíris es en este caso un subconjunto${\displaystyle A}$de${\displaystyle \kappa }$de tal manera que${\displaystyle [A]^{n}}$se lo lleva todo${\displaystyle m}$colores. Cuando${\displaystyle m}$es 2, a menudo se omite. Estas afirmaciones se conocen como relaciones de partición entre corchetes negativos.

Otra variación es la notación

${\displaystyle \kappa \nrightarrow [\lambda$ ;\mu ]_{m}^{2}}

lo cual es una forma abreviada de decir que existe una coloración del conjunto.${\displaystyle [\kappa ]^{2}}$de subconjuntos de 2 elementos de${\displaystyle \kappa }$con${\displaystyle m}$colores tales que para cada subconjunto${\displaystyle A}$del tipo de orden${\displaystyle \lambda }$y cada subconjunto${\displaystyle B}$del tipo de orden${\displaystyle \mu }$, el conjunto${\displaystyle A\times B}$se lo lleva todo${\displaystyle m}$bandera.

Algunas propiedades de esto incluyen: (en lo que sigue)${\displaystyle \kappa }$es un cardenal)

${\displaystyle \displaystyle 2^{\kappa }\nrightarrow [\kappa ^{+}]^{2}}$(Sierpiński)

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]^{2}}$(Sierpiński)

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{3}^{2}}$( Laver , Blass )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{4}^{2}}$( Galvin y Shelah )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}}$( Todorčević )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1};\aleph _{1}]_{\aleph _{1}}^{2}}$( Moore )

${\displaystyle \displaystyle 2^{\aleph _{0}}\nrightarrow [2^{\aleph _{0}}]_{\aleph _{0}}^{2}}$( Galvin y Shelah )

Varias propiedades cardinales importantes pueden definirse utilizando esta notación. En particular:

• Cardenales débilmente compactos${\displaystyle \kappa }$son aquellos que satisfacen${\displaystyle \kappa \rightarrow (\kappa )^{2}}$
• α- Cardenales de Erdős${\displaystyle \kappa }$son los más pequeños que satisfacen${\displaystyle \kappa \rightarrow (\alpha )^{<\,\omega }}$
• Cardenales de Ramsey${\displaystyle \kappa }$son aquellos que satisfacen${\displaystyle \kappa \rightarrow (\kappa )^{<\,\omega }}$

• Dushnik, Ben; Miller, EW (1941), "Conjuntos parcialmente ordenados", American Journal of Mathematics , 63 (3): 600– 610, doi : 10.2307/2371374 , hdl : 10338.dmlcz/100377 , ISSN 0002-9327 , JSTOR 2371374 , MR 0004862   

• Erdős, Paul ; Hajnal, András ; Rado, Richard (1965), "Relaciones de partición para números cardinales" , Acta Math. Acad. Ciencia. Colgado. , 16 ( 1– 2): 93– 196, doi : 10.1007/BF01886396 , SEÑOR 0202613 

• Erdős, Paul ; Hajnal, András (1971), "Problemas sin resolver en teoría de conjuntos", Teoría axiomática de conjuntos (Universidad de California, Los Ángeles, California, 1967) , Actas del Simposio de Matemáticas Puras, vol.  XIII, Parte I, Providence, RI: Sociedad Matemática Americana, págs. 17–48 , MR 0280381  
• Erdős, Paul ; Hajnal, András ; Máté, Atila; Rado, Richard (1984), Teoría combinatoria de conjuntos: relaciones de partición para cardinales , Estudios de lógica y fundamentos de las matemáticas, vol.  106, Ámsterdam: North-Holland Publishing Co., ISBN 0-444-86157-2, MR 0795592 
• Erdős, P .; Rado, R. (1956), "Un cálculo de partición en teoría de conjuntos" (PDF) , Bull. Amer. Math. Soc. , 62 (5): 427–489 , doi : 10.1090/S0002-9904-1956-10036-0 , MR 0081864 
• Kanamori, Akihiro (2000), El infinito superior (segunda  ed.), Springer, ISBN 3-540-00384-3
• Kunen, Kenneth (1980), Teoría de conjuntos: Una introducción a las pruebas de independencia , Ámsterdam: North-Holland, ISBN 978-0-444-85401-8