[FOM] 497:Invariant Maximality Restated
Friedman, Harvey
friedman at math.ohio-state.edu
Wed May 2 02:49:06 EDT 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
**********************************
THIS POSTING IS COMPLETELY SELF CONTAINED
*********************************
INVARIANT MAXIMALITY
by
Harvey M. Friedman
May 2, 2012
1. Graphs, Cliques, Invariance.
2. Restricted Shifts.
3. Profiled Shifts.
4. UHS#, Z+up.
5. Templates.
6. Maximal Squares.
7. Invariant Maximality and Beyond.
1. GRAPHS, CLIQUES, INVARIANCE.
A graph is a pair G = (V,E), where E is an irreflexive symmetric
relation on V. We say that the graph is on V. A clique is a subset of
V, where any two distinct elements are related by E. A maximal clique
in a graph is a clique which is not a proper subset of any clique.
Graph theorists call these simple graphs, and refer to V as the set of
vertices, and E as the set of edges (often using the unordered pairs
instead of the ordered pairs).
THEOREM 1.1. Every graph has a maximal clique. This is equivalent to
the axiom of choice over ZF. In the countable case, this is provable
in RCA_0.
Let R be any relation (a set of ordered pairs). We define R invariance
and complete R invariance for subsets S of an ambient space K.
We say that S containedin K is R invariant if and only if for all x,y
in K with R(x,y), we have x in S implies y in S.
We say that S containedin K is completely R invariant if and only if
for all x,y in K with R(x,y), we have x in S iff y in S.
We treat functions as graphs, and use complete T invariance of S
containedin K, for functions T.
Let Q be the set of all rationals, Z+ be the set of all positive
integers, and Q[a,b] = Q intersect [a,b].
For A contained in Q, let A* be the set of all nonempty finite
sequences of rationals.
All graphs considered are on some Q[0,n]^k, where k,n >= 1.
We say that x,y in Q* are order equivalent if and only if x,y have the
same length, and for all 1 <= i,j <= lth(x), x_i < x_j iff y_i < y_j.
We say that a graph G on Q[0,n]^k is order invariant if and only if
its adjacency relation E containedin Q[0,n]^2k is R invariant, where R
is order equivalence on Q*.
We investigate the statement
IM(k,n,R). Every order invariant graph on Q[0,n]^k has a completely R
invariant maximal clique.
where k,n >= 1, and R is various relations on Q*.
Obviously, if IM(k,n,R) and R' containedin R then IM(k,n,R'). So if
IM(k,n,R) fails, then we try to restrict R to R' so that IM(k,n,R').
2. RESTRICTED SHIFTS.
The Full Shift is the function FS:Q* into Q* defined by FS(x) = x+1.
Here "Full" refers to the shifting of all of the coordinates, rather
than just some of the coordinates.
THEOREM 2.1. For all k >= 1 and n >= 2, IM(k,n,FS) fails. This is
provable in RCA_0.
For T:Q* into Q* and A contained in Q*, we write T|A for the
restriction of T to A.
THEOREM 2.2. For all k,n >= 1, IM(k,n,FS|Q[1,n]*). This is provable in
WKL_0.
The Upper Half Shift, UHS:Q* into Q* is defined by UHS(x) = the result
of shifting (+1) all coordinates of x that are greater than at least
half of the coordinates of x.
THEOREM 2.3. For all k >= 1 and n >= 2, IM(k,n,UHS) fails. This is
provable in RCA_0.
Let T:Q* into Q*. We define T# as T restricted to those vectors such
that T moves only positive integer coordinates.
I.e., T# is T restricted to {x in Q*: Tx_i not= x_i implies x_i is a
positive integer}.
PROPOSITION 2.4. For all k,n >= 1, IM(k,n,UHS#).
THEOREM 2.5. Proposition 2.4 is provably equivalent to Con(SRP) over
ACA'.
Here SRP = ZFC + {there exists lambda with the k-SRP}_k. Lambda has
the k-SRP iff lambda is a limit ordinal, where every partition of the
unordered k-tuples from lambda into two pieces has a stationary
homogeneous set. ACA' = RCA_0 + for all x,n, the n-th Turing jump of x
exists.
3. PROFILED SHIFTS.
FS, UHS, and UHS# are examples of what we call Profiled Shifts. We
characterize the Profiled Shifts T such that for all k,n >= 1,
IM(k,n,T). The proof of the characterization requires large cardinals.
The profile of x in Q* consists of its length, the set {i: the i-th
smallest coordinate = the (i+1)-st smallest coordinate}, and the set
{i: the i-th smallest coordinate is a positive integer}.
Note that in profiles, x is treated as a multiset from a linear
ordering, where we are sensitive to whether elements are positive
integers. Thus profiles are clearly associated with the relational
structure (Q,<,Z+). The use of structures other than (Q,<,Z+) leads to
major research topics.
A Profiled Set is a subset of Q*, where membership of x in Q* depends
only on the profile of x.
A Profiled Shift is a partial T:Q* into Q* such that
i. dom(T) is a Profiled Set.
ii. for all x in dom(T), Tx results in shifting (+1) some coordinates
of x, while leaving the others fixed.
iii. for all x in Q*, the choice of which positions of coordinates are
shifted by T depends only on the profile of x.
Note that FS and UHS are Profiled Shifts. If T is a Profiled Shift
then T# is a Profiled Shift.
THEOREM 3.1. There is a maximum Profiled Shift T contained in FS such
that for all k,n >= 1, IM(k,n,T). We have dom(T) = {x in Q*: min(x) is
in Z+}.
Let x in Q*. The upper half of x is the set of all coordinates of x
greater than at least half of the coordinates of x. UHS shifts the
upper half of x.
The lower half of x is the set of all coordinates of x not in the
upper half of x. UHS fixes the lower half of x.
The middle part of x consists of the highest coordinates in the lower
half of x and the lowest coordinates in the upper half of x. The
middle part of every (p,...,p) consists of all coordinates, and the
middle part of any remaining vector in Q* has exactly two distinct
values.
PROPOSITION 3.2. There is a maximum Profiled Shift T contained in UHS
such that for all k,n >= 1, IM(k,n,T). We have dom(T) = {x in Q*: the
upper part is contained in Z+ or the middle part is contained in Z+}.
THEOREM 3.3. Proposition 3.2 is provably equivalent to Con(SRP) over
ACA'. This is true even for just the first claim.
We now give a characterization of all of the Profiled Shifts T such
that for all k,n >= 1, IM(k,n,T).
PROPOSITION 3.4. Let T be a Profiled Shift. The following are
equivalent.
i. for all n >= 1, IM(k,n,T).
ii. for all x in dom(T),
a. min(x) in Z+ and T(x) = x+1; or
b. there exists x_i,x_j in Z+, where T shifts all x_r >= x_j, T
fixes all x_r <= x_i, and there are no coordinates in (x_i,x_j); or
c. there exists x_i, where T shifts all x_r >= x_i, all of which
are in Z+, and T fixes all x_r < x_i.
THEOREM 3.5. Proposition 3.4 is equivalent to Con(SRP) over ACA'. The
implication i implies ii is provable in RCA_0. THe implication iia
implies i is provable in RCA_0. The implication iic implies i is
provably equivalent to Con(SRP) over ACA'.
4. UHS#, Z+up.
We have already encountered the Profiled Shift UHS# in Proposition 2.4.
Z+up is given by Z+up(x) = the result of shifting all coordinates of x
that are greater than all coordinates of x that are not in Z+.
Z+up is also a Profiled Shift.
PROPOSITION 4.1. For all k,n >= 1, IM(k,n,UHS#) and IM(k,n,Z+up).
THEOREM 4.2. Proposition 4.1, with either UHS# or Z+up, is provably
equivalent to Con(SRP) over ACA'.
Note that the statements
for all k,n >= 1, IM(k,n,UHS#)
for all k,n >= 1, IM(K,n,Z+up)
can be put into the following form: an effective list of sentences in
predicate calculus all have countable models. Therefore both of the
above statements are Pi01 in virtue of their logical form.
It is still important to have explicitly Pi01 sentences independent of
ZFC. This is taken up in a later posting.
5. TEMPLATES.
Let M = (D,R_1,...,R_p) be a nonempty set D together with subsets
R_1,...,R_p of various Cartesian powers of D. We say that X contained
in D^k is M elementary if and only if X can be defined using the R's,
variables v_1,...,v_k, equality, logical connectives, and constants
for elements of D.
We say that X contained in D^k is purely M elementary if and only if X
can be defined using the R's, variables v_1,...,v_k, equality, snd
logical connectives. I.e., constants are not allowed.
EXAMPLE. If M = (R,<,+,x,0,1), then the M elementary relations are the
semi algebraic relations, and the purely M elementary relations are
the rationally semi algebraic relations.
TEMPLATE 1 (four choices). Let R contained in Q[0,n]^k be (purely)
(Q[0,n],<,{1,...,n}) elementary. Every order invariant graph on
Q[0,n]^k has an (completely) R invariant maximal clique.
For which k,n,R does Template 1 hold? This is beyond what we can do now.
A complete solution to Template 1 using elementary and invariant
yields a complete solution to Template 1 for all four choices. This is
because complete R invariance is the same as R' invariance, where R'
is the least symmetric relation containing R.
Yet more ambitious is to template order invariance.
TEMPLATE 2 (sixteen choices). Let R contained in Q[0,n]^2k be (purely)
(Q,<,{1,...,n}) elementary, and R' contained in Q[0,n]^k be (purely)
(Q[0,n],<,{1,...,n}) elementary. Every (completely) R invariant graph
on Q[0,n]^k has an (completely) R' invariant maximal clique.
A complete solution to Template 2 using elementary, elementary,
invariant, and invariant, yields a complete solution to Template 2 for
all sixteen choices.
THEOREM 5.1. For any of the four choices, there is an instance of
Template 1 with k = n = 16, where R is an equivalence relation, which
is provable in SRP but not in ZFC (assuming ZFC is consistent). For
any of the four choices SRP is not sufficient to prove or refute all
instances of Template 2 even for equivalence relations R (assuming SRP
is consistent).
We can be specific about the equivalence relations used for Theorem 5.1.
We say that x,y in Q* are upper Z+ equivalent if and only if x,y are
order equivalent, and for all x_i not= y_i, every x_j >= x_i is in Z+
and every y_j >= y_i is in Z+.
For Theorem 5.1, we use the restrictions of upper Z+ equivalence to
the Q[0,n]^k.
CONJECTURE 5.2. All instances of Template 2 are provable or refutable
in SRP.
CONJECTURE 5.3. For any two instances of Template 2, one implies the
other in ACA'.
6. MAXIMAL SQUARES.
There is a variant of
every graph has a maximal clique
that do not involve graphs, and are stated for arbitrary relations.
Here a relation is simply a set of ordered pairs.
A square in a relation R is a subset of R of the form A x A. A maximal
square in R is a square in R which is not a proper subset of any
square in R.
We have
every relation has a maximal square.
This also is provably equivalent to the axiom of choice over ZF, and
constructive in the countable case.
The most immediate form of Invariant Maximality with relations/squares
is
every invariant relation has an invariant' maximal square.
Note that in this formulation, invariant' applies to the maximal
square, and not to the side of the maximal square. In the graph
formulation, invariant' applies to the maximal clique, which
corresponds to the side of the maximal square.
So it is clear that the maximal square formulations easily imply the
maximal clique formulations, but not vice versa.
However, we do have a way of getting the maximal square formulations
from the maximal clique formulations under very general conditions,
though there is a cost of doubling the dimension.
THus everything in sections 1-5 can be formulated with relations
instead of graphs, and maximal squares instead of maximal cliques,
with the same results.
7. INVARIANT MAXIMALITY AND BEYOND.
This initial development of Invariant Maximality is based on
every graph has a maximal clique
every relation has a maximal square
and moves to
every invariant graph has an invariant' maximal clique
every invariant relation has an invariant' maximal square.
But we can expand the scope of Invariant Maximality greatly by
considering other well known facts of the form
every gadget has a maximal widget
every invariant gadget has an invariant' maximal widget.
Maximality is also something that ultimately can be flexible. We rely
on the nondeterministic character of maximality.
Ultimately, we should be considering the much more general
every gadget has a widget
every invariant gadget has an invariant widget.
Another important goal is to go from the present heavily coordinatized
formulations to coordinate free formulations.
We hope to report on all of these issues in the future, as the
Incompleteness Phenomena becomes everywhere dense uniquely profound
essential features of mathematical thought.
**********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 497th 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-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
456: The Quantifiers "majority/minority" 2/23/11 9:51AM
457: Maximal Cliques and Large Cardinals 5/3/11 3:40AM
458: Sequential Constructions for Large Cardinals 5/5/11 10:37AM
459: Greedy CLique Constructions in the Integers 5/8/11 1:18PM
460: Greedy Clique Constructions Simplified 5/8/11 7:39PM
461: Reflections on Vienna Meeting 5/12/11 10:41AM
462: Improvements/Pi01 Independence 5/14/11 11:53AM
463: Pi01 independence/comprehensive 5/21/11 11:31PM
464: Order Invariant Split Theorem 5/30/11 11:43AM
465: Patterns in Order Invariant Graphs 6/4/11 5:51PM
466: RETURN TO 463/Dominators 6/13/11 12:15AM
467: Comment on Minimal Dominators 6/14/11 11:58AM
468: Maximal Cliques/Incompleteness 7/26/11 4:11PM
469: Invariant Maximality/Incompleteness 11/13/11 11:47AM
470: Invariant Maximal Square Theorem 11/17/11 6:58PM
471: Shift Invariant Maximal Squares/Incompleteness 11/23/11 11:37PM
472. Shift Invariant Maximal Squares/Incompleteness 11/29/11 9:15PM
473: Invariant Maximal Powers/Incompleteness 1 12/7/11 5:13AMs
474: Invariant Maximal Squares 01/12/12 9:46AM
475: Invariant Functions and Incompleteness 1/16/12 5:57PM
476: Maximality, CHoice, and Incompleteness 1/23/12 11:52AM
477: TYPO 1/23/12 4:36PM
478: Maximality, Choice, and Incompleteness 2/2/12 5:45AM
479: Explicitly Pi01 Incompleteness 2/12/12 9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness 2/15/12 8:40AM
482: Maximality, Choice, and Incompleteness 2 2/19/12 7:43AM
483: Invariance in Q[0,n]^k 2/19/12 7:34AM
484: Finite Choice and Incompleteness 2/20/12 6:37AM__
485: Large Large Cardinals 2/26/12 5:55AM
486: Naturalness Issues 3/14/12 2:07PM
487: Invariant Maximality/Naturalness 3/21/12 1:43AM
488: Invariant Maximality Program 3/24/12 12:28AM
489: Invariant Maximality Programs 3/24/12 2:31PM
490: Invariant Maximality Program 2 3/24/12 3:19PM
491: Formal Simplicity 3/25/12 11:50PM
492: Invariant Maximality/conjectures 3/31/12 7:31PM
493: Invariant Maximality/conjectures 2 3/31/12 7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv 4/5/12 4:17PM
495: Invariant Finite Choice 4/5/12 4:18PM
496: Invariant Finite Choice/restatement 4/8/12 2:18AM
Harvey Friedman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120502/ac970daf/attachment-0001.html>
More information about the FOM
mailing list