Erdős – Dushnik – Millerova věta - Erdős–Dushnik–Miller theorem

V matematické teorii nekonečné grafy, Erdős – Dushnik – Millerova věta je forma Ramseyova věta o tom, že každý nekonečný graf obsahuje buď a počítatelně nekonečný nezávislá sada nebo klika se stejným mohutnost jako celý graf.^[1]

Věta byla poprvé publikována Benem Dushnikem a E. W. Millerem (1941 ), a to jak ve výše uvedené formě, tak v ekvivalentu doplňková forma: každý nekonečný graf obsahuje buď nespočetně nekonečnou kliku, nebo nezávislou množinu se stejnou mohutností jako celý graf. Ve svém příspěvku připočítali Paul Erdős s pomocí při dokazování. Tyto výsledky aplikovali na srovnatelné grafy z částečně objednané sady ukázat, že každá částečná objednávka obsahuje buď nespočetně nekonečno antichain nebo a řetěz mohutnosti rovné celému řádu a že každý dílčí řád obsahuje buď nespočetně nekonečný řetězec nebo antichain mohutnosti rovného celému řádu.^[2]

Stejná věta může být také uvedena jako výsledek v teorie množin, za použití šípová notace z Erdős & Rado (1956), tak jako ${ displaystyle kappa rightarrow ( kappa, aleph _ {0}) ^ {2}}$. To znamená, že pro každou sadu ${ displaystyle S}$ mohutnosti ${ displaystyle kappa}$a každý oddíl seřazených párů prvků ${ displaystyle S}$ do dvou podmnožin ${ displaystyle P_ {1}}$ a ${ displaystyle P_ {1}}$, existuje buď podmnožina ${ displaystyle S_ {1} podmnožina S}$ mohutnosti ${ displaystyle kappa}$ nebo podmnožina ${ displaystyle S_ {2} podmnožina S}$ mohutnosti ${ displaystyle aleph _ {0}}$, takže všechny páry prvků ${ displaystyle S_ {i}}$ patřit k ${ displaystyle P_ {i}}$.^[3] Tady, ${ displaystyle P_ {1}}$ lze interpretovat jako okraje grafu, který má ${ displaystyle S}$ jako jeho vrcholová množina, ve které ${ displaystyle S_ {1}}$ (pokud existuje) je klika mohutnosti ${ displaystyle kappa}$, a ${ displaystyle S_ {2}}$ (pokud existuje) je spočetně nekonečná nezávislá množina.^[1]

Li ${ displaystyle S}$ je považován za základní číslovka ${ displaystyle kappa}$ sám, teorém může být formulován v podmínkách řadové číslovky s notací ${ displaystyle kappa rightarrow ( kappa, omega) ^ {2}}$, znamenající, že ${ displaystyle S_ {2}}$ (pokud existuje) má typ objednávky ${ displaystyle omega}$. Za nespočet řádní kardinálové ${ displaystyle kappa}$ (a někteří další kardinálové) to lze posílit ${ displaystyle kappa rightarrow ( kappa, omega +1) ^ {2}}$;^[4] nicméně je konzistentní že toto posílení neplatí pro mohutnost kontinua.^[5]

Erdős – Dushnik – Millerova věta byla nazývána prvním „nevyváženým“ zobecněním Ramseyho věty a prvním významným výsledkem teorie množin Paula Erdőse.^[6]

Reference