The Intersection of a Chain and Antichain

Recall from the Chains of Subsets of a Set page that if $A$ is a finite $n$-element set then a chain is a collection of subsets $B_1, B_2, ..., B_k$ of $A$ such that 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$.

Similarly, we saw on the Antichains of Subsets of a Set page that an antichain is a collection of subsets $B_1, B_2, ..., B_k$ of $A$ such that for each $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$.

We will now look at a relatively simple theorem which tells us that the intersection of a chain and antichain of subsets from a parent set $A$ contains at most one subset of $A$.

Theorem 1: Let $A$ be a finite $n$-element set. Let $B$ be a chain of subsets of $A$ and let $C$ be an antichain of subsets of $A$. Then $\lvert B \cap C \rvert \leq 1$.

• Proof: Let $A$ be a finite $n$-element set. We will carry this proof out by contradiction. Assume that $\lvert B \cap C \rvert > 1$. Then there exists at least two subsets $A_1, A_2 \subset A$ such that $A_1, A_2 \in B \cap C$.

• Since $A_1, A_2 \in B \cap C$ we have that $A_1, A_2 \in B$, that is $A_1$ and $A_2$ are contained in the chain $B$ of subsets from $A$. Therefore we have that either ($*$) $A_1 \subset A_2$ or $A_1 \supset A_2$.

• Similarly, since $A_1, A_2 \in B \cap C$ we have that $A_1, A_2 \in C$, that is $A_1$ and $A_2$ are contained in the antichain $C$ of subsets from $A$. Therefore we have that both $A_1 \not \subset A_2$ and $A_1 \not \supset A_2$. But this is a contradiction from the conclusion we arrived at $*$.

• Therefore $\lvert B \cap C \rvert \leq 1$. $\blacksquare$

It is important to note that Theorem 1 simply states an upper bound for the number of subsets that in common with any chain and antichain of subsets from a parent set $A$. We have not actually shown that it is possible that $\lvert B \cap C \rvert = 1$ under certain circumstances. Fortunately this is rather easy to do.

Consider the $3$-element set $A = \{ x_1, x_2, x_3 \}$. Let $B = \{ \{x_1 \}, \{ x_1, x_2 \}, \{ x_1, x_2, x_3 \} \}$ be a chain of $3$ subsets from $A$. Furthermore, let $C^* = \{ \{x_1, x_2 \}, \{ x_3 \} \}$ and $C^+ = \{ \{x_1 \}, \{x_2, x_3 \} \}$ be antichains of $2$ subsets from $A$.

We have that $B \cap C^* = \{ \{x_1, x_2 \} \}$ and so $\lvert B \cap C^* \rvert = 1$. Furthermore, we have that $B \cap C^+ = \emptyset$ and so $\lvert B \cap C^+ \rvert = 0$. Thus we conclude that $\lvert B \cap C \rvert = 0$ or $\lvert B \cap C \rvert = 1$ for every chain $B$ and antichain $C$ of subsets from a parent set $A$.