Антиланцюг — Вікіпедія
У математиці, в області теорії порядку, антиланцюг є підмножиною частково впорядкованої множини (посета) в якій, будь-якї два елементи є непорівнянні один з одним.
Ланцюг — підмножина частково впорядкованої множини, в якій, будь-якї два елементи є порівнянні один з одним. Тобто, ланцюг — лінійно впорядкована множина.
- Максимальний антиланцюг є антиланцюгом, який не є власною підмножиною будь-якого іншого антиланцюга.
- Максимальний антиланцюг є антиланцюгом, що має потужність, не менше ніж будь-який інший антиланцюг.
- Будь-який антиланцюг може перетинатись з будь-якими ланцюгаом не більше ніж в одному елементі.
- Шириною посета називається величина максимального антиланцюга. За теоремою Ділуорса ширина рівна мінімальній кількості ланцюгів, на які можна розбити посет.
- Висотою посета називається величина максимального ланцюга. За теоремою Мірського висота рівна мінімальній кількості антиланцюгів, на які можна розбити посет.
Операції поєднання та зустріч
[ред. | ред. код]- Будь-якому антиланцюгу відповідає нижня множина:
У кінцевому частковому порядку, для всіх нижніх множин існує антиланцюг.
- Об'єднанням нижніх множин є нижня множина, якій відповідає join їх антиланцюгів:
- ВІдповідно, за meet антиланцюгів відповідає перетин нижніх множин:
- Биркгоф Г. Теория решёток / пер. с англ. В. Н. Салий ; под ред. Л. А. Скорнякова. — 3-е изд. — Москва : Наука, 1984. — 568 с.(рос.)
- Weisstein, Eric W. Antichain(англ.) на сайті Wolfram MathWorld.
- Antichain на PlanetMath