Бинарные отношения | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
« ✓ » указывает, что свойство столбца требуется в определении строки. Например, определение отношения эквивалентности требует, чтобы оно было симметричным. Все определения молчаливо требуют транзитивности и рефлексивности . |
В математике , А общая или линейный порядок является частичным порядком , в котором любые два элемента сравнимы. То есть общий порядок - это бинарное отношение на каком-то наборе , которая удовлетворяет следующему для всех а также в :
- ( возвратный ).
- Если а также тогда ( переходный )
- Если а также тогда ( антисимметричный )
- или же ( сильно связанный , ранее назывался тотальным).
Всего заказы иногда также называют простым , [1] CONNEX , [2] или полными заказами . [3]
Комплект с полным заказом - это полностью заказанный комплект ; [4] также используются термины просто упорядоченное множество , [1] линейно упорядоченное множество , [2] [4] и loset [5] [6] . Термин цепь иногда определяется как синоним полностью упорядоченного множества , [4] , но как правило , относится к какой - то вполне упорядоченных подмножеств данного частично упорядоченного множества.
Расширение данного частичного порядка до полного порядка называется линейным расширением этого частичного порядка.
Строгие и нестрогие итоговые заказы
Строгий порядок общего на множествеэто строгий частичный приказ ов котором любые два элемента сопоставимы. То есть общий порядок - это бинарное отношение на каком-то наборе , которая удовлетворяет следующему для всех а также в :
- Нет ( невозмутимо ).
- Если а также тогда ( переходный ).
- Если , тогда или же ( подключен ).
За каждый (нестрогий) общий заказ есть связанное отношение , называемый строгим полным порядком, связанным с который можно определить двумя эквивалентными способами:
- если а также ( рефлексивная редукция ).
- если не (т.е. является дополнением в обратном из).
И наоборот, рефлексивное замыкание строгого тотального порядка является (нестрогим) полным порядком.
Примеры
- Любое подмножество из полностью упорядоченного множества X вполне упорядочено для ограничения порядка на X .
- Единственный порядок на пустом множестве ∅ - это полный порядок.
- Любой набор кардинальных чисел или порядковых чисел (более сильно, это также заказы ).
- Если X - произвольное множество и fинъективна функция от X к полностью упорядоченному множеству то ф индуцирует полное упорядочение на X с помощью параметра х 1 ≤ х 2 , если и только если ф ( х 1 ) ≤ F ( х 2 ) .
- Лексикографический порядок на декартово произведении семейства вполне упорядоченные множества, индексируется с помощью упорядоченного множества , сам по себе является общим порядком.
- Множество действительных чисел, упорядоченное обычными отношениями «меньше или равно» (≤) или «больше или равно» (≥), полностью упорядочено, и, следовательно, таковы подмножества натуральных чисел , целых и рациональных чисел. . Можно показать, что каждый из них является уникальным (с точностью до изоморфизма порядка ) «начальным примером» полностью упорядоченного множества с определенным свойством (здесь общий порядок A является начальным для свойства, если всякий раз, когда B имеет свойство, существует изоморфизм порядка от A к подмножеству B ): [7] [ необходима ссылка ]
- Натуральные числа образуют начальное непустое полностью упорядоченное множество без верхней границы .
- Целые числа образуют начальный непустой полностью упорядоченный набор без верхней или нижней границы .
- Рациональные числа образуют исходное полностью упорядоченное множество, плотное в действительных числах. Более того, рефлексивная редукция <является плотным порядком на рациональных числах.
- Действительные числа образуют исходное неограниченное полностью упорядоченное множество, связанное в топологии порядка (определенной ниже).
- Упорядоченные поля полностью упорядочены по определению. Они включают в себя рациональные числа и действительные числа. Каждое упорядоченное поле содержит упорядоченное подполе, изоморфное рациональным числам. Любое упорядоченное по Дедекинду поле изоморфно действительным числам.
- Буквы алфавита, упорядоченные в стандартном словарном порядке , например, A < B < C и т. Д., Представляют собой строгий общий порядок.
Цепи
Термин цепь иногда определяется как синоним для полностью упорядоченного множества, но это , как правило , используется для обращения к подмножеству о наличии частично упорядоченного множества , который полностью упорядоченный для индуцированного порядка. [8] [9] Обычно частично упорядоченный набор представляет собой набор подмножеств данного набора, который упорядочен по включению, и этот термин используется для определения свойств набора цепочек. Такое большое количество вложенных уровней наборов объясняет полезность этого термина.
Типичным примером использования цепочки для ссылки на полностью упорядоченные подмножества является лемма Цорна, которая утверждает, что если каждая цепь в частично упорядоченном множестве X имеет верхнюю границу в X , то X содержит по крайней мере один максимальный элемент. [10] Обычно используется лемма Цорна, где X - множество подмножеств; в этом случае UpperBound получается доказать , что объединение элементов цепи в X в X . Это способ, который обычно используется для доказательства того, что векторное пространство имеет базисы Гамеля и что кольцо имеет максимальные идеалы .
В некоторых контекстах рассматриваемые цепочки по порядку изоморфны натуральным числам с их обычным порядком или противоположным порядком . В этом случае цепочка может быть идентифицирована с монотонной последовательностью и называется восходящей цепочкой или нисходящей цепочкой , в зависимости от того, увеличивается или уменьшается последовательность. [11]
Частично упорядоченный набор имеет условие нисходящей цепи, если каждая нисходящая цепочка в конечном итоге стабилизируется. [12] Например, заказ считается обоснованным, если он имеет условие нисходящей цепочки. Точно так же условие восходящей цепи означает, что каждая восходящая цепь в конечном итоге стабилизируется. Например, нетерово кольцо - это кольцо, идеалы которого удовлетворяют условию возрастающей цепи.
В других контекстах рассматриваются только цепи, которые являются конечными множествами . В этом случае говорят о конечных цепях , которые часто сокращают до цепочки . В этом случае длина цепочки - это количество неравенств (или множественных включений) между последовательными элементами цепочки; то есть число минус один из элементов в цепочке. [13] Таким образом, одноэлементный набор - это цепь нулевой длины, а упорядоченная пара - это цепь длины один. Размерность пространства часто определяется или характеризуется как максимальной длины цепочек подпространств. Например, размерность векторного пространства является максимальной длиной цепей линейных подпространств , а размерность Крулля из коммутативного кольца является максимальной длиной цепочек простых идеалов .
«Цепочка» также может использоваться для некоторых полностью упорядоченных подмножеств структур , которые не являются частично упорядоченными наборами. Примером служат правильные цепочки многочленов. Другой пример - использование слова «цепочка» как синонима прогулки по графу .
Дальнейшие концепции
Теория решетки
Можно определить полностью упорядоченное множество как особый вид решетки , а именно такую , в которой мы имеем
- для всех a , b .
Затем мы пишем a ≤ b тогда и только тогда, когда . Следовательно, вполне упорядоченное множество - это дистрибутивная решетка .
Конечная сумма заказов
Простой аргумент подсчета проверяет, что любое непустое конечное полностью упорядоченное множество (и, следовательно, любое его непустое подмножество) имеет наименьший элемент. Таким образом, каждый конечный полный порядок на самом деле является порядком здоровья . Либо путем прямого доказательством или, заметив , что каждый заказ также является порядком изоморфного к порядковым один может показать , что каждый конечный общий порядок порядка изоморфно на начальный отрезок натуральных чисел упорядоченных по <. Другими словами, полный порядок на множестве из 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], и аффинно расширенная система действительных чисел (расширенная линия действительных чисел). Между этими примерами существуют гомеоморфизмы, сохраняющие порядок .
Суммы заказов
Для любых двух непересекающихся суммарных заказов а также , есть естественный порядок на съемочной площадке , который называют суммой двух заказов, а иногда и просто :
- Для , выполняется тогда и только тогда, когда выполняется одно из следующих условий:
- а также
- а также
- а также
Интуитивно это означает, что элементы второго набора добавляются поверх элементов первого набора.
В более общем смысле, если является полностью упорядоченным индексным набором, и для каждого структура - линейный порядок, где множества попарно не пересекаются, то естественный полный порядок на определяется
- Для , имеет место, если:
- Либо есть какие-то с участием
- или есть некоторые в с участием ,
Заказы на декартово произведение полностью упорядоченных множеств
В порядке увеличения силы, т. Е. Уменьшения наборов пар, три из возможных порядков декартова произведения двух полностью упорядоченных наборов:
- Лексикографический порядок : ( 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 каждое из них делает его упорядоченным векторным пространством .
См. Также примеры частично упорядоченных наборов .
Действительная функция n вещественных переменных, определенная на подмножестве R n, определяет строгий слабый порядок и соответствующий общий предварительный порядок на этом подмножестве.
Связанные структуры
Бинарное отношение, которое является антисимметричным, транзитивным и рефлексивным (но не обязательно полным), является частичным порядком .
Группа с совместимым общим порядком является полностью упорядоченной группой .
Есть только несколько нетривиальных структур, которые являются (взаимоопределяемыми как) редуктами общего порядка. Забывание ориентации приводит к отношениям промежуточности . Забыть расположение концов приводит к циклическому порядку . Забывание обоих данных приводит к разделительному отношению . [14]
Смотрите также
- Артинианское кольцо
- Теория порядка
- Хороший порядок
- Проблема суслина
- Земляк линия
- Перестановка
- Порядок префикса - общий частичный порядок вниз
Заметки
- ^ a b Биркгоф 1967 , стр. 2.
- ^ a b Schmidt & Ströhlein 1993 , стр. 32.
- ↑ Fuchs 1963 , стр. 2.
- ^ a b c Дэйви и Пристли 1990 , стр. 3.
- ^ Strohmeier, Альфред; Гениллар, Кристиан; Вебер, Матс (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 .
- ^ Это определение напоминаютчто из исходного объекта в виде категории , но слабее.
- ^ Пол Р. Халмос (1968). Наивная теория множеств . Принстон: Ностранд. Здесь: Глава 14
- ^ Ролан Фраиссе (декабрь 2000 г.). Теория отношений . Исследования по логике и основам математики. 145 (1-е изд.). Эльзевир. ISBN 978-0-444-50542-2. Здесь: стр.35
- ^ Брайан А. Дэйви и Хилари Энн Пристли (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета. ISBN 0-521-36766-2. LCCN 89009753 . Здесь: с.100
- ^ Яннис Н. Мощовакис (2006) Заметки по теории множеств , Тексты для студентов по математике (Биркхойзер) ISBN 0-387-28723-X , стр. 116
- ^ то есть за пределами некоторого индекса все остальные члены последовательности равны
- ^ Дэви и Пристли 1990, Def.2.24, с.37
- ^ Макферсон, Х. Дугальд (2011), «Обзор однородных структур», Дискретная математика , 311 (15): 1599–1634, DOI : 10.1016 / j.disc.2011.01.024
Рекомендации
- Гаррет Биркгоф (1967). Теория решеток . Публикации коллоквиума. 25 . Провиденс: Ам. Математика. Soc.
- Брайан А. Дэйви; Хилари Энн Пристли (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета. ISBN 0-521-36766-2. LCCN 89009753 .
- Фукс, Л. (1963). Частично упорядоченные алгебраические системы . Pergamon Press.
- Джордж Гретцер (1971). Теория решеток: первые понятия и дистрибутивные решетки. WH Freeman and Co. ISBN 0-7167-0442-0
- Джон Г. Хокинг и Гейл С. Янг (1961). Топология. Исправленное переиздание, Дувр, 1988. ISBN 0-486-65676-4
- Розенштейн, Джозеф Г. (1982). Линейные порядки . Нью-Йорк: Academic Press.
- Шмидт, Гюнтер ; Стрёляйн, Томас (1993). Отношения и графы: дискретная математика для компьютерных ученых . Берлин: Springer-Verlag. ISBN 978-3-642-77970-1.
Внешние ссылки
- «Полностью упорядоченное множество» , Энциклопедия математики , EMS Press , 2001 [1994]