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

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

Определения

Линейное расширение частичного порядка

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

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

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

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

Линейное расширение предзаказа

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

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

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

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

Принцип расширения заказа

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

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

Аналогичное утверждение действует и для предзаказов: каждый предзаказ можно расширить до общего предзаказа. Это утверждение было доказано Ханссоном.

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

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

Связанные результаты

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

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

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

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

Алгебраическая комбинаторика

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

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