Антиланцюг

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

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

Нехай P скінченна частково впорядкована множина, тоді антиланцюг P, це набір попарно непорівнянних елементів.

Висота і ширина[ред.ред. код]

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

Приєднання и відповідність операцій[ред.ред. код]

Будь-якому антиланцюгу відповідає нижній набір

L_A = \{x \mid \exists y\in A\mbox{ s.t. }x\le y\}.

У кінцевому частковому порядку,(який задовольняє умови максимальності), мають цю форму:

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

Крім того, ми можемо визначити "відповідність операцій" на антиланцюгу, нижче:

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\}.

Див. також[ред.ред. код]

Література[ред.ред. код]