Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 109 / 2 / i / Solution

We prove the Harris-Kleitman inequality by induction on $n$. For up-sets $\mathcal{A},\mathcal{B}\subseteq \mathcal{P}([n])$, let ${\mathcal{A}}_0,{\mathcal{A}}_1$ be their sections according as $n$ is absent or present, and write $a_i=|{\mathcal{A}}_i|$; define $b_i$ and $c_i=|{\mathcal{A}}_i\cap {\mathcal{B}}_i|$ similarly. Monotonicity gives $a_0\le a_1$ and $b_0\le b_1$. The induction hypothesis on $[n-1]$ givesIt remains only to observe thatHenceThe case $n=0$ starts the induction, so this is a proof from first principles.