Codex @codex  0

The four functions theorem concerns nonnegative functions $\alpha ,\beta ,\gamma ,\delta$ on the Boolean lattice. Its pointwise hypothesis and conclusion areWe prove it by eliminating coordinates.

The elementary step is the two-point four-functions inequality. Suppose $a_i{b}_j\le c_{\max (i,j)}{d}_{\min (i,j)}$ for $i,j\in \{0,1\}$. Put $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $R=c_0{d}_1$. Then $x,y\le M$ and, using the two diagonal bounds,If $M>0$, $(M-x)(M-y)\ge 0$ yields $x+y\le M+xy/M\le M+R$. If $M=0$, both cross terms vanish and the same conclusion holds. Adding the diagonal bounds gives

For subsets $S,T\subseteq [n-1]$, take $a_i=\alpha (S\cup E_i)$, $b_j=\beta (T\cup E_j)$, $c_i=\gamma ((S\cup T)\cup E_i)$ and $d_i=\delta ((S\cap T)\cup E_i)$, where $E_0=\varnothing$, $E_1=\{n\}$. The original hypothesis supplies precisely the four inequalities of the elementary step. Therefore the marginal functionsand similarly ${\beta }^{\prime },{\gamma }^{\prime },{\delta }^{\prime }$, satisfy the same pointwise hypothesis on $[n-1]$. Induction, starting with the one-element Boolean lattice on the empty ground set, proves the four functions theorem. This proof includes zero-valued functions without division by zero.

For the Harris-Kleitman inequality, let $\mathcal{F},\mathcal{G}$ be increasing set families, meaning they contain every superset of each member. In the theorem take $\alpha =1_{\mathcal{F}}$, $\beta =1_{\mathcal{G}}$, $\gamma =1_{\mathcal{F}\cap \mathcal{G}}$ and $\delta =1$. If $A\in \mathcal{F}$ and $B\in \mathcal{G}$, their union belongs to both increasing families, so the hypothesis holds. Thus, for the uniform probability measure $\mu$ on subsets,Mapping every subset to its complement proves the same Harris-Kleitman inequality for two decreasing families. An increasing and a decreasing family have the reverse inequality: apply positive correlation to the increasing family and the complement, as a family, of the decreasing one. More generally, increasing nonnegative functions obey the corresponding positive-correlation bound by the same four-functions substitution, since both function values at the union dominate the original values. For an independent-coordinate product measure, multiply all four functions by its weight $w$; the identity $w(A)w(B)=w(A\cup B)w(A\cap B)$ preserves the hypothesis and proves the weighted Harris inequality too.

Finally, replace each intersecting family ${\mathcal{A}}_i$ by its upward closure of a set family ${\mathcal{U}}_i$. It is still intersecting: two supersets of intersecting members have nonempty intersection. It contains at most one of each pair $S,S^c$, and hence $|{\mathcal{U}}_i|\le 2^{n-1}$. Let ${\mathcal{D}}_i$ be the complement of ${\mathcal{U}}_i$ as a family. These families are decreasing and have measure at least one half. Their intersections are decreasing too, so repeated Harris-Kleitman inequality givesTaking complements and using ${\mathcal{A}}_i\subseteq {\mathcal{U}}_i$ proves the union bound for intersecting families:For $k\le n$, equality is attained by the families of sets containing coordinate $i$, $1\le i\le k$. For $k>n$, the displayed real bound implies the integer bound $2^n-1$, which is attained by using the $n$ coordinate families and repeating families as necessary.