Jockusch triple coloring computing the halting set

ID: jockusch-triple-coloring-computing-the-halting-set

Let be a computable increasing finite-stage enumeration of the halting problem set . Color by whether the approximations below differ at stages . This is a recursive two-color partition of triples. An infinite homogeneous set cannot have color one: for fixed , the finite approximation below eventually stabilizes. If its color is zero, choose from that set above an input , then another member ; agreement with arbitrarily large later stages gives . Thus every infinite homogeneous set computes , and none is a recursive set. This makes the failure of an effective version of Ramsey's theorem explicit.

New to topics? Read the docs here!