[FOM] 265:Pi01/digraphs 2/more

[Harvey Friedman]

This is a continuation of Pi01/Digraphs 2
http://www.cs.nyu.edu/pipermail/fom/2006-January/009625.html

The new Proposition C appears to us to be a little bit more attractive.

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

Pi01 INCOMPLETENESS: simple digraphs 2
continuation
by
Harvey M. Friedman
January 28, 2006

Recall the following independent Propositions from
http://www.cs.nyu.edu/pipermail/fom/2006-January/009625.html

PROPOSITION A. For all n,k,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every <= r element subset of A'
is G isomorphic to a <= r element subset of GA, with the same vector powers
of 2, in which the integer 2^((4kr)^2) - 1 does not appear.

PROPOSITION B. For all n,k,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every <= r element subset of A'
is G isomorphic to a <= r element subset of GA, with the same vector powers
of 2, in which the diagonal vector (2^((4kr)^2) - 1,...,2^((4kr)^2) -1) does
not appear. 

We now present a modification of A,B that appears a little bit more
attractive to us. 

PROPOSITION C. For all n,k,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every <= r element subset of A'
is G isomorphic to a <= r element subset of GA with the same vector powers
of (8kr)!, where (8kr)!-1 does not appear.

Proposition C can be proved with large cardinals but not without.
Proposition C is explicitly Pi01.

Here is more detailed 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. MAH+ proves Proposition C. However, Proposition C are not
provable in any consistent fragment of MAH that derives Z = Zermelo set
theory. In particular, Proposition C are not provable in ZFC, provided
ZFC is consistent. These facts are provable in RCA_0.

THEOREM 2. EFA + Con(MAH) proves Proposition C.

THEOREM 3. It is provable in ACA that Proposition C is equivalent to
Con(MAH).

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 265th 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
262. Correction/Restatement  12/9/05  10:13AM
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM

Harvey Friedman