FOM: natural examples

[Harvey Friedman]

Cooper writes 4:59PM 7/29/99:

>One very often sees something along the lines "The only natural examples
>[of r.e. sets and degrees] are the original ones, i.e. the halting problem
>and the complete r.e. degree", ...
>
>There are of course a number of different definitions of 'natural' in this
>context, depending on different notions of 'natural' information content
>or of degree theoretic context. It is true that all the known canonical
>c.e. sets (e.g. those associated with standard first-order axiomatic
>theories, the halting problem, etc) turn out to be computable or of
>complete c.e. degree, and that for a pure mathematician that is very
>significant. It may also turn out that 0 and 0' are the only Turing
>definable c.e. degrees.
>
>However, there are mathematical criteria according to which *all* c.e.
>sets and Turing degrees potentially contain 'natural' information content
>which may be encountered in specific contexts - just to mention two
>well-known examples:
>
>1) (Feferman, Hanf) All c.e. degrees contain (finitely) axiomatisable
>theories, and
>
>2) (Matiasevich) All c.e. sets are diophantine.

My point was this:

Every mathematical structure or family of mathematical objects that
mathematicians generally believe is important to intensively study the
structure of over a long period of time, has a considerable variety of
explicit, canonical elements or examples that people were interested in
ahead of time. Does anybody know a counterexample to this?

Let us take the case of the r.e. sets of natural numbers. Here the
situation is rather extreme. I know of no mathematically natural example of
an r.e. set of natural numbers that is not recursive. I know of no
mathematically natural example of a complete r.e. set of natural numbers.
And I am using "mathematically natural" in the typical sense that it is
used throughout mathematics.

Of course, there are natural examples of sets of polynomials with integer
coefficients that are complete r.e. E.g., those which have a zero. But when
you try to convert this example to an example of a set of integers by
standard methods, you destroy the mathematical naturalness.

Sticking with sets of polynomials with integer coefficients for the moment,
I know of no natural class whose degree is intermediate. And I know of no
natural polynomial with integer coefficients whose positive range is not
recursive, let alone of intermediate degree. I am thinking of mathematical
naturalness in the usual sense of mathematicians.

Thus it does not appear hopeful that 2) above and related work can be used
to address the issue that I raise.

Also 1) does not appear useful either for this purpose. You can ask for a
finitely axiomatized theory whose theorems have an intermediate degree,
which is "natural."

It is completely against the usual meaning of mathematically natural in
mathematics to think that any finitely axiomatized theory as natural.

It is possible to turn these issues into well defined questions which
appear to be extremely difficult. In various contexts, you can start by
defining natural to mean, say, that the total number of symbols is small.
You can pick a size that is typical of sizes of celebrated objects that
come up naturally in mathematics, or sizes of, say, first order
mathematical axioms such as the group axioms, the field axioms, the ring
axioms, discrete ordered rings, real closed fields, etcetera. It would be
expected that in such context, no intermediate degrees appear, and in most
of these context, no nonrecursive degrees appear. However, proving such a
result is another matter.

>...Of course,
>there is no guarantee that every arcane body of theory, even if built on
>fundamental concepts, will eventually explain anything. But those of us
>who are led by intellectual curiosity (and that is 'the *real* reason',
>maybe incapable of the kind of reduction Steve is looking for) into (what
>may appear to be) more abstruse research topics, can look to one of
>Gian-Carlo Rota's characteristic quotes (taken from an interview with MIT
>Tech Talk) for encouragement:
>
>________________________________________________________________________
>Applications are found after the theory is developed, not before. A math
>problem gets solved, then by accident some engineer gets hold of it and
>says, 'Hey, isn't this similar to...? Let's try it.' For instance, the
>laws of aerodynamics are basic math. They were not discovered by an
>engineer studying the flight of birds, but by dreamers -- real
>mathematicians -- who just thought about the basic laws of nature. If you
>tried to do it by studying birds' flight, you'd never get it. You don't
>examine data first.  You first have an idea, then you get the data to
>prove your idea.
>____________________________________________________________________

Rota uses the phrase "who just thought about the basic laws of nature" is
subject to interpretation. Only under a rather strained interpretation, can
be view the typical person in recursion theory or mathematical logic today
as "just thinking about the basic laws of nature." So I do not feel that
the Rota quote is all that useful for Cooper's position.

Cooper is making a standard defense against the standard criticisms of
subjects which are badly in need of renewal. To my mind, there is an
important division of research projects:

1. Those that are of clear and obvious general intellectual interest.
2. Those that are of clear and obvious applicability to something else.
3. Those that are both.
4. Those that are neither.

And it is vitally important to subdivide 2 (and 2 as a component in 3) into
parts:

2a. Those that are of clear and obvious applicability to something else of
general intellectual interest.
2b. Those that are of clear and obvious applicability to other things, none
of which are of general intellectual interest.

And of course, there is an obvious recursion here that can be analyzed.
NOTE: This further breakdown is nearly always ignored by people stretching
to justify their subject on the basis of applications. They don't wish to
get into the evaluation of those applications, but instead concentrate on
their mere existence.

My own view is that

a) 1 is generally the most fruitful for theoretically oriented intellects;
b) 2 can also be fruitful for theoretically oriented intellects, but it
must be approached with caution, where there is a clear evaluation of the
nature of these applications and the nature of the subject which is the
target of these applications;
c) when there is a choice between a subject in category 1 and a subject in
category 4, one should pick the subject in category 1;
d) if one strongly prefers the subject in category 4 to a subject in
category 1, one should question why this is so; one should continually
examine one's approach to intellectual life as well as that of one's
colleagues.

>Of course, Turing's 1936 paper and the development of the stored-memory
>computer is a famous example of how ostensibly esoteric 'pure' research
>can lead to important applications.

Note that from the outset, this was of obvious general intellectual
interest - category 1.

>Steve may propose perfectly valid criteria of relevance for assessing the
>long-term value of a particular field of research. Unfortunately (as
>computability theory tells us) those criteria may not be effectively
>implementable - and while one may on occasion be forced to attempt such
>implementation, in so doing one must be aware that more damage than
>benefit may result. And one such damaging effect can be demoralisation
>among people producing some very nice mathematics - not necessarily a good
>basis for a 'productive' change of direction, just for diminished research
>activity.

I have seen many opportunities for all parts of mathematical logic to renew
themselves with new directions. But these new directions often come out of
critically evaluating the drawbacks and limitations of present directions.
That's just a fact. E.g., one may criticize recursion theory by saying that
it doesn't take into account resource bounds. And this shouldn't have
demoralized anyone - after all, every single subject, no matter how great,
can be criticized for not taking into account something or other that is
important. And if you take that criticism seriously, you are lead to
computational complexity theory. In fact, you are lead to more
computational complexity theory than demoralization.

Now that you mention "demoralization," what about the demoralization some
people have experienced by producing new directions and new work based on
new directions which gets ignored or downgraded, often simply on the basis
of its perceived subnormal technical content compared to the latest razzle
dazzle? What about the demoralization coming out of the nearly complete
removal of foundations of mathematics as a motivation for research in
mathematical logic?

Davis writes:

>Efforts to decide in advance which lines of inquiry are productive and
>policies designed to channel researchers into such lines are fundamentally
>mistaken.

A subject which rejects critical rethinking of its aims and goals, and
research projects based on such critical rethinking, is itself engaging in
an "effort to decide in advance which lines of inquiry are *not*
productive" and is extering a "policy designed to channel researchers *out*
of such lines." This is typical of subjects at various stages of
development, as described in my FOM posting "Natural Evolution of Many
Mathematical Subjects" 11:14AM 8/2/99.

This is what is fundamentally mistaken and if left unchecked, leads to the
disintegration of the subject through lack of employment opportunities.
What is fundamentally not mistaken is an attempt to inject renewal into
subjects.

Do you regard a critical examination of the state of a subject, together
with productive suggestions for renewal, appended with reasons why such
renewal is needed, as a violation of what you are advocating? Do you want
to discourage such activity?

>The only worthwhile criterion is the ability of individual
>researchers. Let them decide what they want to do.

History shows that the typical researcher celebrated locally in time has
very little chance of their work becoming important (by any reasonable
measure) later. Are you against guidance?

History shows that sizable groups of people often provide a misguided and
artificial support system for each other, insulating themselves from
outside communities, thereby misusing their talent and driving out other
talented people who are more perceptive. Are you against efforts to save
subjects from this fate?

>My paradigmatic example of fund dispensers deciding how genius should direct
>its talents is the Dukes of Hannover insisting that Leibniz take as his
>primary task the researching of their family history.

Do you think that the current academic environment and government funding
is really any different than this? Please give us a candid answer to this.

Stevenson 1:26PM 7/29/99 provided the following interesting quote from von
Neumann:

"As mathematics travels far from its empirical source, or still
more, if it is a second and third generation only indirectly inspired
by ideas coming from ``reality,'' it is beset with very grave
dangers. It becomes more and more purely aestheticizing, more and more
purely {\em l'art pour l'art}. .... In other words, at a great
distance from its empirical source, or after much ``abstract''
inbreeding, a mathematical subject is in danger of
degeneration. At the inception the style is usually classical; when it
shows signs of becoming baroque, then the danger signal is up.''.

   J. von Neuman (1943. ``The Mathematician.'' In *In the Works of the
			   Mind.* Chicago, IL: University of Chicago.)


When I first read this, I thought that it did not apply to f.o.m. On
further examination, it does, in the following sense. F.o.m. is
fundamentally about mathematical thought, and that can be viewed as a
"reality" or "empirical source." It is particularly evident that in, say,
reverse mathematics, one is using mathematics itself as an empirical
source. And there are even major conjectures about this empirical source
that need to be tested empirically: e.g., the linear ordering under
interpretation of actual mathematical statements.

To Davis: What do you think of this quote from von Neumann in light of your
position?