Антиланцюг

У математиці, в області теорії порядку, антиланцюг є підмножиною частково впорядкованої множини (посета) в якій, будь-якї два елементи є непорівнянні один з одним.

Пов'язані означення

Ланцюг — підмножина частково впорядкованої множини, в якій, будь-якї два елементи є порівнянні один з одним. Тобто, ланцюг — лінійно впорядкована множина.

Властивості

• Максимальний антиланцюг є антиланцюгом, який не є власною підмножиною будь-якого іншого антиланцюга.
• Максимальний антиланцюг є антиланцюгом, що має потужність, не менше ніж будь-який інший антиланцюг.
• Будь-який антиланцюг може перетинатись з будь-якими ланцюгаом не більше ніж в одному елементі.

Висота і ширина

• Шириною посета називається величина максимального антиланцюга. За теоремою Ділуорса ширина рівна мінімальній кількості ланцюгів, на які можна розбити посет.

• Висотою посета називається величина максимального ланцюга. За висота рівна мінімальній кількості антиланцюгів, на які можна розбити посет.

Операції поєднання та зустріч

• Будь-якому антиланцюгу ${\displaystyle A}$ відповідає нижня множина:

${\displaystyle L_{A}=\{x\mid \exists y\in A{\mbox{ s.t. }}x\leq y\}.}$

У кінцевому частковому порядку, для всіх нижніх множин існує антиланцюг.

• Об'єднанням нижніх множин є нижня множина, якій відповідає join їх антиланцюгів:

${\displaystyle A\vee B=\{x\in A\cup B\mid \not \exists y\in A\cup B{\mbox{ s.t. }}x<y\}.}$

• ВІдповідно, за meet антиланцюгів відповідає перетин нижніх множин:

${\displaystyle A\wedge B=\{x\in L_{A}\cap L_{B}\mid \not \exists y\in L_{A}\cap L_{B}{\mbox{ s.t. }}x<y\}.}$

Див. також

• Сильний антиланцюг

Джерела

• Биркгоф Г. Теория решёток / пер. с англ. В. Н. Салий ; под ред. Л. А. Скорнякова. — 3-е изд. — Москва : Наука, 1984. — 568 с.(рос.)
• Weisstein, Eric W. Antichain(англ.) на сайті Wolfram MathWorld.
• Antichain на PlanetMath