Chains of Subsets of a Set

Definition: 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 all $i, j \in \{1, 2, ..., k \}$ where $i \neq j$ we have that $B_i \subset B_j$ or $B_i \supset B_j$.

From the definition above, we see that a collection of subsets $B_1, B_2, ..., B_k$ of an $n$-element set $A$ is a chain if for each pair of subsets in this collection one of the subsets is contained within the other.

For example, consider the $5$-element set $A = \{v, w, x, y, z \}$ and consider the subsets $B_1 = \{ v \}$, $B_2 = \{ v, w \}$, $B_3 = \{ v, w, x, y \}$. Is the collection of subsets $B_1$, $B_2$, and $B_3$ of $A$ a chain? Let's check.

For the pair of subsets $B_1$ and $B_2$ we see that $B_1 \subset B_2$. For the pair of subsets $B_1$ and $B_3$ we see that $B_1 \subset B_3$. Lastly, for the pair of subsets $B_2$ and $B_3$ we have that $B_2 \subset B_3$. Therefore the collection $B_1$, $B_2$, and $B_3$ of subsets of $A$ is a chain.

Now let $A$ be a general $n$-element set. Thus, $A$ is of the form:

(1)

\begin{align} \quad A = \{ x_1, x_2, ..., x_n \} \end{align}

In general, we can construct a chain by setting $B_1 = \emptyset$, $B_2 = \{ x_1 \}$, $B_3 = \{ x_1, x_2 \}$, …, $B_n = \{x_1, x_2, ..., x_{n-1} \}$, and $B_{n+1} = \{x_1, x_2, ..., x_{n-1}, x_n \}$. Notice that:

(2)

\begin{align} \quad B_1 \subset B_2 \subset ... \subset B_n \subset B_{n+1} \end{align}

It's not hard to see that therefore each pair of subsets $B_j$ and $B_k$ where $j, k \in \{1, 2, ..., n+1 \}$ and $j < k$ has the property that:

(3)

\begin{align} \quad B_j \subset B_k \end{align}

Therefore a chain of $n + 1$ subsets can always be constructed by a finite $n$-element $A$. As we will see in the following lemma and theorem, the maximum number of subsets in a chain of a finite $n$-element set is $n + 1$.

Lemma 1: If $A$ is a finite $n$-element set then for each $k = 0, 1, 2, ..., n$ there can be at most one $k$-element set in any chain of subsets from $A$.

• Proof: Suppose that $A$ is a finite $n$-element set and suppose that for $k = 0, 1, 2, ..., n$ we have that there exists two subsets $B_1, B_2 \subset A$, $B_1 \neq B_2$ such that $\lvert B_1 \rvert = \lvert B_2 \rvert = k$. Since $B_1$ and $B_2$ have the same number of elements then $B_1$ can be a subset of $B_2$ if and only if $B_2$ is a subset of $B_1$ which implies that $B_1 = B_2$ - a contradiction. Thus if $A$ is a finite $n$-element set then for each $k = 0, 1, 2, ..., n$ there can be at most one $k$-element set in any chain of subsets of $A$. $\blacksquare$

Theorem 1: If $A$ is a finite $n$-element set then the maximum number of sets in any chain of subsets from $A$ is $n + 1$.

• Proof: Let $A$ be a finite $n$-element set. From Lemma $1$ we see that for each $k = 0, 1, 2, ..., n$ there can be at most one $k$-element set in any chain of subsets from $A$. We thus select a $0$, $1$, …, and $n$-element subset of $A$ to form a chain with a maximum number of subsets from $A$ - $n + 1$. $\blacksquare$

In the following theorem we will see the relationship between permutations and the number of chains containing a maximum number of subsets from a finite set.

Theorem 2: If $A$ is a finite $n$-element set then there are precisely $n!$ chains with $n + 1$ subsets of $A$.

• Proof: Let $A$ be a finite $n$-element set. It should be clear that any chain containing the maximum $n + 1$ subsets of $A$ must contain the empty set, $\emptyset$, since it is the only $0$-element set. We now need to choose how to construct a $1$-element set. We can choose any of the $n$ elements $x_1, x_2, ..., x_n$. There are $n$ elements we can choose. For our $2$-element set, we choose the element from the $1$-element set and we can choose any of the remaining $n - 1$ elements, …, for the $n-1$ element set, we choose the elements from the $n-1$-element set and we choose any remaining of the remaining $2$ elements. All elements in $A$ must be chosen for the $n$-element set and so as we can see, every chain containing $n + 1$ subsets of $A$ is related to some $n$-permutation of the $n$ elements in $A$ and so:

(4)

\begin{align} \quad \mathrm{number \: of \: chains \: with \: n+1 \: subsets \: of} \: A = P(n, n) = \frac{n!}{(n - n)!} = n! \quad \blacksquare \end{align}