Antichains of Subsets of a Set
Recall from the Chains of Subsets of a Set page that if $A$ is an $n$-element set then a collection of subsets $B_1, B_2, ..., B_k$ of $A$ is called a chain if for each $i, j \in \{1, 2, ..., k \}$ where $i \neq j$ we have that $B_i \subset B_j$ or $B_i \supset B_j$. We also noted that such a chain can contain at most $n + 1$ subsets of $A$ and the total number of chains containing the maximum number of subsets from $A$ is simply an $n$-permutation of the elements from $A$, i.e., $n!$.
We will now define another type of collection of subsets from $A$ called an antichain.
| Definition: If $A$ is a finite $n$-element set then an Antichain is a collection of subsets $B_1, B_2, ..., B_k$ such that for all $i, j \in \{1, 2, ..., k \}$ where $i \neq j$ we have that $B_i \not \subset B_j$ and $B_i \not \supset B_j$. |
For example, consider the following set:
(1)Let $B_1 = \{ w \}$, $B_2 = \{x, y \}$ and $B_3 = \{ z \}$. Then it should not be hard to see that $B_1 \not \subset B_2$, $B_1 \not \supset B_2$, $B_1 \not \subset B_3$, $B_1 \not \supset B_3$, $B_2 \not \subset B_3$ and $B_2 \not \supset B_3$ since the subsets $B_1$, $B_2$, and $B_3$ form a partition of $A$ and hence contain no elements in common.
In fact, if $A$ is a finite $n$-element set then any collection of subsets $B_1, B_2, ..., B_k$ of $A$ that form a partition of $A$ are an antichain. More generally, if $B_1, B_2, ..., B_k$ is a collection of subsets of $A$ such that for all $i, j \in \{1, 2, ..., k \}$ we have that $B_i \cap B_j = \emptyset$ then the collection of subsets $B_1, B_2, ..., B_k$ of $A$ are an antichain. In other words, any collection of pairwise disjoint subsets of $A$ is an antichain of $A$.
Clearly the largest number of pairwise disjoint subsets are the collection of $1$-elements subsets for which there are $n$. However, are there any antichains of an $n$-element set $A$ that contain more than $n$ subsets of $A$? Fortunately, Sperner's Antichain Theorem answers that question.