# [FOM] 454: Three Milestones in Incompleteness

Harvey Friedman friedman at math.ohio-state.edu
Sun Feb 6 06:33:37 EST 2011

```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
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).

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

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

```