FOM: 60:Program A/Results

Sat Sep 18 08:32:19 EDT 1999

This is the 60th 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
58:Program A/Conjectures  9/12/99  1:03AM
59:Restricted summation:Pi-0-1 sentences  9/17/99  10:41AM

This is a followup to posting #58, where we made a number of conjectures.
We were not able to solve those particular conjectures. However, we have
been able to solve some other conjectures in the same spirit. This gets
Program A going in a more convincing way than posting #45.

This posting is self contained. Again, there are a lot of details to check.

REVIEW OF TERMINOLOGY AND SOME PREVIOUS RESULTS

Let A,B,C be three sets. We say that A,B is a disjoint cover of 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 x_1 + ... + x_n, n
>= 1, such that x_1,...,x_n in A.

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.

Each U containedin Z* defines the restricted summation function
Sigma_U:P(Z) into P(Z) given by Sigma_U(A) = {x_1 + ... + x_n: n >= 1,
x_1,...,x_n in A, and (x_1,...,x_n) in U}. Note that if U = Z* then Sigma_U =
Sigma.

It will be convenient to write UA for Sigma_U(A).

THEOREM 1. Let U containedin Z*\Z. There is a unique A containedin Z^+ such
that A,UA is a disjoint cover of Z^+.

PROPOSITION 2. Let U,V be finite dimensional subsets of Z*\Z. There exist
infinite sets A containedin B containedin C containedin Z^+ such that
B,UB is a disjoint cover of VA, and C\A,(UC)\A is a
disjoint cover of VB.

Here is a strengthened form.

PROPOSITION 3. Let U,V be finite dimensional subsets of Z*\Z, and n >= 1.
There exist infinite sets A_1 properlycontainedin ... properlycontainedin
A_n containedin Z^+ such that for all 1 <= i <= n-1,
A_i+1\A_1,UA_i+1\A_1 is a disjoint cover of VA_i.

THEOREM 4. Propositions 2 and 3 are provably equivalent, over RCA_0, to the
1-consistency of MAH = ZFC + {there exists an n-Mahlo cardinal}_n. In
particular, they are independent of ZFC.

ARITHMETICAL BALANCE

In order to get Program A going, we consider one of many alternative
statements of the independence results. At the moment, the most convenient
alternative is to use arithmetical balance.

We say that a set of positive integers is arithmetically balanced if and
only if it contains and omits a positive element from every residue class.

PROPOSITION 5. Let U,V be finite dimensional subsets of Z*\Z, and n >= 1.
There exist arithmetically balanced sets A_1 properlycontainedin ...
properlycontainedin
A_n containedin Z^+ such that for all 1 <= i <= n-1, A_i+1,UA_i+1 is a
disjoint cover of VA_i.

Theorem 4 applies to Proposition 5.

We now consider the following Propositional form. Note that there are only
finitely many such Propositions in this form, up to formal Boolean
equivalence.

FORM I. Let U,V be finite dimensional subsets of Z*\Z, and n >= 1.
There exist arithmetically balanced sets A_1 properlycontainedin ...
properlycontainedin
A_n containedin Z^+ such that for all 1 <= i <= n-1, a specified Boolean
equation holds between A_i,A_i+1,UA_i,VA_i+1.

NOTE: In Form I, the same single Boolean equation in four set variables is
to hold for all i = 1,...,n-1. Complementation is taken relative to Z^+.

Let MAH' = ZFC + (forall n)(there exists an n-Mahlo cardinal).

THEOREM 6. Let phi be an instance of Form I. Then MAH' proves phi or
RCA_0 proves notphi. In fact, ACA + 1-Con(MAH) proves phi or RCA_0 proves
notphi.

Note that Theorem 6 is itself a Sigma-0-1 sentence, and therefore is
provable just about anywhere.

THEOREM 7. Let T be an extension of RCA_0. The following are equivalent.
i) every instance of Form I is either provable or refutable in T;
ii) T proves or refutes 1-Con(MAH).

PROPOSITION 8. (Finite obstruction.) Let phi be an instance of Form I.
Suppose phi holds with "arithmetically balanced" replaced by "arbitrarily
large finite". Then phi holds.

THEOREM 9. Proposition 8 is provably equivalent to 1-Con(MAH) over RCA_0.

These results all hold even if in Form I, we fix n = 3.

Observe that we have used Boolean equations in A_i,A_i+1,UA_i,VA_i+1. We
could also have used just A_i+1,UA_i,VA_i+1, and obtained the exact same
results. It is better to allow all four sets. In fact, we would like to
obtain the same results using the six sets
A_i,A_i+1,UA_i,VA_i,UA_i+1,VA_i+1. This will take more work.