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.
Articles by others on the same topic
There are currently no matching articles.