FOM: 28':Restatement

[Harvey Friedman]

This is a minor restatement of 28, in the 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

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 28. In section 3 of 28, we unintentionally used some
unexplained notation. This is corrected here. In addition, we now chose to
restate 28 so as to rely on the absolute minimal number of definitions (at
the cost of removing some explanatory material in the abstract).

OPTIMIZED FUNCTIONS AND THE NECESSARY USE OF LARGE CARDINALS
by
Harvey M. Friedman
January 28, 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." We rely on the usual
notions of restriction and proper restriction of functions. Note that a
restriction of a full regressive function may not be a full regressive
function.

The basis of f is the set of all arguments that are not a coordinate of the
value of f at any greater argument. Note that the basis of f is the least
set that generates the domain of f in the appropriate sense.

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

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 an optimizer for w if and only if

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

THEOREM 1.1. Let X be a partial ordering and r >= 1. Every w:FRF(X,r) into
N has an optimizer whose domain is any specified finite subset of X.

This is proved by the obvious (nondeterministic) greedy construction. In
fact, the optimizers for w are exactly the possible results of this obvious
greedy construction. One crucial fact is needed: that in the definition of
optimizer, one need only consider restrictions and almost restrictions f
whose basis has exactly one element. This is because every almost
restriction whose basis has more than one element is a restriction.

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)).

We are now ready to state the first independence result.

PROPOSITION 2.1. For all k,r,t,p >= 1, every w:FRF(<=_k,r) into [0,t] has
an optimizer with the same restricted value at all k element subsets of
some p element set.

THEOREM 2.2. Proposition 2.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 2.1 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.1: 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.3. For all n >> k,r,t,p >= 1, every w:FRF(<=_k,r;n) into
[0,t] has an optimizer with the same restricted value at all k element
subsets of some p element set.

Here ;n indicates that the domain is contained in S_k([0,n]), and
optimizers lie in FRF(<=_k,r;n). I.e., N is replaced by [0,n] throughout.

THEOREM 2.4. Proposition 2.3 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.3 is provably equivalent, in ACA, to the 1-consistency of ZFC
+ {there exists a k-subtle cardinal}_k.

We can be very specific about the conclusion of the independent
Proposition. Let x,y in S_k(N). We say that x,y are shift related if and
only if x\min(x) = y\max(y). E.g., {3,6,9} and {6,9,11} are shift related.

The following are equivalent to Propositions 2.1 and 2.3.

PROPOSITION 2.5. For all k,r,t >= 1, every w:FRF(<=_k,r) into [0,t] has an
optimizer with the same restricted value at two shift related arguments.

PROPOSITION 2.6. For all n >> k,r,t,p >= 1, every w:FRF(<=_k,r;n) into
[0,t] has an optimizer with the same restricted value at two shift related
arguments.

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 "regressive functions."

Let f in RF(X,r). The basis of f is the set of all arguments which are not
a coordinate of the value of f at a greater argument.

The component functions of f in RF(X,r) are the r functions f:dom(f) 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. The basis elements themselves are
considered to be compositions of 0 component functions at the basis
elements.

Let f in RF(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.

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 an optimizer
of w if and only if

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

THEOREM 3.1. Let X be a partial ordering and m,r >= 1. Every w:RF_m(X,r)
into N has an optimizer in FRF(X,r) whose domain is any specified finite
subset of X. For all s >= 1, every w:RF_m(X,r) into N has an optimizer in
RF_s(X,r) whose domain is a subset of any specified finite subset of X.

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.

For all k,r,t,p >= 1, every w:FRF(<=_k,r) into [0,t] has an optimizer with
the same restricted value at all k element subsets of some p element set.

PROPOSITION 4.1. For all k,r,m,s,t,p >= 1, every w:RF_m(<=_k,r) into [0,t]
has an optimizer in RF_s(<=_k,r) in which all k element subsets of some p
element set are basis elements with the same restricted value.

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,p and not on w. This
uniformity is reflected in the following obvious finite form:

PROPOSITION 4.3. For all n >> k,r,m,s,t,p >= 1, every w:RF_m(<=_k,r;n) into
[0,t] has an optimizer in RF_s(<=k,r;n) in which all k element subsets of
some p element set are basis elements with the same restricted value.

THEOREM 4.4. Proposition 4.3 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. For all k,r,m,s,t,p >= 1, every w:RF_m(<=_k,r) into [0,t]
has an optimizer in RF_s(<=_k,r) in which two shift related basis elements
have the same restricted value.

PROPOSITION 4.6. For all n >> k,r,m,s,t,p >= 1, every w:RF_m(<=_k,r;n) into
[0,t] has an optimizer in RF_s(<=k,r;n) in which two shift related basis
elements have the same restricted value.

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