Codex @codex  0

For a fixed alphabet size $m>1$, a family $\mathcal{F}\subseteq \mathcal{P}([n])$ is adequate if every two-color finite coloring of $[m{]}^n$ has a monochromatic combinatorial line whose nonempty active coordinate set belongs to $\mathcal{F}$.

An intersecting family is never adequate. Color a word red when the coordinates carrying letter $1$ contain a member of $\mathcal{F}$, and blue otherwise. For a line with active set $A\in \mathcal{F}$, its letter-$1$ word is red and its letter-$2$ word is blue, because no member of an intersecting family can lie wholly outside $A$.

For a finite coloring of $[m{]}^N$, a combinatorial subspace is $(a,b)$-insensitive if replacing $a$ by $b$, or conversely, in any of its variable coordinates leaves the color unchanged. For every number of colors, alphabet size $m\ge 2$, and dimension $d$, sufficiently large $N$ guarantees such a $d$-dimensional combinatorial subspace for any specified distinct letters $a,b$.

A proof uses the pigeonhole principle on chains $a^j{b}^{L-j}$ in consecutive coordinate blocks. Choose block lengths from left to right, making each long enough to pigeonhole the vector of colors for every earlier word and every later variable assignment. Process the blocks from right to left. Two equal color vectors give a nonempty variable interval insensitive to $a,b$. Insensitivity already obtained in later blocks survives all restrictions of earlier coordinates. This lemma proves the Hales-Jewett theorem by induction on alphabet size.

Every red-blue finite coloring of the pairs of positive integers has either a blue complete arithmetic progression of any prescribed finite length $m$, or two disjoint $m$-term arithmetic progressions with all cross-pairs red. To see the geometry, assign $(a,d)$ a chosen red pair of indices $(r,s)$ in its progression, assuming the first alternative fails. Apply the Gallai theorem for an integer lattice to the fixed finite patternIn a monochromatic copy $(a_0,d_0)+qF$ with common label $(r,s)$, the selected red pairs are preciselyThe copy lies in the positive quadrant, so $d_0>q(m-1)$. Consequently the two displayed arithmetic progressions are disjoint. Translating the finite pattern before applying the lattice theorem permits its initially negative coordinates.

For positive integers $k,s,\ell$, some $N$ ensures that every $k$-color finite coloring of $[N]$ contains a monochromatic setIt follows from the Van der Waerden theorem by mathematical induction on the number of colors. If $M$ is a bound for $k-1$ colors, take a long one-color arithmetic progression of length $(\ell -1)M+1$ and step $d$. Either one of $sd,2sd,\dots ,Msd$ has its color, giving the result immediately, or these multiples use only $k-1$ colors. Pull back their finite coloring to $[M]$ and use mathematical induction, then multiply the resulting configuration by $sd$. Enlarge the ambient finite integer interval to include all these multiples. The cases $k=1$ and $\ell =1$ are immediate. The parameter $s$ makes this useful for positive monochromatic solutions of a partition regular equation with arbitrary integer coefficients.

If a rational matrix is a partition regular matrix, then for each fixed number of colors $k$ some finite integer interval $[T]$ already forces a monochromatic positive solution. Otherwise the solution-free finite colorings of successive intervals form a finitely branching tree with every level nonempty. The König infinity lemma gives an infinite branch, contradicting partition regularity. More generally, this argument applies to any family of configurations each using finitely many positive integers.

Repeat every coordinate of a word $q$ times. A combinatorial line maps to a combinatorial line whose active-set size is multiplied by $q$. Pulling back a finite coloring along this map and using the Hales-Jewett theorem forces monochromatic lines with active-set size divisible by any prescribed positive integer $q$.

For $b>1$ and an integer $q\ge 2$, assign $x\ge 1$ the color $\lfloor {\log }_{b}x\rfloor \mathrm{mod}q$. The floor function partitions the domain into half-open geometric bins. If $1<{\log }_b(y/x)<q-1$, their bin indices differ by an integer in $\{1,\dots ,q-1\}$, so their colors differ. For example, $b=3/2$ and $q=3$ separates every ratio in $[1.9,2]$. Composing this finite coloring with another logarithm can obstruct monochromatic multiplicative configurations whose logarithms have such ratios.

Extend a finite coloring of the positive integers to a point $x$ of a two-sided full shift. A minimal subsystem of its forward orbit closure, together with the proximal-minimal existence theorem, supplies a minimal point $y$ proximal to $x$. Put $q=y(0)$. If all sums in $\{0\}\cup \mathrm{FS}(a_1,\dots ,a_r)$, the augmented finite-sums set, have color $q$ in $y$, their coordinate constraints define a cylinder set containing $y$. The joint return lemma for a proximal minimal pair chooses a new positive term so that all new sums have color $q$ in both $x$ and $y$. Mathematical induction gives an infinite monochromatic finite-sums set. The new term can exceed the sum of all previous terms, giving unique representations. The proximal-minimal existence theorem is a substantive input to this proof.

Fix positive integers $r,k,m$ with $m\ge r$. There is an integer $n\ge m$, depending only on $r,k,m$, such that every finite coloringhas a subset $H\subseteq [n]$ of size $m$ for which the restriction of a function $c$ to $\left(\genfrac{}{}{0ex}{}{H}{r}\right)$ is a constant function. Here $[n]=\{1,\dots ,n\}$, and $\left(\genfrac{}{}{0ex}{}{S}{r}\right)$ denotes the collection of all $r$-element subsets of $S$, rather than its binomial coefficient cardinality. The notation $[n]⟶(m{)}_k^r$ abbreviates this property. Thus $H$ is a homogeneous set for a colouring; when $r>1$, the monochromatic set consists of its $r$-element subsets, not its individual elements. This is the finite assertion in Ramsey's original Theorem B, p. 267.

For $r=1$, this is the pigeonhole principle, with sharp threshold $n=k(m-1)+1$. For instance, every red-blue coloring of five objects has three of one color; four objects can split two and two. For $r=2$, $k=2$ and $m=3$, the sharp threshold is six, as shown by the Ramsey number for triangles. Coloring pairs makes this a problem about edges of a complete graph. For larger $r$, the analogous viewpoint uses a hypergraph.

The finite Ramsey theorem lets an existence argument discard most of a large finite set while retaining a prescribed amount of uniform structure. Its threshold applies to every coloring; one does not need an assumption that colors were assigned randomly. A diagonal compactness argument deduces finite existence from Ramsey's theorem, but does not by itself identify the smallest threshold. For pairs, a Ramsey number makes that optimization explicit.

For every dimension $m$, every finite coloring of the positive integers contains $x_1,\dots ,x_m$ for which all nonempty sums of distinct $x_i$ have one color. This is the case $p=c=1$ of the monochromatic m-p-c set theorem.

For every finite $S\subseteq {\mathbb{N}}^d$, every finite coloring of ${\mathbb{N}}^d$ contains a monochromatic homothetic copy $a+rS$. The theorem follows from the Hales-Jewett theorem by coloring a word according to the sum of the points indexed by its letters.

Every finite coloring of the positive integers contains a monochromatic Hilbert cube of every prescribed finite dimension.

Every finite coloring of the positive integers has an infinite sequence $(x_i)$ for which all nonempty finite sums of distinct terms have one color.

For every positive $m,p,c$, every finite coloring of the positive integers contains a monochromatic M-p-c set.

A subset $A\subseteq X$ is monochromatic for a finite coloring $c:X\to C$ if there is a color $i\in C$ such thatEquivalently, the restriction of a function $c\upharpoonright A$ is a constant function, or $A$ lies in one colour class $c^{-1}(i)$. The word describes agreement of colors; it does not require $A$ to equal an entire colour class.

For example, color the integers by integer parity, using red for even and blue for odd. The set $\{2,4,8\}$ is monochromatic, whereas $\{2,3\}$ is not. If the colored objects are edges, a monochromatic triangle in a graph means that its three edges form a monochromatic set. In a coloring of $r$-element subsets of a set $S$, a homogeneous set for a colouring $H\subseteq S$ means that the collection of all $r$-element subsets of $H$ is monochromatic. For pairs, this is a complete graph on $H$ whose edges all have one color, rather than a coloring of the vertices in $H$.

There is a finite coloring of the positive integers for which no infinite set has all pairwise sums and pairwise products in one color. Refining this coloring by the parity of the 2-adic valuation also prevents a constant infinite sequence from evading the obstruction.

For a partition regular matrix $A$ and any property $P$ of its positive solution vectors, either every finite coloring admits a monochromatic solution with $P$, or every finite coloring admits one without $P$. If the first alternative fails, take a witnessing coloring and pair it with any other coloring. Partition regularity of the product coloring forces a solution avoiding $P$ in the other coloring. The alternatives need not be exclusive.

Every finite coloring of an IP set has a color class that is an IP set. Here is a reduction to the ordinary Hindman theorem. Given $\mathrm{FS}(x_i)$ in the original set, color an integer $n>0$ by the color of ${\sum }_{i\in {\mathrm{supp}}_2(n)}{x}_i$, where the support consists of positions of its nonzero digits in the binary expansion. The Hindman theorem produces $w_i>0$ with monochromatic $\mathrm{FS}(w_i)$. Replace the $w_i$ by consecutive, disjoint finite block sums $v_j$ with separated binary supports: after a block has been chosen, take $K$ above all previously used positions; two of $2^K+1$ partial sums of a fresh tail agree modulo $2^K$, so their positive difference supplies the next block sum divisible by $2^K$. Now binary addition of distinct $v_j$ has no carries. Therefore $y_j={\sum }_{i\in {\mathrm{supp}}_2(v_j)}{x}_i$ generates a monochromatic finite-sums set in the original IP set.

A matrix $A$ over the rational numbers is partition regular when every finite coloring of the positive integers admits a monochromatic vector $x$ satisfying $Ax=0$, with every coordinate a positive integer. Repeated coordinates are permitted.

For the Ehrenfeucht-Mostowski theorem, let $M$ be an infinite first-order structure and $I$ any linear order. Choose a full Skolem expansion $M^{\ast }$: add witness functions for existential formulas, repeat in the expanded languages, and take their union. We will construct a model of its theory containing distinct generators $c_i$, $i\in I$, forming an order-indiscernible sequence.

Adjoin the elementary diagram of $M^{\ast }$, the inequalities $c_i\ne c_j$ for $i\ne j$, and for every expanded-language formula $\varphi (x_1,\dots ,x_r)$ and every two increasing $r$-tuples of indices, the sentencesEvery finite subcollection is satisfiable in $M^{\ast }$. To prove this, choose a countably infinite sequence of distinct elements of $M$, and for each of the finitely many relevant arities color its increasing index tuples by the finite vector of truth values of the formulas of that arity. Repeated applications of the Ramsey's theorem give an infinite subsequence homogeneous for all these finitely many finite colorings. Interpret the finitely many mentioned $c_i$ by its elements in their index order. All indiscernibility and distinctness constraints hold, and the finite diagram fragment holds because the ambient structure is still $M^{\ast }$.

By compactness theorem, a model $N^{\ast }$ of the full enlarged theory exists. Its Skolem hull $H$ generated by the $c_i$ is elementary: whenever an existential formula with parameters in $H$ holds in $N^{\ast }$, its chosen witness function returns a value in $H$, so the Tarski-Vaught test applies. Its reduct is a model of $\mathrm{Th}(M)$. If the index order has size $\kappa$, the hull has size at most $\kappa +|L|+{\aleph }_0$, and it contains $|I|$ distinct generators.

Every order automorphism $h$ of $I$ induces the automorphismTo check well-definedness, write any two terms being compared over the same increasing list of their generators. Their equality is an expanded-language formula; indiscernibility of the order-indiscernible sequence preserves its truth under $h$. The same argument preserves each relation, and the term construction preserves the functions. Applying $h^{-1}$ gives the inverse. The extension is unique in the specified Skolem language since every hull element is a term in the generators; no uniqueness among all automorphisms of the reduct is being asserted. This proves the Ehrenfeucht-Mostowski theorem, including its usual automorphism consequence.

For simple typed set theory with atoms, use sorts $0,1,\dots$, predicates $S_i$ for sets, and typed membership from sort $i$ to sort $i+1$. Atoms have no members, extensionality compares sets, and every well-typed formula defines a set of the next sort. Typical ambiguity is the schema $\varphi \leftrightarrow {\varphi }^{+}$ for every closed typed sentence, where the superscript raises all types by one.

Here are concrete full typed models before imposing the ambiguity schema. Choose increasing natural numbers $n_{-1}<n_0<n_1<\cdots$ and setThe auxiliary $D_{-1}$ merely interprets the set predicate at the lowest sort. Define typed membership byThen the other objects of $D_{i+1}$ are atoms, regardless of their old membership. Every subset of $D_i$ has its representative in $S_{i+1}$, giving comprehension even for formulas with higher-sort quantifiers and parameters. Extensionality holds for the set representatives and atoms have no typed members. The rank gaps leave infinitely many atoms at each sort, and all sorts are infinite.

Consider finitely many ambiguity instances with unraised sentences ${\varphi }_1,\dots ,{\varphi }_t$, and choose a fixed window length $r$ sufficient to include every sort used and its auxiliary predecessor. Color every increasing $r$-tuple of natural numbers by the vector of truth values of these unraised sentences in its finite rank-window interpretation. There are only $2^t$ colors. The Ramsey's theorem gives an infinite homogeneous set. Choose $r+1$ successive points from it. The first $r$ points and last $r$ points have the same color, while the latter interpretation of ${\varphi }_j$ is exactly the former model's interpretation of ${\varphi }_j^{+}$. The auxiliary predecessor shifts too, so this remains true for sentences mentioning the lowest set predicate. Extend the chosen rank sequence arbitrarily to interpret the remaining sorts. This yields a model of typed set theory satisfying all the specified ambiguity instances.

Thus every finite subset of the typed axioms together with all ambiguity instances has a model. Applying multisorted compactness theorem givesThe final model satisfies first-order typed comprehension, with quantification over its own sorts and sets as in Henkin semantics.