[FOM] 296: Order Calculus
Harvey Friedman
friedman at math.ohio-state.edu
Fri Jul 7 12:13:44 EDT 2006
Concerning http://www.cs.nyu.edu/pipermail/fom/2006-July/010631.html
In Theorems 15.1 and 16.1, we can obtain an interpretation of ZF + "there
exists a nontrivial elementary embedding from some V(kappa) into V(kappa),
where V(kappa) is an elementary substructure of V (scheme)". Hugh Woodin has
shown some time ago that ZFC + "there exists a nontrivial elementary
embedding from some successor rank into itself" is interpretable in this
theory, and hence in the Concept Calculus theories of Theorems 15.1 and
16.1.
##########################################
We have found some new Pi01 sentences and Pi01 Templates that we believe are
more systematic than those reported on in FOM posting #287, More Pi01
adventures, http://www.cs.nyu.edu/pipermail/fom/2006-May/010568.html
Let us briefly review the existing status before introducing Order Calclus.
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:
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.
############################################
Note that in the above existing approach, we use both the order of the
positive integers and the spacing out of long series of positive integers -
in this case the factorials.
In the new, closely related, approach, we only really use the ordering of
the positive integers (with some quibbles). Also the approach is
particularly systematic. Hence the name Order Calculus.
The large cardinals involved are somewhat higher than those that we used
earlier.
1. NEW Pi01 STATEMENTS.
We will use relational language rather than graph theory language.
All intervals are discrete. If A is a set of k tuples then A x A is a set of
2k tuples and A^m is a set of km tuples.
Let A containedin [1,n]^k. We write A' for the complement of A relative to
[1,n]^k.
Let R containedin [1,n]^k x [1,n]^k. We say that R is strictly dominating if
and only if R(x,y) implies max(x) < max(y). For A containedin [1,n]^k, we
write RA = {y: (therexists x in A)(R(x,y))}.
We say that A is an antichain for R if and only if A contianedin [1,n]^k and
no two elements of A are related by R.
We say that x,y in [1,n]^k are order equivalent if and only if for all 1 <=
i,j <= k, x_i < x_j iff y_i < y_j.
We say that B containedin [1,n]^k is order invariant if and only if for all
order equivalent x,y in [1,n]^k, x in B iff y in B.
Let B,C containedin [1,n]^r. We write
B [ ] C
if and only if for all x in B, there exists an order equivalent y in C.
More generally, let p >= 1, and 1 <= a1,...,ap,b1,...,bp <= n. We write
B [a_1,...,a_p:b_1,...,b_p] C
if and only if for all x in B, there exists an order equivalent y in C, such
that if x_i = a_j then y_i = b_j.
We write
B [a_1,...,a_p::b_1,...,b_p] C
if and only if for all x in B, there exists an order equivalent y in C, such
that if x_i = a_j then y_i = b_j, and if xi < min(a1,...,ap) then xi = yi.
We begin with our usual starting point.
THEOREM 1.1. For all n,k >= 1 and strictly dominating R containedin [1,n]^k
x [1,n]^k, there exists A containedin [1,n]^k such that RA = A'.
Furthermore, A is unique.
The following is an obvious restatement of Theorem 1.2.
THEOREM 1.2. For all n,k,m >= 1, every strictly dominating R containedin
[1,n]^k x [1,n]^k has an antichain A such that (RA)^m = A'^m.
We now come to something new.
PROPOSITION 1.3. For all n >> k,m >= 1, every strictly dominating order
invariant R containedin [1,3n]^k x [1,3n]^k has an antichain A such that
A'^m [n,2n:n,2n] (RA)^m [n::2n] (RA)^m.
Note that in Proposition 1.3 we have used infix notation for simplicity.
Here we mean that A'^m [n,2n:n,2n] (RA)^m and (RA)^m [n::2n] (RA)^m. We do
not intend to imply that A'^m [n::2n] (RA)^m.
PROPOSITION 1.4. For all n >> k,m >= 1, every strictly dominating order
invariant R containedin [1,4n]^k x [1,4n]^k has an antichain A such that
A'^m [n,2n,3n:n,2n,3n] (RA)^m [n,2n::2n,3n] (RA)^m.
PROPOSITION 1.5. For all n >> k,m,p >= 2, every strictly dominating order
invariant R containedin [1,pn]^k x [1,pn]^k has an antichain A such that
A'^m [n,2n,...,pn:n,2n,...,pn] (RA)^m [n,2n,...,pn-2n::2n,3n,...,pn-n]
(RA)^m.
THEOREM 1.6. The following is provable in EFA. Proposition 1.3 implies
Con(ZFC + "there exists a totally indescribable cardinal") and is implied by
Con(ZFC + "there exists a subtle cardinal"). Proposition 1.4 implies Con(ZFC
+ "there exists a subtle cardinal") and is implied by Con(ZFC + "there
exists a 2 subtle cardinal"). Proposition 1.5 is equivalent to Con(ZFC +
"there exists an n subtle cardinal")_n.
Note that Propositions 1.3-1.5 are not explicitly Pi01. They are explicitly
Pi03. They can be put into an equivalent explicitly Pi01 form by eliminating
n in favor of an expression in m (and m,p) as follows.
PROPOSITION 1.7. For all n >= (8km)!, every strictly dominating order
invariant R containedin [1,3n]^k x [1,3n]^k has an antichain A such that
A'^m [n,2n:n,2n] (RA)^m [n::2n] (RA)^m.
PROPOSITION 1.8. For all n >= (8km)!, every strictly dominating order
invariant R containedin [1,4n]^k x [1,4n]^k has an antichain A such that
A'^m [n,2n,3n:n,2n,3n] (RA)^m [n,2n::2n,3n] (RA)^m.
PROPOSITION 1.9. For all n >= (8kmp)!, p >= 2, every strictly dominating
order invariant R containedin [1,pn]^k x [1,pn]^k has an antichain A such
that A'^m [n,2n,...,pn:n,2n,...,pn] (RA)^m [n,2n,...,pn-2n::2n,3n,...,pn-n]
(RA)^m.
THEOREM 1.10. The following is provable in EFA. Proposition 1.3 is
equivalent to Proposition 1.7. Proposition 1.4 is equivalent to Proposition
1.8. Proposition 1.5 is equivalent to Proposition 1.9.
A nice alternative to the above six Propositions is to instead use the three
pairs of conditions
A'^m [n,2n:n,2n] (RA)^m.
A^m [n::2n] A^m.
A'm [n,2n,3n:n,2n,3n] (RA)^m
A^m [n,2n::2n,3n] A^m.
A'm [n,2n,...,pn:n,2n,...,pn] (RA)^m.
A^m [n,2n,...,pn-2n::2n,3n,...,pn-n] A^m.
The same results hold.
2. NEW Pi01 TEMPLATES.
Here is the Template corresponding to Proposition 1.3.
TEMPLATE 2.1. For all n >> k,m >= 1, every strictly dominating order
invariant R containedin [1,3n]^k x [1,3n]^k has an antichain A such that a
given finite set of conditions of the forms
alpha [a,b:c,d] beta.
alpha [a,b::c,d] beta.
hold, where alpha,beta are among (RA)^m,A'^m, and a,b,c,d are among n,2n.
More ambitiously, we can also include A^m.
Here is the Template corresponding to Proposition 1.4.
TEMPLATE 2.2. For all n >> k,m >= 1, every strictly dominating order
invariant R containedin [1,4n]^k x [1,4n]^k has an antichain A such that a
given finite set of conditions of the forms
alpha [a,b,c:d,e,f] beta.
alpha [a,b,c::d,e,f] beta.
hold, where alpha,beta are among (RA)^m,A'^m, and a,b,c,d,e,f are among
n,2n,3n. More ambitiously, we can also include A^m.
Here is the Template corresponding to Proposition 1.5.
TEMPLATE 2.3. Fix p >= 1. For all n >> k,m >= 1, every strictly dominating
order invariant R containedin [1,pn]^k x [1,pn]^k has an antichain A such
that a given finite set of conditions of the forms
alpha [a1,...,ap:b1,...,bp] beta.
alpha [a1,...,ap::b1,...,bp] beta.
hold, where alpha,beta are among (RA)^m,A'^m, and a1,...,ap,b1,...,bp are
among n,2n,...,pn. More ambitiously, we can also include A^m.
Note that there are finitely many instances of Template 2.3 for any fixed p.
There are infinitely instances of Template 2.3.
We fully expect to be able to determine the truth values of all instances of
Template 2.1, necessarily using large cardinals (e.g., a subtle cardinal).
We do not have the time to carry this out right now.
It is likely that we can carry this out even for Template 2.3.
We expect that true instances correspond roughly to standard levels of set
theory, and false instances are refutable in EFA.
Also, we expect that all instances are equivalent, over EFA, to the versions
where >> is replaced by >= (8km)! or (8kmp)!. This results in explicitly
Pi01 Templates.
There are obviously more ambitious Templates involving more general
expressions than RA,A,A' - along the lines of Boolean Relation Theory (BRT).
Note that "A is an antichain" is a Boolean equation in A,RA.
**********************************
I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 296th 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
287: More Pi01 adventures 5/18/06 9:19AM
288: Discrete ordered rings and large cardinals 6/1/06 11:28AM
289: Integer Thresholds in FFF 6/6/06 10:23PM
290: Independently Free Minds/Collectively Random Agents 6/12/06 11:01AM
291: Independently Free Minds/Collectively Random Agents (more) 6/13/06
5:01PM
292: Concept Calculus 1 6/17/06 5:26PM
293: Concept Calculus 2 6/20/06 6:27PM
294: Concept Calculus 3 6/25/06 5:15PM
295: Concept Calculus 4 7/3/06 2:34AM
Harvey Friedman
More information about the FOM
mailing list