# [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.

"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.

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

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

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).

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.

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.

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

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