Общий заказ

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

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

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

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

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

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

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

Нет ( нерфлексивно ). $а<а$
Если нет, то нет ( асимметричный ). $а<b$ $b<a$
Если и то ( транзитивно ). $а<b$ $b<c$ $а<c$
Если , то или ( связно ). $а\neq b$ $а<b$ $b<a$

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

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

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

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

Примеры

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

Цепи

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

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

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

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

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

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

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

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

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

\{a\vee b,a\wedge b\} = \{a,b\}

для всех а , б .

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

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

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

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

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

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

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

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

$(а, б) знак равно {Икс | а < х и х < б}$ ,
$(-\infty, б) знак равно {Икс | х < б}$ ,
$(а, \infty) знак равно {Икс | a < x}$ и
$(-\infty, \infty) знак равно Икс$ .

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

Когда в наборе используется более одного порядка, говорят о топологии порядка, вызванной конкретным порядком. Например, если 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}\чашка A_{2}$ $A_{1}+A_{2}$

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

x,y\in A_{1}\cup A_{2}

x\leq _ {+}y

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

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

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

Для выполняется , если:

x,y\in \bigcup _ {i\in I}A_ {i}

x\leq y

Либо есть что-то с $я\в I$ $x\leq _ {i}y$
или есть такие , $я<j$ $I$ $x\in A_{i}$ $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 ) (рефлексивное замыкание прямого произведения соответствующих строгих полных порядков). Это тоже частичный заказ.

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

Применительно к векторному пространству Rn каждый из них делает его ^{упорядоченным} векторным пространством .

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

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

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

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

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

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

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

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

Примечания

^ ab Halmos 1968, Глава 14.
^ аб Биркгоф 1967, с. 2.
^ ab Schmidt & Ströhlein 1993, с. 32.
^ Фукс 1963, с. 2.
^ abc Дэйви и Пристли 1990, с. 3.
^ Штромайер, Альфред; Дженийяр, Кристиан; Вебер, Матс (1 августа 1990 г.). «Упорядочение символов и строк». ACM SIGAda Ada Letters (7): 84. doi : 10.1145/101120.101136 . S2CID 38115497.
^ Ганапати, Джаянти (1992). «Максимальные элементы и верхние границы в частично упорядоченных множествах». Журнал Пи Му Эпсилон . 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.
^ Пусть , от противного , что тоже . Затем транзитивностью, которая противоречит иррефлексивности. $a<b$ $b<a$ $a<a$
^ Если , то не по асимметрии. $a<a$ $a<a$
^ Это определение похоже на определение исходного объекта категории , но оно более слабое.
^ Ролан Фрейссе (декабрь 2000 г.). Теория отношений. Исследования по логике и основам математики. Том. 145 (1-е изд.). Эльзевир. ISBN 978-0-444-50542-2.Здесь: с. 35
^ Брайан А. Дэйви и Хилари Энн Пристли (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета. ISBN 0-521-36766-2. LCCN 89009753.Здесь: с. 100
^ Яннис Н. Мошовакис (2006) Заметки по теории множеств , Тексты для студентов по математике (Birkhäuser) ISBN 0-387-28723-X , стр. 116
^ то есть после некоторого индекса все дальнейшие члены последовательности равны
^ Дэйви и Пристли 1990, Def.2.24, с. 37
^ Вейер, Марк (2002). «Разрешимость S1S и S2S». Автоматы, логика и бесконечные игры . Конспекты лекций по информатике. Том. 2500. Спрингер. стр. 207–230. дои : 10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
^ Макферсон, Х. Дугалд (2011), «Обзор однородных структур», Discrete Mathematics , 311 (15): 1599–1634, doi : 10.1016/j.disc.2011.01.024

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

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