Dushnik – Millerova věta - Dushnik–Miller theorem

Nesmí být zaměňována s Erdős – Dushnik – Millerova věta.

V matematice je Dushnik – Millerova věta je výsledkem v teorie objednávek říkat, že každý nekonečný lineární pořadí nemá identitu vkládání objednávek do sebe.[1] Je pojmenován pro Ben Dushnik a E. W. Miller, kteří tuto větu publikovali pro počitatelný lineární objednávky v roce 1940. Silněji ukázaly, že v počitatelném případě existuje objednávka vložená do vlastní podmnožiny dané objednávky; poskytli však příklady, které ukazují, že toto posílení nemusí vždy platit pro nespočetné objednávky.[2]

v reverzní matematika, Dushnik – Millerova věta pro spočetné lineární objednávky má stejnou sílu jako aritmetické porozumění axiomu (ACA0), jeden ze subsystémů „velké pětky“ aritmetika druhého řádu.[1][3] Tento výsledek úzce souvisí se skutečností, že (jako Louise Hay a Joseph Rosenstein dokázal), že existují vypočitatelný lineární objednávky bez vypočítatelného vkládání neidentity.[1][4]

Viz také

Reference

  1. ^ A b C Hirschfeldt, Denis R. (2014), „10.1 Dushnik – Millerova věta“, Krájení pravdy Série přednášek Ústavu pro matematické vědy, Singapurská národní univerzita, 28, World Scientific
  2. ^ Dushnik, Ben; Miller, E. W. (1940), „O transformacích podobnosti lineárně uspořádaných množin“, Bulletin of the American Mathematical Society, 46: 322–326, doi:10.1090 / S0002-9904-1940-07213-1, PAN  0001919
  3. ^ Downey, Rodney G.; Jockusch, Carl; Miller, Joseph S. (2006), „On self-embeddings of computable linear orderings“, Annals of Pure and Applied Logic, 138 (1–3): 52–76, doi:10.1016 / j.apal.2005.06.008, PAN  2183808
  4. ^ Rosenstein, Joseph G. (1982), Lineární uspořádáníČistá a aplikovaná matematika, 98Akademický tisk, Věta 16,49, s. 447, ISBN  0-12-597680-1, PAN  0662564