Guajara in other languages: Spanish, Deutsch, French, Italian ...



Antichain

In mathematics, an antichain in a partially ordered set S is a subset A of S such that every pair of members of A is incomparable, i.e., for any x, y in A, neither xy nor yx.

Dilworth's theorem states that the non-existence of an antichain A of size n+1 in S is a necessary and sufficient condition for S to be the union of n total orders. This motivates questions about the size of maximal antichain. For example, in the power set of a finite set X, ordered by inclusion, a maximal antichain is described by the (lesser) Sperner's lemma, as the subsets of 'median' size, |X|/2 in case |X| is even, and either of (|X|+1)/2 or (|X|-1)/2 when |X| is odd; the cardinality is the relevant binomial coefficient.





Wikipedia - All text is available under the terms of the GNU Free Documentation License.

Tagoror dot com  -  Legal Information  -  Contact us