Войти
В теории порядка, раздел математики ics, линейное расширение частичного порядка - это общий порядок (или линейный порядок), который совместим с частичным порядком. В качестве классического примера лексикографический порядок полностью упорядоченных наборов является линейным продолжением их заказа продукта.
Для любых частичных порядков ≤ и ≤ на множестве X ≤ является линейным расширением ≤, в точности когда (1) ≤ является общий порядок и (2) для всех x и y в X, если x ≤ y, то x ≤ y. Это второе свойство, которое заставляет математиков описывать ≤ как, расширяющее ≤.
В качестве альтернативы, линейное расширение можно рассматривать как сохраняющее порядок биекцию из частично упорядоченного множества P в цепочку C на тот же набор земли.
Утверждение о том, что каждый частичный заказ может быть расширен до полного заказа, известно как принцип расширения заказа . Доказательство с использованием аксиомы выбора было впервые опубликовано Эдвардом Марчевским в 1930 году. Марчевский пишет, что теорема ранее была доказана Стефаном Банахом, Казимеж Куратовски и Альфред Тарский, снова используя аксиому выбора, но доказательства не были опубликованы.
В современной аксиоматической теории множеств Принцип расширения порядка сам по себе воспринимается как аксиома, онтологический статус сравнимый с аксиомой выбора. Принцип расширения порядка подразумевается теоремой о булевом простом идеале или эквивалентной теоремой о компактности, но обратная импликация не выполняется.
Применение порядка- принцип расширения до частичного порядка, в котором каждые два элемента несравнимы, показывает, что (согласно этому принципу) каждый набор может быть линейно упорядочен. Это утверждение, что каждый набор может быть линейно упорядочен, известно как принцип упорядочения, OP, и является ослаблением теоремы о хорошем упорядочивании. Однако существуют модели теории множеств, в которых принцип упорядочения выполняется, а принцип расширения порядка - нет.
Принцип расширения порядка конструктивно доказуемо для конечных множеств с использованием алгоритмов топологической сортировки, где частичный порядок представлен направленным ациклическим графом с элементами множества в качестве его вершин. Несколько алгоритмов могут найти расширение в линейное время. Несмотря на простоту поиска единственного линейного расширения, проблема подсчета всех линейных расширений конечного частичного порядка является # P-complete ; однако это может быть оценено с помощью полностью рандомизированной схемы аппроксимации с полиномиальным временем. Среди всех частичных порядков с фиксированным числом элементов и фиксированным числом сопоставимых пар частичные порядки, которые имеют наибольшее количество линейных расширений, - это полупорядки.
размерность порядка частичного порядка - минимальная мощность множества линейных расширений, пересечение которых является заданным частичным порядком; эквивалентно, это минимальное количество линейных расширений, необходимое для обеспечения того, чтобы каждая критическая пара частичного порядка была обращена по крайней мере в одном из расширений.
Антиматроиды можно рассматривать как обобщающие частичные порядки; с этой точки зрения, структуры, соответствующие линейным расширениям частичного порядка, являются основными словами антиматроида.
Эта область также включает одну из самых известных открытых проблем теории порядка, 1 / 3– 2/3 гипотеза, которая утверждает, что в любом конечном частично упорядоченном множестве P, которое не является полностью упорядоченным, существует пара (x, y) элементов P, для которой линейные расширения P в which x < y number between 1/3 and 2/3 of the total number of linear extensions of P. An equivalent way of stating the conjecture is that, if one chooses a linear extension of P uniformly at random, there is a pair (x,y) which has probability between 1/3 and 2/3 of being ordered as x < y. However, for certain infinite partially ordered sets, with a canonical probability defined on its linear extensions as a limit of the probabilities for finite partial orders that cover the infinite partial order, the 1/3–2/3 conjecture does not hold.
Подсчет числа линейных расширений конечного ч.у. множества - обычная проблема алгебраической комбинаторики. Это число задается старшим коэффициентом многочлена порядка ..
Таблица Юнга может рассматриваться как линейное расширение конечного идеала порядка в бесконечном чугуре 
