[FOM] 469: Invariant Maximaility/Incompleteness

Sun Nov 13 11:16:04 EST 2011

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

The new independence results reported in #468 have been written up in  
a preprint on my webstie, INVARIANT MAXIMAL CLIQUES AND  
INCOMPLETENESS. There have been a few revised versions, and I am  
finishing up a new one.

HOWEVER, one item has come up of particular note.

There is a way of saying this without using graphs.

The use of graphs is very elemental and very friendly even for people  
who don't like graphs. One need these notions:

graphs, cliques, maximal cliques, order equivalence/invariance, upper  
equivalence/invariance.

HOWEVER, the new way needs only

maximal squares (i.e., A x A), order equivalence/invariance, upper  
equivalence/invariance.

I am being given advice to stick with the graph formulation, and  
mention the new formulation as an alternative.

HOWEVER I NOW DISAGREE WITH THIS ADVICE.

Let me lay out the statements in both forms, and I WOULD LIKE THE  
READERS TO GIVE ME FEEDBACK AS TO WHAT THEY PREFER.

There is already an acknowledgement that the new graph free  
formulation has greater flexibility - since simply raising a dimension  
in the formulation has the effect of going from graphs to hypergraphs,  
which is normally an awkward move in graph theory. I.e., in graph  
theory, graphs are much much better than hypergraphs. However, in  
general elemental mathematics, A^p is not worse than A^2, in a setting  
where there is already an arbitrary dimension in another spot.

FEEDBACK DESPERATELY NEEDED!!

1. GRAPH FORMULATION.
INVARIANT MAXIMAL CLIQUES AND INCOMPLETENESS

Let Q be the set of rationals and Z^+ the set of positive integers.  
Let Q[a,b] be the set of rationals in the interval [a,b].

A graph is a pair G = (V,E), where V is a set and E is an irreflexive  
symmetric binary relation on V. We say that G is a graph on V. We say  
that x,y are adjacent iff E(x,y).

A clique in G is a set of vertices, where any two distinct elements  
are adjacent. A maximal clique is a clique which is not a proper  
subset of a clique.

We say that x,y in Q^k are Order Equivalent if and only if for all 1  
<= i,j <= k, x_i < x_j iff y_i < y_j. We say that S contained in Q^k  
is Order Invariant if and only if for all Order Equivalent x,y in Q^k,  
x in S iff y in S.

We that a graph G on Q^k is Order Invariant if and only if E is an  
Order Invariant subset of Q^2k.

We say that x,y in Q^k are Upper Equivalent if and only if for all 1  
<= i <= k, if x_i not= y_i then every x_j >= x_i is in Z^+ and every  
y_j >= y_i is in Z^+.

UPPER INVARIANT MAXIMAL CLIQUE THEOREM. UIMCT. For all k >= 1 and p in  
Q, every Order Invariant graph on Q[0,p]^k has an Upper Invariant  
maximal clique.

THEOREM. UIMCT is provably equivalent to Con(SRP) over ACA'.

2. NON GRAPH FORMULATION.
INVARIANT MAXIMAL CUBES AND INCOMPLETENESS

Let Q be the set of rationals and Z^+ the set of positive integers.  
Let Q[a,b] be the set of rationals in the interval [a,b].

A square in a set A is a subset of A of the form S^2. A maximal square  
in A is a square in A that is not a proper subset of a square in A.

We say that x,y in Q^k are Order Equivalent if and only if for all 1  
<= i,j <= k, x_i < x_j iff y_i < y_j. We say that S contained in Q^k  
is Order Invariant if and only if for all Order Equivalent x,y in Q^k,  
x in S iff y in S.

We say that x,y in Q^k are Upper Equivalent if and only if for all 1  
<= i <= k, if x_i not= y_i then every x_j >= x_i is in Z^+ and every  
y_j >= y_i is in Z^+.

UPPER INVARIANT MAXIMAL SQUARE THEOREM. UIMST. For all k >= 1 and p in  
Q, every Order Invariant subset of Q[0,p]^2k contains an Upper  
Invariant maximal square.

THEOREM. UIMST is provably equivalent to Con(SRP) over ACA'.

3. COMPARISONS.

The definitions of square and maximal square almost do not need to be  
made for a general audience. But the definitions of graph, clique and  
maximal clique need to be made for an audience outside combinatorics.

In section 4 below, we give a formulation avoiding these definitions.

Also, UIMST has more flexibility:

UPPER INVARIANT MAXIMAL CUBE THEOREM. UIMST. For all k,n >= 1 and p in  
Q, every Order Invariant subset of Q[0,p]^kn contains an Upper  
Invariant maximal n-cube.

The above, formulated in graphs, would need the awkward move from  
graphs to hypergraphs, that people don't like to make.

I think I may be able to get some extra mileage out of using dimension  
kn, but am not ready to report on this yet.

ALSO: The rectangle version(s) may give me mileage as well. I.e.,  
maximal S_1 x S_2, or even maximal S_1 x ... x S_n.

4. NON GRAPH FORMULATION. MORE CONCISE.
INVARIANT MAXIMAL CUBES AND INCOMPLETENESS

Let Q be the set of rationals and Z^+ the set of positive integers.  
Let Q[a,b] be the set of rationals in the interval [a,b].

We say that x,y in Q^k are Order Equivalent if and only if for all 1  
<= i,j <= k, x_i < x_j iff y_i < y_j. We say that S contained in Q^k  
is Order Invariant if and only if for all Order Equivalent x,y in Q^k,  
x in S iff y in S.

We say that x,y in Q^k are Upper Equivalent if and only if for all 1  
<= i <= k, if x_i not= y_i then every x_j >= x_i is in Z^+ and every  
y_j >= y_i is in Z^+.

UPPER INVARIANT MAXIMAL SQUARE THEOREM. UIMST. For all k >= 1 and p in  
Q, every Order Invariant subset of Q[0,p]^2k contains an Upper  
Invariant maximal S^2.

UPPER INVARIANT MAXIMAL CUBE THEOREM. UIMCT. For all k,n >= 1 and p in  
Q, every Order Invariant subset of Q[0,p]^kn contains an Upper  
Invariant maximal S^n.

UPPER INVARIANT MAXIMAL RECTANGLE THEOREM. UIMST. For all k >= 1 and p  
in Q, every Order Invariant subset of Q[0,p]^2k contains an Upper  
Invariant maximal rectangle S x T.

UPPER INVARIANT MAXIMAL RECTANGLE THEOREM. UIMST. For all k >= 1 and p  
in Q, every Order Invariant subset of Q[0,p]^kn contains an Upper  
Invariant maximal rectangle S_1 x ... x S_n.

THEOREM. UIMST is provably equivalent to Con(SRP) over ACA'.

THEOREM. UIMCT is provably equivalent to Con(SRP) over ACA'.

5. UPPER EQUIVALENCE/INVARIANCE?

There is a whole development in the latest revision to come out, with  
a simplified and more powerful treatment of Upper Equivalence/ 
Invariance that shows how these notions arise canonically from simpler  
notions. But this has nothing to do with the issue: graphs or no  
graphs? that I am raising here.

COMMENTS, FEEDBACK??

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

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

Harvey Friedman