Halting-stage colouring of triples

ID: halting-stage-colouring-of-triples

Let be an increasing uniformly computable finite approximation to the diagonal halting set. For , colour the triple if , and otherwise. No infinite homogeneous set for a colouring can have colour , since the finitely many bits below its first element eventually stabilize. Every infinite homogeneous set of colour computes the diagonal halting set: choose in and read membership of in . Homogeneity and unboundedness make this answer final. Thus the colouring has no infinite computable homogeneous set.

New to topics? Read the docs here!