Monday, January 30, 2012

A result of Specker in Recursive Combinatorics






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


More has been proven since then:


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

  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.

  3. Thanks Bill, the explanation was helpful

  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.

  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.

    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.


  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.


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