FOM: 26:Optimized Functions/Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
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
More information about the FOM
mailing list