[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