Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определения [ править ]

Для любых частичных порядков ≤ и ≤ * на множестве X , ≤ * является линейным расширением ≤ точно тогда, когда (1) ≤ * является полным порядком и (2) для любых x и y в X , если x ≤ y , то х ≤ * у . Это второе свойство, которое заставляет математиков описывать ≤ * как расширение ≤.

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

Принцип продления заказа [ править ]

Дополнительная информация: теорема Шпильрайна о расширении

Утверждение, что каждый частичный порядок может быть расширен до полного порядка, известно как принцип расширения порядка . Доказательство с использованием аксиомы выбора было впервые опубликовано Эдвардом Марчевским в 1930 году. Марчевский пишет, что теорема ранее была доказана Стефаном Банахом , Казимиром Куратовски и Альфредом Тарским , снова используя аксиому выбора, но доказательства не были опубликовано. [1]

В современной аксиоматической теории множеств принцип расширения порядка сам по себе воспринимается как аксиома, онтологический статус сравнимый с аксиомой выбора. Принцип порядка расширения вытекает из булевой простой теоремы идеальной или эквивалентной теорема компактности , [2] , но обратная импликация не имеет места. [3]

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

Похожие результаты [ править ]

Принцип расширения порядка конструктивно доказуем для конечных множеств с использованием алгоритмов топологической сортировки , где частичный порядок представлен ориентированным ациклическим графом с элементами множества в качестве вершин . Некоторые алгоритмы могут найти расширение за линейное время . [5] Несмотря на простоту поиска единственного линейного расширения, проблема подсчета всех линейных расширений конечного частичного порядка является # P-полной ; однако его можно оценить с помощью схемы рандомизированной аппроксимации с полностью полиномиальным временем . [6] [7]Среди всех частичных порядков с фиксированным числом элементов и фиксированным числом сопоставимых пар частичные порядки с наибольшим числом линейных расширений являются полупорядками . [8]

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

Антиматроидов можно рассматривать как обобщающие частичные порядки; с этой точки зрения, структуры, соответствующие линейным расширениям частичного порядка, являются основными словами антиматроида. [9]

Эта область также включает одну из самых известных открытых проблем теории порядка, гипотезу 1 / 3–2 / 3 , которая утверждает, что в любом конечном частично упорядоченном множестве P , которое не является полностью упорядоченным, существует пара ( x , y ) элементов из Р , для которых линейных расширений Р , в которых х < у числа между 1/3 и 2/3 от общего числа линейных расширений Р . [10] [11] Эквивалентный способ сформулировать гипотезу состоит в том, что, если кто-то выбирает линейное расширение P равномерно случайным образом, существует пара ( x ,y ), который с вероятностью от 1/3 до 2/3 будет упорядочен как x < y . Однако для некоторых бесконечных частично упорядоченных множеств с канонической вероятностью, определенной на его линейных расширениях как предел вероятностей для конечных частичных порядков, покрывающих бесконечный частичный порядок, гипотеза 1 / 3–2 / 3 неверна. [12]

Алгебраическая комбинаторика [ править ]

Подсчет числа линейных расширений конечного ч.у. множества - обычная проблема алгебраической комбинаторики . Это число определяется как старший коэффициент полинома порядка, умноженный на | P | !.

Таблицу Юнга можно рассматривать как линейные расширения конечного идеала порядка в бесконечном чугуре , и они подсчитываются по формуле длины крюка .

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

  1. ^ Марчевский, Эдвард (1930), "расширение Sur l'де l'Ordre partiel" (PDF) , Fundamenta Mathematicae (на французском языке), 16 : 386-389, DOI : 10,4064 / фм-16-1-386-389.
  2. ^ Jech, Томас (2008) [первоначально опубликованный в 1973 году], аксиома выбора , Dover Publications , ISBN 978-0-486-46624-8.
  3. ^ Felgner, U .; Трасс, JK (март 1999), "Независимость Премьер Ideal теоремы из принципа Order-Extension", журнал символической логики , 64 (1): 199-215, CiteSeerX 10.1.1.54.8336 , DOI : 10,2307 / 2586759 , JSTOR 2586759  .
  4. ^ Матиас, ARD (1971), «Принцип расширения порядка», в Scott, Dana S .; Джеч, Томас Дж. (Ред.), Теория аксиоматических множеств (Калифорнийский университет, Лос-Анджелес, Калифорния, 10 июля - 5 августа 1967 г.) , Труды симпозиумов по чистой математике, 13 , Американское математическое общество, стр. 179– 183.
  5. ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Раздел 22.4: Топологическая сортировка», Введение в алгоритмы (2-е изд.), MIT Press, стр. 549–552, ISBN 978-0-262-03293-3.
  6. ^ Брайтвелл, Грэм Р .; Winkler, Питер (1991), "Counting линейных расширений", Order , 8 (3): 225-242, DOI : 10.1007 / BF00383444 , S2CID 119697949 
  7. ^ Бублей, Расс; Дайер, Мартин (1999), «Более быстрая случайная генерация линейных расширений», Дискретная математика , 201 (1–3): 81–88, DOI : 10.1016 / S0012-365X (98) 00333-1 , S2CID 2942330 .
  8. ^ Фишберн, Питер С .; Троттер, В.Т. (1992), "Линейные расширения полупорядков: проблема максимизации", Дискретная математика , 103 (1): 25–40, DOI : 10.1016 / 0012-365X (92) 90036-F , MR 1171114 .
  9. ^ Бьёрнер, Андерс; Зиглер, Гюнтер М. (1992), «Введение в гридоиды», в White, Neil (ed.), Matroid Applications , Encyclopedia of Mathematics and its Applications, 40 , Cambridge University Press, стр.  284–357 , ISBN 978-0-521-38165-9. См. Особенно пункт (1) на стр. 294.
  10. ^ Кислицын, SS (1968), "Конечные частично упорядоченные множества и связанные с ними множества перестановок", Математические заметки , 4 : 511–518.
  11. ^ Брайтвелл, Грэм Р. (1999), «Сбалансированные пары в частичных порядках», Дискретная математика , 201 (1–3): 25–52, DOI : 10.1016 / S0012-365X (98) 00311-2.
  12. ^ Брайтвелл, GR; Felsner, S .; Trotter, WT (1995), "Балансировка пар и крест гипотеза продукт", заказ , 12 (4): 327-349, CiteSeerX 10.1.1.38.7841 , DOI : 10.1007 / BF01110378 , МР 1368815 , S2CID 14793475   .