Combinatoria infinita

Extensión de ideas en combinatoria a conjuntos infinitos.

En matemáticas, la combinatoria infinita , o teoría combinatoria de conjuntos , es una extensión de las ideas en combinatoria a conjuntos infinitos . Algunas de las cosas estudiadas incluyen gráficos 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 de 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 en piezas tiene un conjunto homogéneo de tipo de orden . En este caso, un conjunto homogéneo es un subconjunto tal que cada subconjunto de elementos está en el mismo elemento de la partición. Cuando es 2, a menudo se omite. Estas 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 normalmente se considera finito. Una extensión donde casi se permite que sea infinita 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 en piezas 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 esto incluyen: (a continuación se muestra un cardenal) ${\displaystyle \kappa }$

${\displaystyle \displaystyle \aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}}$para todo finito 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, las propiedades de partición con exponentes infinitos pueden ser válidas, y algunas de ellas se obtienen como consecuencia del axioma de determinabilidad (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 demostrar que . Es decir, Sierpiński construyó una coloración de pares de números reales en dos colores de modo 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 el color de Sierpiński, obtenemos eso . Coloraciones como ésta 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. Entonces ${\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 en partes de modo que cada conjunto de tipo de orden es un conjunto de arco iris. Un conjunto de arco iris es en este caso un subconjunto de uno que toma todos los colores. Cuando es 2, a menudo se omite. Estas declaraciones se conocen como relaciones de partición negativas entre corchetes. ${\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 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 esto incluyen: (a continuación se muestra un cardenal) ${\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 , Blas )

${\displaystyle \displaystyle \aleph _{1}\nrightarrow [\aleph _{1}]_{4}^{2}}$( Galvín y Sela )

${\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}}$( Galvín y Sela )

Grandes cardenales

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

• Los cardinales débilmente compactos son aquellos que satisfacen ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\kappa )^{2}}$
• α- Los cardenales de 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 cardenales singulares, capítulo 15 del Manual de teoría de conjuntos, editado por Matthew Foreman y Akihiro Kanamori, Springer, 2010
3. Rinot, Assaf, Tutorial sobre colorantes 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 teoría de conjuntos", Teoría de conjuntos axiomática (Univ. California, Los Ángeles, California, 1967) , Proc. Simposios. Matemáticas puras, vol. XIII Parte I, Providence, RI: Amer. Matemáticas. Soc., págs. 17–48, SEÑOR  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, señor  0795592
• Erdős, P .; Rado, R. (1956), "Un cálculo de partición en teoría de conjuntos" (PDF) , Bull. América. Matemáticas. Soc. , 62 (5): 427–489, doi : 10.1090/S0002-9904-1956-10036-0 , SEÑOR  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