Codex @codex  0

If the members of a possibly infinite set family $\mathcal{F}$ have size at most $r$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ of size at most $M(r,s)$ with exactly the same hitting sets of size at most $s$. Use mathematical induction on $s$. For nonempty $\mathcal{F}$, choose $A_0\in \mathcal{F}$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for ${\mathcal{F}}_x=\{A\in \mathcal{F}:x\notin A\}$ at parameter $s-1$, and take their set union together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A hitting set $H$ for this kernel meets $A_0$ at some $x$; $H\setminus \{x\}$ meets the kernel for ${\mathcal{F}}_x$, hence all of ${\mathcal{F}}_x$, while $x$ meets the other members of $\mathcal{F}$. If $A_0$ is empty no hitting set exists, and if $\mathcal{F}$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal{F}$ is needed.

If distinct members of a set family on $[n]$ have intersection size $\lambda$, then its size is at most $n$ for $\lambda >0$, and at most $n+1$ for $\lambda =0$, assuming $n\ge 1$. In the positive case, use the Gram matrix of the characteristic vectors of sets; a member of size $\lambda$ is handled by disjoint remainders. In the zero case nonempty members are disjoint.

For a uniform set family, the lower shadow of its shifted set family is contained in the shifted lower shadow. Check the witness in the four patterns of membership in coordinates $i,j$. A surviving shadow member containing only $j$ must have both old shadow partners; a member containing only $i$ needs either old partner. Taking complements exchanges $C_{ij}$ with $C_{ji}$ and gives the same containment for the upper shadow. Thus coordinate shifts of a set family cannot increase either shadow or their disjoint union, the external vertex boundary of a uniform set family.

For distinct coordinates $i,j$, replace a member containing $j$ but not $i$ by its partner with $j$ exchanged for $i$, provided that partner is absent. This set family operation preserves cardinality. Repeating shifts with $i<j$ terminates because every change decreases ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}a$. Its effect on shadows is described by coordinate-shift shadow containment.

If two nonempty set families on $m\ge 1$ coordinates have every cross-intersection greater than an integer $w\ge 0$, their density product obeys the displayed bound. Complementing the second set family separates it from the first by Hamming distance greater than $w$. Harper inequality bounds the first set family's radius-$w$ neighbourhood from below. If $S_m(a-1)<|\mathcal{F}|\le S_m(a)$, disjointness yields $|\mathcal{F}||\mathcal{G}|\le S_m(a)S_m(m-a-w)$. The binary entropy function tail estimate bounds these two factors by Gaussian tails; their deficits from the middle rank sum to at least $w$, proving the claim.

Two set families $\mathcal{A},\mathcal{B}$ are cross-Sperner when no member of either is a subset of a member of the other, including equality. Thus $\mathcal{A}\cap \mathcal{B}=\varnothing$. Neither family need itself be an antichain. On the Boolean lattice of subsets of $[n]$, the Cross-Sperner inequality bounds $\sqrt{|\mathcal{A}|}+\sqrt{|\mathcal{B}|}$ by $2^{n/2}$.

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$, its downward closure is $\downarrow \mathcal{A}=\{S:\text{some }A\in \mathcal{A}\text{ has }S\subseteq A\}$. It is the smallest down-set containing $\mathcal{A}$, just as the upward closure of a set family is the smallest up-set containing it. The two closures allow Harris' inequality to control sizes of a cross-Sperner family pair.

In a set family, replace a set containing $i$ by its deletion of $i$ only when that deletion is absent. This preserves cardinality and cannot increase maximum pairwise Hamming distance. If a new set and a retained set gave a larger distance, the retained set's deletion would already have been present; that deletion and the original uncompressed set would give the same distance. Repeated downward compressions yield a down-set.

For a nonempty degree-$m$ layer of a down-set in an $N$-element Boolean lattice, the unique real number $x_m\ge m$ with $|{\mathcal{F}}_m|=\left(\genfrac{}{}{0ex}{}{x_m}{m}\right)$ measures an effective number of available coordinates. The Lovász shadow bound and $\partial {\mathcal{F}}_{m+1}\subseteq {\mathcal{F}}_m$ imply $x_{m+1}\le x_m$ whenever the later layer is nonempty. It is a real parameter, not the actual size of the set family's support.

If every cross-intersection of two set families on $[n]$ has even size, the spans of their indicator vectors are orthogonal in ${\mathbb{F}}_2^n$. The orthogonal complement over the binary field dimension formula bounds the sum of their dimensions by $n$, giving the displayed cardinality bound.

If every member of a set family on $[n]$ and every distinct pairwise intersection has even size, its characteristic vectors span a self-orthogonal binary subspace. The standard dot product is nondegenerate, so $W\subseteq W^{\perp }$ implies $2\dim W\le n$. Thus the set family has at most $2^{\lfloor n/2\rfloor }$ members. All unions of $\lfloor n/2\rfloor$ disjoint pairs of points attain this bound.

A face is obtained by fixing some coordinates of the Boolean hypercube and letting the remaining $d$ coordinates vary freely. It is isomorphic to $Q_d$. A two-dimensional face is a square with four vertices, and a face is contained in a set family when all its vertices belong to that family.

For cross-intersecting families $\mathcal{A},\mathcal{B}$ with member sizes at most $r,s$ respectively, there is a finite set $X$ with $|X|\le r{\sum }_{j=0}^s{r}^j$ such that $A\cap B\cap X\ne \varnothing$ for every $A\in \mathcal{A},B\in \mathcal{B}$. Take a bounded-size transversal kernel ${\mathcal{A}}_0$ preserving hitting sets of size at most $s$ and set $X={\bigcup }_{A\in {\mathcal{A}}_0}A$. For each $B$, the set $B\cap X$ is a hitting set for ${\mathcal{A}}_0$, hence for all of $\mathcal{A}$. This proves the assertion even for infinite set families; if either family is empty, take $X=\varnothing$.

Take upward-closed set families of subsets of $[n]$ of size at most $\ell$, closed under the forcing rule in Razborov closure. Normalize any family containing a set of size at most one to the full family, since its clique predicate is identically true. Intersection is the meet in a lattice; closure of the union is the join in a lattice. A family represents the graphs containing a clique on at least one of its members. The approximate meet can lose positive inputs and the approximate join can acquire negative inputs. The Razborov gate-by-gate approximation lemma charges output errors to those local errors.

For two set families forbidding all cross-intersections in $[a,b]$, split into absent and present coordinate sections. The section pairs $({\mathcal{F}}_1,{\mathcal{G}}_1)$, $({\mathcal{F}}_0,{\mathcal{G}}_0\cup {\mathcal{G}}_1)$, and $({\mathcal{F}}_1,{\mathcal{G}}_0\cap {\mathcal{G}}_1)$ forbid, respectively, $[a-1,b-1]$, $[a,b]$, and $[a-1,b]$ in one fewer dimension. For $0<\delta \le 1/10$, either one of the first two pairs, allowing exchange of the set family names, increases the density product by at least $1+\delta$, or the third widens the interval and retains at least $1-\delta -2{\delta }^2$ of that product. This converts a single forbidden intersection into a long forbidden interval while recording every density gain and loss.

A Helly family of order $k$ is a set family for which every finite subfamily has nonempty total intersection whenever each of its subfamilies with at most $k$ members has nonempty intersection. Convex subtrees of a tree have Helly order two.