[FOM] 252:Pi01 Revisited

[Harvey Friedman]

Here we return to the project of finding a simple explicitly Pi01 sentence
independent of ZFC. We have made many postings in the past on this topic.
Looking at this topic again, we prefer one of the approaches. Here we polish
the statement up in explicitly Pi01 form.

Since we are here at the level of Mahlo cardinals, the statement here is
considerably simpler than those discussed in posting #250, Extreme
Cardinals/Pi01  7/31/05  8:34PM.

We use interval notation. All intervals will consist of positive integers.

Let R containedin [1,n]k x [1,n]k = [1,n]2k. For A containedin [1,n] we
write 

RA = {y: (therexists x in A)(R(x,y)}.
A' = [1,n]k\A. 

We say that R is strictly dominating iff for all x,y, R(x,y) implies max(x)
< max(y).

THEOREM 1. For all n,k >= 1 and strictly dominating R containedin [1,n]2k,
there exists nonempty A containedin [1,n]k such that RA = A'. Furthermore, A
is unique.

We say that R is order invariant iff for all x,y in [1,n]2k of the same
order type, R(x) iff R(y).

Let A,B containedin [1,n]r. We say that A,B are order equivalent iff every
element of A has the same order type as some element of B, and every element
of B has the same order type as some element of A.

We say that A,B are order equivalent avoiding p iff every element of A has
the same order type as some element of B in which p is not a coordinate, and
every element of B has the same order type as some element of A in which p
is not a coordinate.

PROPOSITION A. For all n,k >= 1 and strictly dominating order invariant R
containedin [1,n]k, there exists nonempty A containedin [1,n]k such that

A x A x {(1,2,4,8,...,2^n)} x RA
A x A x {(1,2,4,8,...,2^n)} x A'

are order equivalent avoiding 2^(8k)! - 1.

Here 2^(8k)! - 1 is (2^((8k)!))-1. It looks a lot better on a word
processor. We use it because it is safe - it is not tight.

Note that Proposition A is explicitly Pi01.
 
THEOREM 2. The following is provable in ACA. Proposition A holds iff MAH is
consistent. 

MAH = ZFC + {there exists an n-Mahlo cardinal}_n. We use 2^(8k)! - 1 because
it is safe, not because it is anywhere near optimal.

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 250th 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

Harvey Friedman