FOM: 58:Program A/Conjectures
Harvey Friedman
friedman at math.ohio-state.edu
Sat Sep 11 20:03:13 EDT 1999
This is the 58th in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:
1:Foundational Completeness 11/3/97, 10:13AM, 10:26AM.
2:Axioms 11/6/97.
3:Simplicity 11/14/97 10:10AM.
4:Simplicity 11/14/97 4:25PM
5:Constructions 11/15/97 5:24PM
6:Undefinability/Nonstandard Models 11/16/97 12:04AM
7.Undefinability/Nonstandard Models 11/17/97 12:31AM
8.Schemes 11/17/97 12:30AM
9:Nonstandard Arithmetic 11/18/97 11:53AM
10:Pathology 12/8/97 12:37AM
11:F.O.M. & Math Logic 12/14/97 5:47AM
12:Finite trees/large cardinals 3/11/98 11:36AM
13:Min recursion/Provably recursive functions 3/20/98 4:45AM
14:New characterizations of the provable ordinals 4/8/98 2:09AM
14':Errata 4/8/98 9:48AM
15:Structural Independence results and provable ordinals 4/16/98
10:53PM
16:Logical Equations, etc. 4/17/98 1:25PM
16':Errata 4/28/98 10:28AM
17:Very Strong Borel statements 4/26/98 8:06PM
18:Binary Functions and Large Cardinals 4/30/98 12:03PM
19:Long Sequences 7/31/98 9:42AM
20:Proof Theoretic Degrees 8/2/98 9:37PM
21:Long Sequences/Update 10/13/98 3:18AM
22:Finite Trees/Impredicativity 10/20/98 10:13AM
23:Q-Systems and Proof Theoretic Ordinals 11/6/98 3:01AM
24:Predicatively Unfeasible Integers 11/10/98 10:44PM
25:Long Walks 11/16/98 7:05AM
26:Optimized functions/Large Cardinals 1/13/99 12:53PM
27:Finite Trees/Impredicativity:Sketches 1/13/99 12:54PM
28:Optimized Functions/Large Cardinals:more 1/27/99 4:37AM
28':Restatement 1/28/99 5:49AM
29:Large Cardinals/where are we? I 2/22/99 6:11AM
30:Large Cardinals/where are we? II 2/23/99 6:15AM
31:First Free Sets/Large Cardinals 2/27/99 1:43AM
32:Greedy Constructions/Large Cardinals 3/2/99 11:21PM
33:A Variant 3/4/99 1:52PM
34:Walks in N^k 3/7/99 1:43PM
35:Special AE Sentences 3/18/99 4:56AM
35':Restatement 3/21/99 2:20PM
36:Adjacent Ramsey Theory 3/23/99 1:00AM
37:Adjacent Ramsey Theory/more 5:45AM 3/25/99
38:Existential Properties of Numerical Functions 3/26/99 2:21PM
39:Large Cardinals/synthesis 4/7/99 11:43AM
40:Enormous Integers in Algebraic Geometry 5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees 5/25/99 5:11PM
43:More Enormous Integers/AlgGeom 5/25/99 6:00PM
44:Indiscernible Primes 5/27/99 12:53 PM
45:Result #1/Program A 7/14/99 11:07AM
46:Tamism 7/14/99 11:25AM
47:Subalgebras/Reverse Math 7/14/99 11:36AM
48:Continuous Embeddings/Reverse Mathematics 7/15/99 12:24PM
49:Ulm Theory/Reverse Mathematics 7/17/99 3:21PM
50:Enormous Integers/Number Theory 7/17/99 11:39PN
51:Enormous Integers/Plane Geometry 7/18/99 3:16PM
52:Cardinals and Cones 7/18/99 3:33PM
53:Free Sets/Reverse Math 7/19/99 2:11PM
54:Recursion Theory/Dynamics 7/22/99 9:28PM
55:Term Rewriting/Proof Theory 8/27/99 3:00PM
56:Consistency of Algebra/Geometry 8/27/99 3:01PM
57:Fixpoints/Summation/Large Cardinals 9/10/99 3:47AM
57':Restatement 9/11/99 7:06AM
Program A was delineated in postings #39 and #45. In light of the
simplicity of the Restricted Summation results in posting #57', it seems
natural to refocus Program A on Restricted Summation.
This posting is reserved for conjectures only. Some of them appear to be
within reach, and I hope to announce results in the near future. Others
look to be out of reach for the near future.
The stastement of these conjectures is entirely self contained.
**********
We first extract exactly what we need from section 3 of #57' concerning
Restricted Summation for our present purposes.
Let A,B,C be three sets. We say that A,B disjointly partitions C if and only if
i) A intersect B = emptyset;
ii) C containedin A union B.
Let Z be the set of all integers, Z+ be the set of all positive integers.
For A containedin Z, let Sigma(A) be the set of all sums x1 + ... + xn, n
>= 1, such that x1,...,xn in A. We call Sigma:P(Z) into P(Z) the summation
function.
Each U containedin Z* defines the restricted summation function
Sigma_U:P(Z) into P(Z) given by SigmaU(A) = {x1 + ... + xn: n >= 1,
x1,...,xn in A, and (x1,...,xn) in U}. Note that if U = Z* then Sigma_U =
Sigma.
Let Z* be the set of all nonempty finite sequences of integers. We view Z
as a subset of Z*. We say that U containedin Z* is finite dimensional if
and only if there is a finite upper bound to the lengths of the elements of
U.
THEOREM 1. Let U containedin Z*\Z. There is a unique A containedin Z+ such
that A,SigmaU(A) disjointly partitions Z+.
Note that we cannot get away with an arbitrary summation function here.
E.g., suppose U = Z. Then SigmaU(A) = A, and so A,SigmaU(A) can never
disjointly partition Z+.
PROPOSITION 2. Let U,V be finite dimensional subsets of Z*\Z. There exists
infinite sets A containedin B containedin C containedin Z+ such that
B,SigmaU(B) disjointly partitions SigmaV(A), and C\A,SigmaU(C)\A disjointly
partitions SigmaV(B).
Obviously if we delete the two occurrences of \A, then Proposition 2 would
be a trivial consequence of Theorem 1. For then, we can take A = B = C to
be the set given by Theorem 1.
THEOREM 3. Proposition 2 is provably equivalent, over RCA_0, to the
1-consistency of MAH = ZFC + {there exists an n-Mahlo cardinal}n. In
particular, it is independent of ZFC.
All of this is from posting #57', section 3.
Note that Proposition 2 can be put into the following form:
FORM I. Let U,V be finite dimensional subsets of Z*\Z. There exists
infinite sets A containedin B containedin C containedin Z+ such that
a certain specific Boolean equation holds between
A,B,C,SigmaU(B),SigmaU(C),SigmaV(A),SigmaV(B).
Here complementation is interpreted as complementation relative to Z+. Note
that there are at most 2^2^7 Boolean equations between seven sets up to
formal equivalence in Boolean algebra.
It is natural to make several related conjectures. Let MAH' = ZFC + (forall
n)(there exists an n-Mahlo cardinal).
CONJECTURE A. Let phi be an instance of Form I. Then MAH' proves phi or
RCA0 proves notphi. In fact, RCA + 1-Con(MAH) proves phi or RCA0 proves
notphi. Most boldly, RCA0 proves (phi iff 1-Con(MAH)) or RCA0 proves
notphi.
Note that Conjecture A is itself a Sigma-0-1 sentence, and therefore if
true, is provable in RCA0.
The following Conjecture follows from the boldest form of Conjecture A.
CONJECTURE B. Let T be an extension of RCA0. The following are equivalent.
i) every instance of Form 4 is either provable or refutable in T;
ii) T proves or refutes 1-Con(MAH).
Note that by Theorem 3, i) implies ii).
These Conjectures seem out of reach for me right now. We might as well
state some stronger, even more natural conjectures in this vein.
We can put Proposition 2 in the following form which is even more general
that Form I.
FORM II. Let U,V be finite dimensional subsets of Z*\Z. There exists
infinite sets A,B,C containedin Z+ such that a certain specific Boolean
equation holds between
A,B,C,SigmaU(A),SigmaU(B),SigmaU(C),SigmaV(A),SigmaV(B),SigmaV(C).
This involves at most 2^2^9 boolean equations between nine sets up to
formal equivalence in Boolean algebra.
CONJECTURE C. The same as Conjecture A but using Form II.
CONJECTURE D. The same as Conjecture B but using Form II.
We now mention some weaker conjectures that we feel are within reach. A
disjointified partition statement among sets B1,...,Bn is an assertion of
the form "Bi,Bj disjointly partitions Bk", where 1 <= i,j, <= k.
It is easy to put Proposition 2 in the following form. In fact, one needs
only three disjointified partition statements for this purpose.
FORM III. Let U,V be finite dimensional subsets of Z*\Z. There exists
infinite sets A containedin B containedin C containedin Z+ such that
a certain specific set of disjointified partition statements among
A,B,C,SigmaU(B),SigmaU(C),SigmaV(A),SigmaV(B) holds.
Here is a more general form.
FORM IV. Let U,V be finite dimensional subsets of Z*\Z. There exists
infinite sets A containedin B containedin C containedin Z+ such that
a certain specific set of disjointified partition statements among
A,B,C,SigmaU(A),SigmaU(B),SigmaU(C),SigmaV(A),SigmaV(B),SigmaV(C) holds.
We make the same conjectures as Conjectures A,B, but for Forms III and IV.
We close by stating a finite obstruction conjecture associated with each of
the forms I - IV. This asserts the following. Let alpha be an instance of
the given form. Let U,V be finite dimensional subsets of Z*/Z. Suppose that
for all k >= 1 there exists A,B,C with at least k elements such that the
conclusion of alpha holds. Then there exists infinite A,B,C such that the
conclusion of alpha holds.
We conjecture that these four different finite obstruction conjectures are
each provably equivalent to 1-Con(MAH) over RCA0.
More information about the FOM
mailing list