Jump to content

Теорема Кантора об изоморфизме

Это хорошая статья. Нажмите здесь для получения дополнительной информации.

В теории порядка и теории моделей , разделах математики, теорема Кантора об изоморфизме утверждает, что каждые два счетных плотных неограниченных линейных порядка порядково -изоморфны . Например, функция вопросительного знака Минковского производит изоморфизм (однозначное соответствие, сохраняющее порядок) между числовым порядком рациональных чисел и числовым порядком диадических рациональных чисел .

Теорема названа в честь Георга Кантора , который впервые опубликовал ее в 1895 году, используя ее для характеристики (несчетного) порядка действительных чисел . Это можно доказать с помощью обратного метода , который также иногда приписывают Кантору, но на самом деле был опубликован позже Феликсом Хаусдорфом . Тот же метод туда-сюда также доказывает, что счетные плотные неограниченные порядки высоко симметричны и могут быть применены к другим типам структур. Однако в первоначальном доказательстве Кантора использовалась только «действующая» половина этого метода. С точки зрения теории моделей теорему изоморфизма можно выразить, сказав, что теория первого порядка неограниченных плотных линейных порядков счетно категорична , что означает, что она имеет только одну счетную модель с точностью до логической эквивалентности.

Одно из применений теоремы Кантора об изоморфизме включает в себя темпоральную логику — метод использования логики для рассуждений о времени. В этом приложении теорема подразумевает, что для моделирования интервалов времени достаточно использовать интервалы рациональных чисел: использование иррациональных чисел для этой цели не приведет к какому-либо увеличению логической мощности.

Заявление и примеры

[ редактировать ]
Функция вопросительного знака Минковского обеспечивает конкретный изоморфизм рациональных чисел двоично-рациональным числам.

Теорема Кантора об изоморфизме формулируется с использованием следующих понятий:

Имея в виду эти определения, теорема Кантора об изоморфизме утверждает, что каждые два неограниченных счетных плотных линейных порядка порядково-изоморфны. [ 1 ]

Внутри рациональных чисел некоторые подмножества также счетны, неограниченны и плотны. Примером могут служить рациональные числа в открытом единичном интервале. Другой пример — набор двоичных рациональных чисел, чисел, которые можно выразить в виде дроби с целым числителем и степенью двойки в знаменателе. По теореме Кантора об изоморфизме двоичные рациональные числа порядково изоморфны всему множеству рациональных чисел. В этом примере явный изоморфизм порядка обеспечивается функцией вопросительного знака Минковского . [ 4 ] Другой пример счетного неограниченного плотного линейного порядка дан набор действительных алгебраических чисел , действительных корней многочленов с целыми коэффициентами. В этом случае они представляют собой надмножество рациональных чисел, но снова порядково-изоморфны. [ 5 ] Также возможно применить теорему к другим линейным порядкам, элементы которых не определены как числа. Например, двоичные строки , оканчивающиеся на 1, в своем лексикографическом порядке образуют другой изоморфный порядок. [ 6 ]

Доказательства

[ редактировать ]

Одно доказательство теоремы Кантора об изоморфизме, в некоторых источниках называемое «стандартным доказательством», [ 7 ] использует метод «туда-обратно» . Это доказательство строит изоморфизм между любыми двумя заданными порядками с использованием жадного алгоритма в порядке, заданном счетным перечислением двух порядков. Более подробно, доказательство поддерживает два порядково-изоморфных конечных подмножества. и из двух данных ордеров изначально пустой. Он многократно увеличивает размеры и путем добавления нового элемента из одного порядка, первого недостающего элемента в его перечислении, и сопоставления его с эквивалентным порядку элементом другого порядка, существование которого доказано с использованием плотности и отсутствия конечных точек порядка. Два порядка меняются ролями на каждом шаге: доказательство находит первый недостающий элемент первого порядка, добавляет его к , сопоставляет его с элементом второго порядка и добавляет в ; затем находит первый недостающий элемент второго порядка, добавляет его в , сопоставляет его с элементом первого порядка и добавляет в и т. д. Каждый элемент каждого порядка в конечном итоге сопоставляется с эквивалентным по порядку элементом другого порядка, поэтому два порядка изоморфны. [ 8 ]

Хотя метод «туда-обратно» также приписывают Кантору, в первоначальной публикации этой теоремы Кантором в 1895–1897 годах использовалось другое доказательство. [ 8 ] В исследовании истории этой теоремы, проведенном логиком Чарльзом Л. Сильвером, самый ранний пример обратного доказательства, найденного Сильвером, был в учебнике Феликса Хаусдорфа 1914 года , его Grundzüge der Mengenlehre . [ 8 ]

Вместо создания порядково-изоморфных подмножеств и переходя «взад и вперед» между перечислением для первого порядка и перечислением для второго порядка, исходное доказательство Кантора использует только «движущуюся» половину обратного метода. [ 1 ] Он неоднократно дополняет два конечных множества и добавив к первый отсутствующий элемент перечисления первого порядка и добавление к элемент, эквивалентный порядку, который находится первым в перечислении второго порядка. Это естественным образом обнаруживает эквивалентность между первым порядком и подмножеством второго порядка, и Кантор затем утверждает, что включается весь второй порядок. [ 1 ] [ 8 ]

Двустороннее доказательство было формализовано как доказательство, проверенное на компьютере с использованием Coq , интерактивного средства доказательства теорем . Этот процесс формализации привел к усиленному результату: когда два вычислимо перечислимых линейных порядка имеют вычислимый предикат сравнения и вычислимые функции, представляющие их свойства плотности и неограниченности, тогда изоморфизм между ними также вычислим. [ 9 ]

Теория моделей

[ редактировать ]

Один из способов описания теоремы Кантора об изоморфизме использует язык теории моделей . Теория первого порядка неограниченных плотных линейных порядков состоит из предложений математической логики, касающихся переменных, которые представляют элементы порядка, с бинарным отношением, используемым в качестве операции сравнения упорядочивания. Здесь предложение означает правильно составленную формулу , не имеющую свободных переменных . Эти предложения включают в себя как аксиомы, логически формулирующие требования плотного линейного порядка, так и все другие предложения, которые можно доказать как логические следствия из этих аксиом. Аксиомы этой системы можно выразить так: [ 10 ] [ 11 ]

Аксиома Объяснение
Сравнение иррефлексивно : ни один элемент не меньше самого себя.
Сравнение является связным или полным, то есть каждые два различных элемента сравнимы.
Сравнение транзитивно : каждая тройка элементов последовательно упорядочена.
Нижняя граница отсутствует; каждый элемент имеет меньший элемент .
Верхней границы нет; каждый элемент имеет больший элемент .
Порядок плотный: каждые два элемента и есть элемент между ними.

Моделью этой теории является любая система элементов и отношение сравнения, подчиняющаяся всем аксиомам; это счетная модель , когда система элементов образует счетное множество . Например, обычное отношение сравнения рациональных чисел является счетной моделью этой теории. Теорему Кантора об изоморфизме можно выразить, сказав, что теория первого порядка неограниченных плотных линейных порядков счетно категорична : она имеет только одну счетную модель с точностью до логической эквивалентности. [ 1 ] [ 12 ] Однако это не является категоричным для более высоких мощностей : для любой более высокой мощности существует несколько неэквивалентных плотных неограниченных линейных порядков с одинаковой мощностью. [ 13 ]

Метод исключения кванторов в теории первого порядка неограниченных плотных линейных порядков можно использовать для доказательства того, что это полная теория . Это означает, что каждое логическое предложение на языке этой теории является либо теоремой, т. е. доказуемым как логическое следствие аксиом, либо отрицанием теоремы. Это тесно связано с категоричностью (предложение является теоремой, если оно верно для уникальной счетной модели; см. тест Лоша – Воота ), но может существовать несколько различных моделей, имеющих одну и ту же полную теорию. В частности, и упорядочение рациональных чисел, и упорядочение действительных чисел являются моделями одной и той же теории, хотя это разные модели. Удаление кванторов также можно использовать в алгоритме определения того, является ли данное предложение теоремой. [ 11 ]

[ редактировать ]
График автоморфизма рациональных чисел кусочно-линейного порядка, переводящего четыре точки {1,4,5,8} в {3,4,6,7}

Тот же обратный метод, который использовался для доказательства теоремы Кантора об изоморфизме, также доказывает, что счетные плотные линейные порядки высоко симметричны. Их симметрии называются автоморфизмами порядка и состоят из сохраняющих порядок биекций всего линейного порядка в себя. Методом «туда-сюда» каждый счетный плотный линейный порядок имеет автоморфизмы порядка, которые отображают любое множество указывает на любой другой набор точки. Это также можно доказать непосредственно для упорядочения рациональных чисел, построив автоморфизм кусочно-линейного порядка с точками разрыва в точках. заданные баллы. Эта эквивалентность всех -элементные множества точек суммируются, говоря, что группа симметрий счетного плотного линейного порядка «в высшей степени однородна». Однако не существует порядкового автоморфизма, который отображает упорядоченную пару точек в ее обратную сторону, поэтому эти симметрии не образуют 2-транзитивную группу . [ 1 ]

Теорему об изоморфизме можно распространить на раскраски неограниченного плотного счетного линейного порядка с конечным или счетным набором цветов, такие, что каждый цвет плотен в том смысле, что точка этого цвета существует между любыми двумя другими точками целого. заказ. Подмножества точек каждого цвета разбивают порядок на семейство неограниченных плотных счетных линейных порядков. Любое разбиение неограниченного плотного счетного линейного порядка на подмножества со свойством, что каждое подмножество неограниченно (внутри всего множества, а не только само по себе) и плотно (опять же, внутри всего множества), возникает в результате раскраски таким способом. Каждые две раскраски с одинаковым количеством цветов порядково изоморфны при любой перестановке их цветов. Бхаттачарджи и др. (1997) приводят в качестве примера разделение рациональных чисел на двоичные рациональные числа и их дополнения; эти два множества плотны друг в друге, и их объединение имеет порядковый изоморфизм любой другой паре неограниченных линейных порядков, счетных и плотных друг в друге. В отличие от теоремы Кантора об изоморфизме, доказательство требует полного обратного рассуждения, а не просто «продолжения». аргумент. [ 1 ]

Кантор использовал теорему изоморфизма, чтобы охарактеризовать порядок действительных чисел , несчетного множества. В отличие от рациональных чисел, действительные числа являются полными по Дедекинду , что означает, что каждое подмножество действительных чисел, имеющее конечную верхнюю границу, имеет действительную наименьшую верхнюю границу. Они содержат рациональные числа, плотные в действительных числах. Применив теорему об изоморфизме, Кантор доказал, что всякий раз, когда линейный порядок обладает теми же свойствами, что и дедекинд-полнота и содержит счетное плотное неограниченное подмножество, он должен быть порядково-изоморфен действительным числам. [ 14 ] Проблема Суслина спрашивает, должны ли порядки, обладающие некоторыми другими свойствами порядка действительных чисел, включая неограниченность, плотность и полноту, быть изоморфными порядку действительным числам; истинность этого утверждения не зависит от теории множеств Цермело – Френкеля с аксиомой выбора (ZFC). [ 15 ]

Хотя несчетные неограниченные плотные упорядочения могут не быть порядково-изоморфными, из метода «туда-обратно» следует, что любые два таких упорядочения элементарно эквивалентны . [ 7 ] [ 16 ] Другое следствие доказательства Кантора состоит в том, что каждый конечный или счетный линейный порядок может быть вложен в рациональные числа или в любой неограниченный плотный порядок. Назвав это «хорошо известным» результатом Кантора, Вацлав Серпинский доказал аналогичный результат для более высокой мощности: предполагая гипотезу континуума , существует линейный порядок мощности. в который все остальные линейные порядки мощности можно встроить. [ 17 ] Аксиома Баумгартнера , сформулированная Джеймсом Эрлом Баумгартнером в 1973 году для изучения гипотезы континуума, касается -плотные множества действительных чисел, неограниченные множества со свойством, что каждые два элемента разделены точно другие элементы. В нем утверждается, что каждые два таких множества порядково изоморфны, обеспечивая, таким образом, еще один аналог теоремы Кантора об изоморфизме с более высокой мощностью ( определяется как мощность множества всех счетных ординалов). Аксиома Баумгартнера согласуется с ZFC и отрицанием гипотезы континуума и подразумевается правильной аксиомой принуждения : [ 18 ] но независимо от аксиомы Мартина . [ 19 ]

В темпоральной логике можно показать, что различные формализации понятия интервала времени эквивалентны определению интервала парой различных элементов плотного неограниченного линейного порядка. Эта связь подразумевает, что эти теории также счетно категоричны и могут быть однозначно смоделированы интервалами рациональных чисел. [ 20 ] [ 21 ]

Теорема Серпинского, утверждающая, что любые два счетных метрических пространства без изолированных точек гомеоморфны, может рассматриваться как топологический аналог теоремы Кантора об изоморфизме и может быть доказана с использованием аналогичного обратного аргумента.

  1. ^ Jump up to: а б с д и ж г час я дж Бхаттачарджи, Минакси; Макферсон, Дугалд; Мёллер, Рёнвальдур Г.; Нойманн, Питер М. (1997), «Рациональные числа», Заметки о бесконечных группах перестановок , Тексты и материалы для чтения по математике, том. 12, Берлин: Springer-Verlag, стр. 77–86, номер документа : 10.1007/978-93-80250-91-5_9 , ISBN.  81-85931-13-5 , МР   1632579
  2. ^ Jump up to: а б с д и ж Дасгупта, Абхиджит (2014), «Главы 7 и 8: Заказы и типы заказов; Плотные и полные заказы», ​​Теория множеств , Springer New York, стр. 131–174, doi : 10.1007/978-1-4614-8854-5 , ISBN  978-1-4614-8853-8
  3. ^ Jump up to: а б Чекмасов, Андрей (23 октября 2019), "Руковины линейно упорядоченных множеств" , Мел
  4. ^ Гиргенсон, Роланд (1996), «Построение сингулярных функций с помощью дробей Фарея», Журнал математического анализа и приложений , 203 (1): 127–141, doi : 10.1006/jmaa.1996.0370 , MR   1412484
  5. ^ Боси, Г.; Мехта, ГБ (2002), «Существование полунепрерывной или непрерывной функции полезности: единый подход и элементарное доказательство», Journal of Mathematical Economics , 38 (3): 311–328, doi : 10.1016/S0304-4068(02) 00058-7 , МР   1940365 ; см. замечание 3, с. 323
  6. ^ Лори, Маркус; Матиссен, Кристиан (2013), «Изоморфизм правильных деревьев и слов», Information and Computation , 224 : 71–105, arXiv : 1102.2782 , doi : 10.1016/j.ic.2013.01.002 , MR   3016459
  7. ^ Jump up to: а б Брайант, Росс (2006), Вычисление ранга частичного изоморфизма порядковых структур (докторская диссертация), Университет Северного Техаса, стр. 1, 305292986
  8. ^ Jump up to: а б с д Сильвер, Чарльз Л. (1994), «Кто изобрел двусторонний аргумент Кантора?» , Современная логика , 4 (1): 74–78, МР   1253680
  9. ^ Кирст, Доминик (2022), «Вычислительные аргументы вперед и назад в конструктивной теории типов», в Андронике, июнь; де Моура, Леонардо (ред.), 13-я Международная конференция по интерактивному доказательству теорем, ITP 2022, 7–10 августа 2022 г., Хайфа, Израиль , LIPIcs, vol. 237, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 22:1–22:12, doi : 10.4230/LIPIcs.ITP.2022.22
  10. ^ Об этой аксиоматизации строгих линейных порядков см.: Голдрей, Дерек (2005), Исчисление высказываний и предикатов: модель аргумента , Springer, с. 193 , ISBN  9781846282294 . Аксиомы можно сформулировать логически, используя либо строгое сравнение, либо строгое сравнение. или нестрогое сравнение но строгое сравнение упрощает выражение аксиом свойств неограниченности и плотности. Заметим, что нет необходимости указывать, что эти порядки антисимметричны, т. е. что ; это следствие иррефлексивности и транзитивности.
  11. ^ Jump up to: а б Уоррелл, Джеймс (2016), «Разрешимые теории» (PDF) , «Логика и доказательство» (конспекты лекций), Оксфордский университет ; Уоррелл использует другую, но эквивалентную аксиоматизацию для строгих линейных порядков и объединяет две аксиомы неограниченности в одну аксиому.
  12. ^ Бючи, Дж. Ричард ; Данхоф, Кеннет Дж. (1973), «Вариации на тему Кантора в теории реляционных структур», Journal of Mathematical Logic and Foundations of Mathematics , 19 (26–29): 411–426, doi : 10.1002/malq. 19730192604 , МР   0337567
  13. ^ Морли, Майкл (1965), «Категоричность в степени», Труды Американского математического общества , 114 (2): 514–538, doi : 10.2307/1994188 , JSTOR   1994188 , MR   0175782
  14. ^ Йех, Томас (2003), Теория множеств , Монографии Спрингера по математике (изд. 3-го тысячелетия), Берлин: Springer-Verlag, Теорема 4.3, стр. 38, номер домена : 10.1007/3-540-44761-X , ISBN  3-540-44085-2 , МР   1940513
  15. ^ Девлин, Кейт Дж .; Джонсбротен, Ховард (1974), Проблема Суслина , Конспект лекций по математике, том. 405, Берлин и Нью-Йорк: Springer-Verlag, MR   0384542.
  16. ^ Лэнгфорд, CH (1926–1927), «Некоторые теоремы о выводимости», Annals of Mathematics , Second Series, 28 (1–4): 16–40, doi : 10.2307/1968352 , JSTOR   1968352 , MR   1502760
  17. ^ Серпинский, Вацлав (1932), «Обобщение теоремы Кантора о счетных упорядоченных множествах», Fundamenta Mathematicae (на французском языке), 18 : 280–284, doi : 10.4064/fm-18-1-280-284 , Zbl   0004.20502
  18. ^ Баумгартнер, Джеймс Э. (1973), «Все -плотные множества действительных чисел могут быть изоморфными», Fundamenta Mathematicae , 79 (2): 101–106, doi : 10.4064/fm-79-2-101-106 , MR   0317934
  19. ^ Авраам, Ури; Шела, Сахарон (1981): «Аксиома Мартина не означает, что каждые два -плотные множества действительных чисел изоморфны», Israel Journal of Mathematics , 38 (1–2): 161–176, doi : 10.1007/BF02761858 , MR   0599485
  20. ^ ван Бентем, Йохан (1984), «Напряженная логика и время», Журнал формальной логики Нотр-Дам , 25 (1): 1–16, doi : 10.1305/ndjfl/1093870515 , MR   0723616
  21. ^ Ладкин, Питер Б. (1987), «Модели аксиом для временных интервалов» , в Форбусе, Кеннет Д.; Шроб, Ховард Э. (ред.), Материалы 6-й Национальной конференции по искусственному интеллекту. Сиэтл, Вашингтон, США, июль 1987 г. , Морган Кауфманн, стр. 234–239.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: add5cbf2830e466f0c8062f64d036046__1722189180
URL1:https://arc.ask3.ru/arc/aa/ad/46/add5cbf2830e466f0c8062f64d036046.html
Заголовок, (Title) документа по адресу, URL1:
Cantor's isomorphism theorem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)