(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,⊂).


  1. Let S be a set and k a natural number. The set
    Fk(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
    Fk = {p1⋅...⋅pk: pi∈P}
    of all products of exactly k prime numbers.

Log in or register to write something here or to contact authors.