[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