[FOM] 254:Pi01 Progress/more

[Harvey Friedman]

Pi01 INCOMPLETENESS 1
by
Harvey M. Friedman
November 10, 2005

"Beautiful" is a word used by mathematicians with a semi rigorous meaning.

We give an "arguably beautiful" explicitly Pi01 sentence independent of ZFC.
See Proposition A below.

For A containedin [1,n]k, we write A' = [1,n]k\A. This treats [1,n]k as the
ambient space.

We focus on relations R containedin [1,n]3k x [1,n]k. Here we use R in two
ways. Firstly, as a subset of [1,n]4k. Secondly, and most importantly, as an
operator whose arguments and values are subsets of [1,n]k.

In particular, for all A containedin [1,n]k, we define RA = R<A> = R[A3] =
{w in [1,n]k: (therexists x,y,z in A)(R(x,y,z,w))}. For elegance, we will
omit the brackets < > and write RA whenever this does not lead to ambiguity.

Note that in the above, [ ] is the standard forward image notation for R
containedin [1,n]3k x [1,n]k = [1,n]4k.

We say that R is strictly dominating if and only if for all x,y,z,w in
[1,n]k, if R(x,y,z,w) then max(x),max(y),max(z) < max(w). This definition is
the reason why we prefer to write [1,n]3k x [1,n]k rather than [1,n]4k.

We start with the basic unique fixed point theorem for the operator R<A'>.

THEOREM 1.1. For all k,n >= 1 and strictly dominating R containedin ]1,n]3k
x [1,n]k, there exists A containedin [1,n]k such that R<A'> = A.
Furthermore, A containedin [1,n]k is unique.

For A containedin [1,n]k and t >= 1, we write A\t = {x in A: t is not a
coordinate of x} = "A with t omitted".

The "omission" operator R<A'\(8k)!> also has a unique fixed point.

THEOREM 1.2. For all k,n >= 1 and strictly dominating R containedin [1,n]3k
x [1,n]k, there exists A containedin [1,n]k such that R<A'\(8k)!> = A.
Furthermore, A containedin [1,n]k is unique.

However, we can't get a COMMON fixed point

R<A'\(8k)!> = R<A'> = A.

THEOREM 1.3. The following is false. For all k,n >= 1 and strictly
dominating R containedin [1,n]3k x [1,n]k, there exists A containedin [1,n]k
such that R<A'\(8k)!> = R<A'> = A.

We will weaken this three term common fixed point equation so that it is
attainable. The weakening involves replacing = both with containedin and
with "having the same elements of a certain kind".

Our development depends heavily on a very strong regularity condition on R.

We say that R containedin [1,n]3k x [1,n]k is order invariant if and only if
for all x,y in [1,n]4k of the same order type, R(x) iff R(y). The number of
such R is bounded by an exponential expression in k that does not depend on
n. 

The powers of t are the numbers t^i, i >= 0.

THEOREM 1.4. For all k,n >= 1 and strictly dominating order invariant R
containedin [1,n]3k x [1,n]k, there exists A containedin [1,n]k such that
the three sets R<A'\(8k)!> containedin R<A'> containedin A contain the same
k tuples of powers of (8k)!+1.

What happens if we apply R to the expressions in the three term tower of
Theorem 1.4?

This is in rough analogy with standard mathematical contexts where one
passes from degree 1 equations to degree 2 equations and higher. Things can
get much more difficult.

Obviously

RR<A'\(8k)!> containedin RR<A'> containedin RA

follows immediately from

R<A'\(8k)!> containedin R<A'> containedin A.

However, 

"the first tower of sets above contain the same k tuples of powers of
(8k)!+1"

does not follow from

"the second tower of sets above contain the same k tuples of powers of
(8k)!+1."

PROPOSITION A. For all k,n >= 1 and strictly dominating order invariant R
containedin [1,n]3k x [1,n]k, there exists A containedin [1,n]k such that
the three sets RR<A'\(8k)!> containedin RR<A'> containedin RA contain the
same k tuples of powers of (8k)!+1.

Proposition A is obviously an explicitly Pi01 sentence. It is independent of
ZFC. Here is much more precise information.

Let MAH = ZFC + {there exists a strongly n-Mahlo cardinal}_n. Let MAH+ = ZFC
+ "for all n there exists a strongly n-Mahlo cardinal".

THEOREM 1.5. MAH+ proves Proposition A. However, Proposition A is not
provable in any consistent fragment of MAH that derives Z = Zermelo set
theory. In particular, Proposition A is not provable in ZFC, provided ZFC is
consistent. These facts are provable in RCA0.

THEOREM 1.6. It is provable in ACA that Proposition A is equivalent to
Con(MAH).

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 254th 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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM

Harvey Friedman