[FOM] 541: Master Templates

Tue Sep 9 12:41:39 EDT 2014

*This research was partially supported by the John Templeton
Foundation grant ID #36297. The opinions expressed here are those of
the author and do not necessarily reflect the views of the John
Templeton Foundation.

I have now realized that there is a critical Master Template under
which I can interpret all of the perfect mathematically natural
implicitly Pi01 statements corresponding to Con(SRP) as natural
partial results concerning that Template. There are two important
variants of this Master Template for partial functions and regressive
partial functions that are important for the theory.

This is a perfect mathematical story. BUT, bear in mind that I am NOT
claiming or conjecturing that these Master Templates can be completely
analyzed. These Master Templates may be algorithmically unsolvable,
although I have not thought about this. In fact, I have not thought
about any algorithmic unsolvability issues whatsoever in this Pi01
project. Perhaps I should start, in order to see where the boundaries
are.

HOWEVER, for each of the Master Templates, we have a partial result
(proposition) that provides a sufficient condition for the Template to
hold - where the proposition is provably equivalent to Con(SRP) over
WKL0. In particular, provable from large cardinals but not in ZFC
(assuming ZFC is consistent).

These Propositions suggest further derived templates, some of which we
know how to completely analyze - but of course where the complete
analysis can only be carried out using large cardinals and not in ZFC
(assuming ZFC is consistent).

All of these templates are primarily formulated using "universal
properties of S contained in Q[0,1]^k, of partial f:Q[0,1]^k into
Q[[0,1]^r, of regressive partial f:Q[0,1]^k into Q[0,1]^r". The Master
Template for sets incorporates the other two Master Templates.
However, the other two Master Templates are very important for the
theory as they lend themselves to arguably simpler partial results
(propositions), which in turn suggest simpler derived templates that
we know how to completely analyze.

We begin with a presentation of the three Master Templates. Q[0,1] = Q
intersect [0,1], where Q is the set of all rationals. Maximal is
maximal under inclusion.

MASTER TEMPLATE (sets). Let k >= 1 and A,B be universal properties of
S contained in Q[0,1]^k, using < and constants. There is a maximal
solution to A, which is a solution to B.

MASTER TEMPLATE (functions). Let k,r >= 1 and A,B be universal
properties of partial f:Q[0,1]^k into Q[0,1]^r, using < and constants.
There is a maximal solution to A, which is a solution to B.

MASTER TEMPLATE (regressive). Let k,r >= 1 and A,B be universal
properties of regressive partial f:Q[0,1]^k into Q[0,1]^r, using < and
constants. There is a maximal solution to A, which is a solution to B.

There are some special kinds of universal properties. These are the
squares, roots, and cliques in the order theoretic subsets of
Q[0,1]^2k, subsets of Q[0,1]^k, and graphs on Q[0,1]^k, respectively.
Thus, being a square, root, or clique in such sets and graphs is in
fact a universal property of S contained in Q[0,1]^2k, S contained in
Q[0,1]^k, S contained in Q[0,1]^k, respectively. Many of our
propositions remain independent of ZFC even when specialized to
squares, roots, and cliques. There are advantages and disadvantages in
using the more general universal properties instead of our original
squares, roots, and cliques.

The official definition of universal property of S contained in
Q[0,1]^k is that it is a property of the form

(forall p_1,...,p_t in Q[0,1])(phi(S,p_1,...,p_t))

where phi(S,p_1,...,p_t) is a statement using not, and, or, alpha_1 <
alpha_2, (alpha_1,...,alpha_k) in S, where the alpha's are among the
distinct variables p_1,...,p_t and constants from Q[0,1].

For mathematicians, it is easy to give plenty of examples of universal
properties, and examples of properties that are not universal. Already
this is interesting with S contained in Q[0,1]^k. Some examples are a
bit tricky and somewhat interesting. Let j >= 0. "S has at most j
elements". "S is an interval in Q[0,1], which is allowed to be empty,
a singleton, or have endpoints not in Q[0,1]". "S is the union of <= j
pairwise disjoint nonempty intervals, which are allowed to be
singletons or have endpoints not in Q[0,1]". These can be seen to be
universal properties of S contained in Q[0,1], even without constants.
Also "S includes any given finite union of intervals in Q[0,1] with
endpoints from Q[0,1]" is a universal property of S contained in
Q[0,1] with constants (the endpoints of the given intervals). There
are interesting abstract characterizations of the solution sets to
universal properties of S contained in Q[0,1], and more generally of S
contained in Q[0,1]^k.

For partial f:Q[0,1]^k into Q[0,1]^r, we have to be a bit careful
about what purely universal means. The simplest way is to simply treat
such f as certain S contained in Q[0,1]^k+r. Conveniently, being a
partial f:Q[0,1]^k into Q[0,1]^r and being a regressive partial
f:Q[0,1]^k into Q[0,1]^r are universal properties of S contained in
Q[0,1]^k+r. (Regressive is defined below).

But we still would like to give a form for the partial function case
as we have done for the set case. The idea is very simple - we use a
definedness condition. Thus the universal properties of partial
f:Q[0,1]^k into Q[0,1]^r take the form

(forall p_1,...,p_t in Q[0,1])(if every application of f in
psi(f,p_1,...,p_t) is defined, then psi(f,p_1,...,p_t) holds)

where phi(S,p_1,...,p_t) is a statement using not, and, or, alpha <
beta, f(alpha_1,...,alpha_k) < beta, beta < f(alpha_1,...,alpha_k),
f(alpha_1,...,alpha_k) < f(beta_1,...,beta_k), where the alpha's and
beta's are among the distinct variables p_1,...,p_t and constants from
Q[0,1].

We say that partial f:Q[0,1]^k into Q[0,1]^r is regressive if and only
if for all x in dom(f), min(x) > max(f(x)). I.e., values always lie
strictly below arguments. Universal properties of regressive partial
f:Q[0,1]^k into Q[0,1]^r are as above.

Every instance of these Master Templates is very concrete.

THEOREM 1. Every instance of the Master Templates is implicitly Pi01
in the following standard sense. For each instance, we can effectively
associate an algorithm such that the instance holds if and only if the
algorithm continues forever at the empty tape. Furthermore, the
previous sentence can be proved in WKL0, with the forward direction in
RCA0. The effective association is extremely computer efficient.

We are far from having a complete understanding of the Master
Templates. However, we do have partial results. The following featured
partial results (proposition) assert that for a certain natural kind
of A,B, the Master Template holds.

PROPOSITION 2. Every universal property of S contained in Q[0,1]^k has
a maximal solution S such that for all p < 1/k, (1/2,...,1/k,p) in S
iff (1,1/2,...,1/(k-1),p). in S.

PROPOSITION 3. Every universal property of partial f:Q[0,1]^k into
Q[0,1]^r has a maximal solution f such that f(1/2,...,1/(k+1)) < 1/2
implies f(1/2,...,1/(k+1)) = f(1,1/2,...,f/k).

PROPOSITION 4. Every universal property of regressive partial
f:Q[0,1]^k into Q[0,1]^r has a maximal solution f such that
f(1/2,...,1/(k+1)) == f(1,1/2,...,1/k). Here == indicates that both
sides are undefined or both sides are defined and equal.

THEOREM 5. Propositions 2-4 are provably equivalent to Con(SRP) over
WKL_0. In particular, they are provable in SRP+ but not in ZFC
(assuming ZFC is consistent). For fixed k, Propositions 2-4 are
provable in SRP, and are cofinal in the Con(SRP[k]) over WKL0. These
results hold if we replace iff in Proposition 2 with if then or its
converse.

THEOREM 6. For all k >= 1, each of the Master Templates have instances
which are provable in SRP but not in SRP[k] (assuming SRP[k] is
consistent). In particular, each Master Template has an instance which
is provable in SRP but not in ZFC (assuming ZFC is consistent).

Propositions 2-4 suggest some derived templates.

TEMPLATE I. Let k >= 1 and A be a universal property of subsets of
Q[0,1]^k, using constants. Every universal property of subsets of
Q[0,1]^k, using no constants, has a maximal solution which is also a
solution to A.

TEMPLATE II. Let k,r >= 1 and A be a universal property of partial
f:Q[0,1]^k into Q[0,1]^r, using constants. Every universal property of
partial f:Q[0,1]^k into Q[0,1]^r, using no constants, has a maximal
solution which is also a solution to A.

TEMPLATE III. Let k,r >= 1 and A be a universal property of regressive
partial f:Q[0,1]^k into Q[0,1]^r, using constants. Every universal
property of regressive partial f:Q[0,1]^k into Q[0,1]^r, using no
constants, has a maximal solution which is also a solution to A.

THEOREM 7. Theorem 6 applies to Templates I-III.

We do not have a complete understanding of Templates I-III. However,
the specific universal conditions used in Propositions 2-4 are
particularly simple. This suggests some further templates of more
restricted scope.

TEMPLATE IV. Let k >= 1 and A be a universal property of subsets of
Q[0,1]^k with at most one quantifier and at most two occurrences of S.
Every universal property of subsets of Q[0,1]^k, using no constants,
has a maximal solution which is also a solution to A.

TEMPLATE V. Let k,r >= 1 and A be an implication between inequalities,
f(a_1,...,a_k) <,<=,= f(b_1,...,b_k) arrows f(c_1,...,c_k) <,<=,=
f(d_1,...,d_k) with no variables. Every universal property of partial
f:Q[0,1]^k arrows Q[0,1], using no constants, has a maximal solution
win which the implication holds.

TEMPLATE VI. Let k,r >= 1 and A be an equation f(a_1,...,a_k) ==
f(b_1,...,b_k) with no variables. Every universal property of partial
f:Q[0,1]^k arrows Q[0,1], using no constants, has a maximal solution
win which the implication holds. Here == means that either both sides
are undefined, or both sides are defined and equal.

THEOREM 8. Every instance of Templates IV-VI are provable in SRP or
refutable in RCA0. The instances that are not refutable in RCA0 are
cofinal in the Con(SRP[k]) over WKL0. Very simple instances in very
low dimension can be given that are independent of ZFC (assuming ZFC
is consistent).

****************************************
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 541st 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html

528: More Perfect Pi01  8/16/14  5:19AM
529: Yet more Perfect Pi01 8/18/14  5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01  8/22/14  5:16PM
532: More General Theory/Perfect Pi01  8/23/14  7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14  1:17AM
534: Perfect Explicitly Pi01  8/27/14  10:40AM
535: Updated Perfect Explicitly Pi01  8/30/14  2:39PM
536: Pi01 Progress  9/1/14 11:31AM
537: Pi01/Flat Pics/Testing  9/6/14  12:49AM
538: Progress Pi01 9/6/14  11:31PM
539: Absolute Perfect Naturalness 9/7/14  9:00PM
540: SRM/Comparability

Harvey Friedman