Антиланцюг

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

[ред. | ред. код]

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

Властивості

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

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

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

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

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

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]