[FOM] 613: Optimal Function Theory 1

[Harvey Friedman]

THIS POSTING IS SELF CONTAINED
at least for the formal parts 1,2,3

There was a typo in the definition of step maximality in
http://www.cs.nyu.edu/pipermail/fom/2015-September/019080.html

I wrote:

DEFINITION 1.6. Let * be a bop in Q. A step maximal k-emulation of *
in Q is a bop ** in Q where each *|<=n, n in N, is a
maximal k-emulation of f in Q|<=n. A step maximal k-continuation of *
in Q is a  bop ** in Q where each **|<=n is a
step maximal continuation of * in Q|<=n.

Should be:

DEFINITION 1.6. Let * be a bop in Q. A step maximal k-emulation of *
in Q is a bop ** in Q where each *|<=n, n in N, is a
maximal k-emulation of * in Q|<=n. A step maximal k-continuation of *
in Q is a  bop ** in Q where each **|<=n, n in N, is a
step maximal continuation of * in Q|<=n.

Also in section 2 of
http://www.cs.nyu.edu/pipermail/fom/2015-September/019080.html where I
use the factorials, it does not pack enough punch to be independent as
claimed. Most conveniently, I should have used sums of bop products of
factorials as I do here in this section 2 below.

A. Taking Stock of where we are.
B. The New Era - Optimal Function Theory.
C. Where are we going?
1. Optimality of Functions.
2. Factorial Optimality of Binary Operations.
3. Templates.

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

A. TAKING STOCK OF WHERE WE ARE

Let's take stock of where we are. We have had for some time the
perfect implicitly Pi01 sentences

PROPOSITION. Every finite subset of Q^k|>k has a maximal continuation
in Q^k|>=0 with S[1,...,n]|>n = S[0,...,n-1]|>n.
PROPOSITION. Every finite subset of Q^k|>=0 has a maximal emulation in
Q^k|>=0 with S[1,...,n]|>n = S[0,...,n-1]|>n.

and variants, with step maximality in Q^k and towers in Q^k. Even
though these are implicitly Pi01, it does not look possible to get
explicitly Pi01 forms of these statements that meet the current high
standards. Thus the move to functions, particularly binary operations.

So with this move to everywhere defined functions with supports, the
punch lines for the implicitly Pi01 statements are substantially
better, with substantially better templates. For the new explicitly
PI01 statements, the preferred punch line stays the same - omitting
(8k)!!-1. But the notion of maximality - now "optimality" - is
substantially clearer.

B. THE NEW ERA - OPTIMAL FUNCTION THEORY

We now have substantial conceptual improvements and simplifications
since http://www.cs.nyu.edu/pipermail/fom/2015-September/019080.html
We seem to be approaching perfection for both the implicitly and
explicitly Pi01 forms.

For the implicitly Pi01 statements, we work in the spaces T(D,k) of
all functions F:D^k into D, D containedin Q. We define these five
basic notions on T(D,k).

i. F,G are r/isomorphic.
ii. G essentially extends F.
iii. F is r/optimal.
iv. F is step r/optimal.
v. F is locally r/optimal.

Here v implies iv implies iii. The part of F where the value is
nonzero is where the focus is. This is in direct analogy with the
practice in analysis of focusing attention on where a given function
is nonzero.

By an immediate application of Zorn's Lemma in this countable or
finite context (the axiom of choice being irrelevant), we obtain

every function is r/isomorphic to an r/optimal function.
every function is r/isomorphic to a step r/optimal function.
if D is finite, every function is r/isomorphic to a locally r/optimal function.

The implicitly Pi01 statements take the forms

every function is r/isomorphic to an r/optimal function obeying
certain simple shift equations and shift inequalities.
every function is r/isomorphic to a step r/optimal function obeying
certain simple shift equations and shift inequalities.

The explicitly Pi01 statements live in the T({0,...,n},,2), the space
of binary operations (bops) on {0,...,n}. We use these two notions,
instead of iii,iv,v above:

vi. f is factorially k/optimal.
vii. f is locally factorially k/optimal.

The explicitly Pi01 statements take the forms

every bop on {0,...,n!} is k/isomorphic to a factorially k/optimal
function omitting a certain integer.
every bop on {0,...,n} is k/isomorphic to a locally k/factorially
k/optimal function omitting a certain integer.

The equations and inequalities used for the implicitly Pi01 statements
is of course a finite set of ordinary equations in the k component
functions of the optimal function. This immediately suggests an
obvious Template. We should have a complete analysis of this Template,
using large cardinals, but not otherwise.

C. WHERE ARE WE GOING?

This has been a long run, with lots of fits and starts. It has been
spurred mainly by there having been raised a new standard of
perfection by that group of implicitly Pi01 Propositions referred to
in section A above - and not being able to give explicitly Pi01 forms
for them coming close to that level of perfection. I'm glad I took the
plunge. It has led, after a long tortuous road, to the New Era of
Optimal Functions. I have already found that a certain kind of
mathematician readily appreciates the function formulations, with its
optimality, which is really a maximality, far more than the set or
relation formulations, or any formulations involving maximal cliques.
I think that this may be connected with how analysts handle partial
functions in terms of total functions and their supports. And also
there is the famous "analytic continuations" studied in graduate
school.

Putting sociology in side, which is very much in favor of the New Era,
what remains is something OBJECTIVELY more flexible. Even though sets
are arguably more fundamental than functions (OK that is a real
issue...).

OBVIOUSLY, one principal matter than remains is for me to MAKE GOOD on
all of this. But I have chosen to go down this path with reasonably
high belief that all is well, because of the major advances that seem
to come at an unexpected pace here. I do have some private scratch
marks lying around.

Here are three important expected future developments. When progress
along these lines slows down to any kind of normal pace, I will start
MAKING GOOD on what I have.

i. Weaken the statements so that they correspond to levels from PA
through small large cardinals.
ii. Strengthen the statements so that they correspond to measurable
cardinals, and to the HUGE cardinal hierarchy. I already have this for
earlier incarnations of implicitly Pi01 sentences, and not yet
satisfactory for explicitly Pi01 - see
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
#87 But also not up to current perfection standards.
iii. Move into the kind of functions mathematicians grapple with daily.
iv. Move this into graphs, especially finite graph theory.
v. Unknown.

Since at the heart of much of what is going on that generates
independence from ZFC is of a finite combinatorial nature - witness
the explicitly Pi01 forms - I have little doubt that item iii is going
to get off the ground. With any luck at all, I should be able to
penetrate at least somewhat reasonably, subjects like Optimization and
Operations Research, etcetera.

Of course, iv can be done nicely - and the first versions will be
probably boring. But since finite graphs have so many applications to
science and engineering and computer science, this is well worth
pursuing, as I might be able to then directly attack stuff in and
around those applications.

Also v is is probably going to be quite fruitful.

1. OPTIMALITY OF FUNCTIONS

DEFINITION 1.1. Q is the set of all rationals. n,m,r,s,t,i,j denote
positive integers and p,q denote rationals unless otherwise indicated.
T(D,k) is the space of all F:D^k into D. Let F,G in T(D,k). G
essentially extends F if and only if F not= G, and for all x in D^k,
F(x) not= 0  implies F(x) = G(x). F|<=p in T(D,k), where (F|<=p)(x) =
F(x) if max(x) <= p; 0  otherwise.

DEFINITION 1.2. Let F,G in T(D,k). F,G are r/isomorphic if and only if
the following holds.
i. For all A containedin Q, |A| <=r, there exists an order preserving
bijection h:D into Q such that for all x in D^k and y in D, F(x) = y
not= 0 if and only if G(h(x)) = h(y) not= 0.
ii. For all D containedin Q, |D| <=r, there exists an order preserving
bijection h:D into Q such that for all x in D^k and y in D, G(x) = y
not= 0 if and only if F(h(x)) = h(y) not= 0.
Here h acts coordinstewise.

Recall our convention that n denotes a positive integer.

DEFINITION 1.3. Let F in T(Q,k). F is r/optimal if and only if F is
r/isomorphic to all of its essential extensions. F is step r/optimal
if and only if each F|<=n is r/optimal. F is locally r/optimal if and
only if each F|<=p, p > 0, is r/optimal.

THEOREM 1.1. Every F in T(Q,k) is r/isomorphic to some r/optimal G in T(Q,k).

THEOREM 1.2. Every F in T(Q,k) is r/isomorphic to some step r/optimal
G in T(Q,k).

THEOREM 1.3. The following is false. Every F in T(Q,2) is r/isomorphic
to some locally r/optimal G in T(Q,2).

PROPOSITION 1.4. Every F in T(Q,k) is r/isomorphic to some r/optimal G
in T(Q,k), where min(0,G(0,...,k-1)) = min(0,G(1,...,k)).

PROPOSITION 1.5. Every F in T(Q|<=k,k) is r/isomorphic to some
r/optimal G in T(Q|<=k,k), where min(0,G(0,...,k-1)) =
min(0,G(1,...,k)).

PROPOSITION 1.6. Every F in T(Q,k) is r/isomorphic to some step
r/optimal G in T(Q,k), where min(0,G(0,...,k-1)) = min(0,G(1,...,k)).

We can instead use an inequality.

PROPOSITION 1.7. Every F in T(Q,k) is r/isomorphic to some r/optimal G
in T(Q,k), where G(0,...,k-1,p) <= G(1,...,k,p), p < 0.

PROPOSITION 1.8. Every F in T(Q|<=k,k) is r/isomorphic to some
r/optimal G in T(Q|<=k,k), where G(0,...,k-1,p) <= G(1,...,k,p), p <
0.

PROPOSITION 1.9. Every F in T(Q,k) is r/isomorphic to some step
r/optimal G in T(Q,k), where G(0,...,k-1,p) <= G(1,...,k,p), p < 0.

It is clear that Propositions 1.4 - 1.9 are implicitly Pi01 via
Goedel's Completeness Theorem.

THEOREM 1.10. Propositions 1.5, 1.6, 1.8, 1.9 are provably equivalent
to Con(SRP) over WKL_0. Proposition 1.4 - 1.9 are provable in WKL_0 +
Con(SRP).

We know nothing further about the status of Propositions 1.4, 1.7.

2. FACTORIAL OPTIMALITY OF BINARY OPERATIONS

DEFINITION 2.1. The n-bops are the f in T({0,...,n},2). An n-bop f is
factorially k/optimal if and only if f is k/isomorphic to all of its
essential extensions where the new triples consist of <=k length sums
of <=k length f products of factorials <= n. f is locally factorially
k/optimal if and only if each f|<=i is factorially k/optimal. f omits
p if and only if f does not achieve the value p.

THEOREM 2.1. Every n-bop is k/isomorphic to a locally k/optimal bop.

PROPOSITION 2.2. Every n!-bop is k/isomorphic to a factorially
k/optimal bop omitting (8k)!!-1.

PROPOSITION 2.3. Every n-bop is k/isomorphic to a locally factorially
k/optimal bop omitting (8k)!!-1.

Note that Propositions 2.2, 2.3 are explicitly Pi01.

THEOREM 2.4. Propositions 2.2, 2.3  are provably equivalent to
Con(SMAH) over ACA.

Here SMAH is "strongly Mahlo cardinals".

3. TEMPLATES

The punch line in Propositions 1.4 - 1.6

min(0,G(0,...,k-1)) = min(0,G(1,...,k)).

is an equation involving min, k-ary G, and rational constants. There
is no nesting of G. This suggests the following Templates.

TEMPLATE 3.1. Let alpha be a finite set of unnested equations
involving min, max, a k-ary function G, and constants from Q.  Every F
in T(Q|<=k,k) is r/isomorphic to some r/optimal G in t(Q|<=k,k), where
alpha holds.

TEMPLATE 3.2. Let alpha be a finite set of equations involving min,
max, a k-ary function G, and constants from Q.  Every F in T(Q,k) is
r/isomorphic to some step r/optimal G in t(Q,k), where alpha holds.

Note that every instance of Template 3.1 is implicitly Pi01 via
Goedel's Completeness Theorem.

We already know that there are instances of Templates 3.1, 3.2 that are
provably equivalent to Con(SRP) over WKL_0.

CONJECTURE. Every instance of Template 3.1 is provable or refutable in
WKL_0 + Con(SRP).

I do not anticipate any substantial difficulties in proving this
Conjecture. It seems that allowing nesting of G's is also quite
manageable.

The punch line in Propositions 1.7 - 19

G(0,...,k-1,p) <= G(1,...,k,p), p < 0

is an inequality involving k-ary G, rational constants, and parameter
from Q|<0. This also gives rise to a series of ever more ambitious
Templates.

Most ambitious of all, directly along these lines, is the obvious
Template that uses any quantifier free sentence in G, <, rational
constants, and universally quantified parameters over Q (or Q|<=k),
allowing nesting of G's. We conjecture that every instance of this
Template is provable in WKL_0 + Con(SRP) or refutable in RCA_0.

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

Harvey Friedman