[FOM] 253:Pi01 Progress
Harvey Friedman
friedman at math.ohio-state.edu
Wed Oct 26 06:32:48 EDT 2005
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
More information about the FOM
mailing list