[FOM] 625: Optimal Function Theory 4

Wed Sep 23 22:16:13 EDT 2015

THiS POSTiNG IS SELF CONTAINED
at least in section 3

It now looks like the move into optimal functions is quite sound. I
will continue with some further developments.

Let us review where we are. There are quite a number of developments
going back to the original "perfect" statement in maximal clique and
maximal roots.

IMPLICITLY Pi01

1. Maximal cliques in order invariant graphs, maximal roots in order
invariant relations, punch line S[1,...,n]|<0 = S[0,...,n-1]|<0, and
the variant S[1,...,n]|>n = S[0,...,n-1]|>n, depending on whether I am
using Q^k or Q^k|>=0. Here S[1,...,n] is the result of fixing the
first n arguments to be 1,...,n in S containedin Q^k. Of course, think
of n < k. Roots is better for those allergic to graphs. Here the
maximal objects are sets, and I use Q^k, Q^k|>=0 as the set of points.
If I use Q^k, I need step maximality to get independence from ZFC.
Ordinary maximality will be enuf if I use Q^k|>=0 and turn the set
equation around to S[1,...,n]|>n = S[0,...,n-1]|>n. This is because 0
serves as the endpoint that is needed in the reversals.

2. Maximal emulations and continuations. Here we avoid working with a
given order invariant graph or order invariant relation, and instead
use a "seed" which is to be emulated or (stronger) continued.
Otherwise, it is very much like 1, and is based on sets with the above
set equation.

3. I recently took up the use of functions and supports. The idea is
to replace the above set equations with the standard kind of simple
equation used throughout mathematics - even simpler. The use of
functions is entirely compatible with the emulation/continuation idea.
It also allows for some other new features. One is the use of
Universal Conditions, which will be introduced in this posting. The
other is the use of the space of Support Regressive functions, also
introduced in this posting. These bring the punch line down to simply

F(1,...,k) = F(2,...,k+1)

which is a rather simple equation by current mathematical standards.

EXPLICITLY Pi01

1. This was not competitive with the implicitly Pi01 UNTIL I moved to
functions. This deeply motivated my move to functions. In particular,
until I moved to binary functions, and exploited the naturalness of
looking at all k fold products from a finite set (and variants). Now
this explicitly Pi01 stuff threatens to be highly competitive. Here I
use binary operations on sets {0,...,n!}.

2. The huge advantage of the explicitly Pi01 statements - aside from
their actually being explicitly Pi01 - is the punch line. The punch
line is extremely simple, and simply states that (8k)!!-1 is not a
value of the "optimal" function. This is incomparably simpler than
previous punch lines - EXCEPT that in this posting we will see the
punch line F(1,...,k) = F(2,...,k+1). So we have a horse race.

3. Of course, the drawback of the explicitly Pi01 statements is in the
way optimality (maximality) is treated. We can't ask for the kind of
"universal" optimality (maximality) that we get in the implicitly Pi01
statements. Instead, we use what we call Factorial Optimality. This
requires merely that you cannot support extend using stuff built out
of the factorials. 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. If X is too big we get too strong a notion of
optimal (maximal). If X is too small, we get a provable statement. If
X is just right, we get large cardinals. Limited length sums of
factorials is just right. We can even fix X as a set of nonnegative
integers in advance before we start the statement. So we now have a
subject - for which X is the statement true? Presumably we get clear
necessary conditions, and also clear sufficient conditions. I don't
know about necessary and sufficient, although that may be in the
cards. IN ANY CASE, the sufficiency statements on X should be
equivalent to the consistency of large cardinals - SMAH in this case.
(strongly Mahlo cardinals of finite order).

1. SUPPORT REGRESSIVE FUNCTIONS

We now exploit some advantages in working with the spaces SR(E,k),
where E is a set of rationals. Here SR is read "support regressive".

Throughout this section, E denies a subset of Q.

DEFINITION 1.1. The support of F:E^k into E^k is the set of all x in
E^k such that F(x) is not the zero vector in E^k. SR(E,k) is the space
of all functions F:E^k into E^k such that for all x in the support of
F, min(x) > max(F(x)).

We will only be using E = Q and E = Q|<=k+1. The whole point of moving
to strictly regressive functions is to support (pun) the equation

F(1,...,k) = F(2,...,k+1).

2. EMULATIONS AND CONTINUATIONS

These are defined as in
http://www.cs.nyu.edu/pipermail/fom/2015-September/019174.html except
that now we are using range space E^k. Thus we need to use
inequalities involving the k coordinate functions in the obvious way.
Now the statements take the following forms:

PROPOSITION 2.1. Every f in SR(Q,k) (with finite support) has an
optimal emulation with g(1,...,k) = g(2,...,k+1).

PROPOSITION 2.2. Every f in SR(Q,k) with finite support all below 1
has an optimal continuation with g(1,...k) = g(2,...,k+1).

PROPOSITION 2.3. Every f in SR(Q,k)  (with finite support) has a step
optimal emulation with g(1,...,k) = g(2,...,k+1).

PROPOSITION 2.4. Every f in SR(Q,k) with finite support all below 1
has a step optimal continuation with g(1,...k) = g(2,...,k+1).

PROPOSITION 2.5. Every f in SR(Q|<=k+1,k) (with finite support)
has an optimal emulation with g(1,...,k) = g(2,...,k+1).

PROPOSITION 2.6. Every f in SR(Q|<=k+1,k) with finite support all below 1
has an optimal continuation with g(1,...k) = g(2,...,k+1).

Propositions 2.1 - 2.6 can be seen to be implicitly Pi01 via Goedel's
Completeness Theorem.

THEOREM 2.7. Propositions 2.3 - 2.6 are provably equivalent to
Con(SRP) over WKL_0. Propositions 2.1,2.2 are provable in WKL_0 +
Con(SRP). Here we use either form of Propositions 2.1, 2.3, 2.5.

Here SRP = ZFC + {there exists a cardinal with the k-stationary Ramsey
property}_k.

At this time, we don't know much about the status of Propositions 2.1, 2.2.

3. PURELY UNIVERSAL CONDITIONS

There is another approach that is especially natural from the point of
view of elementary model theory. Purely Universal Conditions is a
fundamental concept widely used in model theory.

The new twist here is that we take into account the support of
functions. Here E denotes a subset of Q. Again, we will be only using
E = Q or E = Q|<=k+1.

DEFINITION 3.1. The purely universal condition on SR(E,k) take the
form (for all x_1,...,x_m in E)(phi), where phi is a propositional
combination of inequalities in the function symbol F from k-tuples to
k-tuples. The inequalities take the form s < t, where s,t are
expressions involving the variables x_1,...,x_n and the k coordinate
functions of F.

Note that <=,>,>=,=,not= are not needed because of propositional combinations.

There is an important subfamily of the purely universal conditions
that is easier to work with.

DEFINITION 3.2. The unnested purely universal conditions on SR(E,k)
are the purely universal conditions on SR(E,k) in which there is no
nesting of (the coordinate functions of) F. We write UPUC for
"unnested purely universal condition".

It is well known that every purely universal condition is equivalent
to an unnested purely universal condition, in the usual elementary
model theory setup. However, we will be taking into account supports,
and it is simplest to work only with unnested purely universal
conditions.

DEFINTION 3.3. Let C be a UPUC on SR(E,k). f support realizes C if and
only if C holds for all x_1,...,x_m in E for which all of the
resulting arguments of f lie in the support of f.

DEFINTION 3.4. Let f,g in SR(E,k). g support extends f if and only if
f,g agree on the support of f and f not= g. Let C e a UPUC on SR(E,k).
f is a support optimal realization of C if and only if f support
realizes C and no support extension of f support realizes C. f is a
step support optimal realization of C if and only if each f|<=n is an
optimal support realization of C on SR(E|<=n,k).

THEOREM 3.1. Let 0 in E. Every UPUC on SR(E,k) has a support optimal
realization.

PROPOSITION 3.2. Every UPUC on SR(Q,k) has a support optimal
realization with f(1,...,k) = f(2,...,k+1).

PROPOSITION 3.3. Every UPUC on SR(Q,k) has a step support optimal
realization with f(1,...,k) = f(2,...,k+1).

PROPOSITION 3.4. Every UPUC on SR(Q|<=k+1,k) has a support optimal
realization with f(1,...,k) = f(2,...,k+1).

Propositions 3.2 - 3.4 can be seen to be implicitly Pi01 via Goedel's
Completeness Theorem.

THEOREM 3.5. Propositions 3.3, 3.4 are provably equivalent to
Con(SRP) over WKL_0. Proposition 3.2 is provable in WKL_0 +
Con(SRP).

Here SRP = ZFC + {there exists a cardinal with the k-stationary Ramsey
property}_k.

At this time, we don't know much about the status of Proposition 3.2

4. WHAT'S COMING NEXT?

I am looking at the possibility of using sets of inequalities instead
of universal conditions.

Also, I will be dealing with the Explicitly Pi01 statements. .

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

Harvey Friedman