FOM: 28:Optimized Functions/Large Cardinals:More

[Harvey Friedman]

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

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

This supercedes 26. We restate all of 26 with slightly altered terminology
in order to present a unified treatment of 26 and the present 28. The new
material presents independent pi-0-1 sentences.

OPTIMIZED FUNCTIONS AND THE NECESSARY USE OF LARGE CARDINALS
by
Harvey M. Friedman
January 24, 1999

[A lot of details still need to be checked. But we have some confidence
that these results are the next step in the longstanding project of
obtaining yet simpler discrete/finite necessary uses of large cardinals.]

1. Full regressive functions on partial orderings.

Let (X,<=) be a partial ordering. Define FRF(X,r) to be the set of all
functions f:A into A^r such that

	i) A is a finite subset of X;
	ii) for all x in A, each coordinate of f(x) is <= x.

Here FRF stands for "full regressive functions."

Let f in FRF(X,r). We say that g is a full restriction of f if and only if
g in FRF(X,r) and g containedin f. We say that g is a proper full
restriction of f if and only if g is a full restriction of f that is not f.

We say that B generates C in f if and only if

	i) B containedin C containedin dom(f);
	ii) C = dom(g), where g is the least full restriction of f such
that B containedin dom(g).

THEOREM 1.1. Let f in FRF(X,r). The least set which generates dom(f) in f
exists. It is the set of all arguments that are not a coordinate of the
value of f at any strictly greater argument.

This least set is called the basis for f. The number of elements of the
basis for f is called the degree of f.

Note that g is a full restriction of f if and only if g in FRF(X,r) and
every full restriction of g is a full restriction of f. We say that g is an
almost full restriction of f if and only if g in FRF(X,r) and every proper
restriction of g is a full restriction of f.

THEOREM 1.2. Let f in FRF(X,r). Every almost full restriction of f of
degree > 1 is a full restriction of f. This result does not hold for degree
1.

Now let w:FRF(X,r) into N. We can view w as a "weight function," where w(f)
is the "weight" of f. We say that f is w-optimal if and only if

	i) f in FRF(X,r);
	ii) the weight of every full restriction of f is at most that of
every almost full restriction of f with the same basis.

THEOREM 1.3. Let w:FRF(X,r) into N and A be a finite subset of X. There is
a w-optimal f in FRF(X,r) with domain A. Every full restriction of every
w-optimal function is w-optimal.

This is proved by the obvious greedy construction.

2. Independence results:full regressive functions.

Let N be the set of all nonnegative integers. For sets A and k >= 1, let
S_k(A) be the set of all k element subsets of A.

We use the partial ordering <=_k on S_k(N), where x <=_k y if and only if
max(x) < max(y) or x = y. We work in the spaces FRF(<=_k,r).

Let f in FRF(<=_k,r) and x in dom(f). The restricted value of f at x is the
r-tuple obtained from f(x) by intersecting each coordinate of f(x) with
[0,min(x)).

By way of background, we state the following result from large cardinal
theory; it is easily derived from results in [3].

We say that two k element subsets x,y of a linear ordering are shift
related if and only if x\{min(x)} = y\{max(y)}. For example, {2,5,9} and
{5,9,11} are shift related.

THEOREM 2.1. Let k >= 1 and lambda be a limit ordinal. The following are
equivalent.
	i) lambda is a k-subtle cardinal;
	ii) every f:S_k+1(lambda) into S_k+1(lambda) has the same
restricted value at two distinct shift related arguments;
	iii) for all r >= 1, every f:S_k+1(lambda) into (S_k+1(lambda))^r
has the same restricted value at two distinct shift related arguments.

We are now ready to state the first independence result.

PROPOSITION 2.2. Let k,r,t >= 1 and w:FRF(<=_k,r) into [0,t]. There exists
a w-optimal function with the same restricted value at two distinct shift
related arguments.

THEOREM 2.3. Proposition 2.2 is provable in ZFC + "for all k there exists a
k-subtle cardinal" and not in ZFC + {there exists a k-subtle cardinal}_k.
Proposition 2.2 is provably equivalent, in ACA, to the 1-consistency of ZFC
+ {there exists a k-subtle cardinal}_k.

There is a uniformity in Proposition 2.2: there is a bound on the integers
appearing in the function that depends only on k,r,t and not on w. This
uniformity is reflected in the following obvious finite form:

PROPOSITION 2.4. Let n >> k,r,t >= 1 and w:RF(<=_k,r;n) into [0,t]. There
exists a w-optimal function in RF(<=_k,r;n) with the same restricted value
at two distinct shift related arguments.

Here ;n indicates that the domain is contained in S_k([0,n]).

THEOREM 2.5. Proposition 2.4 is provable in ZFC + "for all k there exists a
k-subtle cardinal" and not in ZFC + {there exists a k-subtle cardinal}_k.
Proposition 2.2 is provably equivalent, in ACA, to the 1-consistency of ZFC
+ {there exists a k-subtle cardinal}_k.

We conclude by stating the following sharper, but equivalent, forms of
Propositions 2.2 and 2.4.

PROPOSITION 2.6. Let k,r,t,p >= 1 and w:FRF(<=_k,r) into [0,t]. There
exists a w-optimal function with the same restricted value at all ke
element subsets of some p element set.

PROPOSITION 2.7. Let n >> k,r,t,p >= 1 and w:RF(<=_k,r;n) into [0,t]. There
exists a w-optimal function in RF(<=_k,r;n) with the same restricted value
at all k element subsets of some p element set.

3. Regressive functions on partial orderings.

Let (X,<=) be a partial ordering. Define RF(X,r) to be the set of all
functions f:A into X^r such that

	i) A is a finite subset of X;
	ii) for all x in A, each coordinate of f(x) is <= x.

Here RF stands for "full regressive functions."

THEOREM 3.1. Let f in RF(X,r). There is a least set E containedin dom(f)
such that for some t, f^t[E] = dom(f).

E is called the basis for f. This definition of basis agrees with the one
given in section 1 for elements of FRF(X,r). As in section 1, we define the
degree of f as the number of elements in its basis.

The component functions of f in RF(X,r) are the r functions f:X into X
given by f_i(x) = the i-th coordinate of f(x).

We now define the important subclass RF_m(X,r) of RF(X,r), m >= 1. Let
RF_m(X,r) be the set of all f in RF(X,r) such that the compositions of any
<=m component functions of f (repetitions allowed) at the basis elements
all exist and form the domain of f.

Let f in RF(X,r) and m >= 1. We say that g is a restriction of f if and
only if g containedin f. We say that g is a proper restriction of f if and
only if g is a restriction of f that is not f. We say that g is a
m-restriction of f if and only if g is a restriction of f that lies in
RF_m(X,r).

We say that g is an almost restriction of f if and only if every proper
restriction of g is a restriction of f. We say that g is an almost
m-restriction of f if and only if g is an almost restriction of f that is a
m-restriction of f.

THEOREM 3.2. Let f in RF(X,r). Every almost restriction of f of degree > 1
is a restriction of f. Every almost m-restriction of f of degree > 1 is a
m-restriction of f. These results do not hold for degree 1.

Now let m >= 1 and w:RF_m(X,r) into N. We can view w as a "weight
function," where w(f) is the "weight" of f. We say that f is w-optimal if
and only if

	i) f in RF(X,r);
	ii) the weight of every m-restriction of f is at most that of every
almost m-restriction of f with the same basis.

THEOREM 3.3. Let m >= 1, w:RF_m(X,r) into N, and A be a finite subset of X.
There is a w-optimal f in FRF(X,r) with domain A. Any restriction of any
w-optimal function is w-optimal.

4. Independence results:regressive functions.

We work in the spaces RF(<=_k,r) and RF_m(<=_k,r).

Let f in RF(<=_k,r) and x in dom(f). The restricted value of f at x is the
r-tuple obtained from f(x) by intersecting each coordinate of f(x) with
[0,min(x)).

We are now ready to state our first pi-0-1 independence result.

PROPOSITION 4.1. Let k,r,m,s,t >= 1 and w:RF_m(<=_k,r) into [0,t]. There
exists a w-optimal function in RF_s(<=_k,r) with the same restricted value
at two distinct shift related basis elements.

THEOREM 4.2. Proposition 4.1 is provable in ZFC + "for all k there exists a
k-subtle cardinal" and not in ZFC + {there exists a k-subtle cardinal}_k.
Proposition 4.1 is provably equivalent, in ACA, to the consistency of ZFC +
{there exists a k-subtle cardinal}_k.

There is a uniformity in Proposition 4.1: there is a bound on the integers
appearing in the function that depends only on k,r,m,s,t and not on w. This
uniformity is reflected in the following obvious finite form:

PROPOSITION 4.3. Let n >> k,r,m,s,t >= 1 and w:RF_m(<=_k,r;n) into [0,t].
There exists a w-optimal function in RF_s(<=_k,r;n) with the same
restricted value at two distinct shift related basis elements.

Here ;n indicates that the domain is contained in S_k([0,n]).

THEOREM 4.4. Proposition 2.4 is provable in ZFC + "for all k there exists a
k-subtle cardinal" and not in ZFC + {there exists a k-subtle cardinal}_k.
Proposition 2.2 is provably equivalent, in ACA, to the consistency of ZFC +
{there exists a k-subtle cardinal}_k.

We can give an estimate for the >> in Proposition 4.3. The estimate is
essentially the same as the usual estimates that appear in the classical
Ramsey theorem; i.e., iterated exponentials. Using this estimate,
Proposition 4.3 then appears in explicitly pi-0-1 form.

We conclude by stating the following sharper, but equivalent, forms of
Propositions 4.1 and 4.3. We can also give a similar estimate for the >>,
thereby obtaining additional explicitly pi-0-1 independence results.

PROPOSITION 4.5. Let k,r,m,s,t,p >= 1 and w:RF_m(<=_k,r) into [0,t]. There
exists a w-optimal function in RF_s(<=_k,r) with the same restricted value
at the k element subsets of some p element set, all of which lie in the
basis.

PROPOSITION 4.6. Let n >> k,r,m,s,t,p >= 1 and w:RF_m(<=_k,r;n) into [0,t].
There exists a w-optimal function in RF_s(<=_k,r;n) with the same
restricted value at the k element subsets of some p element set, all of
which lie in the basis.

REFERENCES

[1] H. Friedman, Finite Functions and the Necessary Use of Large Cardinals,
Annals of Mathematics, Vol. 148, no. 3, pp. 803--893.
[2] H. Friedman, Finite Trees and the Necessary Use of Large Cardinals,
http://www.math.ohio-state.edu/foundations/manuscripts.html
[3] H. Friedman, Subtle Cardinals and Linear Orderings,
http://www.math.ohio-state.edu/foundations/manuscripts.html