Teorema de Erdős-Dushnik-Miller

En la teoría matemática de grafos infinitos , el teorema de Erdős–Dushnik–Miller es una forma del teorema de Ramsey que establece que cada grafo infinito contiene un conjunto independiente numerablemente infinito o una camarilla con la misma cardinalidad que todo el grafo. ^[1]

El teorema fue publicado por primera vez por Ben Dushnik y EW Miller (1941), tanto en la forma indicada anteriormente como en una forma complementaria equivalente : cada grafo infinito contiene una camarilla numerablemente infinita o un conjunto independiente con cardinalidad igual a la del grafo completo. En su artículo, atribuyeron la ayuda de Paul Erdős en su demostración. Aplicaron estos resultados a los grafos de comparabilidad de conjuntos parcialmente ordenados para mostrar que cada orden parcial contiene una anticadena numerablemente infinita o una cadena de cardinalidad igual a la del orden completo, y que cada orden parcial contiene una cadena numerablemente infinita o una anticadena de cardinalidad igual a la del orden completo. ^[2]

El mismo teorema también puede enunciarse como resultado en la teoría de conjuntos , utilizando la notación de flechas de Erdős y Rado (1956), como . Esto significa que, para cada conjunto de cardinalidad , y cada partición de los pares ordenados de elementos de en dos subconjuntos y , existe un subconjunto de cardinalidad o un subconjunto de cardinalidad , tal que todos los pares de elementos de pertenecen a . ^[3] Aquí, puede interpretarse como las aristas de un grafo que tiene como conjunto de vértices, en el que (si existe) es una camarilla de cardinalidad , y (si existe) es un conjunto independiente numerablemente infinito. ^[1] ${\displaystyle \kappa \rightarrow (\kappa ,\aleph _{0})^{2}}$ ${\displaystyle S}$ ${\displaystyle \kappa }$ ${\displaystyle S}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle S_{1}\subset S}$ ${\displaystyle \kappa }$ ${\displaystyle S_{2}\subset S}$ ${\displaystyle \aleph _{0}}$ ${\displaystyle S_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{1}}$ ${\displaystyle S}$ ${\displaystyle S_{1}}$ ${\displaystyle \kappa }$ ${\displaystyle S_{2}}$

Si se toma como el propio número cardinal , el teorema se puede formular en términos de números ordinales con la notación , lo que significa que (cuando existe) tiene tipo de orden . Para cardinales regulares incontables (y algunos otros cardinales) esto se puede reforzar a ; ^[4] sin embargo, es consistente que este fortalecimiento no se cumple para la cardinalidad del continuo . ^[5] ${\displaystyle S}$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\kappa ,\omega )^{2}}$ ${\displaystyle S_{2}}$ ${\displaystyle \omega }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \rightarrow (\kappa ,\omega +1)^{2}}$

El teorema de Erdős-Dushnik-Miller ha sido llamado la primera generalización "desequilibrada" del teorema de Ramsey y el primer resultado significativo de Paul Erdős en la teoría de conjuntos. ^[6]

Referencias

1. Milner, EC; Pouzet, M. (1985), "El teorema de Erdős–Dushnik–Miller para órdenes y gráficos topológicos", Order , 1 (3): 249–257, doi :10.1007/BF00383601, MR  0779390, S2CID  123272176; véase en particular el Teorema 44
2. Dushnik, Ben; Miller, EW (1941), "Conjuntos parcialmente ordenados", American Journal of Mathematics , 63 (3): 600–610, doi :10.2307/2371374, JSTOR  2371374, MR  0004862; véanse en particular los teoremas 5.22 y 5.23
3. Erdős, Paul ; Rado, R. (1956), "Un cálculo de particiones en la teoría de conjuntos", Boletín de la Sociedad Matemática Americana , 62 (5): 427–489, doi : 10.1090/S0002-9904-1956-10036-0 , MR  0081864
4. Shelah, Saharon (2009), "La flecha de Erdős–Rado para cardinales singulares", Canadian Mathematical Bulletin , 52 (1): 127–131, doi : 10.4153/CMB-2009-015-8 , MR  2494318
5. Shelah, Saharon ; Stanley, Lee J. (2000), "Filtros, conjuntos de Cohen y extensiones consistentes del teorema de Erdős–Dushnik–Miller", The Journal of Symbolic Logic , 65 (1): 259–271, arXiv : math/9709228 , doi :10.2307/2586535, JSTOR  2586535, MR  1782118, S2CID  2763013
6. Hajnal, András (1997), "Teoría de conjuntos de Paul Erdős", Las matemáticas de Paul Erdős, II , Algoritmos y combinatoria, vol. 14, Berlín: Springer, págs. 352–393, doi :10.1007/978-3-642-60406-5_33, ISBN 978-3-642-64393-4, Sr.  1425228; véase en particular la Sección 3, "Teoría de Ramsey infinita: primeros artículos", pág. 353