[FOM] 287:More Pi01 adventures
Harvey Friedman
friedman at math.ohio-state.edu
Thu May 18 09:19:29 EDT 2006
In posting #269, Pi01,Pi00/digraphs 2/25/06 3:09AM,
http://www.cs.nyu.edu/pipermail/fom/2006-February/010056.html I gave my
mathematically cleanest, to date, Pi01 sentences independent of
ZFC (also on my website):
PROPOSITION A. For all k,n,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every x!,y_1,...,y_r from V(G)\A
is G equivalent to some x!,z_1,...,z_r from GA\((8kr)!-1).
PROPOSITION B. For all n,r >= 1, every order invariant upgraph G on [1,n]^8
has an independent set A such that every x!,y_1,...,y_r from V(G)\A is G
equivalent to some x!,z_1,...,z_r from GA\((8r)!-1).
This also appears on my website http://www.math.ohio-state.edu/%7Efriedman/
under downloadable manuscripts, manuscript number 51.
In posting 282: Adventures in Pi01 Independence
http://www.cs.nyu.edu/pipermail/fom/2006-May/010515.html, we got the
following project off the ground with an initial result:
*find a natural set of Pi01 sentences whose truth values can all be
determined in ZFC with large cardinals, but not in ZFC.*
The expectation is that the set would be more natural than any existing
individual Pi01 sentence provable in ZFC with large cardinals, but not in
ZFC.
Here I want to present a new approach to * that I prefer. In this posting,
we will be content to make conjectures. I have limited time now to develop
these new ideas in light of the unfinished state of the BRT book.
####################################
Let us recall our usual point of departure for the Pi01 projects.
THEOREM 1. For all k,n >= 1 and strictly dominating order invariant R
containedin [1,n]^k x [1,n]^k, there exists A containedin [1,n]^k such that
RA = A'. Furthermore, A is unique.
We start with the following simple template.
TEMPLATE 2. For all k,n >= 1 and strictly dominating order invariant R
containedin [1,n]^k x [1,n]^k, there exists A containedin [1,n]^k such that
a given Boolean combination of A,RA is equaled to another given Boolean
combination of A,RA.
The number of Boolean combinations of A,RA is 16, up to Boolean identity.
Also any equation between two such is Boolean equivalent to the equality of
a Boolean combination of A,RA and [1,n]^k. The same is true of any set of
such equations. (Here we are taking [1,n]^k as the universal set). Thus it
is a fairly simple matter to look at all 16 such equations and determine the
16 truth values of the Template 2 that arise.
TEMPLATE 3. For all k,n >= 1 and strictly dominating order invariant R
containedin [1,n]^k x [1,n]^k, there exists A containedin [1,n]^k such that
a given equation between finite Cartesian products of Boolean combinations
of A,RA, holds.
Still nothing new.
Let B,C containedin [1,n]^kp. We say that B,C are order equivalent if and
only if every element of B is order equivalent to some element of C, and
every element of C is order equivalent to some element of B.
We can "weaken" Template 3 as follows.
TEMPLATE 4. For all k,n >= 1 and strictly dominating order invariant R
containedin [1,n]^k x [1,n]^k, there exists A containedin [1,n]^k such that
a given order equivalence between finite Cartesian products of Boolean
combinations of A,RA, holds.
In Template 3, we obviously need only consider 16 instances, in light of the
earlier discussion.
However, in Template 4, we cannot use any Boolean algebra tricks, since we
are only talking about order equivalences, and not equalities.
So Template 4 does require us to consider Cartesian products of arbitrarily
long finite lengths. Nevertheless, it is not difficult to completely analyze
the truth values that arise.
We now come to the crucial move. As in posting 282, it is advisable to
introduce a new numerical parameter t, where we hypothesize that n,t >> k >=
1. As in posting 282, the idea is that all of the exponential mess is
embedded in >>. Since >> simply disguises an exponential mess, the
statements involved are still Pi01 - explicitly so, if the exponential mess
is then put in to replace the >>.
For example, applying this method of putting the exponential mess into >>,
to Propositions A,B, we obtain:
PROPOSITION A'. For all n,t >> k,n,r >= 1, every order invariant upgraph G
on [1,n]^k has an independent set A such that every t^x,y_1,...,y_r from
V(G)\A is G equivalent to some t^x,z_1,...,z_r from GA\(t-1).
PROPOSITION B'. For all n,t >> n,r >= 1, every order invariant upgraph G on
[1,n]^8 has an independent set A such that every t^x,y_1,...,y_r from V(G)\A
is G equivalent to some t^x,z_1,...,z_r from GA\(t-1).
We now make our crucial move.
TEMPLATE 6. Let alpha(n,t,k,A,B) and beta(n,t,k,A,B) be elementary set terms
in numerical parameters n,t,k, and set parameters A,B. For all n,t >> k >= 1
and strictly dominating order invariant R containedin [1,n]^k x [1,n]^k,
there exists A containedin [1,n]^k such that alpha(n,r,k,A,RA) and
beta(n,r,k,A,RA) are order equivalent.
The plan is to be more and more liberal about what is considered to be an
"elementary set term". Here is one version.
Terms are defined inductively. They represent sets of vectors of perhaps
various lengths. The notion of order equivalence is trivially extended to
such sets.
i. A, B, [1,n], [1,t], [1,k], {1}, {n}, {t}, {k} are terms.
ii. {1,b,b^2,...,b^c} is a term, where b,c are among the letters n,t,k.
iii. If alpha,beta are terms then alpha + 1, alpha^n, alpha^t, alpha^k,
alpha x beta, alpha union beta, alpha\beta are terms.
THEOREM 7. There is an instance of Template 6 using the terms above, which
is provably equivalent to Con(MAH) over EFA.
The plan is to show that all instances of Template 6 using the terms above,
are all decided in EFA + Con(MAH), with uniform exponential bounds for the
>>, thereby making the statements explicitly Pi01.
The instance cited in Theorem 7 uses very simple terms, with very few
applications of i-iii. A fallback is to carry out the plan for the finite
fragment of instances where the number of uses of i-iii is very small.
If we allow finite sets of order equivalences in Template 6, we get a richer
template. We have shown that for this richer template, there is an instance
which is provably equivalent to Con(SUB) over EFA, where SUB corresponds to
the subtle cardinal hierarchy.
Incidentally, Template 4 needs to be revisited for finite sets of order
equivalences. This should not be a problem.
Obviously, there is a great deal of work to do - after the BRT book is put
on the Internet.
**********************************
I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 287th 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. NOTE: The title of #269 has been corrected from
the original.
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
265. Pi01/digraphs 2/more 1/28/06 2:46PM
266. Pi01/digraphs/unifying 2/4/06 5:27AM
267. Pi01/digraphs/progress 2/8/06 2:44AM
268. Finite to Infinite 1 2/22/06 9:01AM
269. Pi01,Pi00/digraphs 2/25/06 3:09AM
270. Finite to Infinite/Restatement 2/25/06 8:25PM
271. Clarification of Smith Article 3/22/06 5:58PM
272. Sigma01/optimal 3/24/06 1:45PM
273: Sigma01/optimal/size 3/28/06 12:57PM
274: Subcubic Graph Numbers 4/1/06 11:23AM
275: Kruskal Theorem/Impredicativity 4/2/06 12:16PM
276: Higman/Kruskal/impredicativity 4/4/06 6:31AM
277: Strict Predicativity 4/5/06 1:58PM
278: Ultra/Strict/Predicativity/Higman 4/8/06 1:33AM
279: Subcubic graph numbers/restated 4/8/06 3:14AN
280: Generating large caridnals/self embedding axioms 5/2/06 4:55AM
281: Linear Self Embedding Axioms 5/5/06 2:32AM
282: Adventures in Pi01 Independence 5/7/06
283: A theory of indiscernibles 5/7/06 6:42PM
284: Godel's Second 5/9/06 10:02AM
285: Godel's Second/more 5/10/06 5:55PM
286: Godel's Second/still more 5/11/06 2:05PM
Harvey Friedman
More information about the FOM
mailing list