Recursive triple colouring with no computable infinite homogeneous set
ID: recursive-triple-colouring-with-no-computable-infinite-homogeneous-set
Let be increasing finite stage approximations to a noncomputable computably enumerable set . For , colour the triple zero exactly when . 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 . Thus no infinite homogeneous set is computable. This illustrates the difference between a Ramsey's theorem existence result and an effective construction.
New to topics? Read the docs here!