Monday, January 30, 2012

A result of Specker in Recursive Combinatorics

Ernst Specker passed away in December. He has 91. He was not the oldest living mathematician. That title likely belongs to Sergey Nikolsky. A former student of Specker's, Martin Furer, posted about his life and his math on this blog here.

In this post I discuss a results of Specker that is not his most famous (that seems to be the Kochen-Specker theorem) but instead a result that I actually know. Hope you like it.

Background: Ramsey's theorem states that if COL is a 2-coloring of pairs of naturals then there exists an infinite homogenous set H (so every pair from H has the same color). The standard proof is non constructive.

More background: What if you were GIVEN a Turing Machine for a 2-coloring. Could you GIVE ME BACK a Turing machine for a homogenous set? The standard proof does not give this to you, so we are really asking if there is a more constructive proof. So, what is known?

Specker showed that there is a computable 2-coloring of pairs of naturals so that there is NO computable Homogenous set. Here is the proof in brief:
  1. Let A be a bi-immune set (no subset of A or its complement is decidable) that is decidable with oracle HALT. You can easily construct such by an initial segment argument.
  2. By the Shoenfield limit lemma there exists computable f(x,s) such that A(x) = limits→ ∞ f(x,s). (Easy proof of the direction we need: if A is computable in HALT via oracle Turing machine M let f(x,s) be the result of running M for s steps and using as oracle the first s elements of HALT in some enumeration.)
  3. Let COL(x,y) = f(x,y), for x< y. (NOTE- This is a correction, I earlier just had COL(x,y)=f(x,y).)
  4. Assume, by way of contradiction, that there is an infinite homogenous set

    x1 < x2 < x3 < x4 < x5 ...

    For all L we have f(xL,xL+1)= f(xL,xL+2) = f(xL,xL+3) = f(xL,xL+4) = ... (NOTE- I corrected this- I originally had x_1, x_2, x_3, x_4 where I now have x_{L+1}, x_{L+2}, ..)

    Since all of these values equal they also equal limit→ ∞f(xL,s) and hence equals A(xL). Hence either ALL of the x's are IN A or all of the x's are NOT in A. Hence an infinite homogenous set yields an infinite subset of either A or the complement of A, which contradicts that A is bi-immune.
More has been proven since then:
  1. Jockusch showed that (a) there is a 2-coloring of pairs so that no homogenous set is Sigma2, and (b) every 2-coloring has a Pi2 set.
  2. More is known- see the paper by Cholak, Jockusch, Slaman On the strength of Ramsey's theorem for pairs
Specker's result is probability the first theorem in infinite combinatorics to be proven to be non-constructive.

9 comments:

  1. Bill, what is an initial segment argument? (that is, can you sketch the proof of (1)?)

    ReplyDelete
  2. 1) someone emailed me asking of I mean that A bi-immune means that
    neither A nor Abar has an INFINITE decidable set. YES, that is correct.

    2) Initial segment argument: Think of a set as an infinite string of 0's and 1's. We want the set A to satisfy requirements

    R_e^1: If Turing Machine M_e is total and says YES to an infinite set
    of numbers then L(M_e) is not a subset of A.
    (We will make some x such that M_e(x)=1 be NOT in A)

    R_e^2: similar for Abar.

    We satisfiy these requirements in the order R_1^1, R_1^2, R_2^1, R^2_1, etc...

    Initially A is the empty string (no members decided).

    Assume that A is a finite segment and you want to satsify R_e^1.
    ASK HALT: does there exist x bigger than the segement such that
    M_e(x) halts and says YES. If so then extend the segement that is
    representing A to that point x (say with 0's) and make sure that x
    itself gets a 0, so now x NOT IN A, but M_e(x) says 1.

    If the answer to the question was NO then M_e only says YES finite
    often so the requirement is already satisfied.

    Similar for R_e^2.

    SO, A is build up segment by segment.

    that is, FIRST you decide A on (say) 1,2,3,4,5,6.
    Then on 7,8,...,100001, etc. Each time you extend A you
    are satisfying a requirement.

    ReplyDelete
  3. Thanks Bill, the explanation was helpful

    ReplyDelete
  4. I was intrigued by your suggestion that Specker's result was the first of this type, so I posted a query on the Foundations of Mathematics mailing list to see if there were any earlier examples. Ali Enayat and Andrej Bauer responded that in 1952, Kleene proved the existence of an infinite recursive subtree T of the full binary tree such that T has no infinite recursive branch. Specker in fact built on Kleene's work.

    ReplyDelete
  5. In normal Ramsey theory I thought that the coloring relation on pairs is supposed to be symmetric: COL(x,y)=COL(y,x). Your definition of coloring results in an asymmetric COL relation, however.

    ReplyDelete
    Replies
    1. I am replying to myself here. I think the original proof is incorrect as Ramsey theory is ordinarily understood, where a coloring of pairs is symmetric. To fix this, define COL(x,y)=COL(min(x,y),max(x,y)) . Then given any L, all f(x_L,x_k) are identical for k>L. Hence f(x_L,x_k)=A(x_L). As each f(x_i,x_j), j>i, are identical, the result follows as in the original proof.

      nnn

      Delete
  6. Typo above, COL(min(x,y),max(x,y)) should of course read f(min(x,y),max(x,y)). And the references cited in the blog post do indeed use this standard definition of Ramsey's theorem.

    nnn

    ReplyDelete
  7. I have made the correction: COL(x,y) = f(x,y) where x<y.

    ReplyDelete