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