[FOM] 265:Pi01/digraphs 2/more
Harvey Friedman
friedman at math.ohio-state.edu
Sat Jan 28 14:46:26 EST 2006
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
More information about the FOM
mailing list