FOM: 26:Optimized Functions/Large Cardinals

Wed Jan 13 06:53:58 EST 1999

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

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

OPTIMIZED FUNCTIONS AND THE NECESSARY USE OF LARGE CARDINALS
by
Harvey M. Friedman
January 10, 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. Functions on partial orderings.

Let (X,<=) be a partial ordering. Define RF(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 RF stands for "regressive function."

Let f in RF(X,r). We say that g is a restriction of f if and only if g in
RF(X,r) and 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 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 restriction of f such that B
containedin dom(g).

PROPOSITION 1.1. Let f in RF(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 restriction of f if and only if g in RF(X,r) and every
restriction of g is a restriction of f. We say that g is an almost
restriction of f if and only if g in RF(X,r) and every proper restriction
of g is a restriction of f.

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

Now let w:RF(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 restriction of f is at most that of every
almost restriction of f with the same basis.

PROPOSITION 1.3. Let w:RF(X,r) into N and A be a finite subset of X. There
is a w-optimal f in RF(X,r) with domain A.

This is proved by the obvious greedy construction.

2. Independence results.

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 RF(<=_k,r).

Let f in RF(<=_k,r) and x in dom(f). The restricted value of f at x is
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:RF(<=_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.

NOTE: It appears that the results are the same even if we take t = 1. Also,
we are looking at this kind of optimization in the context of other kinds
of structures (other than these functions). It looks like this kind of
optimization is a rich theme.

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