Sperner's theorem

Statement

The maximal number of distinct subsets $A_{1}, \dots, A_{N}$ of $[n] = {1, 2, \dots, n}$ such that for all $i \neq j$ , $A_{i} ⊈ A_{j}$ and $A_{j} ⊈ A_{i}$ is upper bounded by

N \leq (\binom{n}{⌊ \frac{n}{2} ⌋})

and this is a strict bound.

Proof

First, we note that equality can be achieved when we let $N$ be all the subsets of size $⌊ n / 2 ⌋$ .

Then, this follows from DeBruijn's theorem since this statement is equivalent to asking for the largest antichain of a Boolean lattice.