antichain

(Combinatorics, Set Theory, Logic:)

In the combinatorics of sets, especially finite sets, an antichain is a family F of sets such that no member contains any other member:

∀x,y∈F. ¬(x⊂y)

More generally, we can define antichains whenever (P,<) is a poset (a partially ordered set). A subset F⊆P is an antichain if no two elements of F can be compared:

∀x,y∈F. ¬(x<y)

The definition for sets is a special case of the definition for posets (when the family F is a set): take the poset (F,⊂).

Examples.

1. Let S be a set and k a natural number. The set

   F_k(S) = {x⊆S: |x|=k}

   of all subsets of S of size k is an antichain.
2. In the poset (N,|) of natural numbers partially ordered by divisibility, the set P of prime numbers is an antichain. Other antichains include the sets

   F_k = {p₁⋅...⋅p_k: p_i∈P}

   of all products of exactly k prime numbers.