FOM: recursion theory: Lempp/Simpson correspondence

Stephen G Simpson simpson at
Thu Jun 4 17:51:15 EDT 1998

Dear FOM subscribers,

Here is some recent correspondence between me and Steffen Lempp, a
recursion theorist at the University of Wisconsin.  I thought this
might be interesting for the FOM list, because it touches on some
contrasting aspects of contemporary recursion theory
(a.k.a. computability theory) and contemporary foundations of
mathematics.  Some open problems in r.e. degrees and in reverse
mathematics are also mentioned.

For some reason the recursion theorists have been mostly boycotting
the FOM list, but let's try to keep the discussion going.  If any
recursion theorists would like to subscribe to FOM, they should please
send me e-mail.

I'd like to thank Steffen for allowing me to post this correspondence.
By the way Steffen, could you please show me the list of open problems
that you have compiled, so that I could post it on the FOM list?

-- Steve Simpson

Name: Stephen G. Simpson
Position: Professor of Mathematics
Institution: Penn State University
Research interest: foundations of mathematics
More information:

  From: Steffen Lempp <lempp at>
  To: Steve Simpson <simpson at>
  Subject:  1999 summer meeting
  Date: Thu, 21 May 1998 12:33:51 -0500 (CDT)
  Dear Steve,
  A while back we invited you to attend a possible conference in
  computability theory. This is just to let you know that the
  conference "COMPUTABILITY THEORY AND APPLICATIONS" was accepted by
  the AMS, IMS and SIAM, and will be funded by the National Science
  Foundation.  What we currently know about the meeting appears in the
  first public announcement below. Given our expected level of funding
  we will pay for your local costs (dorm room and board).
  The meeting's focus will be on open problems in computability theory
  and its applications. Each speaker will be strongly encouraged to
  concentrate on one major open problem (or a set of closely related
  open problems), that he/she believes is central to the area. At this
  point, we invite your suggestions as to what you believe the
  important problems are so we can organize the topics of the
                         of a
  		                1999 AMS-IMS-SIAM
  	Joint Summer Research Conference
    Sunday, June 13, 1999 to Thursday, June 17, 1999
  	the University of Colorado, Boulder
  The meeting will focus on computability theory and several
  applications in computable model theory and algebra as well as
  reverse mathematics.  The meeting's focus will be on open
  problems. A number of people working in the field have been invited
  and have tentatively agreed to come.  This meeting is open to all
  who are interested and in fact anyone who is interested is
  encouraged to attend.
  The meeting will be held at the University of Colorado -- Boulder
  campus.  Most likely the housing will be in the university's
  dorms. Check-in will be held on Saturday, June 12, 1999 and
  check-out on Friday, June 18, 1999.  Boulder is a college town in
  the eastern foothills of the Colorado Rockies and is very close to
  Rocky Mountain National Park and Denver.
  Peter Cholak (Peter.Cholak.1 at, Steffen Lempp
  (lempp at, Manny Lerman (mlerman at and
  Richard Shore (shore at are organizing the
  meeting. More details concerning the meeting will be made available
  in a second announcement later this year and at the meeting web site Information on
  how these joint meetings were arranged this year can be found at and One would expect similar
  arrangements in 1999.
  From: Stephen G Simpson <simpson at>
  To: Steffen Lempp <lempp at>
  Subject: 1999 summer meeting
  Date: Thu, 21 May 1998 14:18:26 -0400 (EDT)
  Dear Steffen,
  Thanks for the information about the meeting.  Who will be speaking?
  Will there be any talks on reverse mathematics or other foundational
  issues?  Tentatively, I don't plan to attend unless I'm invited to
  give a talk.
  What is the reason for asking me about open problems?  I guess I'm not
  understanding what your request has to do with the meeting, since I
  haven't been invited to give a talk.  Is your request part of a
  screening process of some kind?
  I'm putting the finishing touches on my book and I've signed a
  contract with Springer to deliver the final manuscript by July 31.
  Best regards,
  -- Steve
  From: Steffen Lempp <lempp at>
  To: Stephen G Simpson <simpson at>
  cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at>,
          Steffen Lempp <lempp at>,
          Manny Lerman <mlerman at>,
          Richard Shore <shore at>
  Subject: Re: 1999 summer meeting
  Date: Thu, 21 May 1998 13:28:35 -0500 (CDT)
  Dear Steve,
  We are experimenting with a new format, namely one focusing on open
  problems.  We have not yet decided on who will be invited to speak; at
  this point we are collecting a list of major open problems, and we are
  then planning to invite people to speak about these. Since we have,
  however, decided to make reverse mathematics a major topic of the
  meeting, there will be at least one (probably two) invited 45-minute
  talks in reverse mathematics (plus a number of shorter talks about
  this topic). We have an acceptance from Harvey Friedman that he will
  come, and we very much hope that you will come as well. And we would
  certainly like you to tell us what the major open problems are in your
  I am afraid this is all I can tell you at the moment.
  Best,			Steffen
  From: Stephen G Simpson <simpson at>
  To: Steffen Lempp <lempp at>
  Cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at>,
          Manny Lerman <mlerman at>,
          Richard Shore <shore at>
  Subject: Re: 1999 summer meeting
  Date: Fri, 22 May 1998 01:36:46 -0400 (EDT)
  Dear Steffen,
  A few months back I was speaking with Harvey on the phone and this
  meeting came up.  He didn't sound very enthusiastic.  Are you sure
  that he is planning to attend?  If you are going to use him as a
  drawing card, maybe you had better double check with him first.
  I still don't understand the thrust of your request concerning open
  problems, but I'll take a stab at it.
  Broadly speaking, I think the overriding problem for recursion theory
  as a subject right now is to find its way back to its roots in
  foundations of mathematics.  My feeling is that if this problem
  doesn't get solved, recursion theory will remain isolated.  For
  recursion theorists to ignore this problem is a huge strategic
  mistake.  Reverse mathematics is one possible approach to solving this
  Narrowly speaking, I could list a lot of specific open problems in
  reverse mathematics.  One group of problems where partial results are
  known is the strength of various results in WQO and BQO theory,
  e.g. the Nash-Williams transfinite sequence theorem and Laver's
  theorem (a.k.a. Fraisse's conjecture).  Last month on the FOM list I
  posted a lot of detailed information and references concerning this
  and other similar problems.  I'm surprised that recursion theorists
  are boycotting or otherwise refusing to participate in the discussions
  on the FOM list.  In any case, regarding the open problems, do you
  want specific references?
  Another specific open problem in reverse mathematics is the strength
  of the Lebesgue dominated convergence theorem.  Do you want the
  background of this?  I can think of many other open problems in
  reverse mathematics related to analysis and algebra.  Is this what you
  want?  Why?
  Best regards,
  -- Steve
  From: Steffen Lempp <lempp at>
  To: Stephen G Simpson <simpson at>
  cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at>,
          Steffen Lempp <lempp at>,
          Manny Lerman <mlerman at>,
          Richard Shore <shore at>
  Subject: Re: 1999 summer meeting
  Date: Fri, 22 May 1998 08:05:25 -0500 (CDT)
  Dear Steve,
  Thanks for your message and your input. What we are seeking is a list of open
  problems that people consider central, so your remarks are very helpful. If
  you would like to expand on them, please do so. Some time in the fall (when
  all of us are back), we will put up the list of topics and speakers.
  Best,			Steffen
  From: Steffen Lempp <lempp at>
  To: Steve Simpson <simpson at>
  Subject: open questions
  Date: Tue, 26 May 1998 09:55:22 -0500 (CDT)
  Dear Steve,
  I have been thinking about the open questions we have seen come in
  (not too many so far, unfortunately, but it's getting there), and
  there is one thing I wanted to ask you without sounding critical or
  putting you on the defensive: What IS the goal of reverse mathematics?
  >From what I have heard lately (and this may be my ignorance, or lack
  of time to tune in to FOM...), it appears that reverse mathematics
  studies known mathematical theorems and tries to determine their
  proof-theoretic strength in terms of axioms used. But there must be
  more to this than just doing this for theorem after theorem. Somehow I
  don't get the big picture, what is the eventual goal? Do you have some
  overall "meta" conjecture about what the end result of all this will
  be? What I am looking for is a small number (2 or 3) of "big"
  problems, like I see them in r.e. degrees for example right now: 
  1. Is the Sigma2 theory decidable? (This has a big impact on our
  understanding the algebraic structure, via finite substructures.)
  2. What is the automorphism group of the r.e. degrees? (I am not sure
  any more I believe Cooper's claim.)
  3. Are the r.e. degrees a prime model of their theory? (The latter two
  questions tell us a lot about definability in the r.e. degrees.)
  These are all questions about one special structure, but they are the
  important questions to me: They are the questions an algebraist or
  model theorist would ask about a structure to get the global
  picture. And I admit I am pretty fond of that one structure...
  Best,			Steffen
  From: Stephen G Simpson <simpson at>
  To: Steffen Lempp <lempp at>
  Subject: open questions
  Date: Tue, 26 May 1998 13:35:06 -0400 (EDT)
  Dear Steffen,
  Don't worry, I'm not at all upset or put on the defensive by your
  question.  This is the kind of thing that I wish you were asking on
  the FOM list.
  I can't name 2 or 3 key reverse mathematics problems that are
  true-or-false-type open questions.  The main question motivating
  reverse mathematics is, to what extent are strong set-existence axioms
  needed for ordinary mathematical practice.  This comes from
  philosophical or foundational issues, e.g. is set theory the
  appropriate foundational setup for math.  My "meta-conjecture" (as you
  might call it) is that set theory is largely irrelevant to core
  mathematics.  Harvey is of the opposite opinion -- he thinks that set
  theory will have massive impact in core mathematics.  In any case,
  reverse mathematics tries to shed light on these questions by
  answering special cases of them.
  The main question as described above can be broken down into
  subquestions in various ways.  Ony way is to ask, to what extent are
  strong set-existence axioms needed in particular branches of
  mathematics, e.g., functional analysis.  Once one has shown that a
  fairly strong axiom is needed for a particular theorem in a particular
  branch, there is probably less point in multiplying examples for that
  particular axiom in that particular branch.  But some particular
  questions may still be methodologically or technically interesting.
  The big picture of all this is a rich tapestry which emerges from the
  literature and in particular in my forthcoming book.
  All of this is part of the background of how one judges progress in
  this kind of field.  It requires taste and judgement, because the
  field is motivated by foundational questions, though naturally some
  specific structures or questions take on a life of their own.  It's
  different from a subject like r.e. degrees, where one takes it for
  granted that a particular structure is of interest for its own sake,
  regardless of any possible impact on foundations of mathematics or
  anything else that is of general intellectual interest.
  Best regards,
  -- Steve
  From: Steffen Lempp <lempp at>
  To: Stephen G Simpson <simpson at>
  Subject: Re: open questions
  Date: Tue, 26 May 1998 14:54:36 -0500 (CDT)
  Dear Steve,
  Thanks for your message. I agree with your statement that reverse
  mathematics is an interesting topic in logic. Bu I am still not sure I
  know what the "big" open problem(s) is/are. So let me rephrase my
  question: If you had access to an oracle that would answer (NOT
  necessarily in a yes/no way, but ALSO NOT with an open-ended answer) 2
  or 3 questions, what questions would you pose to it? What solutions to
  questions would make you feel that you now know SIGNIFICANTLY more
  about reverse mathematics?
  I am not trying to put down any part of logic, I think that logic has
  many branches that are mathematically intrincically interesting (the
  MAIN criterion for good mathematics in my opinion), and that we should
  learn to appreciate all the variety rather than try to convince each
  other that one branch is more significant than others? Of course,
  everyone has his/her own opinion about what is more interesting, but I
  try to emphasize the positive and convince others that what I find
  interesting really IS so.
  Best,				Steffen
  From: Stephen G Simpson <simpson at>
  To: Steffen Lempp <lempp at>
  Subject: Re: open questions
  Date: Wed, 3 Jun 1998 16:52:56 -0400 (EDT)
  Dear Steffen,
  I'm not trying to belittle or "put down" any subject.  My point about
  r.e. degrees was that researchers in this area take it for granted
  that the structure of the r.e. degrees is interesting for its own sake
  ("mathematically intrinsically interesting", as you put it), so from
  that standpoint it's always pretty obvious to them what the big open
  questions are at any given moment in time.  One could make the same
  point about other isolated branches of mathematics.  This is in
  contrast to a subject like reverse mathematics, which is not assumed
  to be intrinsically interesting, so one has to constantly reconsider
  and reassess the interest of particular structures or results or
  conjectures with respect to their impact in foundations of
  mathematics, since that is the entire motivation of the subject.  For
  example, the mathematical interest of a particular subsystem of Z_2
  such as WKL_0 or ATR_0 is not taken for granted, but rather has to be
  rigorously established.
  As for open problems in reverse mathematics, one that seems
  significant to me is to find some results in "hard analysis"
  (trigonometric series or something like that) which require strong
  axioms, ATR_0 or Pi^1_1 comprehension or stronger.  Another very
  significant problem is, to find some very natural, very simple, finite
  combinatorial statements which require axioms going beyond ZF, or at
  least high up in the hierarchy of subsystems of Z_2.  Obviously this
  question has motivated a lot of Harvey's recent work and he has made a
  lot of progress, but this is a matter of taste and judgement, since
  there is no true-false type question that is being answered here.
  Best regards,
  -- Steve
  From: Steffen Lempp <lempp at>
  To: Stephen G Simpson <simpson at>
  cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at>,
          Steffen Lempp <lempp at>,
          Manny Lerman <mlerman at>,
          Richard Shore <shore at>
  Subject: Re: open questions
  Date: Wed, 3 Jun 1998 17:40:09 -0500 (CDT)
  Dear Steve,
  I guess I would summarize my point of view as follows:
  I don't view recursion theory to be an isolated area, but rather (like
  any field in mathematics) one driven both by mathematically
  intrinsically interesting problems (which I would judge by their depth
  and intrinsic mathematical beauty) and by applications to other
  subfields. I believe that recursion theory (like any other area of
  mathematics, incl. reverse mathematics) offers problems of both kinds,
  and I find both types of problems equally interesting. Of course, both
  directions also have their dangers: on the one hand, the former can
  become too esoteric; on the other hand, the latter can become too
  ad-hoc. One has to constantly watch out for these dangers, and they
  will be judged differently by different people.
  Best,			Steffen
  From: Stephen G Simpson <simpson at>
  To: Steffen Lempp <lempp at>
  Cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at>,
          Manny Lerman <mlerman at>,
          Richard Shore <shore at>
  Subject: Re: open questions
  Date: Thu, 4 Jun 1998 11:06:44 -0400 (EDT)
  Dear Steffen,
  I think we are having an interesting exchange of views about issues
  and programs in recursion theory and reverse mathematics.  Why don't
  we try to get more people involved in the discussion, by continuing it
  on the FOM list?  I could post the correspondence so far and then you
  and I and others on the FOM list could continue from there.  What do
  you say?  Do I have your permission to post the correspondence up to
  the present?  I know that you are not currently a subscriber to the
  FOM list, but I can easily subscribe you.
  Another thing we could do on the FOM list is to continue the
  discussion of open problems in recursion theory as part of your
  planning for your meeting next summer, thus opening up the discussion
  to a wider group of participants.  For instance, you could provide a
  summary of what you have received so far in the way of open problems,
  and then other people on the FOM list could chime in.  Or we could do
  it some other way -- I'm open to any reasonable idea.  I think the
  subject of open problems in recursion theory is particularly
  appropriate for discussion on the FOM list, especially since you are
  apparently trying to embrace "applications" (e.g. reverse mathematics
  and perhaps other foundational topics) in the scope of your meeting.
  I do think recursion theory could benefit by broadening itself in this
  way.  Again, what do you say?
  Best regards,
  -- Steve
  Stephen G. Simpson
  Department of Mathematics, Pennsylvania State University
  333 McAllister Building, University Park, State College PA 16802
  Office 814-863-0775           Fax 814-865-3735
  Email simpson at    Home 814-238-2274
  World Wide Web
  From: Steffen Lempp <lempp at>
  To: Stephen G Simpson <simpson at>
  Subject: Re: open questions
  Date: Thu, 4 Jun 1998 12:28:11 -0500 (CDT)
  Dear Steve,
  I agree that our discussion is interesting, and you should feel free
  to post it on FOM. However, I am leaving for Italy in 5 days and am
  currently swamped with things to do, there is no way I could read all
  of FOM or participate in a meaningful wider discussion right now! (I
  get dozens of email a day already...) Maybe in the fall when I am less
  Best,			Steffen
  Office address: Prof. Steffen Lempp
  		Department of Mathematics
  		University of Wisconsin
  		480 Lincoln Drive
  		Madison, WI 53706-1388   USA
  Office phone:   (608) 263-1975 or (608) 263-3054
  Office fax:     (608) 263-8891
  WWW home page:

More information about the FOM mailing list