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.

Let $\mathcal{F}$ be a finite union-closed family whose union is nonempty. Some ground element belongs to at least a proportionof its members. Requiring a nonempty union excludes both the empty set family and $\{\varnothing \}$, for which no element can be chosen.

Here is the entropy mechanism. Choose independent uniform random members $A,B$ of $\mathcal{F}$. Then $H(A)=\log |\mathcal{F}|$ and $H(A\cup B)\le \log |\mathcal{F}|$, because the union still belongs to $\mathcal{F}$. If every element had probability at most $u<c$ of belonging to $A$, Will Sawin's binary entropy estimate would givea contradiction when $|\mathcal{F}|>1$. A singleton set family with nonempty union satisfies the conclusion directly.^[ref]

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.

In extremal set theory, a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ is constrained by its intersections, inclusions or traces, and one asks for the largest possible cardinality of $\mathcal{F}$. The choice of constraint is essential: without one, the whole Boolean lattice gives $2^n$ members.

For example, let $n\ge 1$ and require an intersecting family. A set and its complement of a set cannot both belong, so pairing all subsets with their complements gives $|\mathcal{F}|\le 2^{n-1}$. All subsets containing a fixed point attain equality. Adding a uniform-size requirement leads to the Erdős-Ko-Rado theorem.

An antichain instead forbids containment between distinct members. Sperner's theorem gives the sharp central-binomial bound, attained by a full middle level. Coordinate shifts of a set family simplify extremizers while preserving size; the polynomial method in combinatorics turns other intersection restrictions into linear independence. These two methods explain why a problem about subsets can become either an order argument or a vector space dimension 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.

A finite linear space consists of a finite set $P$ of points and a set family $\mathcal{L}$ of subsets called lines, each containing at least two points, such that each pair of distinct points lies on exactly one line. Here the nontrivial convention also excludes a line equal to all of $P$. Two distinct lines therefore meet in at most one point, and counting pairs givesNear-pencils and finite projective planes, including the Fano plane, are examples. The De Bruijn--Erdos pair-covering inequality concerns the corresponding point degrees. The original line-count theorem proves $|\mathcal{L}|\ge |P|$, with equality only for a near-pencil or a finite projective plane.^[ref]

An exactly one-intersecting family with empty total intersection gives such a structure by using its members as points. Each original ground element supplies the set of members containing it. Discard the resulting sets of size zero or one; the others are lines, and every pair of member-points belongs to its unique shared-element line. Empty total intersection excludes an all-point line.

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.

A set $H$ is a hitting set for a set family $\mathcal{F}$ if $H\cap A\ne \varnothing$ for every $A\in \mathcal{F}$. Every set is a hitting set for an empty set family; none is a hitting set for a family containing the empty set. Bounded hitting sets permit finite certificates for some infinite set families, as in the bounded-size transversal kernel.

Two ground elements are incidence-equivalent when they belong to exactly the same members of a set family. Their incidence columns are identical. For the set basis problem, deleting one of two such elements preserves the answer. A basis before deletion can be restricted to the smaller ground set. Conversely, if $x$ remains and $y$ was deleted, lift each reduced basis set $A$ to $A\cup \{y\}$ when $x\in A$, and leave it unchanged otherwise. In every union of lifted basis sets, $y$ appears exactly when $x$ appears, which restores precisely the original input sets. Repeated deletion thus leaves one representative of every incidence class.