FOM: Incompleteness program

[Harvey Friedman]

Shoenfield 5:54PM 9/28/98 writes:

>The principal object
>is to improve Godel's second incompleteness theorem but finding new
>statements unprovable in ZFC which are, in some sense, simpler than
>ConZFC. The most important criterion of simplicity is that the
>setences be mathematical.   This can be explained at least roughly
>as: the sentences should be similar to results which core mathema-
>ticians are proving or attempting to prove.   If there is anything
>seiously misleading or false in this description, let me know.

I will put it a little differently. There is a gross dissimilarity between
say, ConZFC, and all propositions in all mathematical articles written by
algebraists, number theorists, topologists, geometers, analysts, etcetera.
I interpret your remarks on the FOM as pushing for a serious discussion of
this gross dissimilarity. I think it is a difficult, and interesting
exercise. However, it is far more productive at this stage of our knowledge
and experience to operate - as I do - with this gross disimilairity as an
unanalyzed given, and proceed from there, rather than try to construct a
theory surrounding this perception. Neverthess, I will continue from time
to time to try to make some hopefully illuminating remarks in this
connection. Perhaps my remarks might eventually lead to some relevant
theory of intellectual perception - but in the short run, I am much more
hopeful about continuing breakthroughs in the incompleteness phenomena than
this.

This gross dissimilarity is absolutely glaring to anyone from algebraists,
number theorists, topologists, geometers, analysts, etcetera. One
indication of its severity is that these people will immediately say upon
hearing a (necessarily quite long) definition of ConZFC, that "this is not
my business" or "I am not familiar with anything of this kind", etcetera.

Contrast this with, for example, the definition of n(3). n(3) was discussed
in my posting "script:can't run away" 12:11AM 9/15/98), and is "the longest
length of a finite sequence from 3 letters in which no block x_i,...,x_2i
is a subsequence of any other block x_j,...,x_2j." Note how short and
elementary this explanation is. Not a single one of my "victims" said "this
is not my business" or "I am not familiar with anything of this kind."

But I bring up this difference in length and familiarity as just an
indication of a gross dissimilarity - not a full explanation of the actual
gross dissimilarity.

The main dissimilarity that is most vital begins with the consideration of
the notions "mathematical intelligibility" and "intellectual
intelligibility", which are far more restrictive than mere
"intelligibility" as sometimes used by philosophers. The former implies the
latter, but not vice versa. In order for an mathematician (intellectual) to
be motivated to work on a problem as part of his mathematical
(intellectual) activity, he must perceive its mathematical (intellectual)
intelligibility. [Of course a mathematician (intellectual) could work on
something that has no mathematical (intellectual) intelligibility - say
perhaps as a paid consultant. It's solution would not be regarded as an
advance in mathematics (intellectualism) - just a service that has been
provided for a customer.]

An essential requirement of "mathematical intelligibility" and
"intellectual intelligibility" is that the statement must not be ad hoc. It
is beyond the scope of this posting to go into the use of "ad hoc" in this
context. Nevertheless, I hope that the reader finds this posting, taken as
a whole, as an interesting contribution to the discussion.

The mathematical (intellectual) intelligibility of an assertion depends
crucially on the choice of concepts that are used to present it. **In
particular, it is not invariant under coding.**

For example, ConZFC has obvious intellectual intelligibility. However, if
it is presented as a statement about the ring of integers using coding
devices, it no longer has any intellectual intelligibility (and therefore,
no mathematical intelligibility either). This is the case despite the fact
that the coded form is provably equivalent to the original form using the
weakest of principles.

The intellectual intelligibility of ConZFC (as usually presented) rests on
the intellectual intelligibility of ZFC. But that, in turn, rests on a
presentation of abstract set theory. There may be some way of maintaining
the intellectual intelligibility of ZFC without resorting to a presentation
of abstract set theory - perhaps with another interpretation of the system,
or perhaps with doing some powerful reduction so that it becomes some sort
of graph theoretic statement in which the actual axioms and rules of ZFC do
NOT come out as a substantial bunch of ad hoc data. The latter might well
require exactly the kind of work that goes into the construction of my
combinatorial statements - but in any case, has not been done.

Thus (the usual presentation of) ConZFC owes its intellectual
intelligibility to a presentation of abstract set theory involving sets of
unlimited rank, etcetera. In this sense, (the usual presentation of) ConZFC
is not mathematically intelligible in the sense of normal mathematics,
where one does not get involved in sets of unlimited rank.

POSTSCRIPT: I do think that there is some chance of exploiting length as
one way of pinpointing a gross dissimilarity in formal terms. But I won't
take this up until a later posting.

>     In the Godel quotes he discusses certain sentences unprovable in
>ZFC but provable from large cardinal axioms.   It is clear that these
>sentences are of the form ConZFC', where ZFC' is ZFC with some large
>cardinal axioms.

I don't think I understand this paragraph enough to respond to it. Did you
mean to say, e.g., "In the Godel quotes Godel refers to sentences
unprovable in
ZFC but provable from large cardinal axioms. It is clear that these
sentences are of the logical form pi-0-1, which is the same logical form as
ConZFC', where ZFC' is ZFC with some large
>cardinal axioms."?  What does your use of the word "certain" mean?

> He makes various comments intended to show that
>these sentences are simpler than the large cardinal axioms; the sense
>of simpler is made clear by the comments.   There is nothing that
>indicates that he thinks it would be valuable to find undecidable
>sentences which are still simpler.

As I said from the outset, not every aspect of the modern interpretation of
the incompleteness program is reflected explicitly in Godel's writings.
However, it is customary that programs get modified in light of later
experience, and this is no exception.

>Thus he clearly believes that
>these sentences are in the field of Diophantine equations, and shows no
>desire to replace the Diophantine equations by "reasonable" ones.   He
>shows no interest in searching for mathematical (in the above sense)
>sentences.   In fact, the following quotation from the Gibbs lecture
>could indicate that the opposite is true:
>     >It is safe to say that 99.9% of present-day mathematics is con-
>tained in the first three levels of this hierarchy.   However, this
>is a mere historical accident, which is of no importance for questions
>of principle.

The natural and appropriate evolution of programs involving examples is to
move to requiring the examples be reasonable - and obey other important
desiderata. This is normal. Off of the top of my head as I write this, I
just thought of one situation like this from functional analysis. After it
was first shown that there is a separable Banach space with no basis, it
was later shown that there were reasonable separable Banach spaces with no
basis; and after it was first shown that there is a separable Banach space
for which the invariant subspace theorem fails, it was later shown that
there were reasonable separable Banach spaces for which the invariant
subspace theorem fails. I believe that these were considered important
advances.

Of course, here I claim that the move towards "reasonable" is not only
natural, appropriate, and inevaitable; it's crucial, and moves the
incompleteness theorem into a new and deeper level of greater gii.

Furthermore, without taking this step, the interaction of set theory with
mathematics - something that Godel was implicitly interested in - is
curtailed. As I said in my earlier posting, I have no doubt that if Godel
communicated seriously and frequently with mathematicians of a wide
variety, then he would have come to this same conclusion and would likely
have expressed his views on the matter. He was the Great pioneer - but only
the great Pioneer.

>    My description of better came from the Paris-Harrington article;
>if you find it unsatisfactory, perhaps you should tell Leo instead of
>me.  I don't see why I am coming under attack for agreeing with your
>unexplained statement that PH is beteer that KP; perhaps you are
>in an attacking mood.

I'm just trying to poke some fun at your selected reactions to Steve and my
use of informal concepts at the earlier stages of this disucssion about the
incompleteness program (smile).

>    I find an answer to my question on regularity conditions in your
>statement: "I want to find unprovable sentences involving only
>objects ...".   However the meaning of "involving" is not clear.
>I can think of various ways of determining what objects are involved
>in a sentence, and I think the differences might be crucial for your
>program.

You can of course determine what objects are involved in a mathematical
sentence by considering the objects that are involved in that sentence. I'm
sure that you will have no problems with this (smile).

>    Let me further clarify my feelings on vague concepts.   I think
>it is not at all objectionable to use vague terms like "simpler" and
>"involving" in the description of a program.   I think it is often
>desirable to postpone consideration of the precise meanings of these
>concepts until the program progresses, since the results may give
>clues as to what precise meaning these concepts should have.
>But I think it is wise if the author of the program calls attention
>to these imprecisions, lest he later be accused of failing to stick
>to his stated program.

I don't know if this is important for authors to do since we have
Shoenfield around who delights in doing this (smile).