FOM: more on Nabutovsky and Weinberger and Soare
Peter Cholak
cholak at nd.edu
Wed Jun 28 18:14:46 EDT 2000
I have been asked to reply about the following piece of a post on FOM. I
am not aware then it was posted.
>
> Subject: FOM: Urbana thoughts; Soare; Pillay
> From: Stephen G Simpson <simpson at math.psu.edu>
> Date: Fri, 16 Jun 2000 17:25:35 -0400 (EDT)
>
> Matthew Frank Sun, 11 Jun 2000 10:11:16 -0500 (CDT) writes:
>
> > Nabutovsky and Weinberger had needed some new results in
> > computability (which Soare then provided) for their proofs.
>
> Ummm, well, .... My understanding of it (I have been reading up on
> the Nabutovsky/Weinberger stuff) is that Nabutovsky and Weinberger
> originally cited an old theorem about r.e. degrees, the Sacks Density
> Theorem. But then, after discussing the matter with Soare, they found
> that they could get a slightly better geometrical result by applying a
> much easier, tailor-made theorem about r.e. sets, which Soare
> provided. The easier theorem, due to Soare (see also Soare's ASL 2000
> abstract), is that there exists a sequence of r.e. sets such that any
> settling-down function for any one of the sets in the sequence
> dominates any recursive function composed with any settling-down
> function for the next set in the sequence.
>
> This theorem of Soare is much easier because, according to some
> recursion theorists that I asked at ASL 2000, the proof does not need
> a priority argument. Another vindication of the so-called Simpson's
> Thesis! [ This is a reference to the discussion of the role of
> priority arguments in applied recursion theory, FOM,
> July/August/September 1999. See for instance my posting of Wed, 4 Aug
> 1999 19:18:00 -0400 (EDT). ]
>
I have been looking at the N/W stuff. I am finding it difficult to get a
good understanding of what is going. Personally I have heard several
talks about it (two by W and one by one of his students) and surely I will
hear more. Clearly more study is needed (for me). I think Soare gave a
very nice talk on the subject at the ASL meeting. The N/W results are
difficult results and some of them are not completely settled.
Soare's slides are now (partially) available (the diagrams are missing) at
http://www.cs.uchicago.edu/~soare/Geometry/slides.html; also see
http://www.cs.uchicago.edu/~soare/Geometry/Geometry.html for links to the
Nabutovsky/Weinberger papers. The pages of the slides where the needed
computability theory is mentioned is slides 23-25.
N/W first used the Sacks Density Thm for their results. Then they
(actually just W) came to Soare and asked Soare to provide them with a
"tailor-made" theorem. This "tailor-made" result does provide N/W with a
"better" result. I cannot judge how much better. But I would not use the
word "slightly" since N/W asked for and were interested in Soare's result.
Soare told me last spring the proof of his theorem was "easy". Today I
sat down and thought about the proof. The proof I came up with was a
priority argument done on a tree with Pi^0_2 branching nodes. It is a
0''-priority argument. I see no way this can be improved to a 0'-priority
argument (finite injury). Sacks density is also a 0''-priority argument.
I would say that Soare's proof is only slightly easier than the tree proof
of Sacks density since what has to be done is more transparent. But I
think only someone with a good working knowledge of the tree method could
call this proof easy.
I am not going to enter another debate about the "Simpson's thesis" (for
those interested I suggest looking at the FOM archives.) But Soare's
result does not support the "Simpson's thesis".
Best Regards
Peter Cholak <Peter.Cholak.1 at nd.edu>
http://www.nd.edu/~cholak
------------------------------------------------------------------------
Department of Mathematics | Phone: (219) 631-6507
370 Math Building | Fax: (219) 631-6579
Notre Dame, Indiana 46556-5659 | Office: 223 CCMB
------------------------------------------------------------------------
PS: I read FOM in the digest version and I will be away over the weekend,
so if you hope I that will reply further, I suggest send your email both
the FOM list and me.
More information about the FOM
mailing list