[FOM] 631: Order Theoretic Optimization 1

[Harvey Friedman]

THIS IS AN INTERIM REPORT - StTILL CHECKING.

Yes, I found a bug in the reversal. Yes, I have already recovered
nicely. In fact, the new versions are better than the old ones with
bugs.

Also there are important advances in the Explicitly Pi01.

NOTE: I have retitled this series to be somewhat more specific about
the nature of these statements. This is not any kind of shift (no pun
intended) of focus.

***************************

a. I work with the spaces T(Q,k,n) of functions f:Q[0,n]^k into Q[0,n].

b. The notion of UPGRADE is now EVEN SIMPLER than before. g upgrades f
if and only if g changes some f(x) = 0 to f(x) not= 0.

c. I use PUD sets (purely universal defined) as before. There is also
an equivalent form in terms of constraints - see the title of this
posting.

d. SHIFT INVARIANCE has to be changed to LOWER SHIFT INVARIANCE. This
is the same as invariance under +1 provided the value is entirely
lower than the argument.

e. I am now looking at a new kind of explicitly Pi01 statement where
the only change from the implicitly Pi01 statements is to use
subspaces of T(Q,k,n). Even finite subspaces of T(Q,k,n). In this
posting, I only talk of the new implicitly Pi01 sentences, with plans
to talk about the explicitly Pi01 sentences later. There are also ones
with the earlier approach where I omit (8k)!!-1.

1. PUD, CONSTRAINTS

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. Q[0,n] = Q intersect [0,n].

DEFINITION 1.2. T(Q,k,n) is the set of all f:Q[0,n]^k into Q[0,n].

The following is a completely standard notion from elementary model
theory, which is also familiar to many in combinatorics, algebra, real
algebraic/analytic geometry, and computer science.

DEFINITION 1.2. X is a PUD (purely universally defined) subset of
T(Q,k,n) if and only if X ca be defined as the set of all f in
T(Q,k,n) such that (for all x_1,...,x_m in Q[0,n])(phi), where phi is
a propositional combination of inequalities z < w,  f(z_1,...,z_k)
<(<=) w, with z_1,...,z_k,z,w among x_1,...,x_m. No constants are
allowed.

PUD is very robust, and does not change if we allow additional logical
connectives or,implies,iff, additional comparisons =,>=,>,not=, and
arbitrary nesting of f on both sides of the inequalities. PUD is a
widely used concept from elementary model theory which is also
familiar to many algebraists, combinatorists, and computer scientists.

There is another way to look at PUD. This is in terms of constraints.

DEFINITION 1.3. A constraint on T(Q,k.n) is a statement of the form
not(s_1 <(<=) t_1 and ... and s_p <(<=) t_p), where each conjunct is a
term in f in T(Q,k,n) and variables, in which at most one occurrence
of f appears. No constants are allowed.

Once again, there is a lot of robustness here. Nothing changes if we
also allow =,>=,>,not=, and arbitrary nesting of f on both sides of
the inequalities.

THEOREM 1.2. The PUD subsets of T(Q,k,n) and the solutions to finite
sets of constraints on T(Q,k,n) are the same.

2. UPGRADES, OPTIMALITY

DEFINITION 2.1. Let f in T(Q,k,n). g is an upgrade of f if and only if
g in T(Q,k,n) is obtained from f by changing exactly one zero of f to
a nonzero of f.

DEFINITION 2.2. Let X containedin T(Q,k,n). An optimal element of X is
an element of X none of whose upgrades lie in X. Let E be a finite set
of constraints on T(Q,k,n). A solution to E is an f in T(Q,k,n)
obeying all of the constraints in E. f is an optimal solution to E if
and only if f is a solution to E none of whose upgrades are a solution
to E.

THEOREM 2.1. Every nonempty PUD subset of T(Q,k,n) has an optimal
element. Every solvable set of constraints on T(Q,k,n) has an optimal
solution.

DEFINITION 2.3. Let f in T(Q,k,n). f is lower shift invariant over
p_1,...,p_t in Q[0,n] if and only if for all x in {p_1,...,p_t}^k,
f(x) < min(x) implies f(x) = f(x+1). f is <1 shift invariant over
p_1,...,p_t in Q[0,n] if and only if for all x in {p_1,...,p_t}^k,
f(x) < 1 implies f(x) = f(x+1). Here x+1 is the result of adding 1 to
all coordinates of x.

PROPOSITION 2.2. Every PUD subset of T(Q,k,n) containing the zero
function has an optimal element lower (<1) shift invariant over
1,...,n-1.

PROPOSITION 2.3. Every finite set of constraints on T(Q,k) solved by
the zero function has an optimal solution lower (<1) shift invariant
over 1,...,n-1.

Here Propositions 2.2 and 2.3 have two forms according to the choice
of "lower" and "<1". By Theorem 1.2, Propositions 2.2 and 2.3 are
equivalent.

Note that Propositions 2.2 and 2.3 are implicitly Pi01 via Goedel's
Completeness Theorem.

THEOREM 2.4. Propositions 2.2 and 2.3 (both forms of each) are
provably equivalent to Con(SRP) over WKL_0. This holds even if we
require that the solution or element be delta-0-2 in the sense of
recursion theory. There is a small fixed k such that Propositions 2.2
and 2.3 are independent of ZFC (assuming Con(SRP)).

SRP is the stationary Ramsey property hierarchy of large cardinals,
which is the same as the subtle and the ineffable large cardinal
hierarchy.

3. MULTIPLE UPGRADES

DEFINITION 3.1. Let f in T(Q,k,n) and 1 <= alpha <= infinity. g is an
upgrade[alpha] of f if and only if g in T(Q,k,n) is obtained from f by
changing exactly alpha zeros of f to alpha nonzeros of f. g is an
upgrade[<alpha] of f if and only if there exists 1 <= i < alpha such
that g is an upgrade[alpha] of f. g is an upgrade[<=alpha] of f if and
only if there exists 1 <= i <= alpha such that g is an upgrade[alpha]
of f.

DEFINITION 3.2. Optimal[alpha], optimal[<alpha], optimal[<=alpha]
elements of sets and solutions of sets of constraints are defined in
the obvious way using upgrade[alpha], upgrade[<alpha],
upgrade[<=alpha]].

THEOREM 3.1. Every nonempty PUD subset of T(Q,k,n) has an
optimal[<=infinity] element. Every solvable set of constraints on
T(Q,k,n) has an optimal[<=infinity] solution.

PROPOSITION 3.2. Every PUD subset of (finite set of constraints on)
T(Q,k,n) containing (solved by) the zero function has an
optimal[<infinity,<r,r] element (solution) lower (<1) shift invariant
over 1,...,n-1.

Note that there are 12 forms of Proposition 3.2 obtained by picking
one from each of (set of, finite set of constraints on), (<inifnity,
<r, r), and (lower, <1).

Note that all 12 forms of Proposition 3.2 are implicitly Pi01 via
Goedel's Completeness theorem.

THEOREM 3.3. All 12 forms of Proposition 3.2 are provably equivalent
to Con(SRP) over WKL_0. This holds even if we require that the
solution or element be delta-0-2 in the sense of recursion theory.
There is a small fixed k such that all eight are independent of ZFC
(assuming Con(SRP)). These results hold if r is fixed to be any given
positive integer.

4. MULTIPLE FUNCTIONS

There are some advantages in addition to the extra generality, of
using finitely many functions rather than a single function.

DEFINITION 4.1. T(Q,k_1,...,k_s,n) is the space T(Q,k_1,n) x ... x
T(Q,k_s,n). PUD subsets of T(Q,k_1,...,k_s,n) and finite sets of
constraints on T(Q,k_1,...,k_s,n) are defined in the obvious way.

DEFINITION 4.2 .Let  f in T(Q,k,n). f is regressive if and only if for
all x in Q[0,n]^k, f(x) < min(x). f is <1 if and only if for all x in
Q[0,n]^k, f(x) < `1.

PROPOSITION 4.1. Every PUD subset of T(Q,k_1,...,k_s,n) containing the
zero system has an optimal element whose regressive (<1) components
are shift invariant over 1,...,n-1.

PROPOSITION 4.2. Every finite set of constraints on T(Q,k_1,...,k_s,n)
solved by the zero system has an optimal solution whose regressive
(<1) components are shift invariant over 1,...,n-1.

PROPOSITION 4.3. Every PUD subset of (finite set of constraints on)
T(Q,k_1,...,k_s,n) containing (solved by) the zero system has an
optimal[<infinity,<r,r] element (solution) whose regressive (<1)
components are shift invariant over 1,...,n-1.

Exactly the same results hold from sections 2,3 above.

**********************************************************
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 631st 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
627: Optimal Function Theory 6  9/29/15  2:21AM
628: Optimal Function Theory 7  10/2/15  6:23PM
629: Boolean Algebra/Simplicity  10/3/15  9:41AM
630: Optimal Function Theory 8  10/3/15  6PM

Harvey Friedman