Введение

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

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

(рефлексивность). Если , то (транзитивность). Если , то (антисимметричность). или (строго упорядоченные, ранее называемые полными). Рефлексивность (1) уже следует из свойства строго упорядоченности (4), но многие авторы всё же требуют её явного указания, чтобы подчеркнуть связь с частичными порядками. Полные порядки иногда также называют простыми, связными или полными. Множество, снабжённое полным порядком, называется полностью упорядоченным множеством; также используются термины просто упорядоченное множество, линейно упорядоченное множество и loset. Термин "цепочка" иногда определяется как синоним полностью упорядоченного множества, но чаще относится к некоторым видам полностью упорядоченных подмножеств данного частично упорядоченного множества. Расширение данного частичного порядка до полного порядка называется линейным расширением этого частичного порядка.

Примеры

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

Цепи

Термин «цепь» иногда определяется как синоним полностью упорядоченного множества, но обычно используется для обозначения подмножества частично упорядоченного множества, которое полностью упорядочено относительно индуцированного порядка. Чаще всего, частично упорядоченное множество представляет собой множество подмножеств данного множества, упорядоченное по включению, и этот термин используется для формулировки свойств множества цепей. Такое большое количество вложенных уровней множеств объясняет полезность этого термина. Распространенным примером использования термина «цепь» для обозначения полностью упорядоченных подмножеств является лемма Зорна, которая утверждает, что если каждая цепь в частично упорядоченном множестве X имеет верхнюю грань в X, то X содержит по крайней мере один максимальный элемент. Лемма Зорна часто используется, когда X является множеством подмножеств; в этом случае верхняя грань получается путем доказательства того, что объединение элементов цепи в X принадлежит X. Этот подход обычно используется для доказательства того, что векторное пространство имеет базис Гамеля, а кольцо — максимальные идеалы. В некоторых контекстах рассматриваемые цепи изоморфны натуральным числам с их обычным порядком или обратным порядком. В этом случае цепь можно отождествить с монотонной последовательностью, которая называется возрастающей цепью или убывающей цепью, в зависимости от того, является ли последовательность возрастающей или убывающей. Частично упорядоченное множество удовлетворяет условию убывающей цепи, если каждая убывающая цепь в конечном итоге стабилизируется. Например, порядок называется хорошо обоснованным, если он удовлетворяет условию убывающей цепи. Аналогично, условие возрастающей цепи означает, что каждая возрастающая цепь в конечном итоге стабилизируется. Например, ноетерианское кольцо — это кольцо, идеалы которого удовлетворяют условию возрастающей цепи. В других контекстах рассматриваются только конечные цепи. В этом случае говорят о конечной цепи, которую часто сокращают до просто «цепь». В этом случае длина цепи — это количество неравенств (или включений множеств) между последовательными элементами цепи, то есть число элементов в цепи минус один. Таким образом, одноэлементное множество является цепью длины ноль, а упорядоченная пара — цепью длины один. Размерность пространства часто определяется или характеризуется как максимальная длина цепей подпространств. Например, размерность векторного пространства — это максимальная длина цепей линейных подпространств, а размерность Крулла коммутативного кольца — это максимальная длина цепей простых идеалов. Термин «цепь» также может использоваться для некоторых полностью упорядоченных подмножеств структур, которые не являются частично упорядоченными множествами. Примером служат регулярные цепи многочленов. Другой пример — использование термина «цепь» как синонима пути в графе.

Ограниченный общий объем заказов

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

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

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

Решаемость

Теория первого порядка полных порядков является разрешимой, то есть существует алгоритм для определения истинности утверждений первого порядка для всех полных порядков. Используя интерпретируемость в 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 в порядке произведения, то это отношение также выполняется в лексикографическом порядке, и так далее. Все три порядка могут быть аналогично определены для декартова произведения более чем двух множеств. При применении к векторному пространству Rn каждый из них делает его упорядоченным векторным пространством. См. также примеры частично упорядоченных множеств. Действительная функция n действительных переменных, определенная на подмножестве Rn, определяет строгий слабый порядок и соответствующий полный предзаказ на этом подмножестве.

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

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