[FOM] 542: Templates/LC shadow

Wed Sep 10 00:44:36 EDT 2014

In this posting, I want to start applying the Master Templates to
general mathematical structures, and also indicate how the implicitly
Pi01 statements link to standard ideas from the large cardinal theory
surrounding SRP.

DEFINITION 1. We say that M is a normally countable structure if and only if
i. M is a relational structure with finite signature (i.e., with
finitely many constants, relations, and functions).
ii. M is given with a mathematically definable enumeration of its domain.

In ii above, this enumeration does not have to be recognizable in any
way from the point of view of M.

We then form the following Templates.

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

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

If M comes equipped with a linear ordering of its domain, then the
following makes perfectly good sense.

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

The project for each of these Templates is to develop natural partial
results of the following kind.

i. For certain natural classes of A,B, the template statement is true.
ii. For certain natural classes of A,B the template statement is false.

We have been giving examples of i) that are provable using large
cardinals but not in ZFC (assuming ZFC is consistent). We have not
been thinking about ii), and expect examples of ii) to be provable in
RCA_0.

PROPOSAL. Continue this project with i,ii for a variety of normally
countable structures M.

As we see from #541, we have been using M = (Q[0,1],<) only, thus far.
As a first step toward using a variety of normally countable
structures, we turn our attention to  M = (Q,<). Here we are
confronted with a problem that we have not yet solved. Here are
particularly straightforward adaptations of Propositions 2-4 from
http://www.cs.nyu.edu/pipermail/fom/2014-September/018161.html to
(Q,<).

PROPOSITION 2. Every universal property of S contained in Q^k, using
no constants, has a maximal solution with for all p < 0, (0,...,k-1,p)
in S iff (1,...,k,p)  in S.

PROPOSITION 3. Every universal property of partial f:Q^k into Q^r,
using no constants, has a maximal solution with f(0,...,k-1) < 0
implies f(0,...,k-1) = f(1,2,...,k).

PROPOSITION 4. Every universal property of regressive partial f:Q^k
into Q^r, using no constants, has a maximal solution with f(0,...,k-1)
== f(1,2,...,k). Here == indicates that both sides are undefined or
both sides are defined and equal.

We know how to prove these partial results on the Master Templates
from Con(SRP), but we do not know whether they are provable in ZFC.

At this point, it is natural to extend the Master Templates for
linearly ordered normal countable structures M as follows.

DEFINITION 2. Let M be a linearly ordered normal countable structure.
An internal interval is an interval J containedin dom(M) whose
endpoints lie in dom(M) union {-infinity,infinity}. The empty set and
singletons are internal intervals.

MASTER TEMPLATE (M,sets,intervals). Let k >= 1, J be an internal
interval, and A,B be universal properties of S contained in J^k over
M, using constants. There is a maximal solution to A, which is a
solution to B.

MASTER TEMPLATE (M,functions,intervals). Let k,r >= 1, J be an
internal interval, and A,B be universal properties of partial f:J^k
into J^r over M, using constants. There is a maximal solution to A,
which is a solution to B.

MASTER TEMPLATE (M,regressive,intervals). Let k,r >= 1, J be an
internal interval, and A,B be universal properties of regressive
partial f:J^k into J^r over M, using constants. There is a maximal
solution to A, which is a solution to B.

Now we have the following partial results for the above more
comprehensive Master Templates, for M = (Q,<)..

PROPOSITION 5. Let J be an internal interval in Q, properly containing
Q[0,k]. Every universal property of S contained in J^k, using no
constants, has a maximal solution with for all p < 0, (0,...,k-1,p) in
S iff (1,...,k,p)  in S.

PROPOSITION 6. Let J be an internal interval in Q, properly containing
Q[0,k]. Every universal property of partial f:J^k into J^r, using no
constants, has a maximal solution with f(0,...,k-1) < 0 implies
f(0,...,k-1) = f(1,...,k).

PROPOSITION 7. Let J be an internal interval in Q, with negative left
endpoint and right endpoint >= k. Every universal property of
regressive partial f:J^k into J^r, using no constants, has a maximal
solution with f(0,...,k-1) == f(1,...,k). Here == indicates that both
sides are undefined or both sides are defined and equal.

THEOREM 8. Propositions 5-7 are each provably equivalent to Con(SRP) over WKL0.

I have been thinking some about the case M = (Q,<,+). It appears that
in order to develop natural Pi01 incompleteness on M, we are going to
have to weaken the notion of maximal. This will already be an
important move for (Q[0,1],<) and (Q,<). We hope to take this matter
up in a future posting.

We now move to how the implicitly Pi01 statements link to standard
ideas from the large cardinal theory surrounding SRP. It is well known
that the SRP large cardinal hierarchy can be given by the following
familiar properties. A source is
https://u.osu.edu/friedman.8/files/2014/01/subtlecardinals-1tod0i8.pdf
which is published.

*) Let lambda be a suitable large cardinal. Let S be a subset of
lambda^k. There exists ordinals alpha_0 < ... < alpha_k < lambda such
that for all beta < alpha_0, (alpha_0,...,alpha_k-1,beta) in S iff
(alpha_1,...,alpha_k,beta) in S.

*) looks an awful lot like Proposition 5 (if you like, just set J =
Q[-k,k] there). However, in Proposition 5, we have fixed 0,...,k in
advance, whereas in *), alpha_0,...,alpha_k depend on S.

**) Let lambda be a suitable large cardinal. There exists ordinals
alpha_0 < ... < alpha_k < lambda such that the following holds. Let S
be a subset of lambda^k that is set theoretically definable. For all
beta < alpha_0, (alpha_0,...,alpha_k-1,beta) in S iff
(alpha_1,...,alpha_k,beta) in S.

**) turns out to be an easy variant of *). Now Proposition 5 is much
more delicate. We cannot possibly have the conclusion of Proposition 5
for all "definable" S in any sense, or for all "definable maximal
solutions" in any sense. It should be observed that universal
properties using no constants are very heavily definable conditions on
the S. But there is a crucial extra existential quantifier in
Proposition 5 not present in **). I.e., the existential quantifier
over "maximal solutions".

****************************************
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  9/8/14  12:03AM
541: Master Templates  9/9/14  12:41AM

Harvey Friedman