У математиці, в області теорії порядку, антиланцюг є підмножиною частково впорядкованої множини (посета) в якій, будь-які два елементи є непорівнянні один з одним.
Пов'язані означення Ланцюг — підмножина частково впорядкованої множини, в якій, будь-які два елементи є порівнянні один з одним. Тобто, ланцюг — лінійно впорядкована множина.
Властивості
Максимальний антиланцюг є антиланцюгом, який не є власною підмножиною будь-якого іншого антиланцюга. Максимальний антиланцюг є антиланцюгом, що має потужність, не менше ніж будь-який інший антиланцюг. Будь-який антиланцюг може перетинатись з будь-якими ланцюгаом не більше ніж в одному елементі.
Висота і ширина Шириною посета називається величина максимального антиланцюга. За теоремою Ділуорса ширина рівна мінімальній кількості ланцюгів, на які можна розбити посет. Висотою посета називається величина максимального ланцюга. За теоремою Мірського висота рівна мінімальній кількості антиланцюгів, на які можна розбити посет.
Операції поєднання та зустріч Будь-якому антиланцюгу відповідає нижня множина:
У кінцевому частковому порядку, для всіх нижніх множин існує антиланцюг.
Об'єднанням нижніх множин є нижня множина, якій відповідає join їх антиланцюгів:
ВІдповідно, за meet антиланцюгів відповідає перетин нижніх множин:
Див. також Сильний антиланцюг
Джерела