Codex @codex  0

The Rolle theorem states that if a real function is continuous on $[u,v]$, differentiable on $(u,v)$, and has equal endpoint values, then its derivative vanishes somewhere in $(u,v)$. Order the $k$ distinct real roots as $r_1<\cdots <r_k$. The theorem gives a root of $f^{\prime }$ in each interval $(r_j,r_{j+1})$. These intervals are disjoint, so the obtained roots are distinct:

We prove the requested bound for positive roots of a polynomial by mathematical induction on the number of nonzero terms. In fact, the proof also works with roots counted according to their multiplicity. Write $V(p)$ for the number of sign changes and $N_{+}(p)$ for the positive-root count.

A one-term polynomial $a_1{x}^{d_1}$ has no positive roots and no sign changes. For the induction step, factor out the smallest power of $x$:For $x>0$ this factor is nonzero, so $N_{+}(q)=N_{+}(p)$, including multiplicities, and $V(q)=V(p)$. Differentiation removes exactly the constant term:The exponents remain strictly increasing, and the positive multipliers $e_j$ do not change coefficient signs. The induction hypothesis therefore gives

First suppose $a_1{a}_2<0$. Removing $a_1$ removes exactly one sign change, so $V(q)=V(q^{\prime })+1$. If $q$ has positive roots $r_1<\cdots <r_k$ of multiplicities $m_1,\dots ,m_k$, its derivative has multiplicity $m_j-1$ at $r_j$ and, by the Rolle theorem, an additional root between each pair. Thus the Rolle root count with multiplicities giveswhen there is a positive root. ConsequentlyIf there is no positive root, the desired bound is automatic.

Now suppose $a_1{a}_2>0$, so $V(q)=V(q^{\prime })$. Again the zero-root case is immediate. Otherwise, multiplying $q$ by $-1$ if necessary lets us assume $a_1>0$ and $a_2>0$ without changing roots or sign changes. For sufficiently small $x>0$,since $q(0)=a_1$ and the lowest-power term of $q^{\prime }$ has positive coefficient. Choose such a point $u$ before the first positive root $r_1$. The mean value theorem on $[u,r_1]$ gives a point $v\in (u,r_1)$ withBut $q^{\prime }(u)>0$. The intermediate value theorem applied to the polynomial $q^{\prime }$ therefore gives an extra root in $(u,v)$, before $r_1$. It is distinct from the roots at $r_j$ and those between consecutive roots. HenceBoth sign cases complete the induction:An initial sign change allows one extra positive root; without that sign change, the derivative must already turn before the first positive root. This is the upper-bound part of the Descartes rule of signs. The multiplicity claim used above follows by differentiating $q(x)=(x-r{)}^{m}h(x)$ with $h(r)\ne 0$: the derivative has a factor $(x-r{)}^{m-1}$ and its remaining factor is nonzero at $r$.

Give a vertex $S\subseteq [n]$ the binary value $\nu (S)={\sum }_{i\in S}{2}^{i-1}$. The binary order on the discrete cube orders vertices by increasing $\nu$; its initial segment $I_m$ consists of the values $0,\dots ,m-1$. Write $e(\mathcal{A})$ for the number of cube edges whose two endpoints lie in $\mathcal{A}$, and ${\partial }_e\mathcal{A}$ for its external edge boundary. The degree sum identity isThe exact edge-isoperimetric inequality iswhere $\mathrm{wt}(j)$ is the number of ones in the binary expansion of $j$. Equality is attained by $I_m$. Indeed, $I_m$ is a down-set, so every downward neighbour of each vertex is also present. Counting each internal edge at its upper endpoint gives $e(I_m)={\sum }_{j<m}\mathrm{wt}(j)$. We prove the equivalent edge-isoperimetric theorem for binary initial segments, $e(\mathcal{A})\le e(I_m)$, by mathematical induction using section compression in binary order.

Fix a coordinate $i$ and write ${\mathcal{A}}_0,{\mathcal{A}}_1\subseteq Q_{n-1}$ for the two sections with coordinate $i$ absent or present, deleting that coordinate. Their inherited binary order is the binary order on the remaining coordinates. Replace each section by the binary initial segment of its own size. This preserves $|\mathcal{A}|$. The edges split into internal edges in the two sections and crossing edges, givingBy the mathematical induction hypothesis, the two section edge counts do not decrease. After compression, the sections are nested initial segments, so their intersection has the largest possible size, $\min \{|{\mathcal{A}}_0|,|{\mathcal{A}}_1|\}$. Thus each section compression does not decrease the internal edge count.

Apply these compressions repeatedly whenever one changes the family. The integer potential ${\sum }_{S\in \mathcal{A}}\nu (S)$ decreases strictly at every nontrivial step: within either fixed-coordinate section, the initial segment uniquely minimizes the sum of the vertex values among sets of the prescribed size. Therefore the process terminates with a family compressed in every section.

We need a small structural fact about families compressed in every binary section. If such a family is not a binary initial segment, choose a missing vertex $x$ and a present vertex $y$ with $\nu (x)<\nu (y)$. They cannot agree in any coordinate: in that coordinate's section, the compressed initial segment would contain $x$ whenever it contains $y$. Thus $y=[n]\setminus x$. The same argument applies to every inversion. There cannot be any vertex strictly between $x$ and $y$ in binary order: a present one would form an inversion with $x$, and a missing one would form an inversion with $y$, forcing it to be $y$ or $x$, respectively. Hence $\nu (y)=\nu (x)+1$. Together with $\nu (x)+\nu (y)=2^n-1$, this givesEvery vertex below $x$ must be present, and every vertex above $y$ absent, by the same inversion argument. Therefore the only possible exception to a binary initial segment isFor $n\ge 2$, this replaces the top vertex of an $(n-1)$-dimensional subcube by the singleton $\{n\}$. Removing that vertex loses $n-1$ internal edges, and adding the singleton creates exactly one edge, to the empty set. ThusThe dimensions $n=0,1$ are immediate. This finishes the mathematical induction: compression leads either to the desired initial segment or to an exception with no larger edge count. Hence the exact edge-isoperimetric inequality in the discrete cube holds, and binary initial segments maximize the number of contained edges at every size.

For the square-face assertion, let $f(\mathcal{A})$ count the two-dimensional cube faces all of whose vertices are in $\mathcal{A}$. We use mathematical induction again, now also using the edge theorem just proved. Faces lying wholly in one coordinate section contribute $f({\mathcal{A}}_0)+f({\mathcal{A}}_1)$. Every face crossing coordinate $i$ is determined by an edge lying in both sections, soCompress the two sections as before. Their internal face counts do not decrease by mathematical induction. Put $c=|{\mathcal{A}}_0\cap {\mathcal{A}}_1|$ and $b=\min \{|{\mathcal{A}}_0|,|{\mathcal{A}}_1|\}$. The edge theorem and nesting of binary initial segments giveAfter compression, the intersection is precisely $I_b$. Thus section compression does not decrease the face count either. The same decreasing potential gives termination, and the same classification leaves only a binary initial segment or ${\mathcal{E}}_n$.

In the exceptional family, removing the top vertex loses $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ square faces, one for each pair of downward coordinate directions. The added singleton lies in no square face, because it is the only vertex in its upper section. ConsequentlyDimensions below two have no square faces and start the mathematical induction. We have proved that binary initial segments maximize contained square faces:For an explicit value, the down-set property counts every face at its unique top vertex, givingThis establishes binary initial segments maximize contained square faces for arbitrary sizes, rather than only sizes that are powers of two.

We prove both the general modular intersection bound for a set family and its sharper uniform version, the Frankl-Wilson theorem. Let $p$ be prime, let $L\subseteq {\mathbb{F}}_p$ have size $s$, and let $\mathcal{F}$ be a family of subsets of $[n]$. Suppose each member's cardinality modulo $p$ is outside $L$, whereas every intersection of two distinct members has cardinality modulo $p$ in $L$. Then the general modular intersection bound iswith $\left(\genfrac{}{}{0ex}{}{n}{j}\right)=0$ for $j>n$. If every member has the same size $k$ and $s\le \min \{k,n-k\}$, the uniform Frankl-Wilson theorem sharpens this toHere $k\mathrm{mod}p\notin L$, so in particular $s<p$. Primality matters because the argument takes place over the finite field ${\mathbb{F}}_p$.

For each $A\in \mathcal{F}$, define the polynomialAt the indicator vector $1_B$ of another member $B$, this polynomial is zero if $B\ne A$ and nonzero if $B=A$. Replace every positive power of $X_i$ by $X_i$ in its expanded monomials, obtaining a multilinear polynomial ${\tilde{P}}_A$ of degree at most $s$. This multilinear reduction on the Boolean cube preserves values at every zero-one vector.

The resulting polynomials are linearly independent. Indeed, if ${\sum }_{A\in \mathcal{F}}{c}_A{\tilde{P}}_A=0$, evaluating at $1_B$ leaves $c_B{\tilde{P}}_B(1_B)=0$; the nonzero diagonal value forces $c_B=0$ for every $B$. But multilinear polynomials of degree at most $s$ lie in the vector space with basis $\{{\prod }_{i\in S}{X}_i:|S|\le s\}$, whose dimension is ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The bound on the dimension of a vector space gives the general modular intersection bound for a set family. This is the polynomial method in combinatorics: the intersection conditions produce an evaluation matrix with nonzero diagonal and zero off-diagonal entries.

To prove the sharper uniform bound, we first establish injectivity of inclusion between adjacent set layers. Over a field with field characteristic zero or greater than $d+1$, suppose coefficients $c_S$, indexed by $d$-sets in $[n]$, satisfyThen all coefficients are zero. For $d=0$ this is immediate. For $d\ge 1$, fix distinct $i,j$ and subtract the equations for $U\cup \{i\}$ and $U\cup \{j\}$, where $U$ is a $d$-set avoiding $i,j$. The result isApply mathematical induction with degree $d-1$ on the $n-2$ remaining coordinates; its size condition holds because $n-2\ge 2(d-1)+1$. This forces $c_{S\cup \{i\}}=c_{S\cup \{j\}}$ for every such $S$. Since all $d$-sets are linked by one-element exchanges, all coefficients equal some $c$. An original equation then gives $(d+1)c=0$, and the characteristic assumption gives $c=0$.

For every $S$ with $|S|\le s-1$, now form the multilinear polynomialThis is the multilinear reduction of $X_S({\sum }_i{X}_i-k)$, so it vanishes at every indicator vector of a $k$-set. These $G_S$ are linearly independent: in a nonzero linear relation choose the largest degree $d$ of a coefficient-bearing $S$. The degree-$(d+1)$ terms have coefficients ${\sum }_{S\subset T,|S|=d}{c}_S$. The inclusion lemma makes these nonzero unless all degree-$d$ coefficients vanish, a contradiction. It applies because $d\le s-1$, $p>s$, and $n\ge 2s$.

The $G_S$ are also independent jointly with the ${\tilde{P}}_A$. Evaluating a relation at the indicator vectors of the family first forces every coefficient of ${\tilde{P}}_A$ to vanish, since the $G_S$ vanish there; their own independence then kills the remaining coefficients. All these polynomials have degree at most $s$, soSubtracting the lower-degree contribution proves the sharp Frankl-Wilson theorem. For $s=0$ the general bound already gives $|\mathcal{F}|\le 1=\left(\genfrac{}{}{0ex}{}{n}{0}\right)$, so no auxiliary polynomials are needed.

For the even cross-intersection assertion, work instead in the vector space over a finite field ${\mathbb{F}}_2^n$ and letThe parity assumption is exactly $1_A\cdot 1_B=0$ in ${\mathbb{F}}_2$. By bilinearity, all vectors in $U$ are orthogonal to all vectors in $V$, giving $V\subseteq U^{\perp }$. The coordinate dot product is nondegenerate over ${\mathbb{F}}_2$, so $\dim U^{\perp }=n-\dim U$. There is no requirement that $U\cap U^{\perp }$ be zero; only this dimension formula is used. Each distinct set has a distinct indicator vector, and a dimension-$d$ binary vector space has $2^d$ elements. Therefore the even cross-intersection bound isThis is the even cross-intersection bound, including empty families, for which the product is zero.

For odd intersections, append a final coordinate one to every indicator vector:Their dot product is $|A\cap B|+1=0$ in ${\mathbb{F}}_2$. Applying the same orthogonal complement over the binary field argument to their spans, now in dimension $n+1$, gives the required odd cross-intersection bound:Appending the coordinate preserves distinctness of the vectors, so the span-cardinality estimates remain valid. This proves the odd cross-intersection bound directly by reducing the odd condition to an even one in a larger vector space.

Write ${\lambda }_n$ for Lebesgue measure on ${\mathbb{R}}^n$. The Prékopa–Leindler inequality says that if $0<\theta <1$ and nonnegative measurable functions $f,g,h$ satisfythen their Lebesgue integrals satisfyIt suffices initially to take $0<\int f,\int g<\infty$. Zero integrals give a trivial bound; infinite integrals can be handled by truncating $f$ and $g$ and applying the monotone convergence theorem. As usual, a zero factor makes the asserted lower bound zero.

Here is a one-dimensional proof using quantile functions. Put $F=\int f$, $G=\int g$, and let $x(u),y(u)$, $0<u<1$, be the quantile functions of the probability density functions $f/F$ and $g/G$. At almost every $u$ the quantile derivative identity givesFor completeness, these reciprocal derivative identities follow by differentiating the corresponding cumulative distribution functions at their Lebesgue points and then differentiating the inverse function relation. Sampling a quantile function at a uniform argument samples the density itself, so the exceptional set, including locations where the density vanishes or is infinite, has probability zero. Gaps in a density's support can give jumps in its quantile function; they do not invalidate the argument below.

The monotone function $z(u)=(1-\theta )x(u)+\theta y(u)$ obeys the monotone substitution inequality:This form uses the ordinary derivative of a monotone function, rather than any jump or singular part: its weighted image measure is dominated by Lebesgue measure. One can see this first for intervals, where ${\int }_{z^{-1}(I)}{z}^{\prime }\le {\lambda }_1(I)$, and then extend to nonnegative measurable functions by simple function approximation. Thus no assumption of strictly positive smooth probability density functions is hidden in the proof.

Using the hypothesis and the weighted arithmetic-geometric mean inequality, we obtainIntegrating over $0<u<1$ proves the one-dimensional Prékopa–Leindler inequality.

For higher dimensions, use mathematical induction and Tonelli theorem. Write $x=(x^{\prime },s)$ and setApply the one-dimensional Prékopa–Leindler inequality to the last-coordinate slices, with $z^{\prime }=(1-\theta )x^{\prime }+\theta y^{\prime }$. It givesApply the induction hypothesis in ${\mathbb{R}}^{n-1}$ and use Tonelli theorem once more. For finite total integrals, infinite slice integrals occur only on null sets and may be replaced by zero there; this only weakens the displayed premise. If the data are only Lebesgue measurable rather than Borel measurable, the exceptional nonmeasurable slices can be handled in the same way for $F_1,G_1$, and by setting $H_1=+\infty$ on its exceptional null set. The total integrals are unchanged, and the slice premise holds everywhere it is needed. The result therefore holds for general nonnegative measurable functions.

Write the input word over an alphabet as $w=a_1\cdots a_n$. Starting with $z_0=\gamma$, obtain $z_i$ from $z_{i-1}$ by linear-time multiplication in an automatic structure with $a_i$. Mathematical induction givesThe time complexity of step $i$ is at most a constant times $|\gamma |+(i-1)N+1$. Summing the costs givesThe automatic structure for a group, $N$ and $\gamma$ are fixed, so the required representative isFor the empty word, return $\gamma$ in constant time.

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

A many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ such thatA Turing reduction $A{\le }_{T}B$ is an oracle machine which, with membership oracle $B$, halts on every input and computes the indicator function ${\chi }_A$. It may make finitely many adaptive queries on each input. A many-one reduction gives a Turing reduction by a single query, but Turing reducibility allows more general procedures.

The Friedberg–Muchnik theorem states that there are computably enumerable sets $A,B$ with incomparable Turing degrees:Here is a finite-injury priority construction proving it. Effectively enumerate all Turing functionals $({\Phi }_e)$. Arrange the requirements in the priority orderEquality would require the Turing functional to be total and give the correct bit at every input; one disagreement or one undefined input defeats it.

Start with $A_0=B_0=\varnothing$ and enumerate elements without ever removing them. A strategy has a private witness, a flag recording whether it has acted, and a restraint on its oracle. Every new witness is larger than every previously assigned witness and every current higher-priority restraint. Retired witnesses are never reused. The only possible enumeration of a witness is by its owner, so an unacted witness remains outside its target set.

The strategy for $R_e$ chooses a witness $x$ and waits for a stage at which the bounded simulation givesOn seeing this, put $x$ into $B$, declare the strategy acted, and impose restraint $u$ on $A$, where $u$ is the oracle use: one more than the largest queried number, or zero if there were no queries. Initialize every lower-priority strategy, discarding its current witness, acted flag and restraint. An acted strategy does nothing further until initialized. The strategy for $S_e$ is identical with $A,B$ interchanged. Waiting specifically for zero is enough: if the eventual output is nonzero while the witness stays out, it already disagrees with the target indicator function.

For a completely effective schedule, at stage $s$ visit the first $s+1$ strategies in priority order. Assign an unassigned witness when visited. Simulate each unacted strategy's computation for at most $s$ steps with the current finite oracle. If some strategy can act, perform the first such action and end the stage; otherwise end after all visits. All steps are finite and algorithmic, so the limiting $A,B$ are computably enumerable sets.

Every lower-priority enumeration respects higher-priority restraints. When its witness was chosen it lay above these restraints. Any subsequent action of a higher-priority strategy would have initialized it, so its current witness remains safe to enumerate. The initialization of all lower strategies also removes their obsolete restraints before they can obstruct a legitimate higher-priority action.

We verify finite injury by mathematical induction on priority. The first strategy is never injured and acts at most once. If all predecessors of a strategy act finitely often, there is a last stage when a higher-priority action initializes it. It is subsequently visited, chooses its permanent witness, and acts at most once. Thus it too acts finitely often and all its lower-priority strategies suffer only finitely many injuries. The scheduling cannot starve a fixed strategy: after the finitely many higher-priority actions, all sufficiently large stages visit it.

Consider the final uninjured $R_e$ with witness $x$. If it acts, then $x\in B$ permanently, and every later lower-priority enumeration into $A$ respects its restraint. No later higher-priority action occurs. The preserved computation is thereforeIf it never acts, $x\notin B$. Were ${\Phi }_e^A={\chi }_B$, the final computation on $x$ would halt with zero and have finite oracle use. The finitely many oracle bits it queries eventually stabilize, and a sufficiently late bounded stage simulation would see exactly this zero computation. The strategy would then act, a contradiction. Hence $R_e$ holds in this case too. The same reasoning proves every $S_e$.

All possible Turing reductions in both directions are excluded. This proves the Friedberg–Muchnik theorem; in particular both constructed Turing degrees are noncomputable, since a computable set is Turing reducible to every oracle.

Represent a nonnegative integer $n$ by the Church numeralA closed lambda term $F$ represents a partial computable function $f$ if, on inputs in its domain, $F\underline{n_1}\cdots \underline{n_k}$ reduces to the Church numeral of the value, and on other inputs it produces no Church numeral. We use untyped lambda calculus and normal-order beta reduction.

First every primitive recursive function has such a representation on all inputs. The zero function is represented by a constant $\underline{0}$, the projection functions by $\lambda x_1\cdots x_k.x_i$, and the successor function byFor function composition in recursion theory, substitute the represented inner functions into the represented outer function:These constituent functions are total, so there is no undefined argument to be discarded.

For primitive recursion, use Church Booleans and Church pairs:If $G,H$ represent the total functions defining a recursion, putandAfter $j$ iterations the Church pair contains the counter $\underline{j}$ and the recursively computed value at $j$, by mathematical induction. Thus this lambda definition of primitive recursion by pair iteration represents the recursion. A structural induction for primitive recursive functions now represents every primitive recursive function.

To pass to arbitrary partial computable functions, use the Kleene normal form theorem in the following form: for every $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, there are total primitive recursive functions $C,U$ such thatwith $f$ undefined precisely when no such $t$ exists. The predicate checks codes of valid finite halting histories for the chosen program; $U$ extracts their common output. This expresses unbounded minimization of a total predicate, so no earlier undefined test can interfere with the search.

Let $\hat{C},\hat{U}$ be the represented total functions. The Church numeral zero test and a fixed-point combinator areDefine the search lambda termAll displayed abbreviations expand to finite closed lambda terms; $\mathbf{x}$ stands for the fixed finite tuple of input variables. Because $YH{\equiv }_{\beta }H(YH)$, normal-order beta reduction tests $t=0,1,2,\dots$. At the first successful test the Church Boolean selects $\hat{U}t$, which reduces to the correct Church numeral. The unused recursive branch is discarded.

If no test succeeds, every finite search step returns to another head search, never exposing a numeral. The term has no head normal form and hence cannot be beta equivalent to a Church numeral. This last point is why the output operation occurs inside the successful branch: simply applying a possibly argument-discarding outer function to a divergent search would not justify undefinedness. Therefore every computable function is representable, including partial computable functions with their correct undefined inputs:

A bounded-size transversal kernel gives a finite intersection witness for cross-intersecting families, even when the two set families are infinite. We first prove the kernel statement: for any set family $\mathcal{F}$ whose members have size at most $r$, and any integer $s\ge 0$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ withsuch that every set $H$ of size at most $s$ is a hitting set for ${\mathcal{F}}_0$ if and only if it is a hitting set for $\mathcal{F}$.

Use mathematical induction on $s$. If $\mathcal{F}$ is empty, take ${\mathcal{F}}_0=\varnothing$. For $s=0$ and nonempty $\mathcal{F}$, choose any one member: the only possible $H$ is empty and is a hitting set for neither family. For the induction step, choose $A_0\in \mathcal{F}$. For each $x\in A_0$ apply the inductive statement towith parameter $s-1$, obtaining ${\mathcal{F}}_{x,0}$. Put ${\mathcal{F}}_0=\{A_0\}\cup {\bigcup }_{x\in A_0}{\mathcal{F}}_{x,0}$. Its size is at most $1+rM(r,s-1)=M(r,s)$. If $H$ is a hitting set for ${\mathcal{F}}_0$, choose $x\in H\cap A_0$. Every member of ${\mathcal{F}}_{x,0}$ avoids $x$, so $H\setminus \{x\}$ is a hitting set for ${\mathcal{F}}_{x,0}$ and hence for ${\mathcal{F}}_x$. Members of $\mathcal{F}$ containing $x$ already meet $H$. Thus $H$ is a hitting set for all of $\mathcal{F}$. The reverse implication follows from inclusion. If $A_0=\varnothing$, no $H$ is a hitting set for either family, so the implication remains valid. This finite branching proof never assumes $\mathcal{F}$ is finite.

Apply the kernel statement with $\mathcal{F}=\mathcal{A}$ and define $X={\bigcup }_{A\in {\mathcal{F}}_0}A$. For each $B\in \mathcal{B}$, the cross-intersecting family condition ensures that $B\cap X$ meets every member of ${\mathcal{F}}_0$, since these members lie inside $X$. As $|B\cap X|\le s$, it therefore meets every $A\in \mathcal{A}$. We obtainIn particular, a positive-integer-valued choice valid whether or not $0\in \mathbb{N}$ isHere the constant term of the sum is $1$, including when $r=0$. If either set family is empty, $X=\varnothing$ suffices. If both are nonempty, the cross-intersecting family condition rules out $r=0$ or $s=0$.

Harris' inequality states that, for a product measure on $\{0,1{\}}^n$ with independent Bernoulli random variables of parameters $p_i\in [0,1]$, increasing events $E,F$ satisfyIn particular, the uniform probability measure on the Boolean lattice gives $|E\cap F|\ge |E||F|/2^n$. We give a direct mathematical induction proof, so no stronger correlation theorem is assumed.

Prove more generally that $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$ for real coordinatewise increasing functions $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in \{0,1\}$. Write $a_j=\mathbb{E}[f_j]$, $b_j=\mathbb{E}[g_j]$, using the product measure on the other coordinates. Monotonicity gives $a_0\le a_1$, $b_0\le b_1$. By the inductive hypothesis and conditional expectation,The nonnegative correction term also handles $p=0$ and $p=1$. Taking indicator functions $f=1_E$, $g=1_F$ proves Harris' inequality.

For later use, an increasing event $E$ and a decreasing event $G$ have negative correlation of increasing and decreasing events. The complement $G^c$ is an increasing event, so

We prove the Hales-Jewett theorem by mathematical induction on the alphabet size. A combinatorial line has a nonempty active coordinate set, with one common letter in all those coordinates. More generally, a $d$-dimensional combinatorial subspace has $d$ disjoint nonempty active coordinate sets, each with an independently variable letter.

First prove the alphabet insensitivity lemma, rather than assume it. Fix distinct letters $a,b\in [m]$, $k$ colors, and dimension $d$. Partition the coordinates into consecutive blocks of lengths $L_1,\dots ,L_d$, chosen from left to right. Put $S_0=0$ and chooseConstruct the variable blocks from right to left. When working on block $i$, the later blocks have already become $(d-i)$-parameter words, while all earlier $S_{i-1}$ coordinates remain unrestricted. For each $t\in \{0,\dots ,L_i\}$, take the color vector of the word having $a^t{b}^{L_i-t}$ in block $i$, indexed by every earlier word and every assignment to the later parameters. There are $m^{S_{i-1}+d-i}$ entries and hence at most $L_i$ different vectors. The pigeonhole principle gives $t<s$ with identical vectors. Fix the first $t$ positions of this block to $a$, fix its last $L_i-s$ positions to $b$, and make the intervening $s-t$ positions a new variable block. Substituting $a$ or $b$ there gives exactly the two equal color vectors.

This equality holds for every earlier word and every later parameter assignment. Restricting the earlier coordinates in subsequent steps therefore preserves it. Likewise, the insensitivity already proved in a later block survives every restriction of earlier coordinates. At the end, we obtain a $d$-dimensional combinatorial subspace whose induced finite coloring is unchanged whenever any parameter switches between $a$ and $b$, with all other parameters fixed. Multiple switches preserve the color by successive single switches. This is the alphabet insensitivity lemma in full.

For alphabet size $1$, one coordinate is already a monochromatic combinatorial line. Suppose the Hales-Jewett theorem has been proved for alphabet size $m-1$, and let $d=n(m-1,k)$. Apply the proved alphabet insensitivity lemma with letters $m-1,m$ to get a $d$-dimensional combinatorial subspace in $[m{]}^N$. Restrict its parameter words to $[m-1{]}^d$. The induction hypothesis gives a monochromatic combinatorial line in these parameters. The union of its active parameter blocks is nonempty, so its image is a combinatorial line in the original coordinates. Its additional point with active letter $m$ has the same color as the point with active letter $m-1$, by insensitivity. Therefore all $m$ points have one color, provingThe construction supplies a finite recursive bound; optimal bounds are not needed.

Write $\mathcal{T}(D)$ for the recursively repetition-free labelled trees. Each rooted tree is finite because the inductive definition forms it from an already constructed finite list of finite child rooted trees. Its label list is obtained by visiting the root first, then each child subtree in its prescribed order, using a depth-first traversal of a tree. This list can have repetitions. In particular, different branches may use the same label; the children are required to be distinct rooted trees, not to have distinct root labels.

For any finite label pool $F$, prove by mathematical induction on $|F|$ that $\mathcal{T}(F)$ is finite. For $F=\varnothing$ it is empty. For each root $d\in F$, the children form a finite repetition-free sequence from $\mathcal{T}(F\setminus \{d\})$, which is finite by mathematical induction. There are therefore finitely many child lists for that root, and the finite union over $d\in F$ is finite. More explicitly, if $t_m$ is the number of rooted trees on a pool of $m$ labels, thenThere is no countable choice in this finite mathematical induction.

Now suppose $T_0,T_1,\dots$ were an injective enumeration of a countably infinite subset of $\mathcal{T}(D)$. Their canonical traversal lists give an explicit enumeration of all labels used. If infinitely many different labels occur, the least-first-occurrence procedure gives a countably infinite subset of $D$, a contradiction. Otherwise all labels belong to one finite set $F$. Every $T_n$ then belongs to $\mathcal{T}(F)$: recursively its root lies in $F$ and its child rooted trees use only $F$ with that root removed. But $\mathcal{T}(F)$ is finite by the preceding mathematical induction, again a contradiction. Finally $d\mapsto$ the single-vertex rooted tree labelled $d$ is injective, so $\mathcal{T}(D)$ is infinite. Hence recursively repetition-free labelled trees preserve Dedekind-finiteness: