[FOM] 627: Optimal Function Theory 6

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED

We now polish up the new era stuff, which we call ORDER THEORETIC
OPTIMIZATION.

The particular kind of optimization that we consider has the following
structure.

i. We work exclusively in the spaces T(Q,k) of all f:Q^k into Q.
ii. We use a few specific relations on T(Q,k) called "upgrading" and variants.

We will see that some hypothesis is need in order to guarantee that a
nonempty X containedin T(Q,k) has an optimal element - i.e., an
element of X none of whose "upgrades" is an element of X The obvious
hypothesis for this is Universal Definability. UD is the same notion
(for sets of f:Q^k into Q) that is used in, e.g.,
https://en.wikipedia.org/wiki/Łoś–Tarski_preservation_theorem (see the
definition there of upside down A sub 1).

Under this hypothesis, we can do much more: Every such X has an
optimal element that is shift invariant over a tail of integers.

In order to prove the above claim, we must go well beyond the usual
ZFC axioms for mathematics.

In this posting, we make a quick direct path to the incompleteness
results. In later postings, we will offer some more background
information and other interesting results, only some of which lead to
incompleteness.

1. IMPROVEMENTS IN T(Q,k)

DEFINITION 1.1. Q,Z+,N are the set of all rationals, positive
integers, and nonnegative integers, respectively. We use
p,q,x,y,z,w,u,v for rationals, and a,b,c,d,e,k,n,m,r,s,t for positive
integers unless indicated otherwise. T(Q,k) is the set of all f:Q^k into Q.

Below, f,g,h always represent elements of T(Q,k).

DEFINITION 1.2. g is an improvement of f if and only if g:Q^k into Q
is obtained from f by choosing f(x) <= 0 and changing f(x) so that 0 <
f(x) < min(x).

We also work with three important variants. There are other important
variants as well, but to simplify the discussion, we focus on just
three more.

DEFINITION 1.3. g is a multiple improvement of f if and only if g:Q^k
into Q is obtained from f by choosing one or more f(x) <= 0 and
changing each of these f(x) so that 0 < f(x) < min(x).

Here and henceforth, "one or more" and "zero or more" always allows
for "infinitely many".

DEFINITION 1.4. y in Q^k is markedly higher than x in Q^k if and only
if there is a positive integer n with max(x) <= n < max(y).

DEFINITION 1.5.  g is a flexible improvement of f if and only if g is
obtained from f by choosing f(x) <= 0, changing f(x) so that 0 < f(x)
< min(x), and then zeroing out the y's markedly higher than x.

The idea is that the y's that are so zeroed out can later be
(possibly) given a positive value under f. If f(y) is positive and we
aren't allowed to zero out y, then f(y) would have to remain
unchanged. Hence the name "flexible".

DEFINITION 1.6.  g is a multiple flexible improvement of f if and only
if g is obtained from f by choosing one or more f(x) <= 0, changing
each of these f(x) so that 0 < f(x) < min(x), and then zeroing out
those y's that are markedly higher than all of these x's.

DEFINITION 1.7. Let X containedin T(Q,k). f is a non improvable, non
multiply improvable, non flexibly improvable, non multiply flexibly
improvable element of X if and only if f in X and f has no
improvement, no multiple improvement, no flexible improvement, no
multiply flexible improvement in X, respectively.

THEOREM 1.1. There exists a nonempty X containedin T(Q,k) in which
every element is both improvable and flexibly improvable to an
element. For example, let X = {f: there are infinitely many x with
f(x) <= 0, min(x) > 0, and max(x) < 1}.

We want to ensure that there are non improvable elements, and even
that there are non multiply flexibly improvable elements. For this
purpose, we now put a very well known niceness condition on X.

DEFINITION 1.7. X is a UD (universally defined) subset of T(Q,k) if
and only if X can be defined as the set of all f:Q^k into Q such that
(for all x_1,...,x_m in Q)(phi), where phi is a propositional
combination of inequalities s < t, with s,t terms (expressions) in f,
variables x_1,...,x_m, and constants from Q. Propositional
combinations use the five connectives not, and, or, implies, iff.

THEOREM 1.2. Every nonempty UD subset of T(Q,k) has a non multiply
flexibly improvable element. This is provable in Pi-1-1-CA, but not in
Pi-1-1-CA0.

2. SHIFT INVARIANT OPTIMALITY

We are interested in improving (pun) Theorem 1.2 in the direction of
finding an optimal element that is shift invariant. We need to stick
to improvements and flexible improvements.

DEFINITION 2.1. f:Q^k into Q is shift invariant over E containedin Q
if and only if for all x in E^k, f(x) = f(x+1).

PROPOSITION 2.1. Every UD subset of T(Q,k) has a non improvable
element that is shift invariant over a tail of integers.

PROPOSITION 2.2. Every UD subset of T(Q,k) has a non flexibly
improvable element that is shift invariant over a tail of integers.

It can be seen that Propositions 2.1, 2.2 are implicitly Pi01 via
Goedel's Completeness Theorem.

THEOREM 2.3. Proposition 2.2 is provably equivalent to Con(SRP) over
WKL_0. Proposition 2.1 is provable in WKL_0 + Con(SRP).

We don't know much about where Proposition 2.1 is provable.

THEOREM 2.4. The infinite set of statements obtained by fixing k =
1,2,... in Proposition 2.2 is provably equivalent to the set of
statements {Con(SRP[n]}, over WKL_0.

THEOREM 2.5. Proposition 2.1 for k = 8 is not provable in ZFC
(assuming ZFC is consistent).

We have a target of k = 4 for Theorem 2.5.

**********************************************************
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 627th 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
626: Optimal Function Theory 5  9/2515  10:26PM

Harvey Friedman