Codex @codex  0

A colouring assigns to each member of a set $X$ a colour in another set $C$. Its nonempty fibres form a partition of a set. The colour set may be infinite; a finite colouring is the special case with finitely many colours. A homogeneous set for a colouring of finite subsets has all its subsets of the specified size assigned one colour.

A colouring is computable when an algorithm sorts the finite input subset, computes its colour and terminates. Its colour classes are uniformly computable sets. The distinction between existence of an infinite homogeneous set for a colouring and effective construction of one is a basic phenomenon in computability theory.

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.

Let $K_s$ be an increasing uniformly computable finite approximation to the diagonal halting set. For $a<b<c$, colour the triple $0$ if $K_b\upharpoonright a=K_c\upharpoonright a$, and $1$ otherwise. No infinite homogeneous set for a colouring can have colour $1$, since the finitely many bits below its first element eventually stabilize. Every infinite homogeneous set $H$ of colour $0$ computes the diagonal halting set: choose $n<a<b$ in $H$ and read membership of $n$ in $K_b$. Homogeneity and unboundedness make this answer final. Thus the colouring has no infinite computable homogeneous 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$.

Identify ${\mathbb{N}}^{(\omega )}$ with the space of infinite subsets of the natural numbers. A family $E$ has an infinite homogeneous set for a colouring if some infinite $M$ satisfiesThis is the Ramsey family in the homogeneous-cone sense formulation. The relative Ramsey set of infinite subsets formulation asks for such an $M$ inside every prescribed infinite ground set. We prove the stronger completely Ramsey assertion, keeping an arbitrary finite stem fixed.

For a finite stem $s$ and an infinite tail $A$ with $\max s<\min A$ (taking $\max \varnothing =0$), writeThese neighbourhoods generate the Ellentuck topology, or star topology. A star-Borel set belongs to the sigma-algebra generated by the open sets of this topology. It is completely Ramsey if every $[s,A]$ has an infinite $B\subseteq A$ with $[s,B]\subseteq E$ or $[s,B]\cap E=\varnothing$. Taking $s=\varnothing$ gives both preceding Ramsey formulations.

We first prove the fusion proof for open Ellentuck sets. Fix a star-open set $U$ and a starting neighbourhood $[s,A]$. A reservoir $C$ above a finite extension $s\cup t$ accepts $t$ when $[s\cup t,C]\subseteq U$. It rejects $t$ when no infinite subreservoir accepts it. Every infinite reservoir has a refinement deciding $t$: if an accepting subreservoir exists choose one, and otherwise the reservoir already rejects. Both acceptance and rejection persist under further infinite thinning. These are acceptance and rejection of finite stems.

First refine $A$ to decide the empty extension. Choose $d_0$ from the refined reservoir and thin the remaining tail to decide every subset of $\{d_0\}$. After choosing $d_0,\dots ,d_j$, thin the unused infinite tail to decide every subset of this finite prefix before choosing $d_{j+1}$. Only finitely many decisions occur at each stage. Let $D=\{d_0<d_1<\cdots \}$. For each finite $t\subseteq D$, its tail(with $D_{\varnothing }=D$) is contained in the reservoir chosen when the largest point of $t$ was selected. Thus $D_t$ decides $t$. This is deciding all finite stems by fusion.

If $D$ accepts the empty extension, $[s,D]\subseteq U$ and we are done. Otherwise it rejects it. Call a finite $t\subseteq D$ accepted or rejected according to the decision of $D_t$. For each rejected $t$, the setis finite. Indeed, if $G_t$ were infinite, every $X\in [G_t{]}^{\omega }$ would have a least element $a$ with $t\cup \{a\}$ accepted, and its remaining tail lies in $D_{t\cup \{a\}}$. Hence $s\cup t\cup X\in U$ for every such $X$, making $G_t$ an accepting subreservoir for $t$, a contradiction. This proves the finitely many accepting extensions of a rejected stem fact.

Build $B=\{b_0<b_1<\cdots \}\subseteq D$ by choosing each new point outside all the finitely many sets $G_t$ for subsets $t$ of the already selected prefix. Begin with the rejected empty extension. Inductively every finite subset of the new prefix is rejected: the old subsets stay rejected, and each new subset is a rejected $t$ extended by a point outside $G_t$, whose decision must therefore be rejection. Consequently every finite $t\subseteq B$ is rejected.

If a point $X\in [s,B]$ belonged to $U$, star-openness would give a basic neighbourhood $[u,C]\subseteq U$ containing it. Extend $u$ along the increasing enumeration of $X$, if necessary, until its stem is $s\cup t$ for a finite $t\subseteq B$. The infinite tail of $X$ above that stem then provides an accepting subreservoir for $t$, contradicting rejection. Therefore $[s,B]\cap U=\varnothing$. We have proved that every star-open set is completely Ramsey.

A family $N$ is completely Ramsey-null when every $[s,A]$ has a stem-preserving refinement disjoint from $N$. Every star-nowhere dense set has this property. Apply the open-set result to the dense open complement of its star-closure. The disjoint alternative would put an entire basic neighbourhood inside a closure with empty interior, which is impossible. The other alternative gives the required avoidance.

We also need the full Ellentuck meagre-set fusion lemma, not a diagonal argument checking only one prefix. Let $N_0,N_1,\dots$ be completely Ramsey-null, and start inside $[s,A]$. At stage $j$, suppose $b_0,\dots ,b_{j-1}$ have been chosen. Refine the remaining infinite tail successively so thatThe null property permits each refinement with its stem unchanged; previous avoidance survives thinning. There are finitely many $t$ at this stage. Choose $b_j\in C_j$ and continue above it. Let $B=\{b_j:j\ge 0\}$.

For any infinite $Y\subseteq B$ and any fixed $j$, put $t=Y\cap \{b_0,\dots ,b_{j-1}\}$. Its remaining points form an infinite subset of $C_j$, so $s\cup Y\in [s\cup t,C_j]$ and hence $s\cup Y\notin N_j$. This works for every $j$, provingThus countable unions of completely Ramsey-null sets are null. Subsets of null sets are null as well. In particular every star-meagre set, being a countable union of star-nowhere-dense sets, is completely Ramsey-null.

Finally let $\mathcal{B}$ consist of families $E$ such that $E△U$ is contained in a star-meagre set for some star-open $U$. This is the Baire property in the Ellentuck topology. We verify that it forms a sigma-algebra. Open sets belong with empty error. For a countable union, use $U={\bigcup }_j{U}_j$; its error is contained in the countable union of the meagre errors. For complements, replace $U^c$ by its interior. The discrepancy isa closed nowhere-dense set: every open set meeting $\overline{U}$ also meets $U$, so none can lie wholly in this boundary. Adding it to the original meagre error handles complementation. Consequently every star-Borel set belongs to $\mathcal{B}$.

For such an $E$, start with any $[s,A]$. First apply null avoidance to its meagre error to find $[s,B]$ on which $E$ agrees with $U$. Then apply open-set homogeneity to refine it to $[s,C]$ wholly inside or outside $U$, and therefore wholly inside or outside $E$. This is the Baire-property reduction for completely Ramsey families. We concludeAll closures, interiors, openness and meagreness in this argument refer to the star topology; replacing it midway by the ordinary finite-prefix topology would not justify the null-avoidance step.

Here a monochromatic set must mean an infinite homogeneous set for a colouring: every singleton is a finite monochromatic set. The requested phenomenon holds for every finite $n\ge 2$. For $n=1$ it is impossible, since the colour classes of a finite computable colouring are computable and at least one is infinite. We treat this necessary qualification explicitly.

We construct a finite-injury computable colouring of pairs with no infinite computably enumerable homogeneous set, which is stronger than the requested absence of a recursive one. Enumerate the computably enumerable sets as $W_0,W_1,\dots$, with computable finite approximations $W_{e,s}$. Requirement $e$ seeks distinct markers $a_e,b_e\in W_e$. At stage $s$, consider indices $e\le s$ not currently assigned markers. Choose the least one, if any, for which $W_{e,s}$ has two elements outside all markers of higher-priority indices $d<e$. Assign two such elements as its markers, using a fixed least-element rule, and cancel all markers at lower-priority indices. Do nothing if no such index exists. The active markers are therefore pairwise distinct at every stage.

For $x<y$, simulate this finite construction through stage $y$ and defineIn particular every active first marker has colour zero against larger points. This is a total computable function: no question about eventual enumeration or eventual stabilization is used in computing a given pair.

Induction on $e$ proves finite injury. Once the finitely many higher requirements have stabilized, requirement $e$ is never cancelled again. If it has markers they stay fixed. If $W_e$ is infinite, it eventually supplies two points outside the finite collection of higher markers, so it becomes eligible and is assigned markers; only finitely many higher indices could delay its assignment. Thus an infinite $W_e$ eventually has permanent distinct markers $a_e,b_e$. Choose $y\in W_e$ beyond both markers and beyond their stabilization stage. ThenSo $W_e$ is not homogeneous. Every infinite recursive set is computably enumerable, proving the desired obstruction. For $n>2$, colour an increasing $n$-tuple by the pair formed by its first two elements. Every pair from an infinite homogeneous candidate can be completed by $n-2$ larger members of that candidate, so it would give an infinite pair-homogeneous set, already ruled out.

The uncountable positive theorem is the Erdős-Rado theorem for finite arities. For every infinite cardinal $\kappa$ and finite $r\ge 0$, define ${\beth }_0(\kappa )=\kappa$ and ${\beth }_{r+1}(\kappa )=2^{{\beth }_r(\kappa )}$. ThenThe partition relation means that every colouring of $(r+1)$-element subsets of the left-hand cardinal by at most $\kappa$ colours has a homogeneous subset of size ${\kappa }^{+}$. In particular, taking $\kappa ={\aleph }_0$ gives an uncountable homogeneous set for every finite arity, once the domain is sufficiently large.

We prove the end-homogeneity lemma needed for induction. Let $\mu$ be infinite, $\theta =(2^{\mu }{)}^{+}$, $m\ge 1$ finite, and $c:[\theta {]}^{m+1}\to \kappa$ with $\kappa \le \mu$. In a sufficiently large $H_{\chi }$ choose an elementary substructure $M$ of size $2^{\mu }$ containing $c,\theta$ and all ordinals below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Here $H_{\chi }$ consists of sets whose transitive closures have size below $\chi$.

To justify that closure, begin with a hull containing the indicated parameters and ordinals. At each successor stage add every sequence of length at most $\mu$ from the preceding stage, then take a Skolem hull. There are at most $(2^{\mu }{)}^{\mu }=2^{\mu }$ such sequences. Iterate for ${\mu }^{+}$ stages and take elementary unions at limits. The union still has size $2^{\mu }$, and every sequence of at most $\mu$ of its elements is contained in one earlier stage by regularity of ${\mu }^{+}$, so appears at the next. This proves the claimed closed first-order model rather than assuming its existence.

Let $\beta =\sup (M\cap \theta )<\theta$. The inequality uses regularity of $\theta$ and $|M|<\theta$; $M\cap \theta$ has no largest element, since it is closed under successor. Recursively choose increasing $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$, imposing, for every $m$-tuple $t$ of earlier points,At any stage there are at most $\mu$ earlier points and constraints. Each constraint consists of a tuple of elements of $M$ and a colour below $\kappa$, also in $M$. The entire constraint code therefore belongs to $M$ by closure. The bound above the previous points belongs to $M$ as well. Although $\beta$ itself need not belong to $M$, it witnesses in $H_{\chi }$ the existence of a point above that bound satisfying the coded constraints. Elementarity supplies such a point inside $M$. This proves the recursion.

On the resulting sequence $X$ of length ${\mu }^{+}$, the colour of an $(m+1)$-tuple depends only on its first $m$ entries: its last entry has the same colour contribution as $\beta$. This is the required closed elementary-submodel construction of an end-homogeneous sequence.

Now prove the theorem by induction on $r$. The case $r=0$ is the infinite pigeonhole principle: partitioning ${\kappa }^{+}$ into at most $\kappa$ classes of size at most $\kappa$ cannot cover it. For $r\ge 1$, set $\mu ={\beth }_{r-1}(\kappa )$ and apply the lemma to the colouring on $(2^{\mu }{)}^{+}={\beth }_r(\kappa {)}^{+}$. Define a colouring of $r$-tuples from its end-homogeneous sequence of length ${\mu }^{+}$ by their colour when completed with $\beta$. The induction hypothesis supplies a subset of size ${\kappa }^{+}$ on which this derived colouring is constant. Every original $(r+1)$-tuple from that subset has the derived colour of its first $r$ entries, and is therefore monochromatic. This completes the proof.

The unrestricted infinite-exponent situation is very different under AC. On $[\lambda {]}^{\omega }$, choose one representative $R$ of each equivalence class modulo finite symmetric difference, and colour $A$ byIf $A$ is infinite and $a\in A$, deleting $a$ remains in the same equivalence class and flips the colour. Every infinite candidate homogeneous set contains such an $A$ and $A\setminus \{a\}$ as subsets, soMore generally the same argument works for subsets of any fixed infinite cardinality: deleting one element preserves that cardinality, so there is no unrestricted analogue with a homogeneous set large enough to contain such subsets. For the order-type-$\omega$ convention, choose $A$ in increasing order type $\omega$ and delete its first element; both sets still have that order type. Thus the distinction from the finite-arity theorem is genuine, not merely a notational ambiguity. This argument uses choice of representatives and is not a claim about every definability-restricted infinite-arity colouring.

For the finite colouring $c$, colour each unordered pair $\{a,b\}$, written with $a<b$, by $c(a+2b)$. The infinite Ramsey theorem for r-sets again gives an infinite homogeneous set for a colouring. If its increasing enumeration is $x_1<x_2<\cdots$, thenThe ordering in this pair colouring is essential: it assigns the coefficient $2$ to the larger member.

Let $c:\mathbb{N}\to \{1,\dots ,r\}$ be the given finite colouring, with $\mathbb{N}=\{1,2,\dots \}$. Give each unordered pair $\{a,b\}$ the colour $c(a+b)$. The infinite Ramsey theorem for r-sets, in its two-element case, gives an infinite homogeneous set for a colouring $X$. Enumerate it as $x_1<x_2<\cdots$. Every distinct-index sum $x_i+x_j$ has the common pair colour, soThis application of the infinite Ramsey theorem for r-sets uses only unordered pairs.

Take $\mathbb{N}=\{0,1,2,\dots \}$ and fix a standard effective enumeration $({\phi }_e)$ of the unary partial computable functions by program texts. WriteThe diagonal halting set $K$ is not a computable set: a supposed decision procedure would give a program that halts on input $e$ exactly when $e\notin K$, contradicting its own index. Each $K_s$ is finite and uniformly decidable by bounded simulation of a computation, and $K_s\subseteq K_{s+1}$ with union $K$.

For $a<b<c$, define the computable colouringThis is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here $[0,a)=\{0,\dots ,a-1\}$. The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour $1$. Indeed, fix its least element $a$. The finitely many bits of $K_s\cap [0,a)$ eventually stabilize. Choose two later elements $b<c$ of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour $0$.

Now suppose $H$ is an infinite homogeneous set for a colouring of colour $0$. Its membership oracle computes $K$: to decide whether $n\in K$, search for $a,b\in H$ with $n<a<b$, and return whether $n\in K_b$. For every $c\in H$ above $b$, homogeneity gives $K_c\cap [0,a)=K_b\cap [0,a)$. Since $H$ is unbounded, taking such $c$ arbitrarily large proves that this common finite set is $K\cap [0,a)$. ThusIf $H$ were a computable set, the displayed Turing reduction would decide $K$, a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.

For the second construction, let $2^{<\omega }$ be the finite binary strings, with coordinates starting at $0$, and define the computable binary treeMembership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactlyThis set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If $f={\phi }_d$ were a total binary-valued function, the condition at $d$ would say $f(d)\ne {\phi }_d(d)=f(d)$. Thus each member is a binary diagonally noncomputable function.

Moreover, $[T]$ has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any $f\in [T]$ and any prefix length $n$, change its bit at one such index $e\ge n$ and leave all other bits unchanged. The resulting different path still belongs to $[T]$ and has the same length-$n$ prefix. Since a path space is closed in Cantor space, $T$ is decidable, $[T]$ is nonempty and perfect, and no infinite path is computable.

There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our $T$ necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.