FOM: 31:First Free Sets/Large Cardinals

[Harvey Friedman]

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

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

ERRATA: In posting 30, the fourth paragraph in section 1 should read:

We focus on the subclass DGR(S_k(N)) of GR(S_k(N)) consisting of the
elements of GR(S_k(N)) such that for all edges {x,y}, max(x) notequal
max(y).

******

The independence results in posting 29 rely basically on one simple
elementary combinatorial concept: B is an R-extension of A. This may be
pretty satisfying, combinatorially, but one has to agree that it is not
fully motivated.

I have been pondering how to give an appropriate motivation for it. I came
up with a modified concept which is much better motivated. In fact, it is
so clean that there is no longer any need to isolate the concept and give
it a name - which is something I was compelled to do in 29.

We definitely feel that the present formulation of the independence results
via least free sets is by far the most convincing for the general
mathematical community. For algorithmically oriented mathematicians, those
in 30 are probably the best. I intend to make posting 32 an addendum to
posting 30.

FREE SETS AND THE NECESSARY USE OF LARGE CARDINALS
Harvey M. Friedman
February 26, 1999

Let N be the set of all nonnegative integers. For subsets A,B of N, we
write A <* B if and only if min(A delta B) is in A. (Delta means symmetric
difference). Note that <* linearly orders the subsets of N.

Let P be a property of subsets of N. We say that A is the first set
satisfying P if and only if A is the <*-least subset of N satisfying P;
i.e., P(A) and for all B < A, notP(B).

Let F:N^k into N and A contained in N. We say that A is F-free if and only
if no element of A is the value of F at smaller elements of A.

THEOREM 1. Let k >= 1 and F:N^k into N. There is a first F-free subset of
N. The first F-free subset of N is infinite.

Theorem 1 is easily proved by an inductive construction.

There is a characterization of the first F-free subset of N that is rather
explicit. Specifically, it is the unique set A contained in N such that for
all x in N, x in A if and only if x is not the value of F at k smaller
elements of A.

These first F-free sets are intriguing. It is already interesting to study
the first F-free set, where F:N into N is of the form F(x) = ax+b. And even
more intriguing to study the first F-free set, where F:N^2 into N is of the
form F(x,y) = ax+by+c. And then there are the polynomials with positive
integer coefficients. And of course the notion of F-free subset of N makes
perfectly good sense no matter what the domain and range of F are. There
will still be a first F-free set. So we can consider, e.g., polynomials
with integer coefficients.

Such problems should lend themselves to interesting computer experimentation.

We know that for semilinear F:N^k into N with integer coefficients, the
first F-free sets exhibit computational complexity completeness phenomena.

We now present our first independence result.

PROPOSITION 2. Let k,n >= 1 and F:N^k into N. There exists sets A[1]
containedin A[2] ... containedin A[n] containedin N such that
i) A[1] is an infinite set of odd integers;
ii) for all 1 <= i <= n-1, A[i+1] is the first F-free subset of A[i+1]
union A[i]+A[i].

THEOREM 3. In RCA_0, Proposition 2 follows from the 1-consistency of ZFC +
{there exists an n-Mahlo cardinal}_n and implies the consistency of ZFC +
{there exists an n-Mahlo cardinal}_n.

We mention an equivalent form of "A[i+1] is the first F-free subset of
A[i+1] union A[i]+A[i]." It is equivalent to "A[i+1] is F-free, and every x
in (A[i]+A[i])\A[i+1] is the value of F at k smaller elements of A[i+1]."
This equivalent is more local and obviously more technical.

Let A[1],...,A[n] be subsets of N and x in N. We write A[i,<x] for {y in
A[i]: y < x}.

PROPOSITION 4. Let k,n >= 1 and F:N^k into N. There exists infinite sets
A[1] containedin A[2] ... containedin A[n] containedin N such that for all
x in A[1] and 1 <= i <= n-1, A[i+1,<x] is the first F-free subset of
A[i+1,<x] union A[i,<x]+A[i,<x].

THEOREM 5. In RCA_0, Proposition 4 follows from the 1-consistency of ZFC +
{there exists an n-Mahlo cardinal}_n and implies the consistency of ZFC +
{there exists an n-Mahlo cardinal}_n.

We now give the obvious finite form for Proposition 4.

PROPOSITION 6. Let k,n,p >= 1 and F:N^k into N. There exists A[1]
containedin A[2] ... containedin A[n] containedin N, |A[1]| = p, such that
for all x in A[1] and 1 <= i <= n-1, A[i+1,<x] is the first F-free subset
of A[i+1,<x] union A[i,<x]+A[i,<x].

THEOREM 7. In RCA_0, Proposition 6 is provably equivalent to the
consistency of ATR(<omega^2) = arithmetic transfinite recursion on every
ordinal < omega^2.

We can neatly make this into an explicitly pi-0-1 independence result as
follows:

PROPOSITION 8. Let k,n,p,q >= 1 and F:[0,q]^k into N. There exists A[1]
containedin A[2] ... containedin A[n] containedin [0,2^[8knp]], |A[1]| = p,
such that for all x in A[1] and 1 <= i <= n-1, A[i+1,<x] is the first
F-free subset of A[i+1,<x] union A[i,<x]+A[i,<x].

Here 2^[t] is an exponential stack of 2's of length t.

THEOREM 9. In RCA_0, Proposition 6 is provably equivalent to the
consistency of ATR(<omega^2) = arithmetic transfinite recursion on every
ordinal < omega^2.

We now add additional estimates to Propositions 6 and 8 as follows:

PROPOSITION 10. Let k,n,p >= 1 and F:N^k into N. There exists A[1]
containedin A[2] ... containedin A[n] containedin N, |A_1| = p, such that
for all x in A[1] and 1 <= i <= n-1, A[i+1,<x] is the first F-free subset
of A[i+1,<x] union A[i,<x]+A[i,<x] of cardinality <= |A[i,<x]|^8kn.

THEOREM 11. In RCA_0, Proposition 10 is provably equivalent to the
consistency of ZFC + {there exists an n-Mahlo cardinal}_n.

And this can also be made explicitly pi-0-1:

PROPOSITION 12. Let k,n,p,q >= 1 and F:[0,q]^k into N. There exists A[1]
containedin A[2] ... containedin A[n] containedin [0,2^[8knp]], |A[1]| = p,
such that for all x in A[1] and 1 <= i <= n-1, A[i+1,<x] is the first
F-free subset of A[i+1,<x] union A[i,<x]+A[i,<x] of cardinality <=
|A[i,<x]|^8kn.

THEOREM 13. In EFA, Proposition 12 is provably equivalent to the
consistency of ZFC + {there exists an n-Mahlo cardinal}_n.

The expression |A[i,<x]|^8kn can be improved considerably. I believe that n
can be eliminated, so only k appears; in fact, when I get around making the
computations, one can get a quadratic with coefficient a small function of
k. Actually, this computation is a little tricky, and interesting, but I am
in no mood to make it right now -- this is flu season. Eventually, one
could fix k = say, 4, and the estimate would be a simple polynomial in
|A[i,<x]|.

The same results hold if F is required to be a semilinear function with
integer coefficients.