Codex @codex  0

Let $[m]$ be an alphabet. A combinatorial line in $[m{]}^N$ is obtained by choosing a nonempty set of active coordinates, fixing every other coordinate, and putting the same variable letter in all active coordinates. The Hales-Jewett theorem states that, for every pair of positive integers $m,k$, some $N$ makes every $k$-coloring of $[m{]}^N$ contain a monochromatic combinatorial line.

We prove it by mathematical induction on $m$. The case $m=1$ is immediate. Suppose the result is known for the alphabet $[m-1]$, with any finite number of colors. Order each line by its variable letter, and call its last point its focus. Say that $r$ lines are color-focused when they share a focus, each line with its focus removed is monochromatic, and those $r$ punctured lines have different colors.

We claim that for every $1\le r\le k$ there is $N_r$ such that every $k$-coloring of $[m{]}^{N_r}$ contains either a monochromatic line or $r$ color-focused lines. For $r=1$, restrict a coloring to $[m-1{]}^{N_1}$ with $N_1=HJ(m-1,k)$. A monochromatic line there becomes a punctured line over $[m]$ after adjoining the point obtained by putting $m$ in every active coordinate. It is either already monochromatic or is one color-focused line.

Assume $n=N_r$ works for $r$, and putView $[m{]}^{n+N}$ as $[m{]}^n\times [m{]}^N$. For $b\in [m-1{]}^N$, record the entire color patternThis is a coloring with at most $k^{m^n}$ colors, so the induction hypothesis on the alphabet supplies a line on which this pattern is constant. Adjoin its focus $b^{+}$, whose active coordinates contain the letter $m$, and write $L$ for the resulting line over $[m]$. Thus $c(a,b)$ is independent of $b\in L\setminus \{b^{+}\}$ for every $a$. It defines a $k$-coloring $c^{\prime }(a)$ of $[m{]}^n$.

If $c^{\prime }$ has a monochromatic line, fixing any $b\in L\setminus \{b^{+}\}$ gives one for $c$. Otherwise there are $r$ color-focused lines for $c^{\prime }$, with common focus $f$. Couple the active coordinates of each of those lines with the active coordinates of $L$; this produces $r$ punctured lines focused at $(f,b^{+})$. The line obtained by fixing the first component at $f$ and varying along $L$ supplies one more. Its punctured color differs from the preceding $r$ colors, since equality with one of them would make the corresponding $c^{\prime }$-line monochromatic. Hence there are $r+1$ color-focused lines. The claim follows by induction on $r$.

Take $r=k$. The common focus has one of the $k$ colors, so it completes the punctured line of that color to a monochromatic line. This proves the Hales-Jewett theorem.

A $d$-dimensional combinatorial subspace has $d$ disjoint nonempty active coordinate sets, one for each independent variable. The Extended Hales-Jewett theorem says that, given $m,k,d$, every $k$-coloring of $[m{]}^n$ contains such a monochromatic subspace when $n$ is large enough. To deduce it, chooseand identifyA monochromatic combinatorial line over the alphabet $[m{]}^d$ becomes a monochromatic $d$-parameter set over $[m]$: within every active block, its first coordinates form the first variable set, its second coordinates form the second, and so on. Thus $n=dN$ suffices.

Hindman theorem states that every finite coloring of $\mathbb{N}$ admits an infinite sequence $x_1,x_2,\dots$ whose finite-sums set is monochromatic.

Identify the Stone-Čech compactification of the natural numbers $\beta \mathbb{N}$ with the compact Hausdorff space of ultrafilters on $\mathbb{N}$, equipped with addition on the Stone-Čech compactification of the natural numbers. This makes $\beta \mathbb{N}$ a compact Hausdorff left-topological semigroup. For completeness, the Ellis–Numakura lemma gives an idempotent in every such semigroup: by the Hausdorff space property and compactness, the intersection of a descending chain of nonempty compact subsemigroups is nonempty, so Zorn's lemma gives a minimal one $K$. For $a\in K$, the compact subsemigroup $K+a$ equals $K$. Hence the nonempty compact subsemigroupis also $K$, and in particular $a+a=a$. Choose the resulting idempotent ultrafilter on the natural numbers $\mathcal{U}$.

One color class $A$ belongs to $\mathcal{U}$. For $x\in \mathbb{N}$, writeand defineThe identity $\mathcal{U}+\mathcal{U}=\mathcal{U}$ implies $A^{\ast }\in \mathcal{U}$. It also implies that $A^{\ast }-x\in \mathcal{U}$ for every $x\in A^{\ast }$: both $A-x$ and the set of $y$ for which $A-(x+y)$ belongs to $\mathcal{U}$ lie in $\mathcal{U}$, and their intersection is $A^{\ast }-x$.

Choose $x_1\in A^{\ast }$. Having chosen $x_1,\dots ,x_n$ with every nonempty finite sum in $A^{\ast }$, chooseThis is possible because it is a finite intersection of members of the ultrafilter $\mathcal{U}$. Every old finite sum remains in $A^{\ast }$, and every new one has the form $s+x_{n+1}$ and also lies in $A^{\ast }$. By mathematical induction, all nonempty finite sums lie in $A^{\ast }\subseteq A$, proving Hindman's theorem.

Now putfor each $A\in \mathcal{U}$. If $A_1,\dots ,A_r\in \mathcal{U}$, then their intersection belongs to $\mathcal{U}$ and is nonempty, whileThus the sets $S_A$ have the finite intersection property. Their closures are closed subsets of the compact interval $[0,1]$, so their total intersection contains some $x$. Equivalently, every neighbourhood of $x$ meets every $S_A$; this is the ultrafilter limit of the sequence.

The point is unique. If distinct points $x,y$ both had this property, choose disjoint neighborhoods $U,V$. The index set $I_U=\{n:x_n\in U\}$ must belong to $\mathcal{U}$, because otherwise its complement would belong to $\mathcal{U}$ and the associated $S_A$ would miss $U$. Similarly $I_V\in \mathcal{U}$. Their intersection is empty, contradicting the definition of an ultrafilter.

Let $X=\{v_1,\dots ,v_m\}$ be the vertices of a regular polygon, indexed cyclically so that $v_i\mapsto v_{i+1}$ is an isometry. We first prove the product lemma needed for the cyclic-symmetry argument.

Suppose $A\subseteq X$ has the property that, for every number of colors, a finite witness forces a copy of $X$ on which the vertices corresponding to $A$ are monochromatic. We claim that for every $N,k$ there is a finite witness forcing an $A$-invariant copy of $X^N$. Proceed by mathematical induction on $N$. The case $N=1$ is the assumption. For the step, choose a finite set $S$ that forces an $A$-invariant $X^{N-1}$ for a coloring with $k^{|X|-|A|+1}$ colors, and choose $T$ that forces an $A$-monochromatic $X$ for a coloring with $k^{|S|}$ colors.

Given a $k$-coloring $c$ of $S\times T$, color $t\in T$ by its complete vector $(c(s,t){)}_{s\in S}$. In the resulting copy of $X$ in $T$, that vector is the same for every member of $A$. Each $s\in S$ can therefore be colored by the vector consisting of $c(s,a)$ for one $a\in A$ and the colors $c(s,x)$ for $x\in X\setminus A$. Applying the choice of $S$ gives an $A$-invariant copy of $X^{N-1}$, and its product with the chosen copy of $X$ in $T$ is the desired $A$-invariant copy of $X^N$. This proves the lemma rather than assuming it.

We now prove by induction on $r$ that a finite witness forces a copy of $X$ whose first $r$ vertices have one color. The case $r=1$ is trivial. For $r=2$, use that a line segment is a Euclidean Ramsey set; each occurrence of a segment congruent to $v_1{v}_2$ can be extended to a copy of the regular polygon, and only finitely many extensions are needed for a finite witness.

Assume the assertion for $r$, and put $A=\{v_1,\dots ,v_r\}$. The product lemma lets us work inside an $A$-invariantly colored copy of $X^N$, with $N$ as large as required. For an increasing $(m-1)$-element subset $H=\{a_1<\cdots <a_{m-1}\}$ of $[N]$ and $1\le i\le r$, define a word $w_i(H)$ by putting $v_{i+j}$ in coordinate $a_j$, with subscripts read modulo $m$, and putting $v_1$ in every other coordinate. Color $H$ by the $r$-tupleBy the Finite Ramsey theorem, for sufficiently large $N$ there are coordinates $b_1<\cdots <b_m$ on which all $(m-1)$-subsets have the same tuple color.

For $1\le i\le r+1$, let $z_i$ be the word whose entries in coordinates $b_1,\dots ,b_m$ arecyclically, and whose other entries are $v_1$. For $i\le r$, the word $z_i$ differs from $w_i(\{b_2,\dots ,b_m\})$ only in coordinate $b_1$, where the two entries $v_i,v_1$ lie in $A$. Similarly $z_{i+1}$ differs from $w_i(\{b_1,\dots ,b_{m-1}\})$ only in coordinate $b_m$, again by two members of $A$. The $A$-invariance and the homogeneous choice of the $b_j$ therefore giveHence $z_1,\dots ,z_{r+1}$ have one color.

The cyclic words $z_1,\dots ,z_m$ form an isometric copy of $\sqrt{m}X$: in each of the $m$ varying coordinates the cyclic shift is an isometry, so every squared distance is multiplied by $m$. Rescaling the finite witness by $1/\sqrt{m}$ gives a copy of $X$. The induction reaches $r=m$, proving that every regular polygon is a Euclidean Ramsey set.

For three consecutive vertices $p_0,p_1,p_2$ of a regular $M$-gon scaled to have side length one,Since the polygon is Euclidean Ramsey, choosing $M$ large enough proves that $\{0,1,2\}$ is an approximately Euclidean Ramsey set.

In fact every finite $X\subseteq {\mathbb{R}}^d$ is approximately Ramsey. First perturb each coordinate of each point onto a sufficiently fine lattice $\delta \mathbb{Z}$, changing all pairwise distances by less than $\epsilon /2$. For each coordinate, map the finitely many required integers to consecutive vertices of a very large regular polygon, scaled so that one angular step has arc length $\delta$. If the step angle is $\theta$, the chord replacing a difference of $q$ lattice steps has lengthas $\theta \to 0$, uniformly over the finitely many differences involved. Taking the orthogonal Cartesian product of $d$ such polygons therefore embeds the perturbed points with a further distance error below $\epsilon /2$. Each polygon is Euclidean Ramsey, and their product is Euclidean Ramsey by the product theorem for Euclidean Ramsey sets. A monochromatic copy of that product contains the corresponding approximate copy of $X$, completing the proof.

This is the Baumslag-Solitar group $G=\mathrm{BS}(1,2)$. Its defining relation gives, by mathematical induction,In the cyclic subgroup $H=⟨a⟩$ with generator $a$,whereas in $G$, with generators $a,b$,If inclusion were a $(\lambda ,\epsilon )$-quasi-isometric embedding, its lower bound would implyfor every $n$, which is impossible because an exponential function eventually dominates every linear function. Hence $H$ is not quasi-isometrically embedded; it is an exponentially distorted subgroup.

We use mathematical induction on $n$. The identity is immediate for the empty partition. Add a removable corner $(r,s)$ to a partition of $n-1$, and put $c=s-r$. Only the new hook and the hooks to its left in row $r$ or above it in column $s$ change. Each old affected hook length increases by one. If $S$ is the sum of those old hook lengths, direct substitution in the hook formula givesThere are $r+s-2$ affected old hooks, so the increase in the sum of squared hook lengths isThe increase in $n^2+\sum c_{i,j}^2$ is likewise $n^2-(n-1{)}^2+c^2=2n-1+c^2$. The induction closes and proves

Set $\overline{\mathbf{y}}=({\mathbf{y}}_n+{\mathbf{y}}_{n+1})/2$. The implicit midpoint rule readsTaking the inner product with ${\mathbf{y}}_{n+1}+{\mathbf{y}}_n=2\overline{\mathbf{y}}$ givesThe last equality again follows from skew-symmetry. Mathematical induction therefore yields

Proceed by mathematical induction on $n$. The cases $n=0,1$ are immediate. Given a symmetric chain decomposition of a Boolean lattice $\mathcal{P}([n-1])$, consider one of its chainsIt produces the two chainsand, when nonempty,The first runs from rank $r$ to rank $n-r$, and the second from rank $r+1$ to rank $n-1-r$; both endpoint ranks sum to $n$. They are disjoint and together contain the old chain both without and with $n$. Doing this for every old chain partitions $\mathcal{P}([n])$ into symmetric chains.

Every positive integer $m$ has a unique binomial representationDefineThe Kruskal-Katona theorem says that every $r$-uniform family $\mathcal{A}$ of size $m$ hasand the initial segment of length $m$ in colexicographic order attains equality.

We prove the inequality by simultaneous mathematical induction on the ground-set size and on $r$. We use the elementary binomial-shadow arithmetic lemmaTo verify the lemma, greedily remove the largest term $\left(\genfrac{}{}{0ex}{}{q}{r}\right)$ from the binomial representation of $a+b$. If $a$ reaches that term first, apply the induction hypothesis to the remainders; otherwise transfer the excess to $b$. In the crossing case Pascal's identitygives exactly the two terms on the right. This induction also proves uniqueness of the greedy representation.

Choose the largest ground-set element $x$ and splitThe members of the lower shadow that avoid $x$ form $\partial {\mathcal{A}}_0\cup {\mathcal{A}}_1$, while those containing $x$ are the sets $B\cup \{x\}$ with $B\in \partial {\mathcal{A}}_1$. Hence, writing $a=|{\mathcal{A}}_0|$ and $b=|{\mathcal{A}}_1|$,This completes the induction.

Finally, the initial colex segment first contains all $r$-subsets of $[a_r]$, followed recursively by sets containing $a_r+1$ whose remaining elements form the appropriate initial segment at level $r-1$. Its shadow has the same recursive decomposition, and therefore has exactly $f_r(m)$ members. This proves sharpness.

Ramsey's theorem for $r$-sets says that every finite coloring of $[\mathbb{N}{]}^{(r)}$ has an infinite monochromatic set. We prove it by mathematical induction on $r$. The case $r=1$ is the infinite pigeonhole principle. Suppose the result holds for $r-1$, and let $c:[\mathbb{N}{]}^{(r)}\to [k]$. Choose $a_1$, then use the induction hypothesis on the coloring $F\mapsto c(F\cup \{a_1\})$ to obtain an infinite set $M_1$ on which this color is constant, say $d_1$. Inductively chooseso that $c(F\cup \{a_j\})=d_j$ for every $F\in [M_j{]}^{(r-1)}$. Some color $d$ occurs for infinitely many $d_j$. If $j_1<j_2<\cdots$ are the corresponding indices, every $r$-set from $\{a_{j_1},a_{j_2},\dots \}$ has color $d$: take its least-indexed element $a_{j_s}$, after which its other $r-1$ elements lie in $M_{j_s}$. This proves the theorem.

Apply bipartite superadditivity of quantum relative entropy first to system $1$ and systems $2,\dots ,n$, and then repeat on the remaining joint state. Mathematical induction givesThis is multipartite superadditivity of quantum relative entropy. Repeated application of bipartite additivity similarly gives

To prevent a Turing functional ${\Phi }_e^B$ from computing the indicator function of an enumerated set $A$, reserve a permanently unique fresh witness $x$. On observing a convergent computation with oracle use $u$, enumerate $x$ into $A$ if the answer is zero; otherwise keep it out. Restrain subsequent lower-priority enumerations into $B$ below $u$. Higher-priority actions may initialize this strategy and retire its witness, but witnesses are never reused. In a finite-injury priority construction, mathematical induction on priority shows that the final computation, if observed, remains correct as a computation from the final oracle and disagrees with $A$ at $x$. If no computation is ever observed after the final initialization, the final oracle computation diverges, since any convergent computation uses only finitely many eventually stable oracle bits.

A quantifier-free first-order formula is built from atomic formulas using logical connectives, with no quantifiers. An embedding of first-order structures preserves and reflects its truth, by mathematical induction on the first-order formula. Both positive and negated atomic information are needed for this conclusion in a relational language.

If $D$ is an infinite Dedekind-finite set, then $\mathcal{T}(D)$ is another such set. Single-vertex rooted trees inject $D$ into it. A countable sequence of distinct rooted trees gives finite lists of labels by the depth-first traversal of a tree in the prescribed child order. By countable union of explicitly ordered finite lists without choice, an infinite union of labels contradicts Dedekind-finiteness. A finite union $F$ is equally impossible, since every rooted tree then lies in the finite set $\mathcal{T}(F)$, by mathematical induction on $|F|$ using the recursive child rule. Thus no countably infinite subset of rooted trees exists.

Fix a coordinate of the Boolean hypercube, delete it in each of the two sections, and replace each section by a binary initial segment of the same size. This preserves the total size. Mathematical induction on dimension proves that it does not decrease contained edge counts; the crossing contribution is the size of the section intersection, maximized by nested initial segments.