[FOM] 471:Shift Invariant Maximal Squares/Incompleteness

Harvey Friedman friedman at math.ohio-state.edu
Wed Nov 23 23:37:23 EST 2011


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

SHIFT INVARIANT MAXIMAL SQUARES AND INCOMPLETENESS
by
Harvey M. Friedman
November 23, 2011

Abstract. We prove the Z+up Invariant Maximal Square Theorem,  
asserting that for all k >= 1, every order invariant subset of Q^2k  
has a completely Z+up invariant maximal square. Here Q is the set of  
all rational numbers, and Z+up adds 1 to all coordinates greater than  
all coordinates outside Z^+. The proof relies on the assumption that  
certain well studied extensions of the usual ZFC axioms for  
mathematics are free of contradiction. We show that some variants  
based on local maximality are equivalent to this assumption. As a  
consequence, these local forms are provable from a certain large  
cardinal hypothesis, and not provable in ZFC (assuming ZFC is  
consistent).

1. Introduction.
2. Maximal and locally maximal squares, order equivalence, restricted  
shifts.
3. Graphs and maximal cliques.
4. Theorems within ZFC.
     4.1. Restricted shifts.
     4.2. In two dimensions.
     4.3. In higher dimensions.
5. The stationary Ramsey property.
6. Z+up invariant maximal square/clique theorems.
7. Reversal of Z+up invariant maximal square/clique theorems.
     7.1. The sets G(k,n).
     7.2. Representation by S formulas.
     7.3. Tupling.
     7.4. Normal Form.
     7.5. Linearly ordered set theory.
     7.6. Bounded separation and bounded indiscernibility.
     7.7. Transfinite induction.
     7.8. ZFC + V = L.
     7.9. Equivalence with Con(SRP).
8. 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 general statement

   1) every binary relation has a maximal square

where a square is a binary relation E is a subset of E of the form S x  
S. A maximal square in E is a square in E which is not a proper subset  
of a square in the binary relation.

This set theoretic statement has a familiar proof using Zorn's Lemma.  
We present the easy proof that 1) is equivalent to the Axiom of Choice.

No Axiom of Choice is needed for countable binary relations, as we can  
enumerate its field and make the so called greedy construction of the  
maximal square.

In this paper, we use the ambient spaces Q^2k = Q^k x Q^k, k >= 1, and  
focus on

   2) for all k >= 1, every subset of Q^2k has a maximal square

Invariance conditions occur throughout mathematics, and we focus on  
two kinds of invariance conditions on the Q^m, m >= 1.

a. Relational. We use a binary relation R on the ambient space Q^m. We  
say that A contained in Q^m is R invariant if and only if R(x,y) and x  
in A implies y in A.  We say that A contained in Q^m is completely R  
invariant if and only if R(x,y) implies (x in A iff y in A).

b. Functional. We have a function T:Q^m into Q^m. We say that A  
contained in Q^m is T invariant if and only if for all x in Q^m, x in  
A implies T(x) in A. We say that A contained in Q^m is completely T  
invariant if and only if for all x in Q^m, x in A iff T(x) in A.

Note that if R is symmetric then R is completely invariant if and only  
if R is invariant.

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

   3) for all k >= 1, every completely Invariant_1 subset of Q^2k has  
a completely Invariant_2 maximal square

In particular, we consider statements of the form

   4) for all k >= 1, every R invariant subset of Q^2k has a  
completely T invariant maximal square

where R is a particular binary relation on Q^2k called order  
equivalence on Q^2k, and T is a particular function from Q^2k into  
Q^2k called Z+up on Q^2k. This R is symmetric, so we delete  
"completely" in front of "R invariant".

Here (x_1,...,x_r) and (y_1,...,y_r) are order equivalent if and only  
if for all 1 <= i,j <= r, x_i < x_j iff y_i < y_j.

And here Z+up(x) is the result of adding 1 to all coordinates that are  
greater than all coordinates outside Z^+. We think of Z+up as a  
"restricted shift function", as it adds 1 to just some of the  
coordinates of its argument. A section of the paper considers the use  
of alternative restricted shift functions.

Z+up INVARIANT MAXIMAL SQUARE THEOREM. Z+up IMST. For all k >= 1,  
every order invariant subset of Q^2k has a completely Z+up invariant  
maximal square.

We give a proof of Z+up IMST using an assumption going well beyond the  
usual ZFC axioms for mathematics. We do not know if Z+up IMST can be  
proved in ZFC, or even in RCA_0. Our ignorance remains even if we  
delete "completely".

The maximal square in E contained in Q^2k constructed in our proof of Z 
+up IMST actually has a sharper maximality property. The square is Z^+  
maximal in E in the sense that for all n >= 1, the square intersect (- 
infinity,n]^2k is a maximal square in E intersect (-infinity,n]^2k.  
This is a form of local maximality. It is easy to see that any Z^+  
maximal square in E is a maximal square in E.

Z^+ maximality can be used to strengthen both 2) and Z+up IMST. Thus  
2) is strengthened by

    5) for all k >= 1, every subset of Q^2k has a Z^+ maximal square

A Z^+ maximal square in 5) is not constructed by the usual proof of  
2). Instead, 5) is proved by iterating 2). We first construct a  
maximal square S_1^2 in E intersect (-infinity,1]^2k. We then extend  
S_1^2 to a maximal square S_2^2 in E intersect (-infinity,2]^2k. We  
continue in this way, constructing squares S_1^2 containedin S_2^2  
containedin ..., and finally take the union of the S_i^2, which is  
easily seen to be a Z^+ maximal square in E.

Also Z+up IMST is strengthened by

Z+up INVARIANT MAXIMAL SQUARE THEOREM (Z^+ max). Z+up IMST(Z^+ max).  
For all k >= 1, every order invariant subset of Q^2k has a completely Z 
+up invariant Z^+ maximal square.

We show that Z+up IMST(Z^+ max) is provably equivalent to Con(SRP)  
over ACA'. In particular, Z+up IMST(Z^+ max) can be proved using  
suitable large cardinals but not in ZFC (assuming ZFC is consistent).

The unprovability of Z+up IMST(Z^+ max) remains even if we  
considerably weaken Z^+ maximality. Let p_1,...,p_r be in Q, r >= 1.  
We say that a square is p_1,...,p_r maximal in E contained in Q^2k if  
and only if for all 1 <= i <= r, the square intersect (- 
infinity,p_i]^2k is a maximal square in E intersect (-infinity,p_i]^2k.

For each p_1,...,p_r in Q, r >= 1, we consider

Z+up INVARIANT MAXIMAL SQUARE THEOREM (p_1,...,p_r max). Z+up  
IMST(p_1,...,p_r max). For all k >= 1, every order invariant subset of  
Q^2k has a completely Z+up invariant p_1,...,p_r maximal square.

We identify a particular n in Z^+ such that Z+up IMST(n max) is  
unprovable in ZFC (assuming ZFC is consistent). Specifically, we can  
set n to be any particular integer >= 2^[10]. Here 2^[1] = 2, 2^[i+1]  
= 2^2^[i]. We do not know if Z+up IMST(3 max) is provable in ZFC, or  
even in RCA_0.

We can weaken Z+up IMST(Z^+ max) further, by restating Z+up IMST(n  
max) just on the interval (-infinity,n]. This does require that we  
define complete T invariance, in the obvious way, where T does not map  
the restricted ambient spaces (-infinity,n]^2k into themselves. We  
also show that this truncated Z+up IMST(n max) is equivalent to Z+up  
IMST(n max), and lives in Q intersect (-infinity,n] with distinguished  
points 1,2,...,n.

More generally, let B be a subset of Q, We say that a square is B  
maximal in E contained in Q^2k if and only if for all p in B, the  
square is p maximal in E.

For B contained in Q, we consider

Z+up INVARIANT MAXIMAL SQUARE THEOREM (B max). Z+up IMST(B max). For  
all k >= 1, every order invariant subset of Q^2k has a completely Z+up  
invariant B maximal square.

We also consider the statements

Z+up INVARIANT MAXIMAL SQUARE THEOREM (pt max). Z+up IMST(pt max). For  
all k >= 1 and p in Q, every order invariant subset of Q^2k has a  
completely Z+up invariant p maximal square.

Z+up INVARIANT MAXIMAL SQUARE THEOREM (fin max). Z+up IMST(fin max).  
For all k,r >= 1 and p_1,...,p_r in Q, every order invariant subset of  
Q^2k has a completely Z+up invariant p_1,...,p_r maximal square.

Z+up INVARIANT MAXIMAL SQUARE THEOREM (omega max). Z+up IMST(omega  
max). For all k >= 1 and unbounded B contained in Q of type omega,  
every order invariant subset of Q^2k has a completely Z+up invariant B  
maximal square.

The strongest statement that we consider is

Z+up INVARIANT MAXIMAL SQUARE THEOREM (well max). Z+up IMST(well max).  
For all k >= 1 and well ordered B contained in Q, every order  
invariant subset of Q^2k has a completely Z+up invariant B maximal  
square.

We show that the four statements Z+up IMST(Z^+, pt, fin, omega max)  
are all provably equivalent to Con(SRP) over ACA'. We prove Z+up  
IMST(well max) in the system SRP^+.

There are two remaining parameters that are investigated in this  
paper. One is the dimension. This is indicated by writing "dim k".  
Here dim k indicates that the ambient space is Q^2k. E.g., for k >= 1,  
we have the statements

          Z+up IMST(blank, Z^+, pt, fin, omega, well max, dim k)

Also for each p_1,...,p_r in Q, r >= 1, we have the statement

          Z+up IMST(p_1,...,p_r max, dim k)

We show that for integers p = k >= 2^[10], Z+up IMST(p max, dim k) is  
unprovable in ZFC (assuming ZFC is consistent). As the integer p = k  
increases, IMST(p max, dim k) is cofinal in the SRP hierarchy, in the  
obvious sense. Here we can also truncate to Q intersect (- 
infinity,p]^2k, obtaining equivalent statements, as in the case of Z 
+up IMST(p max) discussed above.

We prove Z+up IMST(well max, dim 2), Z+up IMST(1,2 max) well within ZFC.

The second remaining parameter is the restricted shift function. We  
say that x,y in Q^m are (Q,<,Z^+) equivalent if and only if x,y are  
order equivalent, and for all 1 <= i <= m, x_i in Z^+ iff y_i in Z^+.  
The idea is that x,y are "the same from the perspective of (Q,<,Z^+)".

We say that T:Q^m into Q^m is a restricted shift function if and only if

i. For all x in Q^m, T(x) results from x by adding 1 to some (possibly  
none or all) coordinates of x.
ii. For all (Q,<,Z^+) equivalent x,y in Q^m, T(x),T(y) are (Q,<,Z^+)  
equivalent.

Note that when using T:Q^m into Q^m, m must be even, the ambient space  
is Q^m, and the dimension k = m/2. We consider

T IMST(blank, Z^+, pt, fin, omega, well max)

For p_1,...,p_r in Q, r >= 1, we consider

T IMST(p_1,...,p_r max).

For any of the above statements, we completely determine the  
restricted shift functions T for which it holds. The determination is  
stated very simply, but the verification uses ACA' + Con(SRP). In  
fact, it is equivalent to Con(SRP) over ACA'. However, for restricted  
shift functions T:Q^2 into Q^2 and T:Q^4 into Q^4, the verification is  
carried out well within ZFC.

Z+up (Z^+, pt, fin, omega max) are obviously provably equivalent to  
Pi01 sentences over ACA', since they 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. This also applies  
to each Z+up(p_1,...,p_r max), r >= 1.

There remains the important question of giving an explicitly  
arithmetical or even explicitly Pi01 form of these statements. There  
has been much progress on this, and we will take this up elsewhere.

Every one of these maximal square statements has a corresponding  
maximal clique statement where the given set E contained in Q^2k is  
replaced by a graph on Q^k. The maximal square statements easily imply  
the maximal clique statements, but the reverse is not immediate. All  
of the results proved with maximal squares are also proved with  
maximal cliques. The graph/clique terminology is quite useful, and  
most of the proofs throughout the paper use the graph/clique  
terminology.

We conclude with a list of open questions.

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

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

Harvey Friedman




More information about the FOM mailing list