Линейное расширение

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

Частичный порядок — это рефлексивное , транзитивное и антисимметричное отношение. При наличии любых частичных порядков и на множестве есть линейное расширение именно тогда, когда ${\displaystyle \,\leq \,}$${\displaystyle \,\leq ^{*}\,}$${\displaystyle X,}$ ${\displaystyle \,\leq ^{*}\,}$${\displaystyle \,\leq \,}$

1. ${\displaystyle \,\leq ^{*}\,}$это полный порядок , и
2. Для каждого если то${\displaystyle x,y\in X,}$${\displaystyle x\leq y,}$${\displaystyle x\leq ^{*}y.}$

Именно это второе свойство заставляет математиков называть его расширяющимся${\displaystyle \,\leq ^{*}\,}$ ${\displaystyle \,\leq .}$

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

Предпорядок — это рефлексивное и транзитивное отношение. Разница между предпорядком и частичным порядком заключается в том, что предпорядок позволяет двум разным элементам считаться «эквивалентными», то есть, и выполняются, тогда как частичный порядок позволяет это только когда . Отношение называется линейным расширением предпорядка, если:${\displaystyle x\precsim y}$${\displaystyle y\precsim x}$${\displaystyle x=y}$${\displaystyle \precsim ^{*}}$${\displaystyle \precsim}$

1. ${\displaystyle \precsim ^{*}}$это полный предварительный заказ , и
2. Для каждого если то , и${\displaystyle x,y\in X,}$${\displaystyle x\precsim y}$${\displaystyle x\precsim ^{*}y}$
3. Для каждого если то . Здесь означает « и не ».${\displaystyle x,y\in X,}$${\displaystyle x\prec y}$${\displaystyle x\prec ^{*}y}$${\displaystyle x\prec y}$${\displaystyle x\precsim y}$${\displaystyle y\precsim x}$

Разница между этими определениями только в условии 3. Когда расширение является частичным порядком, условие 3 не нужно указывать явно, так как оно следует из условия 2. Доказательство : предположим, что и не . По условию 2, . По рефлексивности, «не » подразумевает, что . Так как является частичным порядком, и подразумевают «не ». Следовательно, . ${\displaystyle x\precsim y}$${\displaystyle y\precsim x}$${\displaystyle x\precsim ^{*}y}$${\displaystyle y\precsim x}$${\displaystyle y\neq x}$${\displaystyle \precsim ^{*}}$ ${\displaystyle x\precsim ^{*}y}$${\displaystyle y\neq x}$${\displaystyle y\precsim ^{*}x}$${\displaystyle x\prec ^{*}y}$

Однако для общих предпорядков условие 3 необходимо для исключения тривиальных расширений. Без этого условия предпорядок, при котором все элементы эквивалентны ( и выполняются для всех пар x , y ), был бы расширением каждого предпорядка.${\displaystyle y\precsim x}$${\displaystyle x\precsim y}$

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

Аналогичное утверждение существует для предпорядков: каждый предпорядок может быть расширен до полного предпорядка. Это утверждение было доказано Ханссоном. ^{[2] : Лемма 3}

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

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

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

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

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

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

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

Таблицы Юнга можно рассматривать как линейные расширения конечного идеала порядка в бесконечном частично упорядоченном множестве , и они подсчитываются по формуле длины крючка .${\displaystyle \mathbb {N} \times \mathbb {N} ,}$