[FOM] 626: Optimal Function Theory 5

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED

First a correction to my musings under Explicitly Pi01 paragraph 3 in
625: Optimal Function Theory 4. I wrote

"Recall that I used <= sums of <=k length binary
operation products of factorials. It is probably more natural to use
<=k length binary operation products of X, and then talk about what we
can take X to be."

It may be more natural, but it doesn't work - you don't get the
desired independence from ZFC.

Also, it is important to state optimality more carefully when we move
to functions. Optimality in the function context means that you cannot
support extend by a single argument/value. In the set case, not being
able to extend (proper containment) is equivalent to not being able to
extend by a single point. Not so for functions. This point was
overlooked in the Optimal Function Theory series so far.

########################################

We now enter a new era - CLIMBING and FALLING. Here is what is
happening. I will be more formal with more results in later postings.

T(Q,k) is the space of all f:Q[0,k]^k into Q[0,k]. A climb (as in Hill
Climbing in Computer Science) of f in T(Q,k) is a g in T(Q,k) obtained
from f by choosing some f(x) = 0 and then redefining f(x) so that 0 <
f(x) < min(x). A fall of f in T(Q,k) is a g in T(Q,k) obtained from f
by choosing some f(x) > 0 and then redefining f(x) to be 0.

Note that just as in Hill Climbing, climbs (and falls) only take place
at a single argument. Of course, we can consider multiple climbs and
multiple falls, where possibly infinitely many arguments are affected.

A locally optimal element of X containedin T(Q,k) is an element of X
none of whose climbs lie in X. An (globally) optimal element of X
containedin T(Q,k) is an element of X non of whose multiple climbs lie
in X.

It is easy to see that some nonempty X containedin T(Q,k) does not
have any locally optimal elements. However, there are always locally
optimal elements - even optimal elements - for a very important and
well known kind of X.

These are the purely universal subsets of T(Q,k), defined by a single
universal sentence involving a propositional combination of
inequalities (<) between terms (expressions) involving the unknown f
in T(Q,k) and variables, and using only the constant 0. There are only
finitely many such for any fixed k.

THEOREM 1. Every nonempty purely universal subset of T(Q,k) has an
optimal element. In particular, it has a locally optimal element.

There is a very reasonable hypothesis on purely universal subsets of
T(Q,k). Namely, GENEROSITY. X is generous if and only if every fall of
an element of X is an element of X.

In generous X, if you fall, then you are still competitive - i.e., you
remain in X, and might be able to climb within X.

PROPOSITION. Every purely universal generous subset of T(Q,k)  has a
locally optimal element which is shift invariant over {0,...,k}.

It is easy to see that this Proposition is implicitly Pi01 via
Goedel's Completeness Theorem. It is independent of ZFC.

THEOREM. The Proposition is provably equivalent to Con(SRP) over WKL_0.

Next posting we plan to reap another big benefit from CLIMBING. We
will restrict climbers to be using their available equipment - not
perhaps stardust from other galaxies. The idea is that this weakens
the notion of local optimality in order to have locally optimal
functions that are zero a.e. We are then led to explicitly Pi01
independence from ZFC.

**********************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 626th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html

600: Removing Deep Pathology 1  8/15/15  10:37PM
601: Finite Emulation Theory 1/perfect?  8/22/15  1:17AM
602: Removing Deep Pathology 2  8/23/15  6:35PM
603: Removing Deep Pathology 3  8/25/15  10:24AM
604: Finite Emulation Theory 2  8/26/15  2:54PM
605: Integer and Real Functions  8/27/15  1:50PM
606: Simple Theory of Types  8/29/15  6:30PM
607: Hindman's Theorem  8/30/15  3:58PM
608: Integer and Real Functions 2  9/1/15  6:40AM
609. Finite Continuation Theory 17  9/315  1:17PM
610: Function Continuation Theory 1  9/4/15  3:40PM
611: Function Emulation/Continuation Theory 2  9/8/15  12:58AM
612: Binary Operation Emulation and Continuation 1  9/7/15  4:35PM
613: Optimal Function Theory 1  9/13/15  11:30AM
614: Adventures in Formalization 1  9/14/15  1:43PM
615: Adventures in Formalization 2  9/14/15  1:44PM
616: Adventures in Formalization 3  9/14/15  1:45PM
617: Removing Connectives 1  9/115/15  7:47AM
618: Adventures in Formalization 4  9/15/15  3:07PM
619: Nonstandardism 1  9/17/15  9:57AM
620: Nonstandardism 2  9/18/15  2:12AM
621: Adventures in Formalization  5  9/18/15  12:54PM
622: Adventures in Formalization 6  9/29/15  3:33AM
623: Optimal Function Theory 2  9/22/15  12:02AM
624: Optimal Function Theory 3  9/22/15  11:18AM
625: Optimal Function Theory 4  9/23/15  10:16PM

Harvey Friedman