[FOM] 253:Pi01 Progress

[Harvey Friedman]

CORRECTION. In Proposition A, I wrote

R containedin [1,n]k.

This should be 

R containedin [1,n]2k.

############################################

The most unnatural feature of Proposition A in #252 is the appearance of

{(1,2,4,8,...,2^n)}

as a component in those two Cartesian products.

Here we move this to a more natural place, where we can, as a bonus, get rid
of the symbols.

#############################################

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

Let R containedin [1,n]k+m. For A containedin [1,n]k we write

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

Let R containedin [1,n]2k. 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 B containedin Nr and p >= 1. We define

B, without p 

to be the set of all elements of B in which p is not a coordinate.

A power of 2 is a tuple of integers of the form 2^n, for nonnegative
integers n.

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

A x A x RA
A x A x A'
A x A x RA, without 2^(8k)! - 1
A x A x A', without 2^(8k)! - 1

under any given order invariant subset of [1,n]4k contain the same powers of
2.

Here 2^(8k)! - 1 is (2^((8k)!))-1. It looks a lot better on a word
processor. We use it because it is safe and readable - 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
252. Pi01 Revisited  10/25/05  10:35PM

Harvey Friedman