[FOM] 474:Invariant Maximal Squares

Harvey Friedman friedman at math.ohio-state.edu
Wed Jan 11 01:09:40 EST 2012


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

SUMMARY OF NEW DEVELOPMENTS FOR PREVIOUS READERS OF http://www.cs.nyu.edu/pipermail/fom/2011-December/016037.html
FOR OTHER READERS, THE ABSTRACT BELOW IS SELF CONTAINED.

There are advances and breakthroughs on these fronts:

1. We have finally managed to get reasonable specific integers in the  
independent statement. I expect these numbers to be lowered somewhat  
from what I am claiming here, in the final manuscript.
2. We have fixed on a particular invariance condition that is the most  
immediately understandable. We still study alternative invariance  
conditions as well. For the headline statement we use complete Z+up  
invariance, whereas the stronger notion of upper integral invariance  
is also studied, and has a special place in the theory as the  
strongest natural invariance condition that can be used.
3. We have also fixed on an immediately understandable explicitly  
finite form involving finite independent dominators from graph theory.  
We take an utterly obvious explicitly finite form, show that it is  
weak, and then strengthen it by imposing a basic inequality on the  
finite dominator. The result is explicitly Pi01 and unprovable in ZFC.

The following is provable using large cardinals, but not in ZFC  
(assuming ZFC is consistent).

EVERY ORDER INVARIANT SUBSET OF Q[0,16]^32 HAS A COMPLETELY Z+up  
INVARIANT MAXIMAL SQUARE.

The above is proved in ZFC for Q[0,k]^2, and Q[0,2]^n.

On the printed page, Z+up appears as Z with superscript + followed by  
an up arrow, and is defined momentarily.

We have fixed on the following unified general setup for invariance.  
Let R be any binary relation, and K be any set (ambient space). We say  
that A contained in K is R invariant if and only if for all R related  
x,y from K, x in A implies y in A. We say that E contained in K is  
completely R invariant if and only if for all R related x,y from K, x  
in A iff y in A. For this purpose, functions are treated as relations.

Let Q* be the set of all finite sequences from Q. Z+up:Q* into Q* is  
given by Z+up(x) = the result of adding 1 to all coordinates greater  
than those outside Z+. The statement uses complete Z+up invariance,  
with the implied ambient space Q[0,16]^32.

Z+up is an example of what we call a restricted shift function. I.e.,  
we add 1 only to some selected coordinates. We consider restricted  
shift functions based on a reasonable selection criterion. We show  
that the use of Z+up in the above statement is best possible.

The (essentially equivalent) graph theoretic formulation is:

EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16 HAS A COMPLETELY Z+up  
INVARIANT MAXIMAL CLIQUE.

Here the adjacency relation of graphs are irreflexive and symmetric  
subsets of (Q[0,16]^16)^2 = Q[0,16]^32 (with vertex set Q[0,16]). The  
cliques are subsets of Q[0,16]^16. Thus here the implied ambient space  
for the edge set is Q[0,16]^32, and the implied ambient space for the  
clique is Q[0,16]^16.

The square formulation has the advantage of using only a single  
ambient space. It also avoids basic graph theoretic terminology, which  
still makes some mathematicians uncomfortable. But for mathematicians  
fully comfortable with graphs, the graph formulation is likely  
preferable.

Note that this assertion (both the square and the clique forms) is  
rather obviously equivalent to the consistency of a finite list of AE  
sentences in first order predicate calculus with a single 16-ary  
relation symbol, constants 0,1,...,16, and the binary relation symbol <.

This predicate calculus construction clearly establishes that the  
statement is implicitly Pi01. However, there is the issue of  
explicitly Pi01 forms.

For this, we continue to use the dual to maximal cliques, which is  
independent dominators.

An independent set of vertices of G is a set A of vertices, where no  
two elements of A are adjacent. A dominator of G is a set A of  
vertices, where every x outside A is adjacent to some y in A.

Here is the dual statement:

EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16 HAS A COMPLETELY Z+up  
INVARIANT INDEPENDENT DOMINATOR.

An entirely obvious finite form is provable in EFA:

IN EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16, EVERY FINITE SET HAS A  
COMPLETELY Z+up INVARIANT FINITE INDEPENDENT DOMINATOR.

We now impose an inequality on the finite dominators.

For x in Q*, define d(x) to be the least positive n such that nx is an  
integer.

An f-dominator of a set A of vertices is a set B of vertices, where

i. (forall x in A\B)(therexists y in B)(y is adjacent to x and d(y) <=  
f(d(x))).
ii. (forall y in B)(therexists x in A)(d(x) <= f(d(y)).

IN EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16, EVERY FINITE SET HAS A  
COMPLETELY Z+up INVARIANT INDEPENDENT 256^n-DOMINATOR.

This statement is explicitly Pi01, provable using large cardinals, but  
not provable in ZFC (assuming ZFC is consistent).

We can also equivalently use upper integral invariance.

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

INVARIANT MAXIMAL SQUARES AND INCOMPLETENESS
by
Harvey M. Friedman
January 11, 2011

Abstract. We prove that every order invariant subset of Q[0,16]^32 has  
a completely Z+up invariant maximal square. Here Q[0,16] consists of  
the rationals in [0,16], and Z+up adds 1 to every coordinate greater  
than those 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 the statement cannot be proved in  
ZFC (assuming ZFC is free of contradiction).

1. Introduction.
2. Maximal squares, graphs, maximal cliques, independent dominators.
3. Order, Z+up, upper integral invariance.
4. UIMST for Q[0,2]^k and Q[0,k]^2.
5. The stationary Ramsey property.
6. UIMST using large cardinals.
7. Reversal of Z+up IMCT for Q[0,16]^16.
8. Finite Z+up IIDT, UIIDT.
9. Z+up and UIM are canonical.
10. Open questions.

1. 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 subset of X^2 has a maximal square.

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 if X is countable, as we can enumerate  
X^2 and make the so called greedy construction of the S contained in  
X^2 such that S^2 is maximal.

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

   2) Every subset of Q[0,k]^2n has a maximal square.

Invariance conditions occur throughout mathematics. Here is a general  
unified setup.

Let R be a binary relation (set of ordered pairs), and K be a set  
(ambient space). We say that A is R invariant if and only if for all R  
related x,y in K, we have x in A implies y in A. We say that A is  
completely R invariant if and only if for all R related x,y from K, we  
have x in A iff y in A.

For (complete) invariance, we view functions as relations. We consider  
cases of

   3) Every (completely) Invariant_1 subset of Q[0,k]^n has an  
(completely) Invariant_2 maximal square.

In particular, we consider statements of the form

   4) Every (completely) R invariant subset of Q[0,k]^n has a  
(completely) F invariant maximal square.

where R is order equivalence on Q*, and F is the function Z+up:Q* into  
Q*. Here Q* is the set of all finite sequences from Q. These are  
defined in section 2.

In 4), the ambient space for both R and F invariance is Q[0,k]^n.

FOR FOM READERS: Here are the relevant definitions.

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.

Z+up(x) is the result of adding 1 to all coordinates greater than  
those outside Z+.

As indicated in the Abstract, we investigate

Z+up INVARIANT MAXIMAL SQUARE THEOREM (16,32). Z+up IMST(16,32). Every  
order invariant subset of Q[0,16]^32 has a completely Z+up invariant  
maximal square.

In section 6, we prove Z+up IMST(16,32) using large cardinal  
hypotheses introduced in section 5. In section 7, we show that Z+up  
(IMST(16,32) is not provable in ZFC (assuming ZFC is consistent).

Z+up is an example of what we call a restricted shift function. I.e.,  
we add 1 only to some selected coordinates. We consider restricted  
shift functions based on a reasonable selection criterion. In section  
9, we show that the use of Z+up in the above statement is best possible.

We also treat the more general

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

using stronger large cardinal hypotheses from section 5. In  
particular, we show in section 6 that

i. Z+up IMST(16,32) is provable in SRP_16, but not in ZFC (assuming  
ZFC is consistent).
ii. Z+up IMST is provably equivalent to Con(SRP) over ACA'.

In section 4, we prove Z+up IMST(k,2) and Z+up (2,n) in ZFC.

FOR FOM READERS:

"SRP" is read stationary Ramsey property. This asserts that every  
partition of the unordered n-tuples from limit ordinal lambda into two  
pieces has a stationary homogeneous set.

SRP = ZFC + {there exists an ordinal with the k-SRP}_k. SRP_k = ZFC +  
{there exists an ordinal with k-SRP}.

ACA' is ACA_0 + "for all n,x, the n-th Turing jump of x exists".

We also treat closely related graph theoretic formulations. We use  
graphs, cliques, and dominators (see section 2).

Z+up INVARIANT MAXIMAL CLIQUE THEOREM (16,16). Z+up IMCT(16,16). Every  
order invariant subset of Q[0,16]^16 has a completely Z+up invariant  
maximal clique.

Z+up INVARIANT INDEPENDENT DOMINATOR THEOREM (16,16). Z+up  
IIDT(16,16). Every order invariant subset of Q[0,16]^16 has a  
completely Z+up invariant independent dominator.

Z+up INVARIANT MAXIMAL CLIQUE THEOREM. Z+up IMCT. For all k,n >= 1,  
every order invariant subset of Q[0,k]^n has a completely Z+up  
invariant maximal clique.

Z+up INVARIANT MAXIMAL DOMINATOR THEOREM. Z+up IIDT. For all k,n >= 1,  
every order invariant subset of Q[0,k]^n has a completely Z+up  
invariant independent dominator.

In section 3, we observe that, over RCA_0, Z+up IMCT(16,16) and Z+up  
IIDT(16,16) are equivalent, and follow from Z+up IMST(16,32). Also  
over RCA_0, Z+up IMCT, Z+up IIDT, and Z+ IMST are provably equivalent.

FOR FOM READERS:

A graph is a pair G = (V,E), where V is a set of vertices, and E  
contained in Z^2 is an irreflexive symmetric binary relation on V. E  
is called the edge relation or the adjacency relation.

A clique in G is an S contained in V, where any two distinct x,y in S  
are adjacent.

An independent set in G is an S contained in V, where any two x,y in S  
are not adjacent.

A dominator in G is a D contained in V such that every x in V\D is  
adjacent to some y in D.

A maximal clique in G is a clique in G which is not a proper subset of  
any clique in G.

An independent dominator in G is a dominator in G that is independent  
in G.

In section 3, we introduce a natural strengthening of Z+up invariance,  
called upper integral invariance. This is based on the equivalence  
relation UIE = upper integral equivalence on Q*. We write UIMST,  
UIMCT, UIIDT for Z+up IMST, Z+up IMCT, Z+up IIDT using UIE invariance  
instead of Z+up invariance. The first three trivially imply the latter  
three, also with fixed parameters k,n. In fact, in section 3, we show  
that all six statements are provably equivalent in RCA_0. Equivalence  
for fixed k,n is less clear, but we show that k,n+1 for the first  
three follow from k,n for the latter three within RCA_0. (It is likely  
that there is equivalence without using n+1 - I will address this in  
the final manuscript).

FOR FOM READERS:

x,y in Q* are upper integral equivalent if and only if x,y are order  
equivalent, and for all 1 <= i <= lth(x), if x_i not= x_j then every  
x_j >= x_i and every y_j >= y_i is in Z+. Note that x,F(x) are upper  
integral equivalent.

We now come to explicitly Pi01 forms. An entirely obvious finite form is

IN EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16, EVERY FINITE SET HAS A  
COMPLETELY Z+up INVARIANT FINITE INDEPENDENT DOMINATOR.

The above explicitly Pi01 statement is shown to be provable in EFA.

We now strengthen the notion of dominator by imposing an inequality.

For x in Q*, define d(x) to be the least positive n such that nx is an  
integer.

An f-dominator of a set A of vertices is a set B of vertices, where

i. (forall x in A\B)(therexists y in B)(y is adjacent to x and d(y) <=  
f(d(x))).
ii. (forall y in B)(therexists x in A)(d(x) <= f(d(y)).

IN EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16, EVERY FINITE SET HAS A  
COMPLETELY Z+up INVARIANT INDEPENDENT 256^n-DOMINATOR.

This statement is obviously explicitly Pi01. It is provably equivalent  
to Z+up IIDT(16,16) in WKL_0. Thus it is provable using large  
cardinals, but not in ZFC (assuming ZFC is consistent). The 256^n  
function is safe, and is expected to be sharply reduced.

We can also equivalently use upper integral invariance:

IN EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16, EVERY FINITE SET HAS AN  
UPPER INTEGRAL INVARIANT INDEPENDENT 256^n-DOMINATOR.

The 256^n function is safe, and is expected to be sharply reduced.

In section 9, we show that upper integral invariance is the strongest  
reasonable invariance condition that we can use, in an appropriate  
sense, for all of the statements considered.

FOR FOM READERS:

The Q[0,16]^32 and Q[0,16]^16 statements can be proved in SRP_16, but  
imply Con(ZFC) over ACA'. It appears that they imply Con(ZFC + SRP_5)  
over ACA'. At the moment, in order to get outside of ZFC, I have to  
overshoot like this.

The statements with quantification over all k,n are provably  
equivalent to Con(SRP) over ACA'. For fixed k,n, SRP_max(k,n)  
suffices. In fact, we can get away with min(k-1,n-1)-subtle cardinals.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 474th 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
473: Invariant Maximal Powers/Incompleteness 1  12/7/11  5:13AMs

Harvey Friedman


More information about the FOM mailing list