Combinatoria infinita

Extensión de ideas en combinatoria a conjuntos infinitos

En matemáticas, la combinatoria infinitaria , o teoría de conjuntos combinatorios , es una extensión de las ideas de la combinatoria a los 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]

Teoría de Ramsey para conjuntos infinitos

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

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

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

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

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

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

Otra variación es la notación

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

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

Algunas propiedades de este incluyen: (en lo que sigue hay un cardinal) ${\displaystyle \kappa }$

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

${\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 darse propiedades de partición con exponentes infinitos, y algunas de ellas se obtienen como consecuencia del axioma de determinación (AD). Por ejemplo, Donald A. Martin demostró que AD implica

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

Colorantes fuertes

Wacław Sierpiński demostró que el teorema de Ramsey no se extiende a conjuntos de tamaño al mostrar que . Es decir, Sierpiński construyó una coloración de pares de números reales en dos colores tal que para cada subconjunto incontable de números reales , toma ambos colores. Tomando cualquier conjunto de números reales de tamaño y aplicándole la coloración de Sierpiński, obtenemos que . Coloraciones como esta 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. ${\displaystyle \aleph _{1}}$ ${\displaystyle 2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}}$ ${\displaystyle X}$ ${\displaystyle [X]^{2}}$ ${\displaystyle \aleph _{1}}$ ${\displaystyle \aleph _{1}\not \rightarrow (\aleph _{1})_{2}^{2}}$

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

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

es una forma abreviada de decir que existe una coloración del conjunto de subconjuntos de elementos de en partes tales que cada conjunto de tipo de orden es un conjunto arco iris. Un conjunto arco iris es en este caso un subconjunto de tal que toma todos los colores. Cuando es 2, a menudo se omite. Tales declaraciones se conocen como relaciones de partición de corchetes negativos. ${\displaystyle [\kappa ]^{n}}$ ${\displaystyle n}$ ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle \lambda }$ ${\displaystyle A}$ ${\displaystyle \kappa }$ ${\displaystyle [A]^{n}}$ ${\displaystyle m}$ ${\displaystyle m}$

Otra variación es la notación

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

que es una forma abreviada de decir que existe una coloración del conjunto de subconjuntos de 2 elementos de con colores tal que para cada subconjunto de tipo de orden y cada subconjunto de tipo de orden , el conjunto toma todos los colores. ${\displaystyle [\kappa ]^{2}}$ ${\displaystyle \kappa }$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle \lambda }$ ${\displaystyle B}$ ${\displaystyle \mu }$ ${\displaystyle A\times B}$ ${\displaystyle m}$

Algunas propiedades de este incluyen: (en lo que sigue hay un cardinal) ${\displaystyle \kappa }$

${\displaystyle \displaystyle 2^{\kappa }\nrightarrow [\kappa ^{+}]^{2}}$(Sierpinski)

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

${\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 )

Cardenales grandes

Se pueden definir varias propiedades cardinales importantes utilizando esta notación. En particular:

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

Notas

1. Andreas Blass , Características cardinales combinatorias del continuo , capítulo 6 del Manual de teoría de conjuntos, editado por Matthew Foreman y Akihiro Kanamori , Springer, 2010
2. Todd Eisworth, Sucesores de cardinales singulares, capítulo 15 en Handbook of Set Theory, editado por Matthew Foreman y Akihiro Kanamori, Springer, 2010
3. Rinot, Assaf, Tutorial sobre coloraciones fuertes y sus aplicaciones, 6.ª Conferencia Europea de Teoría de Conjuntos , consultado el 10 de diciembre de 2023

Referencias

• 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 no resueltos en la teoría de conjuntos", Axiomatic Set Theory (Univ. California, Los Ángeles, Calif., 1967) , Proc. Sympos. Pure Math, vol. XIII Parte I, Providence, RI: Amer. Math. Soc., 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, Sr.  0795592
• Erdős, P. ; Rado, R. (1956), "Un cálculo de particiones en la 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: Holanda Septentrional, ISBN 978-0-444-85401-8