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