FOM: recursion theory: Lempp/Simpson correspondence
Stephen G Simpson
simpson at math.psu.edu
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: www.math.psu.edu/simpson/
From: Steffen Lempp <lempp at math.wisc.edu>
To: Steve Simpson <simpson at math.psu.edu>
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
sessions.
Best,
Steffen
FIRST ANNOUNCEMENT
of a
1999 AMS-IMS-SIAM
Joint Summer Research Conference
in
COMPUTABILITY THEORY AND APPLICATIONS
Sunday, June 13, 1999 to Thursday, June 17, 1999
at
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 nd.edu), Steffen Lempp
(lempp at math.wisc.edu), Manny Lerman (mlerman at math.uconn.edu) and
Richard Shore (shore at math.cornell.edu) 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
http://www.nd.edu/~cholak/computability/joint.html. Information on
how these joint meetings were arranged this year can be found at
http://www.ams.org/meetings/src.html and
http://www.ams.org/meetings/srcbroc.html. One would expect similar
arrangements in 1999.
From: Stephen G Simpson <simpson at math.psu.edu>
To: Steffen Lempp <lempp at math.wisc.edu>
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 math.wisc.edu>
To: Stephen G Simpson <simpson at math.psu.edu>
cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at nd.edu>,
Steffen Lempp <lempp at math.wisc.edu>,
Manny Lerman <mlerman at math.uconn.edu>,
Richard Shore <shore at math.cornell.edu>
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
opinion.
I am afraid this is all I can tell you at the moment.
Best, Steffen
From: Stephen G Simpson <simpson at math.psu.edu>
To: Steffen Lempp <lempp at math.wisc.edu>
Cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at nd.edu>,
Manny Lerman <mlerman at math.uconn.edu>,
Richard Shore <shore at math.cornell.edu>
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
problem.
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 math.wisc.edu>
To: Stephen G Simpson <simpson at math.psu.edu>
cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at nd.edu>,
Steffen Lempp <lempp at math.wisc.edu>,
Manny Lerman <mlerman at math.uconn.edu>,
Richard Shore <shore at math.cornell.edu>
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 math.wisc.edu>
To: Steve Simpson <simpson at math.psu.edu>
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 math.psu.edu>
To: Steffen Lempp <lempp at math.wisc.edu>
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 math.wisc.edu>
To: Stephen G Simpson <simpson at math.psu.edu>
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 math.psu.edu>
To: Steffen Lempp <lempp at math.wisc.edu>
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 math.wisc.edu>
To: Stephen G Simpson <simpson at math.psu.edu>
cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at nd.edu>,
Steffen Lempp <lempp at math.wisc.edu>,
Manny Lerman <mlerman at math.uconn.edu>,
Richard Shore <shore at math.cornell.edu>
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 math.psu.edu>
To: Steffen Lempp <lempp at math.wisc.edu>
Cc: AMS SRC Organizing Committee -- Peter Cholak <Peter.Cholak.1 at nd.edu>,
Manny Lerman <mlerman at math.uconn.edu>,
Richard Shore <shore at math.cornell.edu>
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 math.psu.edu Home 814-238-2274
World Wide Web http://www.math.psu.edu/simpson/
From: Steffen Lempp <lempp at math.wisc.edu>
To: Stephen G Simpson <simpson at math.psu.edu>
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
busy.
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: http://www.math.wisc.edu/~lempp
***********************************************************************
More information about the FOM
mailing list