[FOM] 628: Optimal Function Theory 7

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED
new era seems to be moving along

This posting and possibly one or two more should be the last postings
before I prepare a serious sketch of key proofs (reversals). I am at a
point where significant further progress depends on layers being error
free, and in highly efficient and flexible form. The stack of layers
has now reached a critical mass.

I have a lot of backup tools to deal with any difficulties that might
arise as I bury myself in details. So if the need arises, there will
be altered formulations which should be of comparable interest. It is
likely that i will emerge unscathed, but this is not certain.

Here I also include the latest Explicitly Pi01 statements. Note that I
have returned to the spaces of binary operations on {0,...,n!} for
this purpose, but incorporating the new maximal element (Order
Theoretic Optimization) approach.

MINOR NOTE. In http://www.cs.nyu.edu/pipermail/fom/2015-September/019202.html
I said that

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

This remark should only apply to Proposition 2.2.

Also in http://www.cs.nyu.edu/pipermail/fom/2015-September/019202.html
I forgot to put in a "nonempty" hypothesis for the UD sets. The
appropriate hypothesis is "includes the zero function", as we use
below.

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

ORDER THEORETIC OPTIMIZATION
by
Harvey M. Friedman
October 2, 2015

ABSTRACT. We define the extremely simple binary relation <* on the
f:Q^k into Q^k, and the very simple binary relation <** on f:Q^k into
Q^k.

We first show that every Purely Universally Defined set of f:Q^k into Q^k
containing the zero function has a <* maximal element and a <**
maximal element.

We then show that every Purely Universally Defined set of f:Q^k into
Q^k containing the zero function has a <* maximal element which is
shift invariant over the positive integers. We also show that every
Purely Universally Defined set of f:Q^k into Q^k containing the zero
function has a <** maximal element which is shift invariant over the
positive integers.

The only proofs that we have for the two claims in the previous
paragraph go well
beyond the usual axioms of ZFC. In the case of <**, ZFC does not
suffice (assuming ZFC is consistent).

The notion of Purely Universally Defined sets of f:Q^k into Q^k is a
completely standard notion from elementary model theory, readily
familiar to theoretical computer scientists and
mathematically oriented philosophers, as well as most researchers in
real algebraic/analytic geometry and many parts of algebra and
combinatorics.

Rather restricted subfamilies of the Purely Universally Defined sets
of f:Q^k into Q^k are sufficient to drive the independence from ZFC.
We are researching this now.

We also use an appropriate binary relation <# relating the binary
operations on {0,...,n!}. Here the allowed reassignments are of zeros
built from 1!,...,n!.

1. T(Q,k), PUD

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) i s the space of all f:Q^k into Q^k.

DEFINITION 1.2. 0* is the 0 vector in Q^k. Let x,y in Q^k. min(x),
max(x) are the smallest and largest coordinates of x, respectively. y
is markedly higher than x if and only if there exists n such that
max(x) <= n < max(y).

The idea behind "markedly higher" is that y has past a threshold that
x has not. The relevant thresholds are given by the positive integers.

DEFINITION 1.3.  f <* g if and only if f,g in T(Q,k), and g is
obtained by changing some f(x) = 0* so that 0 < min(f(x)) <= max(f(x))
< min(x). f <** g if and only if f,g in T(Q,k), and g is obtained by
changing some f(x) = 0* so that 0 < min(f(x)) <= max(f(x)) < min(x),
and  zeroing out all y markedly higher than x.

We think of <* as an obvious notion of "upgrade", lifting the value at
the chosen zero into wholly positive territory, still wholly below the
zero. In the case of <** there is the upgrade component that mimics
<*, but there is an information loss component that zeroes out
markedly higher tuples. We can think of this second component as
"wiping the slate clean markedly higher up" thereby providing the
opportunity to "later" upgrade the f(y), y markedly higher than x.

We focus only on the following two very well known kinds of subsets of T(Q,k).

DEFINITION 1.4. X is a PUD (purely 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^k 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 the k coordinate functions of f, and the variables
x_1,...,x_m. Propositional combinations use the five connectives not,
and, or, implies, iff. No constants are allowed in phi. If constants
from Q are allowed in phi, then we write UD (universally defined)
instead of PUD.

THEOREM 1.1. Every UD subset of T(Q,k) has a <* maximal element and a
<** maximal element.

2. SHIFT INVARIANCE

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

PROPOSITION 2.1. Every PUD subset of T(Q,k) containing the zero
function has a <* maximal element which is shift invariant over the
positive integers.

PROPOSITION 2.2. Every UD subset of T(Q,k) containing the zero
function has a <* maximal element which is shift invariant over a tail
of positive integers.

PROPOSITION 2.3. Every PUD subset of T(Q,k) containing the zero
function has a <** maximal element which is shift invariant over the
positive integers.

PROPOSITION 2.4. Every UD subset of T(Q,k) containing the zero
function has a <** maximal element which is shift invariant over a
tail of positive integers.

It can be easily seen that Propositions 2.3,2.4 are implicitly Pi01
via Goedel's Completeness Theorem.

THEOREM 2.5. Propositions 2.3, 2.4 are provably equivalent to Con(SRP)
over WKL_0. Propositions 2.1. 2.2 are provable in WKL_0 + Con(SRP).

We don't know if Propositions 2.1, 2.2 are provable in ZFC.

SRP is the stationary Ramsey property hierarchy of large cardinals,
otherwise known as the subtle or ineffable cardinal hierarchy.

3, EXPLICIT UPGRADES

After some reconsideration, we have decided to return to working in
finite spaces for the explicitly Pi01 statements.

>From the recursion theoretic point of view, Propositions 2.1 - 2.4 are
already explicitly arithmetical after we simply assert that the
maximal element (function) is delta-0-2. However, here we are
interested in explicit Pi01 from the standard mathematical point of
view.

DEFINITION 3.1. W(n) is the space of f:{0,...,n!}^2 into {0,...,n!}.

DEFINITION 3.2. Let f,g:{0,...,n!}^2 into {0,...,n!}. f <' g if and
only if g is obtained from f by changing some f(x,y) = 0 to f(x,y) >
0, and zeroing out the (z,w) with max(z,w) > max(x,y).

Thus <' is essentially the same as <** except that the zeroing out is
more aggressive.

THEOREM 3.1. Every subset of W(n) containing the zero function has a
<' maximal element.

However, we have no control over <' maximal elements. Towards
obtaining some control, we need to look at "nice" subsets of W(n) and
also strengthen <'.

DEFINITION 3.3. X is a k-PUD subset of W(n) if and only if X is
defined as in the definition of PUD (this time with one dimensional
ranges), but where the total number of occurrences of the operation is
at most k.

DEFINITION 3.4. Let f,g:{0,...,n!}^2 into {0,...,n!}. f <# g if and
only if g is obtained from f by changing some f(x,y) = 0 to f(x,y) >
0, where x,y are expressions in f,+1, and 1!,2!,...,n!, where the
total number of occurrences of the two operations is at most k,and
zeroing out the (z,w) with max(z,w) > max(x,y).

PROPOSITION 3.2. Every k-PUD subset of W(n) containing the zero
function has a <# maximal element without the value (8k)!!-1.

Obviously Proposition 3.2 is explicitly Pi01.

THEOREM 3.3. Proposition 3.2 is provably equivalent to Con(SMAH) over ACA.

SMAH is the strongly Mahlo large cardinal hierarchy of finite orders.

**********************************************************
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 628th 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

Harvey Friedman