[FOM] 262:Correction/Restatement

[Harvey Friedman]

In posting #258, 

http://www.cs.nyu.edu/pipermail/fom/2005-November/009395.html

we switched over to

1) R containedin [1,n]k x [1,n]k

from 

2) R containedin [1,n]3k x [1,n]k.

I used RRRR instead of RR in order to make this move.

However, RRRR with 1) is not an adequate replacement for RR with 2), and so
this move was not done quite right.

So we now go back to

2) R containedin [1,n]3k x ]1,n]k

but incorporate my other improvements such as using A\{t}k and flog_t+1.

BUT, this move was in principal a very good one, as

1) R containedin [1,n]k x [1,n]k

corresponds to GRAPHS, as we have remarked. AND the CORRECT way to implement
this move is to think of my idea of RRRR as a PATH in a graph, of length 4
(4 edges). 

So in the next posting we will move over to GRAPH THEORY.

As usual, for a complete and formatted copy, see

http://www.math.ohio-state.edu/%7Efriedman/

under downloadable manuscripts, manuscript number 49, entitled "Pi01
Incompleteness: set equations", December 4, 2005.

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

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

We give "arguably beautiful" explicitly Pi01 sentences independent of ZFC.

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

Let R containedin [1,n]3k x [1,n]k. We define

R<A> = {y in [1,n]k: (therexists x in A3)(R(x,y))}.

We say that R is strictly dominating if and only if for all x in
[1,n]3k and y in [1,n]k, if R(x,y) then max(x) < max(y).

We say that A is R free if and only if A and R<A> are disjoint.

THEOREM. For all k,n >= 1 and t >= (8k)!, every strictly dominating order
invariant R contained [1,n]3k x [1,n]k has a free set A such that flog_t+1
R<A\{t}k> = flog_t+1 A'.

PROPOSITION A.  For all k,n >= 1 and t >= (8k)!, every strictly dominating
order invariant R contained [1,n]3k x [1,n]k has a free set A such that
flog_t+1 R<R<A\{t}k>> = flog_t+1 R<A'>.

PROPOSITION B. For all k,n >= 1 and t >= (8k)!, every strictly dominating
order invariant R contained [1,t^k]3k x [1,t^k]k has a free set A such that
flog_t+1 R<R<A\{t}k>> = flog_t+1 R<A'>.

PROPOSITION C. For all k,n >= 1 and t >= (8k)!, every strictly dominating
order invariant R contained [1,t^k]3k x [1,t!!]k has a free set A such that
flog_t+1 R<R<A\{t}k>> = flog_t+1 R<A'>.

PROPOSITION D. For all k,r >= 1 and t >= (8k)!, every strictly dominating
order invariant R containedin [1,t^r]3k x [1,t^r]k has a free set A such
that flog_t+1 R<R<A\{t}k>> = flog_t+1 R<A'>.

Proposition A is provably equivalent, over ACA, to Con(MAH).

Proposition B is provably equivalent, over EFA, to Con(PA).

Proposition C is provably equivalent, over PRA, to Con(WZC).

Proposition D, for fixed r, is provably equivalent, over EFA, to roughly
Con(PA_r). 

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 262nd 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
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM

Harvey Friedman