FOM: 39:Large Cardinals/synthesis

[Harvey Friedman]

This is the 39th 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

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

FAVORITE SELF CONTAINED POSTINGS: 21, 25, 27, 31, 32, 34, 35', 37, 38, 39.

There has been a significant simplification in the approach I had to
independence results involving infinite sets of natural numbers, before I
introduced first F-free sets. This has also led to a renewed interest in
embedding such independence results in natural families of problems that
can only be solved uniformly using large cardinals.

CAUTION: Again, I have to invoke the warning that I am still searching for
the right formulations before all relevant details are checked.

Here is the new form of the independence results. Let N be the set of all
nonnegative integers. Let F:N^k into N. For A containedin N, we write F[A]
for the set of all values of F at arguments from A. We use A delta B for
the symmetric difference of A and B, which is A\B union B\A.

We start with the following fundamental result which neatly encapsulates
recursion. We say that F:N^k into N is strictly dominating if and only if
for all x_1,...,x_n in N, F(x_1,...,x_n) > x_1,...,x_n.

THEOREM 1. Let k >= 1 and F:N^k into N be strictly dominating. There exists
an infinite set A containedin N such that A delta F[A] = N. In fact, A is
unique.

The construction A delta F[A] plays such a fundamental role for us that it
deserves a name. We call it the discrepancy of F on A.

Theorem 1 is easily proved within weak systems like RCA_0.

We now come to the new independence result. Consider the following obvious
weakening of Theorem 1:

COROLLARY 2. Let k,n >= 1 and F:N^k into N be strictly dominating. There
exists infinite sets A_1 containedin A_2 containeedin ... containedin A_n
containedin N such that for all 1 <= i <= n-1, A_i + A_i containedin A_i+1
delta F[A_i+1].

This is immediately obtained from Theorem 1 by setting A_1,...,A_n to be
the unique A in Theorem 1. However, consider this new independent statement:

PROPOSITION 3. Let k,n >= 1 and F:N^k into N be strictly dominating. There
exists infinite sets A_1 containedin A_2 containeedin ... containedin A_n
containedin N such that for all 1 <= i <= n-1, A_i + A_i containedin (A_i+1
delta F[A_i+1])\A_1.

In this posting, we will not discuss finite forms. This continues to be an
issue with this kind of independence result. That was a main reason why I
used the first F-free set approach in 31 - it lends itself to a certain
kind of finite form. I want to revisit the sticky matter of finite forms in
a later posting. I think that the ideas presented in this posting should
lead to another approach to finite forms.

For the sake of completeness, let me mention two earlier independence
results in this style. I still prefer Proposition 3, however.

PROPOSITION 4. Let k,n >= 1 and F:N^k into N be strictly dominating. There
exists A_1 containedin A_2 containeedin ... containedin A_n containedin N
such that
i) A_1 contains infinitely many odd elements;
ii) for all 1 <= i <= n-1, A_i + A_i containedin A_i+1 delta F[A_i+1].

PROPOSITION 5. Let k,n >= 1, F:N^k into N be strictly dominating, and E be
an infinite subset of N. There exists A_1 containedin A_2 containeedin ...
containedin A_n containedin N such that
i) A_1 is an infinite subset of E;
ii) for all 1 <= i <= n-1, A_i + A_i containedin A_i+1 delta F[A_i+1].

Let MAH be the formal system ZFC + {there exists an n-Mahlo cardinal}_n.

THEOREM 6. Propositions 3-5 are provable in ZFC + "for all n there exists
an n-Mahlo cardinal," but none are provable in MAH, assuming MAH is
consistent. Propositions 3-5 are provable from the 1-consistency of MAH,
and each imply the consistency of MAH.

NOTE: I have postponed the detailed work involved in determining the exact
equivalent of Propositions 3-5. I strongly suspect that they are equivalent
to 1-Con. This issue has now become CRITICAL as we shall see below.

There is a natural and important generalization of these Propositions where
we use multiple sum sets. For r >= 1 and A containedin N, write +_r(A) =
{x_1+...+x_r: x_1,...,x_r in A}. Thus +_1(A) = A and +_2(A) = A+A.

We now modify the Propositions to incorporate +_r(A).

PROPOSITION 3'. Let k,n,r >= 1 and F:N^k into N be strictly dominating.
There exists infinite sets A_1 containedin A_2 containeedin ... containedin
A_n containedin N such that for all 1 <= i <= n-1, +_r(A_i) containedin
(A_i+1 delta F[A_i+1])\A_1.

PROPOSITION 4'. Let k,n,r >= 1 and F:N^k into N be strictly dominating.
There exists A_1 containedin A_2 containeedin ... containedin A_n
containedin N such that
i) A_1 contains infinitely many odd elements;
ii) for all 1 <= i <= n-1, +_r(A_i) containedin A_i+1 delta F[A_i+1].

PROPOSITION 5'. Let k,n,r >= 1, F:N^k into N be strictly dominating, and E
be an infinite subset of N. There exists A_1 containedin A_2 containeedin
... containedin A_n containedin N such that
i) A_1 is an infinite subset of E;
ii) for all 1 <= i <= n-1, +_r(A_i) containedin A_i+1 delta F[A_i+1].

The main consequence of introducing the new parameter r is that these
Propositions are already independent even for n = 3.

THEOREM 6'. Theorem 6 holds for Propositions 3'-5'. Theorem 6 also holds
for Propositions 3'-5' with n set to 3. However, if n is fixed in
Propositions 3-5, then we get statements that correspond to Mahlo cardinals
of order roughly n+c, where c is a small universal constant.

We now come to the synthesis. A remarkable aspect of Proposition 3 is how
easily it can be embedded in a very natural infinite class of problems
which are subject to rather stunning conjectures. However, we feel that
these conjectures are not within reach at this time. But we then move to
some interesting subclasses of problems where the corresponding conjectures
look within reach.

A Boolean expression in t variables (representing sets) is a term involving
union, intersection, complementation, and the t variables.

We now consider the following problem P_1:

Given: n >= 1 and a Boolean expression H in 3n variables.
Determine: For all k >= 1 and strictly dominating F:N^k into N, there
exists infinite sets A_1 containedin A_2 containedin ... containedin A_n
containedin N such that
H(A_1,...,A_n,F[A_1],...,F[A_n],A_1+A_1,...,A_n+A_n) = N.

We also consider the following problem P_2:

Given: n >= 1 and a Boolean expression H in 3n variables.
Determine: For all k,r >= 1 and strictly dominating F:N^k into N, there
exists infinite sets A_1 containedin A_2 containedin ... containedin A_n
containedin N such that
H(A_1,...,A_n,F[A_1],...,F[A_n],+_r(A_1),...,+_r(A_n)) = N.

Here are some conjectures about P_1:

1.1. P_1 can be decided in exponential time. This fact can be proved in ACA.
1.2. However, no algorithm exists which, provably in MAH, decides P_1
(assuming MAH is consistent).
1.3. In fact, if T is a system of set theory, then the following are
equivalent:
	i) there exists an algorithm such that T proves that algorithm
decides P_1;
	ii) T proves the 1-consistency of MAH.
1.4. Every instance of P_1 is either refutable in ACA or provable in MAH.
There is an exponential time decision procedure which, provably in ACA,
takes each instance of P_1 and provides either a refutation in ACA or a
proof in MAH.
1.5. P_1 obeys a finiteness theorem. I.e., for every instance of P_1, if
that instance is true where "infinite" is replaced by "arbitrarily large
finite", then that instance is true.
1.6. However, this finiteness theorem for P_1 is provably equivalent to the
1-consistency of MAH over ACA.
1.7. Over ACA, the instances of P_1 provably represent consistency
strengths of well ordered type at most omega^omega which are cofinal in the
consistency strengths of the fragments of MAH. The comparison relation on
the consistency strenghts is given by an exponential time algorithm that
provably works within ACA.

Here are some conjectures about P_2. Let MAH+ = ZFC + "for all n there
exists an n-Mahlo cardinal."

2.1. P_2 can be decided in exponential time. This fact can be proved in ACA.
2.2. However, no algorithm exists which, provably in MAH, decides P_2
(assuming MAH is consistent).
2.3. In fact, if T is a system of set theory, then the following are
equivalent:
	i) there exists an algorithm such that T proves that algorithm
decides this problem;
	ii) T proves the 1-consistency of MAH.
2.4. Every instance of P_2 is either refutable in ACA or provable in MAH+.
There is an exponential time decision procedure which, provably in ACA,
takes instances of P_2 and provides either a refutation in ACA or a proof
in MAH+.
2.5. In fact, every instance of P_2 is either refutable in ACA or provable
in ACA or provably equivalent (over ACA) to the 1-consistency of MAH. There
is an exponential time decision procedure which, provably in ACA, takes
instances of P_2 and provides either a refutation in ACA or a proof in ACA
or a proof in ACA of its equivalence to the 1-consistency of MAH.
2.6. P_2 obeys a finiteness theorem. I.e., for every instance of P_2, if
that instance is true where "infinite" is replaced by "arbitrarily large
finite", then that instance is true.
2.7. However, this finiteness theorem for P_2 is provably equivalent to the
1-consistency of MAH over ACA.
2.8. There are instances of P_2 that are provably equivalent to the
1-consistency of MAH over ACA.
2.9. Moreover, every instance of P_2 that is not provable in ACA is
provably equivalent to the 1-consistency of MAH over ACA.

I have been careful to use ACA instead of RCA_0 throughout, because in an
appropriate sense, the classical infinite Ramsey theorem is an integral
part of this situation, and I want to choose a base theory that proves it.
However, I suspect that RCA_0 can be used throughout these conjectures.

Becuase of the obvious embeddings of Propositions 3 and 3', we already know
a little bit about these conjectures. We already know that 1.2 and 2.2 are
true. Also in 1.3 and 2.3, we know that i) implies ii) (for sure with
consistency). With regard to 1.6 and 2.7, we at least know that this
finiteness "theorem" implies the 1-consistency of MAH over ACA (for sure
with consistency). And we know 2.8 (for sure with implying consistency).
Also with regard to 1.7, we know that there exists integers n_1 < n_2 < ...
such that for each i, some consistency strength between n_1-Mahlo and
n_2-Mahlo is represented by an instance of P_1.

But the main obstacle is that there are such a large variety of Boolean
expressions involved here that 1.1 and 2.1 look out of reach - at least
without a great deal of PAINstaking analysis of unpredictable duration.

These conjectures amount to an encapsulation of the logical universe from
the bottom up through some of the small large cardinals that go way beyond
the usual axioms for mathematics within elementary discrete mathematics.

A more general program is to encapsulate the entire known logical universe
from the bottom up through the entire large cardinal hierarchy within not
only elementary discrete mathematics, but in various mathematical subjects
of a "structural" nature. I say "structural" since we must avoid the
undecidability of Hilbert's tenth problem and the like.

Now since I have been vaguely talking about conjectures like the precise
ones above for years, it is most imperative that I formulate some versions
that I feel are within reach - or almost done. That is the point of the
remainder of this posting.

In order to make these conjectures easier, we work directly with the
discrepancy sets A delta F[A]. A comparison condition R in r variables
B_1,...,B_r is a list of zero or more clauses of the forms:

i) B_i containedin B_j;
ii) B_i disjoint from B_j.

We write R(B_1,...,B_r) if all clauses of R hold. Obviously, comparison
conditions can be written in the form H(B_1,...,B_r) = N. In this sense, we
are watering down the scope of the conjectures.

We now consider the following problem P_3:

Given: n >= 1 and a comparison condition R in 3n variables.
Determine: For all k >= 1 and strictly dominating F:N^k into N, there
exists infinite sets A_1 containedin A_2 containedin ... containedin A_n
containedin N such that R(A_1,...,A_n,A_1 delta F[A_1],...,A_n delta
F[A_n],A_1+A_1,...,A_n+A_n).

We also consider the following related problem P_4:

Given: n >= 1 and a comparison condition R in 3n variables.
Determine: For all k,r >= 1 and strictly dominating F:N^k into N, there
exists infinite sets A_1 containedin A_2 containedin ... containedin A_n
containedin N such that R(A_1,...,A_n,A_1 delta F[A_1],...,A_n delta
F[A_n],+_r(A_1),...,+_r(A_n)).

We make the same conjectures for P_3 that we made for P_1. And we make the
same conjectures for P_4 that we made for P_2. We have the same partial
results. We believe that these are within reach - except 1.7, which
probably requires a truly massive investigation.

Now for a punch line. I expect I should have NO TROUBLE in verifying these
conjectures in the very special case of P_4 where the comparison condition
has only 3 clauses in 3 variables. Again, we have the same partial results
because of Proposition 3' for n = 3. Thus even this extremely special case
is already tied up with Mahlo cardinals of finite order!