= Jockusch triple coloring computing the halting set
{c}
{title2=$c(x,y,z)=\mathbf1\{K_y\cap x\ne K_z\cap x\}$}
Let $K_s$ be a computable increasing finite-stage enumeration of the <halting problem> set $K$. Color $x<y<z$ by whether the approximations below $x$ differ at stages $y,z$. This is a recursive two-color partition of triples. An infinite homogeneous set cannot have color one: for fixed $x$, the finite approximation below $x$ eventually stabilizes. If its color is zero, choose $x$ from that set above an input $n$, then another member $y>x$; agreement with arbitrarily large later stages gives $K(n)=K_y(n)$. Thus every infinite homogeneous set computes $K$, and none is a <recursive set>. This makes the failure of an effective version of <Ramsey's theorem> explicit.
Back to article page
