Thursday, December 16, 2010

Low, Superlow, supersuperlow sets, and Paywalls

Recall the following:
  1. If A is a set then A' (pronounced 'A jump') is the halting set relative to A. Formally it is:
    { e | MeA(e) converges }
  2. A set A is low if A' &leT HALT.
  3. A set A is superlow if A' &lett HALT.
There is a well known construction of an undecidable low c.e. (What I call c.e., computably enumerable, used to be called r.e., recursively enumerable. See Soare's article for why the change makes sense.) This is one way to get an intermediary Turing Degree. However, it turns out that the set is not just low, its superlow. Consider the following definition of supersuperlow which I made up:
A set A is supersuperlow if A' &lebtt HALT.
I wondered if there exists an undecidable supersuperlow set. I asked four prominent computability theorists (spellcheck wanted me to write computable theorists). They all (1) thought it was a good question, (2) thought the answer was NO and KNOWN, and (3) didn't have a proof or reference. I then asked Carl Jockusch and he (1) thought it was a good question, (2) knew the answer was NO and KNOWN, and (3) had both a proof and a reference.

Since they all thought it was a good question, and because papers that contain the needed results are behind paywalls or unpublished, and hence lost to humanity forever, I did an exposition, which you can get free online here where I present the following:
  1. The classic proof that there exists an undecidable c.e. low set.
  2. Comments on this classic proof that show how it really resulted in an undecidable c.e. superlow set.
  3. A complete unpublished proof that if A is supersuperlow then A is decidable.
Should I add more to it and make it a real survey for a real journal?
  1. PRO: The referees comments may help improve it.
  2. PRO: If the journal is free online then it will be better archived.
  3. PRO: I will get to learn all of this material.
  4. PRO: A paper on my resume.
  5. CON: Referees can be a pain in the neck.
  6. CON: Math arXiv is just as good, perhaps better, than a journal for archiving (I will certainly polish it a bit and submit it to math arXiv at some point)
  7. CON: I will have to learn all this stuff. Do I care beyond what I have already found out? I stopped doing recursion theory back when it was still called recursion theory. Now I'd rather spend my time and energy on Ramsey Theory and other things. (I could, of course, do a survey of Computable Ramsey Theory. Sample theorems by Carl Jockusch: (1) If COL is a COMPUTABLE 2-coloring of the edges of the complete graph on N then there exists a &Pi2 homogeneous set. (2) There exists a COMPUTABLE 2-coloring of the edges of the complete graph on N such that no homogeneous set is &Sigma2. There is one problem with that: I already did! Its part of my survey of recursive combinatorics.
  8. CAVEAT: Is having a survey on my resume that valuable? I ask this non-rhetorically which is why this is a CAVEAT rather than a CON.


  1. do you have a grad student who could learn most of that other stuff and co-author a paper with you? that has the "PRO" of less new stuff for you to learn outright and the "PRO" of having you help teach a grad student how to do something useful and prepare for academia

  2. 1. Bill, this is SUPERCOOL!! (especially Lemma 2.5.)

    2. I would vote for the name "superduperlow." It's more idiomatic.

    3. Frank Stephan just told me another proof of this fact using Kummer's Cardinality Theorem. Using this method it is possible to even get A is weakly btt below K implies A is recursive.

  3. Anon: Great Idea! Grad or ugrad or
    HS student might work for this.

    Teutsch: Please either you or Frank post the proof.

    All: The link to Kummer's cardinality theorem proof is to a paper you have to pay for. If you go to my website, click on
    Publications with links
    and then search for GEMS you will
    get a FREE ONLINE survey of bounded queries in recursion theory that will include a proof of Kummer's Cardinality Theory
    (Theorem 3.4). This is a diff proof than Kummer had.

  4. I have now INCLUDED Frank Stephan's
    proof in the exposition and also changed SUPERSUPERLOW to SUPERDUPERLOW.

    THANKS to Teutsch and Frank Stephan!

    Frank's proof is in section 4.

  5. Hello, could you please tell, does there exist a low set, which is not superlow? I'm sure that such a set should exist, but have never seen a direct construction.