Общий заказ

Порядок, все элементы которого сравнимы

В математике полный порядок или линейный порядок — это частичный порядок , в котором любые два элемента сравнимы. То есть полный порядок — это бинарное отношение на некотором множестве , которое удовлетворяет следующим условиям для всех и в : ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle a,b}$ ${\displaystyle c}$ ${\displaystyle X}$

1. ${\displaystyle a\leq a}$( рефлексивный ).
2. Если и то ( транзитив ). ${\displaystyle a\leq b}$ ${\displaystyle b\leq c}$ ${\displaystyle a\leq c}$
3. Если и то ( антисимметрично ). ${\displaystyle a\leq b}$ ${\displaystyle b\leq a}$ ${\displaystyle a=b}$
4. ${\displaystyle a\leq b}$или ( сильно связанный , ранее назывался тотальным). ${\displaystyle b\leq a}$

Рефлексивность (1.) уже следует из связности (4.), но тем не менее явно требуется многими авторами для указания родства с частичными порядками. ^[1] Полные порядки иногда также называют простыми , ^[2] связными , ^[3] или полными порядками . ^[4]

Множество, снабженное полным порядком, является полностью упорядоченным множеством ; ^[5] также используются термины просто упорядоченное множество , ^[2] линейно упорядоченное множество , ^{[3] [5]} и loset ^{[6] [7] . Термин} chain иногда определяется как синоним полностью упорядоченного множества , ^[5], но обычно относится к некоторому виду полностью упорядоченных подмножеств данного частично упорядоченного множества.

Расширение данного частичного порядка до полного порядка называется линейным расширением этого частичного порядка.

Строгие и нестрогие общие заказы

Строгий полный порядок на множестве — это строгий частичный порядок на , в котором любые два различных элемента сравнимы. То есть, строгий полный порядок — это бинарное отношение на некотором множестве , которое удовлетворяет следующим условиям для всех и в : ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle <}$ ${\displaystyle X}$ ${\displaystyle a,b}$ ${\displaystyle c}$ ${\displaystyle X}$

1. Нет ( нерефлексивно ). ${\displaystyle a<a}$
2. Если нет, то ( асимметрично ). ${\displaystyle a<b}$ ${\displaystyle b<a}$
3. Если и то ( транзитив ). ${\displaystyle a<b}$ ${\displaystyle b<c}$ ${\displaystyle a<c}$
4. Если , то или ( связано ). ${\displaystyle a\neq b}$ ${\displaystyle a<b}$ ${\displaystyle b<a}$

Асимметрия следует из транзитивности и нерефлексивности; ^[8] более того, нерефлексивность следует из асимметрии. ^[9]

Для целей разграничения полный порядок, как определено выше, иногда называют нестрогим порядком. Для каждого (нестрогого) полного порядка существует связанное отношение , называемое строгим полным порядком, связанным с которым, которое может быть определено двумя эквивалентными способами: ${\displaystyle \leq }$ ${\displaystyle <}$ ${\displaystyle \leq }$

• ${\displaystyle a<b}$если и ( рефлексивная редукция ). ${\displaystyle a\leq b}$ ${\displaystyle a\neq b}$
• ${\displaystyle a<b}$если нет (т.е. является дополнением обратного к ) . ${\displaystyle b\leq a}$ ${\displaystyle <}$ ${\displaystyle \leq }$

Наоборот, рефлексивное замыкание строгого тотального порядка является (нестрогим) тотальным порядком. ${\displaystyle <}$

Примеры

• Любое подмножество полностью упорядоченного множества X полностью упорядочено относительно ограничения порядка на X.
• Уникальный порядок на пустом множестве ∅ является полным порядком.
• Любой набор количественных или порядковых чисел (точнее, это порядки ).
• Если X — любое множество и fинъективная функция из X в полностью упорядоченное множество, то f индуцирует полный порядок на X , устанавливая x ₁ ≤ x ₂ тогда и только тогда, когда f ( x ₁ ) ≤ f ( x ₂ ) .
• Лексикографический порядок декартова произведения семейства полностью упорядоченных множеств, индексированного вполне упорядоченным множеством , сам по себе является полным порядком.
• Множество действительных чисел, упорядоченное обычными отношениями «меньше или равно» (≤) или «больше или равно» (≥), полностью упорядочено. Следовательно, каждое подмножество действительных чисел полностью упорядочено, например, натуральные числа , целые числа и рациональные числа . Можно показать, что каждое из них является уникальным (с точностью до изоморфизма порядка ) «начальным примером» полностью упорядоченного множества с определенным свойством (здесь полный порядок A является начальным для свойства, если всякий раз, когда B обладает этим свойством, существует изоморфизм порядка из A в подмножество B ): ^{[10] [ необходима цитата ]}
  • Натуральные числа образуют исходное непустое полностью упорядоченное множество без верхней границы .
  • Целые числа образуют исходный непустой полностью упорядоченный набор, не имеющий ни верхней, ни нижней границы .
  • Рациональные числа образуют начальный полностью упорядоченный набор, который плотен в действительных числах. Более того, рефлексивная редукция < является плотным порядком на рациональных числах.
  • Действительные числа образуют исходный неограниченный полностью упорядоченный набор, который связан в топологии порядка (определенной ниже).
• Упорядоченные поля полностью упорядочены по определению. Они включают рациональные числа и действительные числа. Каждое упорядоченное поле содержит упорядоченное подполе, которое изоморфно рациональным числам. Любое дедекиндово-полное упорядоченное поле изоморфно действительным числам.
• Буквы алфавита, упорядоченные в стандартном словарном порядке , например, A < B < C и т. д., представляют собой строгий общий порядок.

Цепи

Термин «цепь» иногда определяется как синоним полностью упорядоченного множества, но обычно он используется для обозначения подмножества частично упорядоченного множества , которое полностью упорядочено для индуцированного порядка. ^{[1] [11]} Обычно частично упорядоченное множество представляет собой множество подмножеств данного множества, которое упорядочено включением, и этот термин используется для указания свойств множества цепей. Такое большое количество вложенных уровней множеств объясняет полезность термина.

Распространенным примером использования цепочки для ссылки на полностью упорядоченные подмножества является лемма Цорна , которая утверждает, что если каждая цепочка в частично упорядоченном множестве X имеет верхнюю границу в X , то X содержит по крайней мере один максимальный элемент. ^[12] Лемма Цорна обычно используется для X , являющегося множеством подмножеств; в этом случае верхняя граница получается путем доказательства того, что объединение элементов цепочки в X принадлежит X. Этот способ обычно используется для доказательства того, что векторное пространство имеет базисы Гамеля , а кольцо имеет максимальные идеалы .

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

Частично упорядоченное множество имеет условие нисходящей цепи , если каждая нисходящая цепь в конечном итоге стабилизируется. ^[14] Например, порядок хорошо обоснован, если он имеет условие нисходящей цепи. Аналогично, условие восходящей цепи означает, что каждая восходящая цепь в конечном итоге стабилизируется. Например, нётерово кольцо — это кольцо, идеалы которого удовлетворяют условию восходящей цепи.

В других контекстах рассматриваются только цепи, которые являются конечными множествами . В этом случае говорят о конечной цепи , часто сокращенно называемой цепью . В этом случае длина цепи — это число неравенств (или включений множеств) между последовательными элементами цепи; то есть число элементов в цепи минус один. ^[15] Таким образом , одноэлементное множество — это цепь нулевой длины, а упорядоченная пара — это цепь длины один. Размерность пространства часто определяется или характеризуется как максимальная длина цепей подпространств. Например, размерность векторного пространства — это максимальная длина цепей линейных подпространств , а размерность Крулля коммутативного кольца — это максимальная длина цепей простых идеалов .

«Цепь» может также использоваться для некоторых полностью упорядоченных подмножеств структур , которые не являются частично упорядоченными множествами. Примером служат регулярные цепочки многочленов. Другим примером является использование «цепи» в качестве синонима для прогулки по графу .

Дальнейшие концепции

Теория решеток

Полностью упорядоченное множество можно определить как особый вид решетки , а именно, такую, в которой мы имеем

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$для всех а , б .

Тогда мы пишем a ≤ b тогда и только тогда, когда . Следовательно, полностью упорядоченное множество является дистрибутивной решеткой . ${\displaystyle a=a\wedge b}$

Конечные общие заказы

Простой подсчет аргументов проверит, что любое непустое конечное полностью упорядоченное множество (и, следовательно, любое непустое его подмножество) имеет наименьший элемент. Таким образом, каждый конечный полный порядок на самом деле является вполне порядком . Либо прямым доказательством, либо наблюдением того, что каждый вполне порядок является порядком, изоморфным ординалу , можно показать, что каждый конечный полный порядок является порядком, изоморфным начальному сегменту натуральных чисел, упорядоченных с помощью <. Другими словами, полный порядок на множестве с k элементами индуцирует биекцию с первыми k натуральными числами. Следовательно, конечные полные порядки или вполне порядки с типом порядка ω обычно индексируют натуральными числами таким образом, чтобы соблюдался порядок (начиная с нуля или с единицы).

Теория категорий

Полностью упорядоченные множества образуют полную подкатегорию категории частично упорядоченных множеств , причем морфизмы являются отображениями, которые соблюдают порядки, т.е. отображениями f такими, что если a ≤ b , то f ( a ) ≤ f ( b ).

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

Топология заказа

Для любого полностью упорядоченного множества X мы можем определить открытые интервалы

• ( а , б ) = { х | а < х и х < б } ,
• (−∞, b ) = { x | x < b } ,
• ( а , ∞) = { х | а < х } , и
• (−∞, ∞) = X .

Мы можем использовать эти открытые интервалы для определения топологии на любом упорядоченном множестве, топологии порядка .

Когда на множестве используется более одного порядка, говорят о топологии порядка, индуцированной определенным порядком. Например, если N — это натуральные числа, < меньше и > больше, мы могли бы ссылаться на топологию порядка на N, индуцированную < , и топологию порядка на N, индуцированную > (в этом случае они оказываются идентичными, но в общем случае — нет).

Можно показать, что топология порядка, индуцированная полным порядком, является наследственно нормальной .

Полнота

Полностью упорядоченное множество называется полным, если каждое непустое подмножество, имеющее верхнюю границу , имеет наименьшую верхнюю границу . Например, множество действительных чисел R является полным, а множество рациональных чисел Q — нет. Другими словами, различные концепции полноты (не путать с «полным») не переносятся на ограничения . Например, над действительными числами свойство отношения ≤ состоит в том, что каждое непустое подмножество S из R с верхней границей в R имеет наименьшую верхнюю границу (также называемую супремумом) в R. Однако для рациональных чисел этот супремум не обязательно является рациональным, поэтому то же свойство не выполняется при ограничении отношения ≤ на рациональные числа.

Имеется ряд результатов, связывающих свойства топологии порядка с полнотой X:

• Если топология порядка на X связна, то X является полным.
• X связно в топологии порядка тогда и только тогда, когда оно полно и в X нет разрыва (разрыв — это две точки a и b в X , где a < b, такие, что ни одно c не удовлетворяет a < c < b ).
• X полно тогда и только тогда, когда каждое ограниченное множество, замкнутое в топологии порядка, компактно.

Полностью упорядоченное множество (с его топологией порядка), которое является полной решеткой, является компактным . Примерами являются замкнутые интервалы действительных чисел, например единичный интервал [0,1], и аффинно расширенная система действительных чисел (расширенная прямая действительных чисел). Между этими примерами существуют гомеоморфизмы , сохраняющие порядок .

Суммы заказов

Для любых двух непересекающихся полных порядков и существует естественный порядок на множестве , который называется суммой двух порядков или иногда просто : ${\displaystyle (A_{1},\leq _{1})}$ ${\displaystyle (A_{2},\leq _{2})}$ ${\displaystyle \leq _{+}}$ ${\displaystyle A_{1}\cup A_{2}}$ ${\displaystyle A_{1}+A_{2}}$

Для выполняется тогда и только тогда , когда выполняется одно из следующих условий: ${\displaystyle x,y\in A_{1}\cup A_{2}}$ ${\displaystyle x\leq _{+}y}$

1. ${\displaystyle x,y\in A_{1}}$и ${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$и ${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$и ${\displaystyle y\in A_{2}}$

Интуитивно это означает, что элементы второго набора добавляются поверх элементов первого набора.

В более общем случае, если — полностью упорядоченный набор индексов, и для каждого из них структура является линейным порядком, где наборы попарно не пересекаются, то естественный полный порядок на определяется как ${\displaystyle (I,\leq )}$ ${\displaystyle i\in I}$ ${\displaystyle (A_{i},\leq _{i})}$ ${\displaystyle A_{i}}$ ${\displaystyle \bigcup _{i}A_{i}}$

Для справедливо , если: ${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$ ${\displaystyle x\leq y}$

1. Либо есть некоторые с ${\displaystyle i\in I}$ ${\displaystyle x\leq _{i}y}$
2. или есть некоторые в с , ${\displaystyle i<j}$ ${\displaystyle I}$ ${\displaystyle x\in A_{i}}$ ${\displaystyle y\in A_{j}}$

Разрешимость

Теория первого порядка полных порядков разрешима , т.е. существует алгоритм для определения того, какие утверждения первого порядка справедливы для всех полных порядков. Используя интерпретируемость в S2S , монадическая теория второго порядка счетных полных порядков также разрешима. ^[16]

Порядки декартового произведения полностью упорядоченных множеств

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

• Лексикографический порядок : ( a , b ) ≤ ( c , d ) тогда и только тогда, когда a < c или ( a = c и b ≤ d ). Это полный порядок.
• ( a , b ) ≤ ( c , d ) тогда и только тогда, когда a ≤ c и b ≤ d ( порядок произведения ). Это частичный порядок.
• ( a , b ) ≤ ( c , d ) тогда и только тогда, когда ( a < c и b < d ) или ( a = c и b = d ) (рефлексивное замыкание прямого произведения соответствующих строгих тотальных порядков). Это также частичный порядок.

Каждый из этих порядков расширяет следующий в том смысле, что если в порядке произведения x ≤ y , то это отношение сохраняется и в лексикографическом порядке и т. д. Все три могут быть аналогичным образом определены для декартова произведения более чем двух множеств.

Применительно к векторному пространству R ⁿ каждое из этих утверждений делает его упорядоченным векторным пространством .

См. также примеры частично упорядоченных множеств .

Действительная функция n действительных переменных, определенная на подмножестве R ^{n ,} определяет строгий слабый порядок и соответствующий полный предварительный порядок на этом подмножестве.

Связанные структуры

Бинарное отношение, которое является антисимметричным, транзитивным и рефлексивным (но не обязательно полным), является частичным порядком .

Группа с совместимым полным порядком является полностью упорядоченной группой .

Существует лишь несколько нетривиальных структур, которые являются (взаимоопределяемыми как) редуктами общего порядка. Забывание ориентации приводит к отношению промежуточности . Забывание расположения концов приводит к циклическому порядку . Забывание обоих данных приводит к отношению разделения . ^[17]

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

• Артиново кольцо  – кольцо, удовлетворяющее условию убывания цепочек на идеалахPages displaying wikidata descriptions as a fallback
• Линия Countryman
• Теория порядка  – Раздел математики
• Перестановка  – Математическая версия изменения порядка.
• Префиксный порядок  – обобщение понятия префикса строки и понятия дерева Pages displaying wikidata descriptions as a fallback– нисходящий полный частичный порядок
• Проблема Суслина  – предложение, независимое от ZFC, о том, что непустой неограниченный полный плотный тотальный порядок, удовлетворяющий условию счетной цепи, изоморфен действительным числамPages displaying wikidata descriptions as a fallback
• Вполне упорядоченный  – класс математических упорядочений

Примечания

1. Halmos 1968, гл.14.
2. Birkhoff 1967, стр. 2.
3. Schmidt & Ströhlein 1993, стр. 32.
4. Фукс 1963, стр. 2.
5. Дэви и Пристли 1990, стр. 3.
6. Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1 августа 1990 г.). «Упорядочение символов и строк». ACM SIGAda Ada Letters (7): 84. doi : 10.1145/101120.101136 . S2CID  38115497.
7. Ганапати, Джаянти (1992). «Максимальные элементы и верхние границы в частично упорядоченных множествах». Pi Mu Epsilon Journal . 9 (7): 462–464. ISSN  0031-952X. JSTOR  24340068.
8. Пусть , предположим от противного, что также . Тогда по транзитивности, что противоречит нерефлексивности. ${\displaystyle a<b}$ ${\displaystyle b<a}$ ${\displaystyle a<a}$
9. Если , то нет по асимметрии. ${\displaystyle a<a}$ ${\displaystyle a<a}$
10. Это определение напоминает определение начального объекта категории , но оно слабее.
11. Ролан Фрессе (декабрь 2000 г.). Теория отношений. Исследования по логике и основаниям математики. Т. 145 (1-е изд.). Elsevier. ISBN 978-0-444-50542-2.Здесь: стр. 35
12. Брайан А. Дэйви и Хилари Энн Пристли (1990). Введение в решетки и порядок . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN  89009753.Здесь: стр. 100
13. Яннис Н. Мошовакис (2006) Заметки о теории множеств , Бакалаврские тексты по математике (Birkhäuser) ISBN 0-387-28723-X , стр. 116 
14. то есть, за пределами некоторого индекса все дальнейшие члены последовательности равны
15. Дэйви и Пристли 1990, Def.2.24, стр. 37
16. Weyer, Mark (2002). «Разрешимость S1S и S2S». Автоматы, логика и бесконечные игры . Конспект лекций по информатике. Том 2500. Springer. С. 207–230. doi :10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
17. Макферсон, Х. Дугалд (2011), «Обзор однородных структур», Дискретная математика , 311 (15): 1599–1634, doi : 10.1016/j.disc.2011.01.024

Ссылки

• Биркгофф, Гарретт (1967). Теория решеток . Colloquium Publications. Том 25. Провиденс: Am. Math. Soc.
• Дэви, Брайан А.; Пристли, Хилари Энн (1990). Введение в решетки и порядок . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN  89009753.
• Фукс, Л. (1963). Частично упорядоченные алгебраические системы . Pergamon Press.
• Джордж Гретцер (1971). Теория решеток: первые концепции и распределительные решетки. WH Freeman and Co. ISBN 0-7167-0442-0 
• Халмош, Пол Р. (1968). Наивная теория множеств . Принстон: Nostrand.
• Джон Г. Хокинг и Гейл С. Янг (1961). Топология. Исправленное переиздание, Дувр, 1988. ISBN 0-486-65676-4 
• Розенштейн, Джозеф Г. (1982). Линейные упорядочения . Нью-Йорк: Academic Press.
• Шмидт, Гюнтер ; Штрёляйн, Томас (1993). Отношения и графы: Дискретная математика для компьютерных ученых. Берлин: Springer-Verlag. ISBN 978-3-642-77970-1.

Внешние ссылки

• «Полностью упорядоченное множество», Энциклопедия математики , EMS Press , 2001 [1994]