[FOM] 472:Shift Invariant Maximal Squares/Incompleteness 2
Harvey Friedman
friedman at math.ohio-state.edu
Mon Nov 28 21:05:42 EST 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
*****************************************
WE HAVE KEPT THE PREVIOUS MATERIAL, BUT HAVE INSERTED THE NEW
"INVARIANT MAXIMAL SQUARE TOWER THEOREM" IN AS OUR LEAD UNPROVABLE
STATEMENT.
*****************************************
SHIFT INVARIANT MAXIMAL SQUARES AND INCOMPLETENESS
by
Harvey M. Friedman
November 28, 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 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 an extension, the Z
+up Invariant Maximal Square Tower Theorem, is in fact equivalent to
this assumption. As a consequence, this variant is provable from a
large cardinal hypothesis, yet not provable in ZFC (assuming ZFC is
consistent).
1. Introduction.
2. Maximal squares, order invariance, shift functions.
3. Graph and cliques.
4. Theorems within ZFC.
4.1. In one and two dimensions.
4.2. In higher dimensions.
5. The stationary Ramsey property.
6. Proof of the Z+up Invariant Maximal Square/Clique Tower Theorem.
7. Reversal of the Z+up Invariant Maximal Square/Clique Tower Theorem.
8. Further results.
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 general set theoretic 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.
a. Relational. 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, if x in A
then y in A.
b. Functional. Let T be a function. We say that A is T invariant if
and only if for all x in A, T(x) in A.
We introduce invariance conditions in 2). We consider cases of
3) for all k >= 1, every Invariant_1 subset of Q^2k has an
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 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.
Here x,y in Q^2k are order equivalent if and only if for all 1 <= i,j
<= 2k, x_i < x_j iff y_i < y_j.
For x in Q^2k, 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" on Q^2k, 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. In particular, use of
the shift function, where we add 1 to all coordinates of the argument,
leads to trivially false statements.
Z+up INVARIANT MAXIMAL SQUARE THEOREM. Z+up IMST. For all k >= 1,
every order invariant subset of Q^2k has a 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.
The main focus of this paper is on an obvious extension of Z+up IMST
using towers. This is the Z+up Invariant Maximal Square Tower Theorem,
or Z+up IMTT. We prove the Z+up IMSTT using the same assumption that
goes well beyond ZFC, but also show that this is required. E.g., Z+up
IMSTT is not provable in ZFC (assuming ZFC is consistent). In fact, we
show that Z+up IMSTT is provably equivalent to Con(SRP) over ACA'.
We start with a well known sharpening of 2).
5) for all k >= 1, in every subset of Q^2k, every square is
contained in a maximal square
A tower of sets is a saquence of finite or infinite length, where each
term is a subset of the succeeding terms.
The following are easy consequence of 5), obtained by iteration.
6) for all k >= 1, every tower of subsets of Q^2k has a tower of
maximal squares
Z+up INVARIANT MAXIMAL SQUARE TOWER THEOREM. Z+up IMSTT. Every tower
of order invariant subsets of Q^2k has a tower of Z+up invariant
maximal squares.
Note that the towers in question are of finite length, since for each
k >= 1, there are finitely many order invariant subsets of Q^2k.
We show that Z+up IMSTT is provably equivalent to Con(SRP) over ACA'.
In particular, Z+up IMSTT can be proved using suitable large cardinals
but not in ZFC (assuming ZFC is consistent).
We introduce parameters k,n >= 1 as follows.
Z+up INVARIANT MAXIMAL SQUARE TOWER THEOREM (dim k). Z+up IMSTT(dim
k). Every tower of order invariant subsets of Q^2k has a tower of Z+up
invariant maximal squares.
Z+up INVARIANT MAXIMAL SQUARE TOWER THEOREM (lth n). Z+up IMSTT(lth
n). For all k >= 1, every length n tower of order invariant subsets of
Q^2k has a tower of Z+up invariant maximal squares.
Z+up INVARIANT MAXIMAL SQUARE TOWER THEOREM (dim k, lth n). Z+up
IMSTT(dim k, lth n). Every length n tower of order invariant subsets
of Q^2k has a tower of Z+up invariant maximal squares.
We prove Z+up IMSTT(dim <=2) well within ZFC.
We give some estimates as to how much of the SRP hierarchy is
necessary and/or sufficient to prove Z+up IMSTT(dim k), Z+up IMSTT(lth
n), Z+up IMSTT(dim k, lth n). In fact, we show that Z+up IMSTT(dim 8,
lth 8) is unprovable in ZFC (assuming ZFC is consistent).
There is another extension of Z+up IMSTT which does not use towers,
but does need a strengthening of maximality. Let p in Q union
{infinity}. We say that S^2 is a p maximal square in E contained in
Q^2k if and only if S^2 contained in (-infinity,p]^2k is a maximal
square in E contained in (-infinity,p]^2k. Let B contained in Q union
{infinity}. We say that S^2 is a B maximal square in E contained in
Q^2k if and only if for all p in B, S^2 is a p maximal square in E.
Note that S^2 is an infinity maximal square in E contained in Q^2k if
and only if S^2 is a maximal square in E. It is easily shown that if B
contained in Q has no finite upper bound, then any B maximal square in
E contained in Q^2k is a maximal square in E.
Let B contained in Q union {infinity}. We consider the following
variant of 2).
7) for all k >= 1, every subset of Q^2k has a B maximal square.
We show that 7) holds if and only if B is well ordered. Consider the
following.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (Z+up max). Z+up IMST(Z^+ max).
For all k >= 1, every order invariant subset of Q^2k has a Z+up
invariant B maximal square.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (fin Z^+ max). Z+up IMST(fin Z^+
max). For all k >= 1 and finite B contained in Z^+, every order
invariant subset of Q^2k has a Z+up invariant B maximal square.
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 Z+up invariant B maximal square.
We prove that Z+up IMST(fin Z^+ max) and Z+up IMST(Z^+ max) are
equivalent to Con(SRP) over ACA'. Thus they have the same
metamathematical status as Z+up IMSTT. In particular, all three are
provably equivalent in ACA'. We prove Z+ IMST(well max) using SRP^+.
We can also fix the dimension k in these statements. We prove Z+up
IMST(dim <=2, well max) well within ZFC.
We can go further, and use the n max, n in Z^+. We can show that this
is strong if we strengthen invariance to complete invariance. This
standard notion is defined as follows.
Let T:V into V. We say that K contained in V is completely T invariant
if and only if for all x in V, x in K iff T(x) in K.
Z+up IMSTT, Z+up IMST(Z^+ max), Z+up IMST(fin Z^+ max), Z+up IMST(well
max) remain unaffected when we use complete Z+up invariance instead of
Z+up invariance.
We now come to
Z+up INVARIANT MAXIMAL SQUARE THEOREM (pt Z^+ max). Z+up IMST(pt Z^+
max). For all k,n >= 1, every order invariant subset of Q^2k has a
completely Z+up invariant n maximal square.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (dim k, n max). Z+up IMST(dim k,
n max). Every order invariant subset of Q^2k has a completely Z+up
invariant n maximal square.
We show that Z+up IMST(pt Z^+ max) is also provably equivalent to
Con(SRP) over ACA'.
We give some estimates as to how much of the SRP hierarchy is
necessary and/or sufficient to prove Z+up IMST(dim k, n max). In fact,
we show that Z+up IMSTT(dim 8, 8 max) is unprovable in ZFC (assuming
ZFC is consistent).
We can also use the Q[0,n]^2k for the ambient space. Here Q[0,n] = Q
intersect [0,n]. This has the advantage of simplifying the setting, in
that this amounts to a dense linear ordering with endpoints, and a
finite number of distinguished elements (including the right
endpoint). Of course, now our restricted shift function Z+up does not
map the ambient space into itself. Nevertheless, we still use Z+up in
the following way.
We say that K contained in Q[0,n]^2k is relatively Z+up invariant if
and only if for all x,Z+up(x) in Q[0,n]^2k, we have x in K iff Z+up(x)
in K.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (intervals). Z+up
IMST(intervals). For all k,n >= 1, every order invariant subset of
Q[0,n]^2k has a relatively Z+up invariant maximal square.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (dim k, intervals). Z+up
IMST(intervals). For all n >= 1, every order invariant subset of
Q[0,n]^2k has a relatively Z+up invariant maximal square.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (Q[0,n]). Z+up IMST(Q[0,n]). For
all k >= 1, every order invariant subset of Q[0,n]^2k has a relatively
Z+up invariant maximal square.
Z+up INVARIANT MAXIMAL SQUARE THEOREM (dim k, Q[0,n]). Z+up IMST(dim
k, Q[0,n]). Every order invariant subset of Q[0,n]^2k has a relatively
Z+up invariant maximal square.
We show that Z+up IMST(intervals) is again provably equivalent to
COn(SRP) over ACA'.
We give some estimates as to how much of the SRP hierarchy is
necessary and/or sufficient to prove Z+up IMST(dim k, Q[0,n]). In
fact, we show that Z+up IMST(dim 8, Q[0,8]) is unprovable in ZFC
(assuming ZFC is consistent).
We say that T:Q^2k into Q^2k is a restricted shift function if and
only if
i. For all x in Q^2k, 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^2k, T(x),T(y) are (Q,<,Z^+)
equivalent.
For Z+up IMSTT, Z+up IMST(Z^+ max), and many other of the above
statements, we completely determine the restricted shift functions T
for which it holds; i.e., when Z+up on Q^2k is replaced by T:Q^2k into
Q^2k. 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 IMST(Z^+ max) is obviously provably equivalent to Pi01 sentences
over ACA', since it is provably equivalent to Con(SRP) over ACA'. Thus
it is implicitly Pi01. However, we can see directly that it is
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.
There remains the important question of giving an explicitly
arithmetical or even explicitly Pi01 form of these statements. We have
made much progress on this, and we will report on this 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 472nd 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
Harvey Friedman
More information about the FOM
mailing list