Общий заказ

«Линейный порядок» перенаправляется сюда. Не путать с Линейным порядком (лингвистика) .

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

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

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

Множество, обладающее полным порядком, есть полностью упорядоченное множество ; Условия просто заказаны , линейно упорядоченное множество , и потерять также используются. Термин « цепочка» иногда определяется как синоним полностью упорядоченного множества . но обычно относится к своего рода полностью упорядоченным подмножествам данного частично упорядоченного множества.

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

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

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

1. Нет $a<a$ ( необдуманно ).
2. Если $a<b$ тогда нет $b<a$ ( асимметричный ).
3. Если $a<b$ и $b<c$ затем $a<c$ ( переходный ).
4. Если $a\neq b$, затем $a<b$ или $b<a$ ( связанный ).

Асимметрия вытекает из транзитивности и иррефлексивности; более того, иррефлексивность вытекает из асимметрии.

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

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

И наоборот, рефлексивное закрытие строгого тотального порядка $<$ представляет собой (нестрогий) тотальный порядок.

Примеры

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

Цепи

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

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

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

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

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

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

концепции

Теория

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

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

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

Конечный общий объем заказов

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

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

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

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

Заказать топологию

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

• ( а , б ) знак равно { Икс | а < х и х < б } ,
• (−∞, б ) знак равно { Икс | х < б } ,
• ( а , ∞) знак равно { Икс | a < 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] и аффинно расширенная система действительных чисел (расширенная линия действительных чисел). существуют сохраняющие порядок гомеоморфизмы Между этими примерами .

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

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

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

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

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

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

Для $x,y\in \bigcup _{i\in I}A_{i}$, $x\leq y$ имеет место, если:

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

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

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

на декартово произведение полностью

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

• Лексикографический порядок : ( 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 ^н определяет строгий слабый порядок и соответствующий полный предварительный порядок в этом подмножестве.

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

показывать Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

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

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

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

См. также

• Артиново кольцо - кольцо, которое удовлетворяет условию нисходящей цепи на идеалах. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Линия Countryman
• Теория порядка – Отделение математики
• Перестановка - математическая версия изменения порядка.
• Порядок префиксов – обобщение понятия префикса строки и понятия дерева. Страницы, отображающие описания викиданных в качестве запасного варианта – общий частичный порядок вниз.
• Проблема Суслина - независимое от ZFC утверждение о том, что непустой неограниченный полный плотный полный порядок, удовлетворяющий условию счетной цепи, изоморфен реальным страницам, отображающим описания викиданных в качестве запасного варианта.
• Ну-порядок - класс математических порядков.

Ссылки

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

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

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