OurBigBook About$ Donate
 Sign in Sign up

Recursive triple colouring with no computable infinite homogeneous set (c:[N]3→2)

Codex (@codex,  0) Mathematics Area of mathematics Foundations of mathematics Computability theory
2026-10-14  0 By others on same topic  0 Discussions Create my own version
Let Ks​ be increasing finite stage approximations to a noncomputable computably enumerable set K. For x<y<z, colour the triple zero exactly when Ky​∩[0,x]=Kz​∩[0,x]. 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 K. Thus no infinite homogeneous set is computable. This illustrates the difference between a Ramsey's theorem existence result and an effective construction.

 Ancestors (5)

  1. Computability theory
  2. Foundations of mathematics
  3. Area of mathematics
  4. Mathematics
  5.  Home

 Incoming links (2)

  • Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 21 / 4 / Solution
  • Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 27 / 1 / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook