[FOM] 454: Three Milestones in Incompleteness

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

*****************************************

I want to headline three milestones in Incompleteness which have been  
discussed at various times on the FOM.

This is NOT intended to be any kind of thorough or in depth discussion  
of all relevant milestones by me, let alone all researchers.

Furthermore, I hope - and expect - to see greater milestones in  
incompleteness, of various kinds, in the future.

I claim that the situation below definitely shows that "measurable"  
progress continues to be made in Concrete Mathematical Incompleteness.

The Introduction to the BRT book, in section 3 of http://www.math.osu.edu/~friedman/manuscripts.html 
  is on Concrete Mathematical Incompleteness, and gives an historical  
overview. Many additional milestones are discussed there.

1. PERFECTLY NATURAL THEOREM (PA level). The situation with regard to  
incompleteness of PA has taken an interesting turn.

I mentioned these three statements in http://www.cs.nyu.edu/pipermail/fom/2010-December/015154.html

THEOREM 1. Let n >> k,r,p >= 1. Every r coloring of the unordered k-
tuples from {1,...,n} has an at least p element monochromatic set with
at least as many elements as its min.

THEOREM 2. Let n >> k >= 1. For every x_1,...,x_n from {1,...,k},
there exists 1 <= i < j <= n/2 such that x_i,...,x_2i is a subsequence
of x_j,...,x_2j.

THEOREM 3. Let n >> k >= 1. For every f:{1,...,n}^k into {1,...,n}^k
obeying max(f(x)) <= max(x), there exist distinct x_1,...,x_k+1 such
that f(x_1,...,x_k) <= f(x_2,...,x_k+1) coordinatewise.

Theorems 1,3 are equivalent to 1-Con(PA), and Theorem 2 is equivalent
to 1-Con(PA_2). PA_2 is 2 quantifier induction.
I have come to the following assessments based on testing my own view  
in discussions with well known mathematicians, particularly  
combinatorists.

Theorem 1 (Paris/Harrington) was a seminal event in f.o.m.

Theorem 1 is somewhat unnatural in light of its essentially  
unprecedented dual use of an integer for an element and a count.

Theorem 2 received mixed reactions. I have heard "perfectly natural"  
and I have heard "slightly unnatural". I, personally, am not sure. It  
is at least "arguably perfectly natural". It is also provable in PA,  
as opposed to Theorems 1,2.

Theorem 3 is *perfectly* natural.

Of course, I have no way of formally treating "perfectly natural". But  
I believe that there is a clear sense in which this is true, and in  
the future we will be able to formally treat this notion.

So I maintain that there has been major progress in PA Incompleteness  
with regard to mathematical naturalness which is readily discernible -  
if not formally characterizable (at this juncture).

Also see
Adjacent Ramsey Theory, http://www.math.osu.edu/~friedman/manuscripts.html 
  Section 1. Preprints, Drafts, and Abstracts, #66

where proofs are given, and several variants are also treated.

2. PERFECTLY NATURAL RICH MATHEMATICAL PROGRAM (beyond ZFC). Boolean  
Relation THeory (BRT) is a perfectly natural rich mathematical  
program. It quickly leads to necessary uses of large cardinals in the  
natural course of development. BRT will have a permanent place in the  
history of mathematics in light of its perfect coherence and  
illuminating connections with diverse mathematical topics.

See the BRT book at http://www.math.osu.edu/~friedman/ 
manuscripts.html, Section 3.

3. PERFECTLY NATURAL MATHEMATICAL PROBLEMS (perhaps beyond ZFC).

In http://www.cs.nyu.edu/pipermail/fom/2011-January/015253.html  
section 4, I present a reasonably natural result in discrete  
mathematics whose proof requires large cardinals - and in fact is  
provably equivalent to the consistency of certain large cardinal  
axioms. This is a milestone on two counts - the reasonable  
naturalness, and the equivalence with Pi01.

But I want to emphasize that the omission of certain features in that  
statement leads to an extremely attractive perfectly natural OPEN  
PROBLEM - sufficiently attractive for a well known combinatorist to  
consider part of their normal activity. In fact, they put a reasonably  
serious effort into solving the OPEN PROBLEM, without success.

Moreover, I obtained a partial result on this OPEN QUESTION using  
large cardinals, and do not know if this can be done in ZFC or even  
RCA_0. This was also sufficiently attractive, and there was a  
reasonably serious effort also without success.

The open question is

> QUESTION. Does every Q-graph have a maximal clique, which contains its
> upper shift?

from http://www.cs.nyu.edu/pipermail/fom/2011-January/015253.html  
section 4 The partial result using large cardinals is also presented  
there.

The hope and expectation is to show that large cardinals are necessary  
and sufficient to prove a result that is perfectly natural in the  
sense of the above QUESTION (instead of just reasonably natural).

*****************************************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 454th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html

450: Maximal Sets and Large Cardinals II  12/6/10  12:48PM
451: Rational Graphs and Large Cardinals I  12/18/10  10:56PM
452: Rational Graphs and Large Cardinals II  1/9/11  1:36AM
453: Rational Graphs and Large Cardinals III  1/20/11  2:33AM

Harvey Friedman