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

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

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

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

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

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

Линейный порядок или полный порядок определяется набором элементов и операцией сравнения, которая упорядочивает каждую пару отдельных элементов и подчиняется транзитивному закону . ^{[ 1 ]}^{[ 2 ]} Знакомые числовые порядки целых , рациональных и действительных чисел — все это примеры линейных порядков. ^{[ 2 ]}
Неограниченность означает, что упорядочение не содержит минимального или максимального элемента. Это отличается от концепции ограниченного множества в метрическом пространстве . Например, открытый интервал (0,1) не ограничен как упорядоченное множество, даже если он ограничен как подмножество действительных чисел, поскольку ни его нижняя граница 0, ни верхняя граница 1 не принадлежат интервалу. ^{[ 1 ]} Целые, рациональные и действительные числа также не ограничены. ^{[ 2 ]}
Упорядочение является плотным , когда между каждой парой элементов есть еще один элемент . ^{[ 1 ]} Это отличается от топологически плотного множества действительных чисел. ^{[ 2 ]} Рациональные и действительные числа плотны в этом смысле, поскольку среднее арифметическое любых двух чисел принадлежит одному и тому же множеству и лежит между ними, но целые числа не являются плотными, поскольку между любыми двумя последовательными целыми числами нет другого целого числа . ^{[ 3 ]}
И целые, и рациональные числа образуют счетные множества , но действительные числа не образуют, согласно другому результату Кантора, его доказательству того, что действительные числа несчетны . ^{[ 2 ]}
Два линейных порядка изоморфны существует взаимно однозначное соответствие , если между ними , сохраняющее их порядок. ^{[ 1 ]}^{[ 2 ]} Например, целые и четные числа по порядку изоморфны при условии биекции, которая умножает каждое целое число на два. ^{[ 3 ]}

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

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

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

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

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

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

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

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

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


Аксиома	Объяснение
$\forall a\,{\bigl (}\lnot (a<a){\bigr )}$	Сравнение иррефлексивно : ни один элемент не меньше самого себя.
$\forall a\,\forall b\,(a=b\vee a<b\vee b<a)$	Сравнение является связным или полным, то есть каждые два различных элемента сравнимы.
$\forall a\,\forall b\,\forall c\,{\bigl (}(a<b\wedge b<c)\Rightarrow a<c{\bigr )}$	Сравнение транзитивно : каждая тройка элементов последовательно упорядочена.
$\forall a\,\exists b\,(b<a)$	Нижняя граница отсутствует; каждый элемент $a$ имеет меньший элемент $b$ .
$\forall a\,\exists b\,(a<b)$	Верхней границы нет; каждый элемент $a$ имеет больший элемент $b$ .
$\forall a\,\forall b\,{\bigl (}a<b\Rightarrow \exists c\,(a<c\wedge c<b){\bigr )}$	Порядок плотный: каждые два элемента $a$ и $b$ есть элемент $c$ между ними.

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

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

Связанные результаты

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Бхаттачарджи, Минакси; Макферсон, Дугалд; Мёллер, Рёнвальдур Г.; Нойманн, Питер М. (1997), «Рациональные числа», Заметки о бесконечных группах перестановок , Тексты и материалы для чтения по математике, том. 12, Берлин: Springer-Verlag, стр. 77–86, номер документа : 10.1007/978-93-80250-91-5_9 , ISBN. 81-85931-13-5 , МР 1632579
^ 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
^ Jump up to: ^а ^б Чекмасов, Андрей (23 октября 2019), "Руковины линейно упорядоченных множеств" , Мел
^ Гиргенсон, Роланд (1996), «Построение сингулярных функций с помощью дробей Фарея», Журнал математического анализа и приложений , 203 (1): 127–141, doi : 10.1006/jmaa.1996.0370 , MR 1412484
^ Боси, Г.; Мехта, ГБ (2002), «Существование полунепрерывной или непрерывной функции полезности: единый подход и элементарное доказательство», Journal of Mathematical Economics , 38 (3): 311–328, doi : 10.1016/S0304-4068(02) 00058-7 , МР 1940365 ; см. замечание 3, с. 323
^ Лори, Маркус; Матиссен, Кристиан (2013), «Изоморфизм правильных деревьев и слов», Information and Computation , 224 : 71–105, arXiv : 1102.2782 , doi : 10.1016/j.ic.2013.01.002 , MR 3016459
^ Jump up to: ^а ^б Брайант, Росс (2006), Вычисление ранга частичного изоморфизма порядковых структур (докторская диссертация), Университет Северного Техаса, стр. 1, 305292986
^ Jump up to: ^а ^б ^с ^д Сильвер, Чарльз Л. (1994), «Кто изобрел двусторонний аргумент Кантора?» , Современная логика , 4 (1): 74–78, МР 1253680
^ Кирст, Доминик (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
^ Об этой аксиоматизации строгих линейных порядков см.: Голдрей, Дерек (2005), Исчисление высказываний и предикатов: модель аргумента , Springer, с. 193 , ISBN 9781846282294 . Аксиомы можно сформулировать логически, используя либо строгое сравнение, либо строгое сравнение. $<$ или нестрогое сравнение $\leq$ но строгое сравнение упрощает выражение аксиом свойств неограниченности и плотности. Заметим, что нет необходимости указывать, что эти порядки антисимметричны, т. е. что $a<b\Rightarrow \lnot (b<a)$ ; это следствие иррефлексивности и транзитивности.
^ Jump up to: ^а ^б Уоррелл, Джеймс (2016), «Разрешимые теории» (PDF) , «Логика и доказательство» (конспекты лекций), Оксфордский университет ; Уоррелл использует другую, но эквивалентную аксиоматизацию для строгих линейных порядков и объединяет две аксиомы неограниченности в одну аксиому.
^ Бючи, Дж. Ричард ; Данхоф, Кеннет Дж. (1973), «Вариации на тему Кантора в теории реляционных структур», Journal of Mathematical Logic and Foundations of Mathematics , 19 (26–29): 411–426, doi : 10.1002/malq. 19730192604 , МР 0337567
^ Морли, Майкл (1965), «Категоричность в степени», Труды Американского математического общества , 114 (2): 514–538, doi : 10.2307/1994188 , JSTOR 1994188 , MR 0175782
^ Йех, Томас (2003), Теория множеств , Монографии Спрингера по математике (изд. 3-го тысячелетия), Берлин: Springer-Verlag, Теорема 4.3, стр. 38, номер домена : 10.1007/3-540-44761-X , ISBN 3-540-44085-2 , МР 1940513
^ Девлин, Кейт Дж .; Джонсбротен, Ховард (1974), Проблема Суслина , Конспект лекций по математике, том. 405, Берлин и Нью-Йорк: Springer-Verlag, MR 0384542.
^ Лэнгфорд, CH (1926–1927), «Некоторые теоремы о выводимости», Annals of Mathematics , Second Series, 28 (1–4): 16–40, doi : 10.2307/1968352 , JSTOR 1968352 , MR 1502760
^ Серпинский, Вацлав (1932), «Обобщение теоремы Кантора о счетных упорядоченных множествах», Fundamenta Mathematicae (на французском языке), 18 : 280–284, doi : 10.4064/fm-18-1-280-284 , Zbl 0004.20502
^ Баумгартнер, Джеймс Э. (1973), «Все $\aleph _{1}$ -плотные множества действительных чисел могут быть изоморфными», Fundamenta Mathematicae , 79 (2): 101–106, doi : 10.4064/fm-79-2-101-106 , MR 0317934
^ Авраам, Ури; Шела, Сахарон (1981): «Аксиома Мартина не означает, что каждые два $\aleph _{1}$ -плотные множества действительных чисел изоморфны», Israel Journal of Mathematics , 38 (1–2): 161–176, doi : 10.1007/BF02761858 , MR 0599485
^ ван Бентем, Йохан (1984), «Напряженная логика и время», Журнал формальной логики Нотр-Дам , 25 (1): 1–16, doi : 10.1305/ndjfl/1093870515 , MR 0723616
^ Ладкин, Питер Б. (1987), «Модели аксиом для временных интервалов» , в Форбусе, Кеннет Д.; Шроб, Ховард Э. (ред.), Материалы 6-й Национальной конференции по искусственному интеллекту. Сиэтл, Вашингтон, США, июль 1987 г. , Морган Кауфманн, стр. 234–239.

[bmmn-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Бхаттачарджи, Минакси; Макферсон, Дугалд; Мёллер, Рёнвальдур Г.; Нойманн, Питер М. (1997), «Рациональные числа», Заметки о бесконечных группах перестановок , Тексты и материалы для чтения по математике, том. 12, Берлин: Springer-Verlag, стр. 77–86, номер документа : 10.1007/978-93-80250-91-5_9 , ISBN. 81-85931-13-5 , МР 1632579

[dasgupta-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

[chalkdust-3] Jump up to: ^а ^б Чекмасов, Андрей (23 октября 2019), "Руковины линейно упорядоченных множеств" , Мел

[girgensohn-4] Гиргенсон, Роланд (1996), «Построение сингулярных функций с помощью дробей Фарея», Журнал математического анализа и приложений , 203 (1): 127–141, doi : 10.1006/jmaa.1996.0370 , MR 1412484

[bosmet-5] Боси, Г.; Мехта, ГБ (2002), «Существование полунепрерывной или непрерывной функции полезности: единый подход и элементарное доказательство», Journal of Mathematical Economics , 38 (3): 311–328, doi : 10.1016/S0304-4068(02) 00058-7 , МР 1940365 ; см. замечание 3, с. 323

[lohmat-6] Лори, Маркус; Матиссен, Кристиан (2013), «Изоморфизм правильных деревьев и слов», Information and Computation , 224 : 71–105, arXiv : 1102.2782 , doi : 10.1016/j.ic.2013.01.002 , MR 3016459

[bryant-7] Jump up to: ^а ^б Брайант, Росс (2006), Вычисление ранга частичного изоморфизма порядковых структур (докторская диссертация), Университет Северного Техаса, стр. 1, 305292986

[silver-8] Jump up to: ^а ^б ^с ^д Сильвер, Чарльз Л. (1994), «Кто изобрел двусторонний аргумент Кантора?» , Современная логика , 4 (1): 74–78, МР 1253680

[kirst-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

[goldrei-10] Об этой аксиоматизации строгих линейных порядков см.: Голдрей, Дерек (2005), Исчисление высказываний и предикатов: модель аргумента , Springer, с. 193 , ISBN 9781846282294 . Аксиомы можно сформулировать логически, используя либо строгое сравнение, либо строгое сравнение. $<$ или нестрогое сравнение $\leq$ но строгое сравнение упрощает выражение аксиом свойств неограниченности и плотности. Заметим, что нет необходимости указывать, что эти порядки антисимметричны, т. е. что $a<b\Rightarrow \lnot (b<a)$ ; это следствие иррефлексивности и транзитивности.

[worrell-11] Jump up to: ^а ^б Уоррелл, Джеймс (2016), «Разрешимые теории» (PDF) , «Логика и доказательство» (конспекты лекций), Оксфордский университет ; Уоррелл использует другую, но эквивалентную аксиоматизацию для строгих линейных порядков и объединяет две аксиомы неограниченности в одну аксиому.

[bd-12] Бючи, Дж. Ричард ; Данхоф, Кеннет Дж. (1973), «Вариации на тему Кантора в теории реляционных структур», Journal of Mathematical Logic and Foundations of Mathematics , 19 (26–29): 411–426, doi : 10.1002/malq. 19730192604 , МР 0337567

[morley-13] Морли, Майкл (1965), «Категоричность в степени», Труды Американского математического общества , 114 (2): 514–538, doi : 10.2307/1994188 , JSTOR 1994188 , MR 0175782

[jech-14] Йех, Томас (2003), Теория множеств , Монографии Спрингера по математике (изд. 3-го тысячелетия), Берлин: Springer-Verlag, Теорема 4.3, стр. 38, номер домена : 10.1007/3-540-44761-X , ISBN 3-540-44085-2 , МР 1940513

[dj-15] Девлин, Кейт Дж .; Джонсбротен, Ховард (1974), Проблема Суслина , Конспект лекций по математике, том. 405, Берлин и Нью-Йорк: Springer-Verlag, MR 0384542.

[langford-16] Лэнгфорд, CH (1926–1927), «Некоторые теоремы о выводимости», Annals of Mathematics , Second Series, 28 (1–4): 16–40, doi : 10.2307/1968352 , JSTOR 1968352 , MR 1502760

[sierpinski-17] Серпинский, Вацлав (1932), «Обобщение теоремы Кантора о счетных упорядоченных множествах», Fundamenta Mathematicae (на французском языке), 18 : 280–284, doi : 10.4064/fm-18-1-280-284 , Zbl 0004.20502

[baumgartner-18] Баумгартнер, Джеймс Э. (1973), «Все $\aleph _{1}$ -плотные множества действительных чисел могут быть изоморфными», Fundamenta Mathematicae , 79 (2): 101–106, doi : 10.4064/fm-79-2-101-106 , MR 0317934

[as-19] Авраам, Ури; Шела, Сахарон (1981): «Аксиома Мартина не означает, что каждые два $\aleph _{1}$ -плотные множества действительных чисел изоморфны», Israel Journal of Mathematics , 38 (1–2): 161–176, doi : 10.1007/BF02761858 , MR 0599485

[vanben-20] ван Бентем, Йохан (1984), «Напряженная логика и время», Журнал формальной логики Нотр-Дам , 25 (1): 1–16, doi : 10.1305/ndjfl/1093870515 , MR 0723616

[ladkin-21] Ладкин, Питер Б. (1987), «Модели аксиом для временных интервалов» , в Форбусе, Кеннет Д.; Шроб, Ховард Э. (ред.), Материалы 6-й Национальной конференции по искусственному интеллекту. Сиэтл, Вашингтон, США, июль 1987 г. , Морган Кауфманн, стр. 234–239.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice