Общий заказ

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Февраль 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике , в общем порядке , простой порядка , ^[1] линейный порядка , Connex порядка , ^[2] или полный порядок ^[3] является бинарным отношением на некотором множестве , которое является антисимметричным , переходным , и Connex связи . Набор в паре с общим порядка называется цепью , ^[4] упорядоченное множество , ^[4] просто упорядоченное множество , ^[1] линейно упорядоченное множество ,${\ displaystyle X}$^{[2] [4]} или проигрыш . ^{[5] [6]}

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

Антисимметрия : если и тогда ;${\ displaystyle a \ leq b}$${\ displaystyle b \ leq a}$${\ displaystyle a = b}$

Транзитивность : если и тогда ;${\ displaystyle a \ leq b}$${\ displaystyle b \ leq c}$${\ displaystyle a \ leq c}$

Связь : или .${\ displaystyle a \ leq b}$${\ displaystyle b \ leq a}$

Антисимметрия исключает неопределенные случаи, когда и предшествует, и предшествует . ^{[7] : 325} Отношение, обладающее свойством Connex, означает, что любая пара элементов в наборе отношения сравнима по отношению. Это также означает, что набор можно изобразить как линию элементов, дав ему название линейный . ^{[7] : 330} Connex свойство также предполагает рефлексивность , т.е. ≤ . Следовательно, полный порядок также является (частным случаем) частичным порядком.${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle a}$, поскольку для частичного порядка свойство связности заменяется свойством более слабой рефлексивности. Расширение данного частичного порядка до полного порядка называется линейным расширением этого частичного порядка.

Строгий общий порядок [ править ]

Для каждого (нестрогого) общего порядка ≤ есть связанный асимметричный (отсюда иррефлексивный ) транзитивно semiconnex отношение <, называется строго общий порядком или строгий semiconnex порядка , ^[2] , который может быть определены два эквивалентными способами:

• a < b, если a ≤ b и a ≠ b
• a < b, если не b ≤ a (т. е. <является обратным к дополнению ≤)

Характеристики:

• Отношение транзитивно: a < b и b < c влечет a < c .
• Отношение трихотомическое : верно ровно одно из a < b , b < a и a = b .
• Отношение является строгим слабым порядком , где соответствующая эквивалентность - равенство.

Мы можем пойти другим путем и начать с выбора <в качестве транзитивного трихотомического бинарного отношения; тогда общий порядок ≤ может быть определен двумя эквивалентными способами:

• a ≤ b, если a < b или a = b
• a ≤ b, если не b < a

Еще два связанных порядка - это дополнения ≥ и>, завершающие четверку {<,>, ≤, ≥}.

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

Примеры [ править ]

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

Цепи [ править ]

• Термин « цепочка» является синонимом полностью упорядоченного множества, в частности, термин часто используется для обозначения полностью упорядоченного подмножества некоторого частично упорядоченного множества , например, в лемме Цорна . ^[9]
• Возрастающая цепочка является полностью упорядоченный набор , имеющий (единственный) минимальный элемент, в то время как нисходящая цепь является полностью упорядоченный набор , имеющий (единственный) максимальный элемент. ^{[ необходима цитата ]}
• Учитывая множество S с частичным порядком ≤, бесконечная убывающая цепочка является бесконечным , строго убывающая последовательность элементов х ₁ > х ₂ > ... . ^[10] В качестве примера, в множестве целых чисел , то цепь -1, -2, -3, ... бесконечная убывающая цепочка, но не существует бесконечной убывающая цепи на натуральных числах , так как каждый цепь природного числа имеет минимальный элемент. Если частично упорядоченный набор не имеет бесконечных нисходящих цепочек, говорят, что он удовлетворяет условию нисходящей цепочки. Предполагая аксиому выбора , условие нисходящей цепочки на частично упорядоченном множестве эквивалентно требованию, чтобы соответствующий строгий порядок был хорошо обоснован . Более сильное условие, что не должно быть бесконечных нисходящих цепей и бесконечных антицепей , определяет хорошо квазиупорядочения . Полностью упорядоченное множество без бесконечных убывающих цепочек называется хорошо упорядоченным .
• См. Также условие восходящей цепи для этого понятия.

Высота от посета обозначает мощность его крупнейшей сети в этом смысле. ^{[ необходима цитата ]}

Например, рассмотрим набор всех подмножеств целых чисел, частично упорядоченных по включению . Тогда набор { I _n  : n - натуральное число}, где I _n - множество натуральных чисел ниже n , является цепочкой в ​​этом порядке, поскольку он полностью упорядочен по включению: если n ≤ k , то I _n равно подмножество I _k .

Дальнейшие концепции [ править ]

Теория решеток [ править ]

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

${\ Displaystyle \ {а \ ви б, а \ клин б \} = \ {а, б \}}$для всех а , б .

Затем мы пишем a ≤ b тогда и только тогда, когда . Следовательно, вполне упорядоченное множество - это дистрибутивная решетка .${\ Displaystyle а = а \ клин б}$

Конечная сумма заказов [ править ]

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

Теория категорий [ править ]

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

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

Топология заказа [ править ]

Для любого полностью упорядоченного множества X мы можем определить открытые интервалы ( a , b ) = { x  : a < x и x < b }, (−∞, b ) = { x  : x < b }, ( a , ∞) = { х  : < х } и (-∞, ∞) = х . Мы можем использовать эти открытые интервалы для определения топологии на любом упорядоченном множестве, топологии порядка .

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

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

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

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

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

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

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

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

Связанные структуры [ править ]

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

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

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

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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