WikiDer > Теорема Душника – Миллера

Dushnik–Miller theorem
Не путать с Теорема Эрдеша – Душника – Миллера..

В математике Теорема Душника – Миллера это результат теория порядка заявляя, что каждый бесконечный линейный порядок имеет неидентификационный заказать встраивание в себя.[1] Он назван в честь Бена Душника и Э. В. Миллера, опубликовавших эту теорему для счетный линейные порядки в 1940 году. Более того, они показали, что в счетном случае существует порядок, вложенный в собственное подмножество данного порядка; однако они привели примеры, показывающие, что такое усиление не всегда справедливо для бесчисленных заказов.[2]

В обратная математика, теорема Душника – Миллера для счетных линейных порядков имеет такую ​​же силу, как и аксиома арифметического понимания (ACA0), одной из «большой пятерки» подсистем арифметика второго порядка.[1][3] Этот результат тесно связан с тем, что (поскольку Луиза Хэй и Джозеф Розенштейн доказал) существуют вычислимый линейные порядки без вычислимого нетождественного самовложения.[1][4]

Смотрите также

Рекомендации

  1. ^ а б c Хиршфельдт, Денис Р. (2014), «10.1 Теорема Душника – Миллера», Нарезка правды, Серия лекций Института математических наук Национального университета Сингапура, 28, World Scientific
  2. ^ Душник, Бен; Миллер, Э. У. (1940), "О преобразованиях подобия линейно упорядоченных множеств", Бюллетень Американского математического общества, 46: 322–326, Дои:10.1090 / S0002-9904-1940-07213-1, МИСТЕР 0001919
  3. ^ Дауни, Родни Г.; Джокуш, Карл; Миллер, Джозеф С. (2006), "О самовложениях вычислимых линейных порядков", Анналы чистой и прикладной логики, 138 (1–3): 52–76, Дои:10.1016 / j.apal.2005.06.008, МИСТЕР 2183808
  4. ^ Розенштейн, Джозеф Г. (1982), Линейные порядки, Чистая и прикладная математика, 98, Academic Press, Теорема 16.49, с. 447, ISBN 0-12-597680-1, МИСТЕР 0662564