No subject
Robert I. Soare
soare at cs.uchicago.edu
Mon Aug 2 13:54:07 EDT 1999
%%% fom143.epn F 8/1/99 07:45
%%%-----------------------------------------------------------------------
%% F 7/30/99 10:40 fom137 next version
%%% Abandoned fom136, decided to keep parts I, II, III
%% all in one big paper, not split into part I and topology II+III
%% in a later paper.
%% F 7/30/99: 10:50 fom 137 sent to ucb printer. Use fom137 to
%% compare hard copy.
%% F 7/30/99 13:00 fom140 more corrections from Item 1C onward.
%% Su 8/1/99 07:45 fom143. Take out satyagraha.
=========================================================================
DATE: Monday, August 1, 1999
TO: FOM (Foundations of Mathematics): fom at math.psu.edu
FROM: Robert Soare, The University of Chicago
RE: CORRECTIONS of SIMPSON'S MATHEMATICAL ERRORS
We choose NOT to discuss any OTHER parts of Simpson's memos (of June
21, July 13, July 19, July 22, etc.) which may be objectionable, NOT to
debate or excessively criticize, but JUST to correct the MATHEMATICAL
MISTAKES. Namely,
"IT'S THE ERRORS, JUST THE ERRORS!"
--------------------------------------------------------------------
BRIEF HISTORY:
Stephen Simpson, moderator of FOM, sent me, unsolicited, a copy of
his FOM "review" of the AMS Workshop on Computability Theory and
Applications (CTA) in Boulder (Simpson FOM June 21, 1999). There
were a number of mathematical mistakes, omissions, and misleading
statements in parts relating to MY OWN research area. I responded to
these with a msg to the much smaller "comp-thy" email list (of
Cholak) on July 9. (I could not respond on FOM because Simpson was
away, and because I was not member of FOM at the time.) Simpson made
some FURTHER postings (FOM, July 16, 19, 22) with corrections,
modifications and clarifications, but THE MATHEMATICS is STILL WRONG.
I have now joined FOM with the intention in order to post this msg
with the mathematical corrections.
THIS message will be posted on my WEB PAGE:
www.cs.uchicago.edu/~soare/lectures/fom.html
A lot of other RELATED MATERIAL can be found on my WEB HOME PAGE:
www.cs.uchicago.edu/~soare [Abbreviated below as simply: /~soare/ ]
I feel sure that Simpson did not make these mistakes INTENTIONALLY. I
I have some experience and expertise in these areas: Core ("Pure")
Computability Theory (CCT); computably enumerable (c.e.) sets and
degrees; priority arguments; and their connections with other
mathematical fields, such as topology and differential geometry.
(see /~soare/cv2.html.) I would like to clarify a few points.
======== ABSTRACT OF THESE THREE MATHEMATICAL ITEMS ===============
ITEM 1: SIMPSON'S THESIS ON PRIORITY ARGUMENTS
Simpson (FOM, June 21) formulated SIMPSON'S THESIS (ST) that there are
few "connections/applications" of the priority method to areas of
"applied computability." This is refuted by: nearly 200 references to
the contrary, even in Reverse Mathematics (Simpson's own field);
logical analysis of Simpson's argument; and by the supporting
testimony of other expert witnesses in a variety of areas.
--------------------------------------------------------------------------
ITEM 2: COMPUTABILITY AND TOPOLOGY, Paper NW-1: SIMPSON GOT IT WRONG TWICE.
At the AMS Boulder meeting Nabutovsky (Toronto) and Weinberger
(Chicago), announced two very interesting papers, NW-1 and NW-2,
applying computability theory and specifically computably enumerable
(c.e.) sets to problems in topology and differential geometry.
Simpson (FOM, June 22) quoted from NW-1, but got it WRONG. He then
tried again and STILL claimed,
>
> (Simpson, FOM, July 16):
> However, I don't think this a very SERIOUS error on my part.
> It is an error of ATTRIBUTION, not SUBSTANCE.
>
But his ORIGINAL mistake (NOT corrected in his later July 16 posting)
was INDEED an ERROR of SUBSTANCE; in fact it was a MAIN POINT as
the topologist had EARLIER stated.
--------------------------------------------------------------------------
ITEM 3: SIMPSON OMITTED A **KEY NEW** APPLICATION OF COMPUTABILITY,
TOPOLOGISTS' NABUTOVSKY AND WEINBERGER PAPER NW-2
Simpson (FOM June 21) did NOT mention AT ALL one of the most exciting
parts of the Boulder conference and of paper NW-2, an announcement of
a theorem on comparing the depths of local minima on manifolds, and
the distance between them, using the Sacks Density Theorem [1964] for
computably enumerable (c.e.) degrees, proved by a priority argument,
and did even give an ANNOUNCEMENT of ANY of the exciting topologists'
results announced at Boulder relating computably enumerable (c.e.)
sets to scales on the manifold, a topic already presented in numerous
seminars and in TWO lectures at Boulder. Simpson explains that he had
DELIBERATELY OMITTED this material,
>
> Simpson (FOM July 16):
> "BECAUSE, FRANKLY, I DON'T TRUST THESE CLAIMS."
>
Simpson does not say EXACTLY WHAT he mistrusts here. Is it the
THIRTY-FIVE YEAR OLD Sacks Density Theorem [1964]; or the TOPOLOGISTS'
ANNOUNCED APPLICATION of it to fractals and manifolds?
ITEM 4. SUMMARY of mistakes and omissions in ITEMS 1,2, and 3.
ITEM 5. EPILOGUE
This does not belong to the mathematical part of the paper, but
contains some remarks on the philosophy of foundations of computability,
using the Socratic method as a way to glimpse the truth.
==================== END OF SUMMARY ================================
======================= BODY OF THE PAPER ==============================
ITEM 1: APPLICATIONS OF CORE COMPUTABILITY AND PRIORITY METHODS:
ITEM 1A: "SIMPSON'S THESIS" ON PRIORITY ARGUMENTS
Simpson (FOM, June 21) stated his thesis, now known as,
>
> SIMPSON'S THESIS (ST): [since Simpson, FOM, July 22]:
> ``priority methods are almost completely absent from applied
> recursion theory.''
>
Since Simpson later viewed this as a bit "imprecise," he later
clarified this,
>
> (Simpson, FOM, July 16):
> My actual view is that the pure/applied DISTINCTION is almost always
> CONFUSING and HARMFUL, both in mathematics generally and in recursion
> theory particularly. What does it mean to ``apply'' one branch of
> pure mathematics to another branch of pure mathematics? Wouldn't it
> be better to speak of a ``CONNECTION'' RATHER THAN an ``APPLICATION''?
>
[The emphasis here is mine.]
Simpson continued later in the same vein ,
>
> (Simpson, FOM, July 22):
> In the present context, it seems MORE LEGITIMATE to speak of
> ``CONNECTIONS'' between recursion theory and other parts of
> mathematics, RATHER THAN ``APPLICATIONS'' of recursion theory.
>
Putting these two statements together with ST it seems that Simpson
really MEANT to assert is,
>
> SIMPSON'S THESIS (restated) (ST'):
>
> "Priority methods are almost completely absent from
> `connections/applications' with applied recursion theory."
Which is it Mr. Simpson, ST or ST'? It doesn't really matter because
they are BOTH REFUTABLE.
-------------------------------------------------------------------------
ITEM 1B: GATHERING AN OVERWHELMING NUMBER OF COUNTER EXAMPLES
In only a few days computability theorists have gathered nearly TWO
HUNDRED references to refute Simpson's Thesis (ST), including a NUMBER
IN REVERSE MATHEMATICS (Simpson's OWN research area), with hundreds
more to come. These references are posted on the web page,
www.cs.uchicago.edu/~soare/lectures/applications.html
Definitions of the three areas of computability theory suggested by
Jockusch including the core (pure) computability and the two
"interactive" or applied area may be found in,
www.cs.uchicago.edu/~soare/lectures/corrections.html
These are certainly "connections," and so they refute ST' in ANY case.
Finding both statements of his thesis on shaky ground, Simpson has
added additional conditions NOT present earlier, such as "is the
priority method NECESSARY?" "Could it have been REPLACED by another
method?" We deal with these LATER. (Even with these FURTHER
modifications of ST and ST' it is still not difficult to REFUTE
them, as we shall see.)
-----------------------------------------------------------------------------
ITEM 1C: MARTIN'S BOREL DETERMINACY AND HARRINGTON'S REVERSE MATHEMATICS.
Priority arguments are nothing more than computable approximations to
diagonal arguments or other noneffective theorems. For example, Let K
be Godel's diagonal c.e. non computable set [1931] and let 0' also
denote K. Kleene-Post [1954] used a 0'-oracle construction to build
two sets A and B computable in 0' which are incomparable under Turing
reducibility.
Friedberg-Muchnik [1956-57] took the SAME strategy, but EFFECTIVIZED
it using a PRIORITY construction to eliminate the dependence on a
0'-ORACLE, and produced the STRONGER AND MORE EFFECTIVE result that
there exist computably enumerable sets which are Turing incomparable.
Thus, the priority method generally operates in the setting of a
COMPUTABLE construction (rather than an ORACLE construction or a
classical proof as often in algebra, analysis, or topology) and it is
therefore more CLOSELY tied to many real world APPLICATIONS, and to
COMPUTER SCIENCE, both theoretical and applied.
Many others, such as Nerode and his school of students and co-workers,
like Kalantari, Remmel, Millar and many others, and the entire RUSSIAN
school work on problems involving effectivizations of classical
results in algebra, analysis, model theory, and many more. Priority
arguments are used BOTH to find effectivizations IF they exist, and
often to REFUTE their existence if they do NOT. If we DISCARD
PRIORITY ARGUMENTS we discard a MAJOR TOOL for analyzing the EFFECTIVE
content of mathematics.
Like other approximations in mathematics, priority methods have a
very useful role. For example, the first proof of Tony Martin's
beautiful result on BOREL DETERMINACY was proved by a priority
argument. Later proofs were given, but it was the PRIORITY proof
which led to the DISCOVERY of Borel Determinacy.
in Reverse Mathematics ITSELF, Leo Harrington [1979] proved that that
boldface Sigma-1-1 axiom of choice does not imply lightface Sigma-1-1
dependent choices. A precise statement of these two definitions and
the relationship to the BOLDFACE version proved by John Steel in his
1975 thesis can be found on Soare's WEB page:
www.cs.uchicago.edu/~soare/lectures/steel.text
Harrington and Steel explain there how a priority argument is the
right method to use in order to MAKE the EARLIER boldface Steel proof
more "EFFECTIVE," a typical use of the priority method applied by
Harrington and others many times, to effectivize a noneffective
result. Steel writes there,
> In my proof, that para. was introduced by forcing over L_omega_1^ck,
> so it was not even Hyp. Leo showed how to construct a recursive
> parameter. He had to control the Sigma_1^1 properties of this para.,
> and for that the "shiny box" technique came in.
>
[The "shiny box" technique is a method of Sacks [Proc. AMS, 1967],
"On a theorem of Lachlan and Martin," where Sacks uses a beautiful
method he calls the "shiny little box" to present a simpler proof of
what had been a much more difficult theorem.]
------------------------------------------------------------------------
ITEM 1D: THE LOW BASIS THEOREM
A very often applied theorem is the Low Basis Theorem, first
discovered by Jockusch and Soare [TAMS, 1972], using a priority
argument. As a co-author, I can say with CERTAINTY that this theorem
might very well NEVER have been discovered without the priority method,
and that the later 0'-oracle proof (see Soare's book, [1987, p. 109])
is just the CONVERSION of the ORIGINAL priority proof obtained simply
by using a O'-oracle to analyze the injury pattern in the priority
proof, and then taking the action in ONE step, instead of waiting for
the computable construction to unfold.
As a co-author I can EMPHATICALLY say that the MATHEMATICAL,
CONCEPTUAL, INSPIRATIONAL, and INTELLECTUAL basis of this theorem lies
in the FIRST proof using the PRIORITY METHOD; the second proof is
merely a direct consequence of the first ideas.
-------------------------------------------------------------------------------
ITEM 1E: REVERSE MATHEMATICS: SEVERAL EXAMPLES
Simpson (FOM, June 21) proclaims that, "my book on reverse mathematics
contains absolutely no applications of priority arguments." However,
there ARE a number of Reverse Mathematics results proved by priority
methods, in addition to the Sigma^1_1 AC result by Harrington above.
Slaman noted that in Reverse Mathematics Leo HARRINGTON adapted the
proof of the Low Basis Theorem to nonstandard models and showed that
WKL_0 (Weak Konig's Lemma_0) is conservative over RCA_0 for Pi^1_1
sentences. The Low Basis Theorem was also applied in David Seetapun's
proof that Ramsey's Theorem for pairs does not imply ACA_0 over RCA_0.
These are examples of places where core computability theory (CCT)
made an essential appearance. (These are not necessarily all priority
arguments directly, although the Low Basis Theorem was discovered by a
priority argument as explained above.)
If one specifically desires applications of the priority method to
Reverse Mathematics, then Mytilinaios and Slaman used a priority
argument in their Reverse Mathematics paper, "On a question of Brown
and Simpson," and solved a problem posed by Brown and Simpson in 1993.
Reed Solomon in his 1997 Cornell Ph.D thesis on Reverse Mathematics
used a priority argument. Simpson (FOM June 21) HIMSELF points out
still ANOTHER such application to Reverse Mathematics by Kucera which
answers a question of Julia Knight about Pi^0_1 classes.
------------------------------------------------------------------
ITEM 1F: ALGEBRA, MODEL THEORY, LINEAR ORDERINGS, JUMPS OF STRUCTURES
Simpson concedes (FOM, July 22) that for computable model theory,
computable linear orderings, computable Boolean algebras, jump degrees
of structures, "it is true that priority arguments are used
extensively." The Nerode-Remmel-Kalantari-Millar school has a great
many results using priority arguments obtained for over 35 years.
Likewise the Russian equivalent in Novosibirsk or elsewhere in Russia.
There are many other results in analysis and topology. These examples
ALONE are enough to refute Simpson's Thesis in ANY form.
------------------------------------------------------------------
ITEM 1G: APPLICATIONS OF THE PRIORITY METHOD IN COMPUTER SCIENCE
Simpson (FOM June 21) specifically includes "theoretical computer
science" under his category of "applied recursion theory," but he
asserts (FOM July 22) that theoretical computer science and
complexity theory do NOT use priority arguments. This is challenged
by Steve Fenner (FOM July 26), a computer scientist with publications
in theoretical computer science. Also recall that the Blum Speedup
Theorem has a finite injury priority argument.
Stuart Kurtz, Professor and Chairman of the Department of Computer
Science at the University of Chicago, gives several references for use
of the priority method in theoretical computer science and writes
(FOM July 27), (with some short excerpts here):
>
> ...
> By using a PRIORITY ARGUMENT, we were able to demonstrate that a
> collapsing degree exists in exponential time -- a far more interesting
> and significant result, ...
>
> I think it is worth knowing that organizing real computations around a
> dynamic collection of goals, each of which with a particular PRIORITY,
> is a GENUINELY USEFUL APPROACH. ....
>
> Indeed, a PRIORITY BASED PROGRAMMING ARCHITECTURE is so common and
> useful that specialized data structures have been developed to support it
> ...
> The moral may be surprising, even to a computability theorist.
> PRIORITY METHODS are ROUTINELY TAUGHT to freshmen computer scientists,
> and they are a major organizing principle of many large programs,
See Professor Kurtz's ENTIRE statement in (FOM July 27), or my WEB page:
www.cs.uchicago.edu/~soare/html/lectures/kurtz.html
-----------------------------------------------------------------------------
ITEM 1H: THE SOCRATIC DIALOGUES AND CHANGING GROUND
Simpson (FOM, July 22), when confronted with the list above of
nearly 200 applications, replied there were still many MORE applications
of the priority method in PURE recursion theory than APPLIED
recursion theory and THAT is what was his original point in stating
Simpson's Thesis.
> ---[Simpson (FOM, July 22)]: ---
> First of all, I think everyone agrees that priority arguments are
> *much less* prevalent in ``applied recursion theory'' than in the
> ``pure'' theory of r.e. sets, r.e. degrees, etc. That contrast was my
> original point in stating Simpson's Thesis, and I think it is a valid
> and important point for anyone interested in recursion/computability
> theory to keep in mind."
This argument CONFOUNDS first order logic and BEGS a Socratic dialogue.
> SOCRATES:
> "But Alcibiades, if there be 200 applications of A to B, and
> in ADDITION there be 500 applications of A to C does the
> multitude of 500 diminish the effect of the 200,
> or does it merely demonstrate the enhanced intellectual
> vitality of A, and thereby increase its chance of still MORE
> applications of A to B in the FUTURE?
>
> "And anyway, Alcibiades, if your thesis (even as MODIFIED)
> mentions ONLY applications of A to TOPIC *B*
> what relevance is it if there are any connections of A to C
> at ALL or a multitude of them? The point is CONNECTIONS
> of TOPIC A TO TOPIC B. Any other topics are entirely
> irrelevant.
>
[Adapted from Plato's work, "Symposium," in which a dialogue between
Socrates and Alcibiades takes place, as Alcibiades takes one
unreasonable position after another. Socrates, with gently probing
questions, gets him to abandon each one. See also the EPILOGUE here
for MORE on Socratic dialogues and their relevance to this discussion
of FOUNDATIONS of mathematics.]
------------------------------------------------------------------------------
ITEM 1I. "PROOF CLEANSING" OF PRIORITY ARGUMENTS
When confronted with the list of nearly 200 applications, Simpson
THEN asked whether the use of the priority method
in each proof was ESSENTIAL or could be removed.
>
> (Simpson, FOM July 22)
>
> For each ``application'' of recursion theory, we need to say
> what the field of application is, whether the statement of the
> result or only the proof involves recursion-theoretic concepts,
> which recursion-theoretic concepts and/or methods and/or results are
> used, WHETHER the recursion-theoretic concepts and/or methods and/or
> results can be ELIMINATED, what are the costs of eliminating them,
> etc. There are many distinctions to be made, and these distinctions
> are of essential scientific importance.
If the priority method proved a theorem FIRST, what does it MATTER
whether later on there is ANOTHER (maybe even better, simpler,
shorter) proof? For example, Jockusch and Soare first proved the
often applied Low Basis Theorem with a priority argument, and then
they discovered an oracle proof (see Soare's book [1987, p. 109]).
Martin's Borel Determinacy was first proved with a priority argument,
and then later was given another proof.
In such a case there must have been an original intellectual and
conceptual CONNECTION with the priority method, or the priority
argument would NOT have been used in the DISCOVERY. Whether the
original priority proof can be replaced by a non priority proof
matters little to the DISCOVER of the theorem, only to those who come
LATER to analyze the proof strength, proof methods, and so on.
The attempts to remove all priority arguments from connections and
applications to other areas reminds me of the attempts by analysts
around 1970 to remove NONSTANDARD ANALYSIS (and by implication logic)
from proofs in analysis. Bernstein (a student of Abraham Robinson)
used nonstandard analysis in the late 1960's to solve an important
open problem on invariant subspaces under a polynomially compact
operator on a Hilbert space. Immediately, the analysts converted this
into a "STANDARD" proof of the same result "which the analysts could
understand" by a proof which was almost an exact translation of
Bernstein's proof into more standard analysis terms. The key point is
that Bernstein's proof yielded the DISCOVERY of a result which the
analysts had been UNABLE to solve using "STANDARD" methods of
analysis. Let's get the DISCOVERY FIRST; the "PROOF CLEANSING" can
come later.
It is natural for reverse mathematicians to want to study whether the
priority method is essential to an argument or not, but this can be
done LATER, and should first DISCOVER a proof, and if a priority
argument will do it, do we strip the laurels from the discoverer just
because some later person, who had not been on the arduous discovery
trip, finds another proof?
-----------------------------------------------------------------------
ITEM 1J: WHY "MUST" IT BE SO?
Friedman (FOM, July 19, 1999) wrote,
> In order to refute what Simpson intends to claim [i.e., Simpson's Thesis]:
> ***The use of priority arguments either HAS to be apparently NECESSARY, or
> at least give the SIMPLEST proof for the general mathematical logician. The
> priority arguments CANNOT be ROUTINELY ELIMINATED.***
ABSOLUTE NONSENSE!!
Simpson's Modified Thesis (ST') says "CONNECTION" rather than
"application," so the 200 references ALREADY refute it. Furthermore,
in working mathematics one FIRST USES a priority argument to prove a
result like Martin's Borel Determinacy result, the Low Basis Thm, or a
result on fractals (NW-2) in differential geometry. AFTER it is
discovered, Then some OTHER logicians can ANALYZE its EXACT LOGICAL
CONTENT in the context of a formal or informal logical system,
alternative methods of proof, while the DISCOVERY PEOPLE just want to
get on and USE the method to DISCOVER MORE theorems in logic, algebra,
topology and computer science.
------------------------------------------------------------------------
To put another way, if COLUMBUS has ships and a crew and sets sail for
a new world, do we ask whether there is ANOTHER ship off the coast of
Spain which MIGHT get there as well, another route which is shorter or
faster? After Columbus reaches the New World, many others leave the comfort
of their armchairs in Spain and journey comfortably along the route
he has blazed. They may find
the shortest trade routes, those with the most favorable winds,
the most comfortable islands to stop for refreshment, and other
useful analyses.
This is worthwhile work, but DISCOVERY comes first, and the laurels
rest with the DISCOVERER, whatever his inspiration and methods, NOT
the subsequent analyzer who comes in his wake.
-------------------------------------------------------------------------
Were the TOPOLOGISTS who used the SACKS DENSITY THEOREM (proved by an
infinite injury priority argument) thinking, as they applied it to
fractals in NW-2? Were they thinking,
"I wonder WHETHER a NON PRIORITY PROOF will work?"
"Is the USE of a priority argument here ABSOLUTELY necessary?
"Can it be routinely ELIMINATED?"
OR were they thinking, "this is what I need in the proof; it works;
now let's get on with further deeper discoveries."
When Columbus' men were ready to muntiny and believed their ship was
about to fall off the edge of the earth if they went one day further,
did Columbus think, "I wonder what the shortest trade route will be?"
-----------------------------------------------------------------------
The quotes at the tops of ITEMS 1I and 1J illustrate the HUGE GAPS in
philosophy, approach, and value of mathematical items, between the
REVERSE MATHEMATICIAN and the ACTIVE RESEARCHER in mathematics from
TOPOLOGY to COMPUTABILITY THEORY. The former is eager to analyze the
proof strength, axiomatic necessity, etc. of hypotheses but of mostly
EXISTING theorems, while the working mathematician wants to get on
with proving NEW theorems, (with as little TIME wasted on EMAIL and
INTERNET LIST FORUMS as possible).
---------------------------------------------------------------------------
ITEM 1K: APPLICATIONS OF *REVERSE MATHEMATICS* TO COMPUTER SCIENCE.
By the way, at Simpson's request, we in computability and computer
science have been analyzing the many applications of CCT in general
and the priority in particular to theoretical and even practical
computer science as discussed here by Kurtz, and Fenner.
NOW let us put the shoe on the OTHER foot. Here are some questions
for Mr. Simpson about the value and applications of Reverse
Mathematics.
QUESTION. what are the APPLICATIONS of REVERSE MATHEMATICS to computer
science? I do not mean the analysis of OLD theorems, their proof
strengths, whether they require WLK_0 of ACA_0, but brand NEW theorems
DISCOVERED using Reverse Mathematics.
---------------------------------------------------------------------------
ITEM 1N: WHAT IT THE *RATIO* OF PRIORITY METHODS TO OTHERS IN CS?
Simpson STILL seems intent on raising the question of the ratio of
arguments which use priority arguments to those that do not.
> Simpson (FOM July 27, reply to FENNER FOM July 26)
> But then, what about the ratio of papers in theoretical
> computer science (or perhaps even computational complexity theory)
> that use priority arguments, to those that don't?
SIMPSON'S THESIS (ST) just claimed "few applications" ALTOGETHER.
If we can demonstrate a few here and a few there, they add up
to "MANY."
QUESTION. How many applications of REVERSE MATHEMATICS (R/M) are
there to computer science? Exactly what are they?
SIMPSON (FOM, July 27) "Now, it seems to me the next question is: How
prevalent are priority arguments in this area?"
QUESTION. How prevalent are "REVERSE MATHEMATICS APPLICATIONS"
in this area?" Exactly what are they?
SIMPSON (FOM July 27, answering Fenner) "My impression is that this
ratio is rather small. Is it as high as 1/10 of a percent? Contrast
this to the ``pure'' theory of r.e. sets and Turing degrees, where
almost every paper uses priority arguments."
ANSWER. This is refuted by Socrates exactly as in Section 1H.
QUESTION. SIMPSON (FOM July 27, answering Fenner)
"It is also relevant to ask whether the priority arguments can be
eliminated, and what are the costs and benefits of eliminating them.
Fenner points to a priority argument used to construct an oracle in
computational complexity theory."
ANSWER. WHO CARES, whether it can be eliminated? Certainly not
the computer scientist interested in getting NEW results.
(See ITEMS 1L and 1M above.)
----------------------------------------------------------------------
RULES FOR COUNTING "APPLICATIONS" OF FIELD A TO ANOTHER FIELD B :
These are rules which most working mathematicians would honor from
topology, algebra, analysis to computability theory and mathematical
logic. In this case field A is Reverse Mathematics (R/M).
RULE 1. The application must involve a brand NEW RESULT in field B,
not previously known (e.g. Martin's first proof of Borel Determinacy,
the Low Basis Theorem, Harrington's proof on dependent choices.)
RULE 2. It does NOT MATTER whether the method or ideas from A in this
proof are LATER eliminated or weakened, or modified.
It only matters whether the DISCOVERY (i.e. FIRST) proof
involved the methods and ideas from A. Just as if Smith
FIRST proved a theorem and LATER Jones gave a much better,
simpler proof. It is still forever "Smith's Theorem."
RULE 3. If workers in field A LATER analyze the proof strength,
or the logical setting, or any of a host of other foundational
issues about this application of the method and results,
OR
if they prove that method applied in the proof or
the logical principles of the theorems and
are even EQUIVALENT to a known logical or mathematical principle,
THIS DOES NOT MATTER AT ALL for our count.
Field A must contribute by its KNOWN RESULTS or KNOWN
METHODS to a NEW RESULT, a discovery or a result of intrinsic
interest to the researchers in field B, not new result of A
which involves merely the logical or mathematical analysis
of an existing result in field B. (For example,
the APPLICATION OF C.E. SETS and PRIORITY ARGUMENTS to the
fractals in NW-2 is such a new result in topology,
as discussed above in ITEM 3.)
----- END OF THE RULES FOR COUNTING APPLICATIONS OF REVERSE MATH ----
Simpson (FOM, Jul 22) specifically asks about UNDECIDABILITY,
>
> undecidable problems in mathematics (Diophantine problems,
> combinatorial group theory, etc.)
>
QUESTION 1-R/M.
When has REVERSE MATHEMATICS (R/M) SOLVED a problem on UNDECIDABILITY
(such as Hilbert's 10 problem, or the word problem for finitely
presented groups, where priority arguments were used by Boone to get
such a word problem of EVERY C.E. DEGREE, or such as in the latest
undecidability results in topology N-W papers in Items 2 and 3, where
they get BOTH UNDECIDABILITY results and ALSO STRUCTURAL results for
fractals and other topological objects using priority methods and
c.e. sets? What EXACTLY are these applications of Reverse Mathematics
to get NEW undecidability results in MATHEMATICS (algebra, analysis,
topology, etc.) and NOT to analyse OLD such proofs with Reverse
Mathematics methods?
QUESTION 2-R/M
A well-known senior mathematician asked me the following questin
about Reverse Mathematics (R/M) but I could not answer it and therefore
pose it as an open question for the subscribers.
> "What's the point in RM to prove reversals for the next 100 theorems
> after you've seen 500? ... Is there a program, or is it just "take
> your favorite math book and reverse"?
I believe that Simpson and Friedman can answer these questions and
can supply us with many references meeting these rules above,
probably as many as the nearly 200 "connections/applications" as we
have listed earlier for priority methods. I am simply not familiar
enough with R/M to list them myself.
=============================================================================
ITEM 2. COMPUTABILITY AND TOPOLOGY
ITEM 2A. SIMPSON GOT IT WRONG TWICE.
Nabutovsky (Toronto) and Weinberger (Chicago), announced two very
interesting papers NW-1 and NW-2, applying computability theory and
specifically computably enumerable (c.e.) sets to problems in
topology and differential geometry. (NW-1 has been submitted for
publication, but NW-2 is only in a 29 page draft form without proofs.
Weinberger gave an hour lecture on these at Boulder. See some remarks in,
www.cs.uchicago.edu/~soare/lectures/geometry.html, and
www.math.uchicago.edu/~shmuel
In Simpson's June 21 statement Simpson attempted to RESTATE the main
result in NW-1 and got it WRONG. Soare (July 9) quoted a statement
from a coauthor of NW which CONTRADICTED Simpson's statement. In
Simpson's third msg on this topic (FOM July 16), Simpson changed the
ATTRIBUTION but not the mathematical CONTENT, so that his revised
statement is STILL INCORRECT and is STILL NOT IN AGREEMENT with the
topologist co-author's main comments as quoted by Soare in the July 9
msg. (See: www.cs.uchicago.edu/~soare/lectures/geometry.html.)
In his attempted reply Simpson wrote,
>
> --- (Simpson, FOM July 16) ---
> I also quoted the Novikov result, but I mistakenly
> attributed it to Markov. Mea culpa. However, I don't think this a
> very serious error on my part. It is an error of attribution, not
> substance.
>
According to the quote by the topologist, it WAS INDEED an error of
SUBSTANCE. In fact it is the MAIN POINT. See the topologist's quote
and full explanation:
www.cs.uchicago.edu /~soare/lectures/corrections.html
Simpson describes NW-1 as a "refinement" of an UNDECIDABILITY RESULT.
In the Soare July 9 quote, but the TOPOLOGIST CONTRADICTS
Simpson about NW-1,
>
> "Our main
> result is *NOT* an UNDECIDABILITY result, although we *DO* have a
> new undecidability result that is crucial for the proof of the main
> theorem."
------------------------------------------------------------------------
ITEM 2B: SIMPSON LEFT OUT A KEY PIECE.
See
www.cs.uchicago.edu/~soare/lectures/geometry/paper1.html
for the details which are only VERY briefly sketched here. Nabutovsky
and Weinberger (NW-1) wrote, in THEOREM A (NW-1) P. 3 (Informal
version), that if M^n is any compact n-dimensional manifold of
dimension > 4, then For all sufficiently large x the sublevel set
diam^{-1}((0,x]) of diameter regarded as a functional on R_1(M^n) is
not connected. Moreover, it can be represented as a union of DISJOINT
non-empty subsets ("components") separated by a "gap" (in the
Gromov-Hausdorff metric) and very roughly the "distance" function
between gaps is NOT computably bounded.
The KEY PART here is that the components are very far apart, so far
that the distance function between them cannot BE MAJORIZED by any
COMPUTABLE FUNCTION. After reading the paper, Soare asked Weinberger
whether the function indeed MAJORIZES every computable function
(something much stronger), which would make it at least of high
degree. The reader familiar with core computability theory (CCT), say
in Soare's [1987] book, will instantly recognize the connections to
familiar objects using domination properties, such as Post h-simple
sets, Martin's dominant sets, high sets, and maximal sets.
It is EXCITING to see computable domination properties and other CCT
properties used to measure distances between these components in
topology. Weinberger thought the stronger domination property which
Soare suggested could be proved, but was not sure, and will think it
through.
Again the INTERESTING THING HERE as in Item 2A is that this is NOT a
mere UNDECIDABILITY result, but a statement which uses DEEPER
PROPERTIES of functions in the hierarchy of functions TURING
COMPUTABLE in 0', namely the \Delta_2 degrees of unsolvability.
Simpson gives NO MENTION of this even though Soare provided Simpson
with a copy of NW-1 which Simpson xeroxed at the Boulder meeting
and "read on the plane home."
===========================================================================
ITEM 3: APPLYING COMPUTABLY ENUMERABLE SETS TO TOPOLOGY
ITEM 3A *TRUSTING* ANNOUNCED RESULTS OF RESPECTED MATHEMATICIANS
In his posting (FOM June 21), Simpson FAILED to mention some of the
key announced results from NW-2, including an application of
computably enumerable (c.e.) sets and degrees to compare the depth of
local minima on a manifold, and their distance from one another. This
was even more surprising because Simpson has been stressing
APPLICATIONS of computability to OTHER branches of mathematics, and
this was one of the MORE INTERESTING APPLICATIONS of computably
enumerable sets and degrees to topology in twenty-five years.
When Soare (July 9) pointed this out, Simpson (FOM July 16) replied,
> "It's true that I didn't say much about the claims that Soare made in
> his Wednesday evening talk and in questions 10 and 11 above. That's
> because, frankly, I don't trust these claims."
It is not clear just WHAT Simpson does "NOT TRUST."
(1) Does Simpson NOT TRUST the Sacks Density Theorem (SDT), Annals of
Math. [1964], which shows that between any two computably enumerable
(c.e.) degrees there is another? The proof (a priority proof) has
been well-known for thirty-five years. (See the reference book by
Soare, Springer-Verlag, [1987, p. 142].)
(2) Does Simpson NOT TRUST the TOPOLOGY AUTHORS, Nabutovsky and
Weinberger, the authors who claim that the SDT can be applied to give
the result on depths of local minima they have announced. It is true
that they do not actually give a full WRITTEN PROOF in their 29 page
working draft, but results are often ANNOUNCED at meetings before they
have been written, since they wrote it down in draft form, and
Weinberger spoke on it in an hour lecture talk at Boulder and
elsewhere.
Just exactly WHAT DOES SIMPSON DISTRUST so much that he was
unwilling to report even an alleged STATEMENT of their announced
result (possibly with a disclaimer that he had not seen a proof)?
-----------------------------------------------------------------------
ITEM 3B USES OF COMPUTABILITY THEORY CLAIMED IN THE NW-2 PAPER:
The NW-2 paper is still preliminary with mostly intuition and
statements (and not complete proofs) of results and connections, but
it suggests some very interesting INTERACTIONS between computability
and differential topology. These are a few direct quotes from NW-2.
There are more quotes there on connections between c.e. sets,
c.e. degrees, and (Turing degrees) with topology and differential
geometry. Nabutovsky-Weinberger (NW-2) write:
> ``Informally, each c.e. degree determines a scale, and at that scale
> there are many distinguished local minima of diameter, that are deep
> in that scale.''
> `` ... in addition to Turing machines being
> useful as a measure of rates of growth, we also find them useful in
> the description of types of subsets of the integers ... ''}
> ``In order to space out our critical points
> suitably around Met(M), we will also vary the `seed' group in
> terms of degree of unsolvability.''
> ``By the ideas of G\"odel [Incompleteness Theorem] which are at the
> heart of this paper, this is what must be the case by the very
> nature of mathematics.''
Regarding use of computably enumerable degrees and the Sacks Density
Theorem used in the NW-2 theorem on page 3, the authors write,
> "For every closed smooth manifold M^n of dimension > 4, and every
> c.e. degree \alpha, there are exp(d^n)
> local minima of diameter functional on the subset of Met(M)
> consisting of metrics with curvature bounded in absolute value
> by 1; The local minima are represented by points of smoothness
> C^{1,\alpha}, and have depth > \gamma(d) for any c.e. degree
> \gamma < \alpha. These points are \alpha(d)-dense in Met(M).
It is unusual and very encouraging to find quotes in a topology paper
and results which link up computability and c.e. sets with local
minima in differential geometry.
============= ITEM 4: SUMMARY OF ITEMS 1, 2, AND 3 ====================
POINT 1. (Dismisses talks negatively without discussion.)
Simpson (June 21, 1999) writes a review of the lectures at the
Boulder meeting, and ALL the talks dismissed with remarks like
> "Another `pure recursion theory' talk" or
> "Why should anyone be interested in this?"
are talks in core ("pure") computability theory (although
some "pure" talks got good reviews).
------------------------------------------------------
POINT 2. (SIMPSON'S THESIS.)
Just before and just after Boulder, Simpson proclaimed to FOM
"SIMPSON'S THESIS," but neglected to mention it to the 60 participants
at the week long meeting who could have refuted it on the well-known
evidence as we have done here. THAT was a REAL open forum with
virtually ALL the world experts and the face to face possibility for
debate and discussion.
------------------------------------------------------
POINT 3. (Topology paper, NW-1.)
After the exciting new results by Nabutovsky and Weinberger presented
at Boulder, Simpson tried to summarize their first paper, NW-1, which
he had "read on the plane," but he presented it in a form which the
topologist authors found inaccurate and SAID so. When told of the
mistake with an EXPLICIT quote from the topologist co-author, Simpson
corrected only the attribution and left the mathematical mistake
untouched.
Meanwhile, Simpson OMITTED to mention a key new feature of the
main Theorem A of NW-1, a relationship between topology and functions
not dominated BY, or perhaps THEMSELVES dominating, all COMPUTABLE
functions, a MOST unusual theorem in a topology paper for its mix
of computability theory.
But this is in Core ("PURE") Computability Theory (CCT),
for which Simpson has already expressed his "impatience."
------------------------------------------------------------------
POINT 4. (Topology paper NW-2.)
Simpson OMITTED ALL MENTION of the announced result by Weinberger
from NW-2 that c.e. sets and the Sacks Density Theorem can
be applied to measure relative depth of local minima on a manifold.
Simpson explained later that he had deliberately omitted this material,
Simpson (FOM July 16): "BECAUSE, FRANKLY, I DON'T TRUST THESE CLAIMS,"
namely the combination of: (1) the Sacks Density Theorem; and (2) the
announced topologists application of it to fractals and manifolds.
-----------------------------------------------------------------------
The material omitted, misstated, or distorted in POINTS 1, 2, 3,
and 4 all happened to be in certain PARTS of Core ("Pure")
Computability Theory, particularly in computably enumerable sets and
degrees, for which Simpson has expressed his distaste for over a
decade.
I am SURE that this was just a coincidence.
======================ITEM 5. EPILOGUE =========================
REACHING OUT TO FOM SUBSCRIBERS:
As a new subscriber I want know to more of the opinions of the vast
silent majority of the 380 FOM subscribers, not just the few who send
in their opinions very often. In addition to any public comments
posted on FOM about this paper, please SEND ME PRIVATE EMAIL with your
comments and suggestions, because one can often say things in private
which one cannot say as candidly or as completely in public for a
variety of reasons. If I do not hear from you I will assume that
almost no one of the 385 subscribers is listening, and I will not
waste time writing more submissions.
TOPICS FOR FUTURE FOM MESSAGES:
I entered this FOM group just to make the enclosed corrections,
but if there is interest in any of the following topics I may continue
with future postings, and I welcome replies.
-----------------------------------------------------------------------
1.EXPOSITORY NOTES ON METHODS AND RESULTS OF COMPUTABILITY THEORY:
The recent discussion on priority methods and CCT indicates a woeful
lack of understanding by some of the most frequent contributors on
basic elements of computability. My book ("Recursively Enumerable
Sets and Degrees, Omega Series," Springer Verlag, 1987) has almost
exhausted its 4000 copy print run. I am under contract with
Springer-Verlag to write a new book (not just a second edition)
"Computability Theory and Computably Enumerable Sets", which will deal
with some CONCEPTUAL issues as well as TECHNICAL ones.
For conceptual issues on computability, see also Soare, "Computability
and Recursion", Bulletin, Symbol. Logic, 1996; and in the Handbook of
Computability Theory (North Holland), see Chapter 1 by Soare, "The
History and Concept of Computability".
>From these materials and others Soare has been thinking about lately,
such as "What is the conceptual analysis (as opposed to mere theorems
about) a c.e. (i.e. Sigma_1) process, namely one with a single
existential quantifier? Why do Sigma_1 processes occur so frequently
in other branches of mathematics: word problems for groups, number
theory, topology and differential geometry, fractals, theoretical
computer science and complexity theory? What standard tools for
dealing with Sigma_1 processes are most effective in giving CONCEPTUAL
and INTELLECTUAL connections (e.g. Kleene recursion theorem, effective
forcing arguments, priority arguments, Lachlan tree of strategies
method)>
If any FOM member is interested in a dialogue on these issues please
send me a PRIVATE message. AFTER we have thought it through we may
THEN have something to post on FOM.
2. FOUNDATIONS OF MATHEMATICS: **PHILOSOPHY** FIRST
To examine the FOUNDATIONS of mathematics (FOM) in the TRUE and
CLASSIC sense of the word, one should start with PHILOSOPHY. One of
the cornerstones of the beginning of Western philosophy was Plato's
collected words, particularly the SOCRATIC DIALOGUES; (alluded to
earlier in ITEM 1H). (For the following page references, see: Irwin
Edman, editor, "The Works of Plato," The Modern Library, Random House,
1928.)
Edman writes,
> "Plato never reveals nor seeks to reveal the secret of the universe,
> yet, in his pages, one seems constantly to hear it whispered.
> Nothing is settled in the dialogues, but everything is somehow
> clarified and enhanced."
Edman continues,
> "His [Socrates'] aim is not to win a debater's victory over an
> opponent, but to clear the atmosphere of false or irrelevant
> definitions, to arrive at the essential character of **essence** of a
> virtue or idea."
The reply to one's opponent in the debate should be carefully and long
considered. In Plato's "Symposium", Alcibiades (perhaps foretelling
the "SHOOT FROM THE LIP" e-mail messages alluded to by Downey, FOM
July 26), says,
>
> "But you must not wonder if I speak anyhow as things come into my
> mind; for the fluent and orderly enumeration of all your singularities
> is not a task which is easy to a man in my condition."
>
*************************************************************************
Robert I. Soare
Paul Snowden Russell
Distinguished Service Professor
of Mathematics and Computer Science
Department of Mathematics PHONE: (773) 702-6029, Secty: 702-7100
The University of Chicago FAX: (773) 702-9787
5734 University Avenue E-MAIL: soare at cs.uchicago.edu
Chicago, IL 60637-1546 USA WEB: http://www.cs.uchicago.edu/~soare
**************************************************************************
More information about the FOM
mailing list