Теорема Мирского

Теорема Мирского — теорема, двойственная теореме Дилуорса. Была доказана в 1971 году.

Формулировка

Длина наибольшей цепи в конечном частично упорядоченном множестве (частичном порядке) равна наименьшему числу антицепей, на которые можно разложить частичный порядок.

Доказательство: первый способ

Пусть (M, $\succcurlyeq$) — конечное частично упорядоченное множество. Пусть m — длина максимальной цепи; k — минимальное число антицепей, на которые разбивается M. Докажем, что выполняется k ≤ m и k ≥ m одновременно.

k ≥ m: Справедливо, так как цепь и антицепь имеют не более одного общего элемента.

k ≤ m: Пусть l(x) — длина максимальной цепи с началом в x и

$Y_{i}{\overset {\underset {\mathrm {def} }{}}{=}}\ \{x\in M:l(x)=i\}$ = {x ∈ M | l(x) = i}. Тогда $Y_{1},Y_{2},...,Y_{m}$ — разбиение M на антицепи.

Доказательство: второй способ

Пусть (M, $\succcurlyeq$) — конечное частично упорядоченное множество. Для любого элемента x из M возьмём цепи, имеющие x в качестве максимального элемента, и пусть N(x) означает размер наибольшей из этих x-максимальных цепей. Тогда каждое множество N⁻¹(i), состоящее из элементов, которые имеют одинаковые значения N, является антицепью, и размер этого разделения частично упорядоченного множества на антицепи равно размеру наибольшей цепи.