[FOM] Simpson on the Medvedv lattice

[Martin Davis]

I'd like to bring it to the attention of FOM subscribers an interesting 
talk given by Steve Simpson at an Amer Math Soc meeting in Baltimore this 
January that has just come to my attention.  The transparencies from that 
talk are available on Steve's web site at
http://www.math.psu.edu/simpson/talks/ams0301/
and they are very clear. I'll make a few brief comments, but recommend that 
subscribers have a look at the transparencies.

Medvedev's notion of reducibility was introduced by him in 1955; a brief 
account is available in Hartley Rogers classic book. As with the other 
reducibility notions, an equivalence relation is obtained  by calling a and 
b equivalent if each is reducible to the other, and then one speaks of the 
corresponding equivalence classes as "degrees".

In his talk, Simpson discusses these Medvedev degrees and contrasts their 
structure with that of the much-studied r.e. dgrees. Whereas the r.e 
degrees only form an upper semi-lattice, Simpson identifies an important 
subset of the the Medvedev degrees (into which the r.e. degrees can be 
embedded) that form a distributive lattice.

He also notes that in addition to the Medvedev degrees forming the top and 
bottom of this lattice, there are intermediate degrees that can be 
identified as precisely the degree of the set of infinite sequences of 0s 
an 1's that are random in the sense of Martin-Löf. This is a really neat 
and surprising (to me), bringing together two fundamental notions. Simpson 
contrasts this situation with the much-studied r.e. degrees, where despite 
the plenitude of intermediate degrees, none has turned up which can 
similarly be identified as the degree of an important problem occurring in 
a different context.

Simpson uses the word "natural" in making this contrast, and I find this 
use unhelpful. If foundations is about anything, it is about making notions 
precise. I would love to see a precise definition of what it means for 
something in mathematics to be "natural", and while we all do use the word, 
short of such a definition, the use is bound to be at least partly 
subjective. Someone deeply immersed in the demanding craft of priority 
constructions, may find sets of intermediate Turing degree constructed by 
those means perfectly "natural". And a debate on this matter is sure to 
become about words not concepts. But one can be quite precise in stating 
that no one has produced an intermediate r.e. degree about which it can be 
said that it is the degree of a decision problem that had been previously 
been studied and named.

Martin



                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com