En la teoría matemática de gráficas infinitas , el teorema de Erdős-Dushnik-Miller es una forma del teorema de Ramsey que establece que cada gráfica infinita contiene un conjunto independiente infinito numerable o una camarilla con la misma cardinalidad que la gráfica completa. [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 infinita numerable o un conjunto independiente con la misma cardinalidad que la grafica completa. En su artículo, le dieron crédito a Paul Erdős por su ayuda en su prueba. Aplicaron estos resultados a los gráficos de comparabilidad de conjuntos parcialmente ordenados para mostrar que cada orden parcial contiene un antichain infinito numerable o una cadena.de cardinalidad igual a todo el orden, y que cada orden parcial contiene una cadena infinita numerable o una antichain de cardinalidad igual a todo el orden. [2]
El mismo teorema también se puede establecer como resultado en la teoría de conjuntos , utilizando la notación de flecha de Erdős & Rado (1956) , como. Esto significa que, para cada set 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 , de modo que todos los pares de elementos de pertenece a . [3] Aquí, se puede interpretar como los bordes de un gráfico que tiene como su conjunto de vértices, en el que (si existe) es una camarilla de cardinalidad , y (si existe) es un conjunto independiente infinito numerable. [1]
Si se toma como el número cardinal en sí mismo, el teorema se puede formular en términos de números ordinales con la notación, significa que (cuando existe) tiene tipo de orden . Para incontables cardenales regulares (y algunos otros cardenales) esto se puede fortalecer para ; [4] sin embargo, es consistente que este fortalecimiento no es válido para la cardinalidad del continuo . [5]
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
- ^ a b Milner, EC; Pouzet, M. (1985), "El teorema de Erdős-Dushnik-Miller para gráficos y órdenes topológicos", Order , 1 (3): 249-257, doi : 10.1007 / BF00383601 , MR 0779390 , S2CID 123272176; ver en particular el Teorema 44
- ^ Dushnik, Ben; Miller, EW (1941), "Conjuntos parcialmente ordenados", American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307 / 2371374 , JSTOR 2371374 , MR 0004862; ver en particular los teoremas 5.22 y 5.23
- ^ Erdős, Paul ; Rado, R. (1956), "Un cálculo de partición en la teoría de conjuntos" , Bull. Amer. Matemáticas. Soc. , 62 (5): 427–489, doi : 10.1090 / S0002-9904-1956-10036-0 , MR 0081864
- ^ Shelah, Saharon (2009), "La flecha de Erdős-Rado para cardenales singulares", Canadian Mathematical Bulletin , 52 (1): 127-131, doi : 10.4153 / CMB-2009-015-8 , MR 2494318 CS1 maint: parámetro desalentado ( enlace )
- ^ Sela, 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 2.586.535 , MR 1782118
- ^ Hajnal, András (1997), "La teoría de conjuntos de Paul Erds", Las matemáticas de Paul Erdős, II , Algorithms and Combinatorics, 14 , Berlín: Springer, págs. 352–393, doi : 10.1007 / 978-3-642-60406 -5_33 , MR 1425228; ver en particular la Sección 3, "Teoría infinita de Ramsey - primeros trabajos", p. 353