[FOM] 473:Invariant Maximal Powers/Incompleteness 1

Harvey Friedman friedman at math.ohio-state.edu
Thu Dec 8 09:52:22 EST 2011


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

*****************************************

THIS POSTING IS ENTIRELY SELF CONTAINED

*****************************************

THIS VERSION IS CLOEST TO THE PREVIOUS #470. IN #471, #472, WE WERE  
INTERESTED IN MAKING THE AMBIENT SPACES CLOSED UNDER AN OPERATION.  
THIS LED TO USING THE Q^2k AS THE AMBIENT SPACES, INSTEAD OF THE  
Q[0,n]^2k OF #470, AND BRINING IN THE FUNCTION Z+up.

IN #471, WE BROUGHT IN LOCAL MAXIMALITY. OVERALL, I THEN MADE THE  
JUDGEMENT CALL THAT BRINGING IN LOCAL MAXIMALITY WAS WORTH DOING IN  
ORDER TO MAKE THE AMBIENT SPACES CLOSED UNDER Z+up.

IN #472, I ALSO BROUGHT IN TOWERS AS AN ALTERNATIVE TO BRINGING IN  
LOCAL MAXIMALITY.

I NOW SEE SOME SERIOUS TECHNICAL OBSTACLES TO THE TOWER APPROACH. THE  
LOCAL MAXIMALITY APPROACH SEEMS FINE.

BUT ---

I HAVE NOW REASSESSED THE SITUATION, AND CONCLUDE THAT THE BEST  
FORMULATION IS TO GO BACK TO #470, AND USE THE Q[0,k]^n AS THE AMBIENT  
SPACES. HERE ARE SOME REASONS.

1. THE FINITE INTERVALS Q[0,n] WITH DISTINGUISHED ELEMENTS 1,...,k IS  
REALLY JUST A DENSE LINEAR ORDERING WITH ENDPOINTS AND FINITELY MANY  
DISTINGUISHED ELEMENTS, AND THIS IS MORE ELEMENTAL THAN Q,< WITH  
INFINITELY MANY DISTINGUISHED ELEMENTS. ONE OF MY FAMOUS CORE  
MATHEMATICIAN ADVISORS WAS PARTICULARLY SENSITIVE TO THE ELEMENTARY  
CHARACTER OF THE SYSTEM (Q[0,k],<,1,...,k).

IN THE NEW FORMULATIONS, THE AMBIENT SPACES ARE NOW THE Q[0,k]^n.  
INSTEAD OF LOOKING AT SQUARES S^2 IN SUBSETS OF Q[0,k]^n, WE LOOK AT  
CARTESIAN POWERS S^m IN SUBSETS OF Q[0,k]^n. NOTE THAT IF m DOES NOT  
DIVIDE n, THEN THE ONLY S^m IN THE GIVEN SUBSET OF Q[0,k]^n IS THE  
EMPTY SET.

2. I AM NOW READY TO CLAIM THAT I CAN MAKE THE THREE PARAMETERS k,n,m  
ALL RATHER SMALL. SPECIFICALLY, 8,24,3.

3. TO WORK WITH SMALL k,n,m, WE NEED TO DIG IN AND PICK OUT EXACTLY  
WHAT WE NEED IN ORDER TO WORK WITH PRE WELL ORDERINGS, COMPARISON  
MAPS, SATISFACTION RELATIONS, TRANSFINITE RECURSIONS, AND SO FORTH.  
THIS SEEMS WELL WORTH THE TROUBLE. WE EXPECT A PROLIFERATION OF  
OPPORTUNITIES FOR CLEVER REDUCTIONS OF THE SIZES OF k,n,m, WITH  
DELICATE TRADEOFFS.

4. WITH REGARD TO MY MAIN BUGABOO - MAKING THE INVARIANCE CONDITION ON  
THE SQUARE (NOW CARTESIAN POWER) AS SIMPLE AND TRANSPARENT AND NATURAL  
AND CANONICAL AS POSSIBLE:

"UPPER RELATED" PROVIDES THE CLEAREST INVARIANCE CONDITION. SINCE WE  
ARE ON THESE FINITE LENGTH INTERVAL SPACES, WE VIEW "UPPER RELATED" AS  
A RELATION, AND NOT A FUNCTION, ON THESE AMBIENT SPACES. SPECIFICALLY,  
AS IN #470, x,y IN Q[0,k]^n ARE UPPER RELATED IF AND ONLY IF y IS  
OBTAINED FROM x BY ADDING 1 TO ALL COORDINATES GREATER THAN ALL  
COORDINATES OUTSIDE {1,...,k}.

"UPPER EQUIVALENT" PROVIDES THE STRONGEST ADMISSIBLE INVARIANCE  
CONDITION THAT CAN BE USED -- THERE IS A THEOREM TO THIS EFFECT. x,y  
IN Q[0,k]^n ARE UPPER EQUIVALENT IF AND ONLY IF x,y ARE ORDER  
EQUIVALENT, AND FOR ALL i <= t, x_i NOT= y_i IMPLIES EVERY x_j >= x_i  
AND EVERY y_j >= y_i LIE IN {1,...,k}.

UPPER RELATED GIVES RISE TO UPPER SHIFT INVARIANCE, AND UPPER  
EQUIVALENT GIVES RISE TO UPPER INTEGRAL INVARIANCE.

WE STATE THE MAIN RESULTS FOR BOTH UPPER SHIFT INVARIANCE AND UPPER  
INTEGRAL INVARIANCE. FOR UPPER SHIFT INVARIANCE, WE USE COMPLETE  
INVARIANCE. FOR UPPER INTEGRAL INVARIANCE, COMPLETE INVARIANCE IS  
AUTOMATIC FROM INVARIANCE.

WE ALSO GIVE THE CORRESPONDING FORMULATIONS IN TERMS OF GRAPHS,  
CLIQUES, HYPERGRAPHS, HYPERCLIQUES, DOMINATORS, AND HYPERDOMINATORS.  
WE ALSO GIVE TRANSPARENT FINITE FORMS.

*****************************************

INVARIANT MAXIMAL POWERS AND INCOMPLETENESS
by
Harvey M. Friedman
December 8, 2011

Abstract. We prove the Upper Shift Invariant Maximal Power Theorem,  
asserting that for all k,n,m >= 1, every order invariant subset of  
Q[0,k]^n has an upper shift invariant maximal S^m. This is based on  
rational [0,k]^n, and the addition of 1 to all coordinates greater  
than all coordinates outside {1,...,k}. The proof relies on the  
assumption that certain well studied extensions of the usual ZFC  
axioms for mathematics are free of contradiction. In fact, we show  
that the theorem is equivalent to this assumption.

1. Introduction.
2. Maximal powers, order invariance, upper invariance.
3. Theorems within ZFC.
    3.1. k = 2 or n = 2m.
    3.2. The R invariant maximal power theorems.
4. The stationary Ramsey property.
5. Proof of the upper integral invariant maximal power theorem.
6. Reversal of the upper shift invariant maximal power theorems.
7. Graphs, cliques, dominators, hypergraphs, hypercliques,  
hyperdominators.
8. Finite invariant maximal power theorems.
9. Open questions.

INTRODUCTION.

{Starts with a brief summary of Concrete Mathematical Incompleteness,  
referring to the BRT book on the web, and how this work differs from  
the BRT work).

In this paper, we begin with the set theoretic statement

   1) for all sets X, every subset of X^2 contains a maximal S^2

and its multidimensional generalization

   2) for all sets X, and n,m >= 1, every subset of X^n contains a  
maximal S^m

I.e., every E contained in X^n contains s subset of the form S^m that  
is maximal under inclusion. If m does not divide n then the only S^m  
contained in X^n is the empty set, and the statement is trivial. If m  
divides n, then every S^m contained in X^n has S contained in X^(n/m).

These set theoretic statements have familiar proofs using Zorn's  
Lemma. We present the easy proof that 1) is equivalent to the Axiom of  
Choice.

No Axiom of Choice is needed if X is countable, as we can enumerate  
X^(n/m) and make the so called greedy construction of the S contained  
in X^(n/m) such that S^m is maximal.

In this paper, we use the ambient spaces Q[0,k]^n, k,n >= 1, where  
Q[0,k] is the set of all rationals in [0,k]. We focus on

   3) for all k,n,m >= 1, every subset of Q[0,k]^n contains a maximal  
S^m.

Invariance conditions occur throughout mathematics. Let R be a binary  
relation (set of ordered pairs). We say that A is R invariant if and  
only if for all (x,y) in R, x in A implies y in A. We say that A is  
completely R invariant if and only if for all (x,y) in R, x in A iff y  
in A.

We introduce invariance conditions in 2). We consider cases of

   4) for all k,n,m >= 1, every (completely) Invariant_1 subset of  
Q[0,k]^n contains an (completely) Invariant_2 maximal S^m

In particular, we consider statements of the form

   5) for all k,n,m >= 1, every (completely) R_1 invariant subset of  
Q[0,k]^n contains a (completely) R_2 invariant maximal S^m

where R_1 is a particular binary relation called "order equivalence"  
on Q[0,k]^n, and R_2 is a particular binary relation called "upper  
shift related" on Q[0,k]^n. We also use the more inclusive relation  
"upper integral equivalent" on Q[0,k]^n. The more inclusive the  
relation, the stronger the associated invariance condition.

Here are the definitions of these binary relations.

x,y in Q[0,k]^n are order equivalent if and only if for all 1 <= i,j  
<= n, x_i < x_j iff y_i < y_j.

x,y in Q[0,k]^n are upper shift related if and only if y is obtained  
by adding 1 to all coordinates in x that are greater than all  
coordinates outside {1,...,k}.

x,y in Q[0,k]^n are upper integral equivalent if and only if x,y are  
order equivalent and for all i <= n, if x_i not= y_i then every x_j >=  
x_i and y_j >= y_i lie in {1,...,k}.

Upper shift related on Q[0,k]^n is included in upper integral  
equivalence on Q[0,k]^n. If k >= 2 then upper shift related on  
Q[0,k]^n is not an equivalence relation. Upper integral equivalence on  
Q[0,k]^n is an equivalence relation.

Upper shift invariance is simpler than the stronger notion of upper  
integral invariance in that the former does not rely on order  
equivalence, whereas the latter does.

UPPER SHIFT INVARIANT MAXIMAL POWER THEOREM. USIMPT. For all k,n,m >=  
1, every order invariant subset of Q[0,k]^n contains a completely  
upper shift invariant maximal S^m.

UPPER INTEGRAL INVARIANT MAXIMAL POWER THEOREM. UIIMPT. For all k,n,m  
 >= 1, every order invariant subset of Q[0,k]^n contains an upper  
integral invariant maximal S^m.

Since order equivalence is symmetric, we omit the first "completely"  
in both statements. Since upper integral equivalence is symmetric, we  
omit the second "completely" in UIIMPT.

Obviously UIIMPT implies USIMPT. We give a proof of UIIMPT using an  
assumption going well beyond the usual ZFC axioms for mathematics. We  
show that USIMPT and UIIMPT are provably equivalent to Con(SRP) over  
ACA'.

We can fix the three parameters k,n,m. I.e.,

UPPER SHIFT INVARIANT MAXIMAL POWER THEOREM (k,n,m). USIMPT(k,n,m).  
Every order invariant subset of Q[0,k]^n contains a completely upper  
shift invariant maximal S^m.

UPPER INTEGRAL INVARIANT MAXIMAL POWER THEOREM (k,n,m). UIIMPT(k,n,m).  
Every order invariant subset of Q[0,k]^n contains an upper integral  
invariant maximal S^m.

If we fix only one or two of k,n,m, then we use blanks for the ones  
that are not fixed, indicating that they are to be universally  
quantified. E.g.,

UPPER INTEGRAL INVARIANT MAXIMAL POWER THEOREM (k,_,_). UIIMPT(k,_,_).  
For all n,m >= 1, every order invariant subset of Q[0,k]^n contains an  
upper integral invariant maximal S^m.

We prove UIIMPT(2,n,m) and UIIMPT(k,2n,n) well within ZFC.

We show that the statements USIMPT(k,n,m) form Pi01 sentences that are  
cofinal in the statements Con(SRP_t), t >= 1. The same is true for the  
statements UIIMPT(k,n,m).

We refine this to show that the statements USIMPT(k,2k,k), UIIMPT(k, 
2k,k) are also cofinal in the statements Con(SRP_t), t >= 1. The  
factor 2 corresponds to invariant maximal squares S^2.

We show that already UIIMPT(8,24,8) proves Con(ZFC), and thus is  
unprovable in ZFC (assuming ZFC is consistent). We expect substantial  
improvements in this result.

Let R be a binary relation on Q[0,k]^n. We consider k,n as part of the  
data. We investigate

R INVARIANT MAXIMAL POWER THEOREM (m). R IMPT(m). Every order  
invariant subset of Q[0,k]^n has a completely R invariant maximal S^m.

We say that R is an admissible relation on Q[0,k]^n if and only if

i. R is contained in Q[0,k]^2n.
ii. R(x,y) holds for all order equivalent x,y in {1,...,k}^n.
iii. Let x,y in Q[0,k]^2n be order equivalent and (for all i <= 2n) 
(x_i in {1,...,k} iff y_i in {1,...,k}). Then x in R implies y in R.

We prove that if k >= n >= 1, m >= 2, and m|k, and R is an admissible  
equivalence relations on Q[0,k]^n, R IMPT(m) holds if and only if R is  
contained in upper integral equivalence on Q[0,k]^n. This  
characterizes upper integral equivalence on Q[0,k]^n as the maximum  
admissible relation such that R IMPT holds (assuming the hypotheses on  
k,n,m). This result is proved in ACA' + Con(SRP). It is in fact  
equivalent to Con(SRP) over ACA'. For k = 2 or n = 2m, this result is  
provable well within ZFC.

We also determine the intervals <p,q>, p,q in Q, for which UIIMPT  
hold. Here < is (,[, and > is ),]. We show that UIIMPT for <p,q> holds  
if and only if either min(<p,q>) is not a positive integer, or q <= p 
+2. We also show this for USIMPT. In fact, we show that these results  
hold even for n = 4.

We also formulate the results in terms of graph theoretic terminology.  
The use of graphs corresponds to m = 2, where cliques are used for S.  
I.e.,

UPPER SHIFT INVARIANT MAXIMAL CLIQUE THEOREM. USIMCT. For all k,n >=  
1, every order invariant graph on Q[0,k]^n contains a completely upper  
shift invariant maximal clique.

UPPER INTEGRAL INVARIANT MAXIMAL CLIQUE THEOREM. UIIMCT. For all k,n  
 >= 1, every order invariant graph on Q[0,k]^n contains an upper  
integral invariant maximal clique.

Note that the above are very close to USIMPT(_,_,2) and UIIMPT(_,_,2),  
as a clique is the side of a square. There is a small difference  
besides that: graphs are irreflexive and symmetric relations. The  
upshot is that USIMPT(_,_,2) and UIIMPT(_,_,2) imply USIMCT and  
UIIMCT, and hence Con(SRP) over ACA'. We actually show that USIMCT and  
UIIMCT are provably equivalent to Con(SRP) over ACA'.

Full USIMPT and UIIMPT are yet closer to the Upper Shift (Integral)  
Invariant Maximal Hyperclique Theorems, using hypergraphs.

We also use the graph/dominator formulation, which is dual to the  
above graph/clique formulation. This is based on the well known  
duality between independent dominators and maximal cliques. In  
addition, we use the hypergraph/hyperdominator formulation.

USIMST, and UIIMST are obviously provably equivalent to Pi01 sentences  
over ACA', since the are provably equivalent to Con(SRP) over ACA'.  
Thus they are implicitly Pi01. However, we can see directly that they  
are provably equivalent to Pi01 sentences by showing their equivalence  
with the satisfiability of effectively generated sentences in the  
first order predicate calculus with equality. This makes a good  
undergraduate exercise in mathematical logic, and the equivalences are  
provable in WKL_0.

In fact, the reduction to predicate calculus also holds for any fixing  
of one or more of the three numerical parameters in USIMST and UIIMST.

There remains the important question of giving an explicitly  
arithmetical or even explicitly Pi01 form of these statements. For  
this, it is most natural to use the graph/dominator formulations, with  
dominators for finite sets of vertices. For small k,n,m, we use the  
hypergraph/hyperdominator formulations, with hyperdominators for  
finite sets of vertices. This provides explicitly Pi01 sentences of an  
entirely transparent kind that are also equivalent to Con(SRP) over  
ACA'.

We conclude with a list of open questions.

*****************************************

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 473rd 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

Harvey Friedman


More information about the FOM mailing list