= Recursive triple colouring with no computable infinite homogeneous set
{title2=$c:[\mathbb N]^3\to2$}
Let $K_s$ be increasing finite stage approximations to a noncomputable <computably enumerable set> $K$. For $x<y<z$, colour the triple zero exactly when $K_y\cap[0,x]=K_z\cap[0,x]$. An infinite homogeneous set has colour zero, since each bounded approximation eventually stabilizes. Its first two elements above any requested bound recover the final approximation at that bound, so the homogeneous set computes $K$. Thus no infinite homogeneous set is <computable>. This illustrates the difference between a <Ramsey's theorem> existence result and an effective construction.
Back to article page
