FOM: 63:Disjoint Covers/Large Cardinals

[Harvey Friedman]

This is the 63rd 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
60:Program A/Results  9/17/99  1:32PM
61:Finitist proofs of conservation  9/29/99  11:52AM
62:Approximate fixed points revisited  10.11.99  1:35AM

This is the second in a series of three postings that corrects, restates,
and extends all of the postings #57-#60.

By way of orientation, two different lines of development have emerged
since the November 1998 Annals of Mathematics paper. The first one is
1-dimensional and has a considerable amount of technical overlap with that
paper, but does not directly rely on that paper. The second one is
multi-dimensional and directly builds on top of the Annals paper. This
posting concerns the 1-dimensional approach. The next posting concerns the
multi-dimensional approach.

DISJOINT COVERS AND LARGE CARDINALS
by
Harvey M. Friedman
October 9, 1999

1. DISJOINT COVERS OF N

We use N for the set of all nonnegative integers.

Let A,B,C containedin Z. We say that A,B is a disjoint cover of C if and
only if

i) A,B are disjoint;
ii) C containedin A union B.

For x in N^k, we write max(x) for the maximum of the coordinates of x.

Let F:N^k into N. We say that F is strictly dominating if and only if for
all x in N^k, |F(x)| > |x|.

For A containedin N, we write F[A] for the forward image of A^k under F.

We start with the following infinite disjoint cover theorem.

THEOREM 1.1. Let F:N^k into N be strictly dominating. There exists A
containedin N such that A,F[A] is a disjoint cover of N. A is unique and
infinite.

Can we say anything more about A than the fact that it is infinite? The
answer is very little.

THEOREM 1.2. Let k >= 1 and A containedin N. i) implies ii) implies iii):
i) A is infinite, 0 in A, and for all n >= 1, A_n+1 - A_n <= k((n-1)^k-1);
i) A,F[A] is a disjoint cover of Z for some strictly dominating F:N^k into N;
ii) A is infinite, 0 in A, and for all n >= 1, A_n+1 - A_n <= n^k.

Here A_n is the n-th element of A counting from 1.

All further developments are based on the idea that we wish to put some
constraints on disjoint covers other than such growth conditions. Obviously
we have to relax the condition that A,F[A] is a disjoint cover of the whole
space N.

For instance, we can fix an infinite set X containedin N and ask that
A,F[A] is a disjoint cover of X. Then we have similar counting criteria.

2. DISJOINT COVERS OF A+A, F:N^k INTO N

The situation becomes more delicate when we ask that A,F[A] is a disjoint
cover of a set that depends on A. This is the direction we pursue. In
particular, we can ask that A,F[A] is a disjoint cover of A+A.

THEOREM 2.1. Let k >= 1 and F:N^k into N be strictly dominating. There are
infinitely many A containedin N such that A,F[A] is a disjoint cover of
A+A. However, we cannot replace "infinitely" by "uncountably many".

The second statement in Theorem 2.1 severely inhibits our ability to have
the desired control over A such that A,F[A] is a disjoint cover of A+A.
This is made clearer by the following stronger statement.

THEOREM 2.2. For all k >= 1 there is a strictly dominating F:N^k into N
such that the following holds. If A,F[A] is a disjoint cover of A+A then A
is finite or eventually equaled to the multiples of a positive integer.

We thus are led to pairs A containedin B containedin N such that B,F[B] is
a disjoint cover of A+A. We wish to have some control over such A,B. This
possibility is evident from the following.

THEOREM 2.3. Let k >= 1 and F:N^k into N be strictly dominating. There are
continuumly many pairs A containedin B containedin N such that B,F[B] is a
disjoint cover of A+A, where the B's are almost disjoint.

The following result indicates that we can find "large" A,B.

THEOREM 2.4. Let k >= 1, F:N^k into N be strictly dominating, and V be a
countable set of infinite subsets of N. There exist A containedin B
containedin N meeting every element of V, such that B,F[B] is a disjoint
cover of A+A.

It is natural to extend this to finite sequences. However, the result is
independent of ZFC, and can only be proved by using Mahlo cardinals of
every finite order.

PROPOSITION 2.5. Let k,r >= 1, F:N^k into N be strictly dominating, and V
be a countable set of infinite subsets of N. There exist A_1 containedin
... containedin A_r containedin N meeting every element of V, such that for
all 1 <= i <= r-1, A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i.

There are some important special cases of Proposition 2.5.

PROPOSITION 2.6. Let k,r >= 1, F:N^k into N be strictly dominating, and E
be an infinite subset of N. There exist A_1 containedin ... containedin A_r
containedin N with infinitely many elements in common with E, such that for
all 1 <= i <= r-1, A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i.

And also the special case where E = 2N+1.

PROPOSITION 2.7. Let k,r >= 1, F:N^k into N be strictly dominating. There
exist A_1 containedin ... containedin A_r containedin N with infinitely
many odd elements, such that for all 1 <= i <= r-1, A_i+1,F[A_i+1] is a
disjoint cover of A_i + A_i.

In fact, we can even weaken this as follows.

PROPOSITION 2.8. Let k,r >= 1, F:N^k into N be strictly dominating. There
exist A_1 containedin ... containedin A_r containedin N where A_r has
infinitely many odd elements, such that for all 1 <= i <= r-1,
A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i.

We can consider two strictly dominating functions.

PROPOSITION 2.9. Let k,r >= 1 and F,G:N^k into N be strictly dominating.
There exist infinite A_1 containedin  ... containedin A_r containedin N and
B_1 containedin ... containedin B_r containedin N such that for all 1 <= i
<= r-1, A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i, B_i+1,G[B_i+1] is
a disjoint cover of B_i + B_i, and A_1 = B_1.

We can combine this with 2.5.

PROPOSITION 2.10. Let k,r >= 1, F,G:N^k into N be strictly dominating, and
V be a countable set of infinite subsets of N. There exist A_1 containedin
... containedin A_r containedin N and B_1 containedin ... containedin B_r
containedin N such that for all 1 <= i <= r-1, A_i+1,F[A_i+1] is a disjoint
cover of A_i + A_i, B_i+1,G[B_i+1] is a disjoint cover of B_i + B_i, and
A_1 = B_1 meets all elements of V.

THEOREM 2.11. Propositions 2.5 - 2.10 are provably equivalent to the
1-consistency of MAH = ZFC + {there exists an n-Mahlo cardinal}_n over ACA.
The forward direction is provable in RCA_0.

There are obvious extensions of Propositions 2.9 and 2.10 to finitely many
strictly dominating functions to which Theorem 2.11 also applies.

3. DISJOINT COVERS OF A+A, SEMILINEAR FUNCTIONS

An integral semilinear function is a function from some N^k into N whose
graph is a semilinear subset of N^k+1. A semilinear subset of N^k is a
Boolean combination of finitely many halfplanes given by integer
coefficients.

We can consider Propositions 2.5 - 2.10 with "strictly dominating" replaced
by "a strictly dominating integral semilinear function."

THEOREM 3.1. Propositions 2.5 - 2.10 so modified are provably equivalent to
the consistency of MAH. The forward direction is provable in RCA_0.

PROPOSITION 3.2. Let k,r >= 1, F:N^k into N be a strictly dominating
integral semilinear function. There exist A_1 containedin ... containedin
A_r containedin N starting with an infinite geometric progression, such
that for all 1 <= i <= r-1, A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i.

THEOREM 3.3. Proposition 3.2 is provably equivalent to the consistency of
MAH. The forward direction is provable in RCA_0.

4. DISJOINT COVERS OF A+A, SEMILINEAR FUNCTIONS, FINITE FORMS

We first put Proposition 3.2 in a more explicit form.

PROPOSITION 4.1. Let k,r >= 1, F:N^k into N be a strictly dominating
integral semilinear function, and t be sufficiently large. There exist
{1,t,t^2,...} =  A_1 containedin ... containedin A_r containedin N such
that for all 1 <= i <= r-1, A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i.

We now give the following obvious finite form.

PROPOSITION 4.2. Let k,r >= 1, F:N^k into N be a strictly dominating
integral semilinear function, and t,n be sufficiently large. There exist
{1,t,t^2,...,t^n} = A_1 containedin ... containedin A_r containedin N such
that for all 1 <= i <= r-1, A_i+1,F[A_i+1] is a disjoint cover of A_i + A_i.

Note that Proposition 4.2 is explicitly in Pi-0-4 form.

We can put Proposition 4.2 in explicitly Pi-0-1 form with the help of
estimates. Here are the considerations that allow us to do this. By the
"presentation", we
will mean the presentation of the graph of F as a Boolean combination of
finitely many halfplanes, and the parameters k,r.

i. We can use linear algebra to bound the universal quantifiers in the
definition of strictly dominating, double exponentially in the presentation.

ii. We can hypothesize that t,n be double exponentially higher than the
presentation. This requires a detailed understanding of the proof of
Proposition 4.2 from Mahlo cardinals.

iii. We can bound the magnitudes of the elements of A_r double exponentially
in the presentation and t,n.

THEOREM 4.3. Propositions 4.1 and 4.2 are provably equivalent to the
consistency of MAH. The forward direction is provable in RCA_0. For
Proposition 4.2, the equivalence can be proved in EFA* = exponential
function arithmetic with indefinitely iterated exponention, with the
forward direction provable in EFA = exponential function arithmetic.

5. DISJOINT COVERS OF A+A, POLYNOMIALS

We revisit sections 3 and 4 in terms of integral polynomials. An integral
polynomial is a function P from some Cartesian power of Z into Z which is
given by a polynomial with integer coefficients.

There are not enough strictly dominating integral polynomials for our
purposes. Instead, we look at arbitrary integral polynomials but use a
modified notion of image. Let F:Z^k into Z and A containedin N. We write
F_<[A] for the set of all F(x_1,...,x_k) such that

i) x_1,...,x_k are from A;
ii) x_1 < ... < x_k < F(x_1,...,x_k).

Thus F_<[A] is the range of the largest restriction F' of F to a subset of
A^k such that F' is strictly dominating.

PROPOSITION 5.1. Let r >= 1 and P be an integral polynomial. There exists
A_1 containedin ... containedin A_r containedin N with infinitely many odd
elements such that for all 1 <= i <= r-1, A_i+1,P_<[A_i+1] is a disjoint
cover of A_i + A_i.

PROPOSITION 5.2. Let r >= 1, P be an integral polynomial, and t be
sufficiently large. There exists {1,t,t^t,(t^t)^t,...} = A_1 containedin
... containedin A_r containedin N such that for all 1 <= i <= r-1,
A_i+1,P_<[A_i+1] is a disjoint cover of A_i + A_i.

PROPOSITION 5.3. Let r >= 1, P be an integral polynomial, and t,n be
sufficiently large. There exists finite {1,t,t^t,t^(t^2),...,t^(t^n)} = A_1
containedin ... containedin A_r containedin N such that for all 1 <= i <=
r-1, A_i+1,P_<[A_i+1] is a disjoint cover of A_i + A_i.

Note that Proposition 5.3 is in explicitly Pi-0-4 form. It can be made
explicitly Pi-0-3 by bounding A_r. However, it is not clear how to do
better in a natural way.

THEOREM 5.4. Propositions 5.1 - 5.3 are provably equivalent to the
1-consistency of MAH. The forward direction is provable in RCA_0. For
Proposition 5.3, the equivalence can be proved in EFA*, with the forward
direction provable in EFA.

6. DISJOINT COVERS OF P[A], POLYNOMIALS

The approch in section 5 of using P_<[A} instead of P[A} suggests the use
of P[A]. However, we have to be careful.

THEOREM 6.1 The following is false. Let r >= 1 and P be an integral
polynomial. There exists A_1 containedin ... containedin A_r containedin N
with infinitely many odd elements such that for all 1 <= i <= r-1,
A_i+1,P_<[A_i+1] is a disjoint cover of P[A_i] intersect N.

This can be fixed by modifying P_<[A]. However, it is more natural to move
to a related setting instead.

Let F:Z^k into Z and E containedin Z^k. We say that F is expansive on E if
and only if there exists c > 1 such that for all x_1,...,x_k in E,

*|F(x_1,...,x_k)| > c|x_1|,...,c|x_k|.*

We write F_E[A] for F[A^k intersect E].

A set is bi-infinite if and only if it has infinitely many positive and
negative elements.

THEOREM 6.1. Let P be an integral polynomial that is expansive on a set E.
There exists bi-infinite A containedin B containedin Z such that B,P_E[B]
is a disjoint cover of P[A].

Now we consider three sets.

PROPOSITION 6.2. Let P be an integral polynomial that is expansive on a set
E. There exists bi-infinite A containedin B containedin C containedin Z
such that B,P_E[B] is a disjoint cover of P[A] and C,P_E[C] is a disjoint
cover of P[B].

PROPOSITION 6.3. Let r >= 1 and  P be an integral polynomial that is
expansive on a set E. There exists bi-infinite A_1 containedin ...
containedin A_r
containedin Z such that for all 1 <= i <= r-1, A_i+1,P_E[A_i+1] is a
disjoint cover of P[A_i].

THEOREM 6.4. Propositions 6.2 and 6.3 are provably equivalent to the
1-consistency of MAH over ACA. The forward direction of this equivalence is
provable in RCA_0.

7. DISJOINT COVERS OF P[A], POLYNOMIALS, FINITE FORMS

An integral polytope is the intersection of finitely many halfplanes with
integer coefficients in some Cartesian power of Z.

As a first step towards concreteness, consider the following specialization
of Proposition 6.3.

PROPOSITION 7.1. Let r >= 1 and P be an integral polynomial that is
expansive on an integral polytope E. There exist bi-infinite A_1
containedin ... containedin A_r containedin Z such that for all 1 <= i <=
r-1, A_i+1,P_E[A_i+1] is a disjoint cover of P[A_i].

PROPOSITION 7.2. Let r >= 1 and P be an integral polynomial that is
expansive on an integral polytope E. There exist infinite sets
{1,t,t^t,t^(t^2),...} = A_1 containedin ... containedin A_r containedin Z
such that for all 1 <= i <= r-1, A_i+1,P_E[A_i+1] is a disjoint cover of
P[A_i].

We now take the final step.

PROPOSITION 7.3. Let r >= 1 and P be an integral polynomial that is
expansive on an integral polytope E, and t,n be sufficiently large. There
exist finite sets {1,t,t^t,t^(t^2),...,t^(t^n)} = A_1 containedin ...
containedin A_r containedin Z such that for all 1 <= i <= n-1,
A_i+1,P_E[A_i+1] is a disjoint cover of P[A_i].

Proposition 7.3 is in explicitly Pi-0-4 form. The final existential
quantifier can be easily bounded, and so it can be put in explicit Pi-0-3
form. Acoording to the following Theorem, it is provably equivalent to a
Pi-0-2 sentence, but we do not know how to write it as a natural explicitly
Pi-0-2 sentence.

THEOREM 7.4. Propositions 7.1 - 7.3 are provably equivalent to the
1-consistency of MAH over RCA_0. For Proposition 7.3, we may use EFA*, with
EFA for the forward direction. Moreover, these results hold if we set n = 3
or if we replace all n inclusions by proper inclusions.

For Pi-0-1 sentences, we use linear functions, as in section 4.

8. DISJOINT COVERS OF T[A], POSITIVE LINEAR FUNCTIONS, FINITE FORMS

A positive integral linear function is a function from some Cartesian power
of Z into Z which is given by a linear transformation whose coefficients
are nonnegative integers. Another way of saying this is that it is an
integral linear function which maps some Cartesian power of Z^+ into Z^+.

PROPOSITION 8.1. Let r >= 1 and T be a positive integral linear function
that is
strictly dominating on an integral semilinear set E. There exist sets
{1,t,t^2,...} = A_1 containedin ... containedin A_n containedin Z such that
for all 1 <= i <= r-1, A_i+1,T_E[A_i+1] is a disjoint cover of T[A_i].

We now take the final step.

PROPOSITION 8.2. Let r >= 1, T be a positive integral linear function that is
strictly dominating on an integral semilinear set E, and t,n be
sufficiently large. There exist finite {1,t,t^2,...,t^n} containedin A_1
containedin ... containedin A_n containedin Z such that for all 1 <= i <=
r-1, A_i+1,T_E[A_i+1] is a disjoint cover of T[A_i].

THEOREM 8.3. Propositions 8.1 and 8.2 are provably equivalent to the
consistency of MAH over RCA_0. For Proposition 8.2, we may use EFA*, with
EFA for the forward direction. Moreover, these results hold if we set n =
3 or if we replace all n inclusions by proper inclusions.

We can follow the same procedure as indicated for Proposition 4.2 in order
to put Proposition 8.2 in explicitly Pi-0-1 form, where Theorem 8.3 still
holds.

9. CLASSIFICATION PROBLEMS

We start with Proposition 7.1 formulated with proper inclusions. As stated
in section 7, this is provably equivalent to the 1-consistency of MAH over
ACA.

PROPOSITION 7.1. Let r >= 1 and P be an integral polynomial that is
expansive on a set E. There exists bi-infinite A_1 properlycontainedin ...
properlycontainedin A_r properlycontainedin Z such that for all 1 <= i <=
r-1, A_i+1,P_E[A_i+1] is a disjoint cover of P[A_i].

FORM I. Let P be an integral polynomial that is expansive on a set E, and r
>= 1. There exists bi-infinite A_1 properlycontainedin ...
properlycontainedin A_r properlycontainedin Z such that for all 1 <= i <=
r-1, a specific Boolean equation holds among A_i+1,P_E[A_i+1],P[A_i].

Here it is understood that there is a single Boolean equation in three sets
which is to hold of A_i+1,P_E[A_i+1],P[A_i] simultaneouly as i goes from 1
to r-1.

Note that Proposition 7.1 is obviously an instance of Form I.

There are exactly 256 instances of Form I up to Boolean equivalence of
Boolean equations. Of course, there are far fewer than that many when one
takes into account other formal aspects of the situation. The following
result indicates that there are, in some sense, only three different kinds
of instances of Form I.

THEOREM 9.1. Every instance of Form I is either provable in ACA, refutable
in RCA_0, or equivalent to the 1-consistency of MAH over ACA. All three
possibilities are realized.

THEOREM 9.2. Let T be an extension of ACA. The following are equivalent.
i) every instance of Form I is either provable or refutable in T;
ii) T proves or refutes the 1-consistency of MAH.

THEOREM 9.3. (First finite obstruction) Suppose a given instance of Form I
holds with "bi-infinite" replaced by "arbitrarily large finite." Then it
holds with "bi-infinite" replaced by "infinite."

PROPOSITION 9.4. (Second finite obstruction) Suppose a given instance of
Form I holds with "bi-infinite" replaced by "infinite." Then it holds
unmodified.

PROPOSITION 9.5. (Third finite obstruction) Suppose a given instance of
Form I holds with "bi-infinite" replaced by "arbitrarily large finite."
Then it holds unmodified.

Obviously third finite obstruction is equivalent to the conjuunction of
first and second finite obstruction.

THEOREM 9.6. Second and third finite obstruction are provably equivalent to
the consistency of MAH over ACA, with RCA_0 for the forward direction.

We conjecture that these results hold for the much more comprehensive Form
II below. However, this is not within reach at the moment.

FORM II. Let P be an integral polynomial that is expansive on a set E, and
n >= 1. There exists bi-infinite A-_1 properlycontainedin ...
properlycontainedin A_n properlycontainedin Z such that for all 1 <= i <=
n-1, a specific Boolean equation holds among
A_i,A_i+1,P[A_i],P[A_i+1],P_E[A_i],P[A_i+1].

However, there is an interesting subcase of Form II that seems within reach.

FORM III. Let P be an integral polynomial that is expansive on a set E, and
n >= 1. There exists bi-infinite A_1 properlycontainedin ...
properlycontainedin A_n properlycontainedin Z such that for all 1 <= i <=
n-1, a specific set of disjoint cover conditions holds among
A_i,A_i+1,P[A_i],P[A_i+1],P_E[A_i],P_E[A_i+1].

Obviously, Proposition 7.1 is an instance of Form III.