[FOM] 481:Complementation and Incompleteness

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

This is a much improved version of 480: Order Equivalence and  
Incompleteness.

For *explicitly* Pi01 incompleteness, we now prefer the Exotic  
Complementation Theorem (finite) and Exotic Complementation Theorem  
(finite,3), below.

For *implicitly* Pi01 incompleteness, or Pi01 Incompleteness relative  
to predicate calculus, we prefer the highly strategic infinite  
statements in http://www.cs.nyu.edu/pipermail/fom/2012-February/016165.html 
  (maximal cliques and maximal squares).

COMPLEMENTATION AND INCOMPLETENESS
by
Harvey M. Friedman
February 15, 2012

*PROPOSITIONS*

COMPLEMENTATION THEOREM (infinite). For all R containedin Z+^2k, there  
exists a unique A containedin Z+^k, such that R<[A] = c(A).

COMPLEMENTATION THEOREM (finite). For all R containedin {1,...,n}^2k,  
there exists a unique A containedin {1,...,n}^k, such that R<[A] = c(A).

EXOTIC COMPLEMENTATION THEOREM (infinite). For all R containedin Z 
+^2k, there exists A containedin Z+^k, such that R<[A]^r and c(A)^r  
are similar over some infinite set disjoint from fld(A)+1.

EXOTIC COMPLEMENTATION THEOREM (concrete infinite). For all order  
invariant R containedin Z+^2k, there exists A containedin Z+^k, such  
that R<[A]^3 and c(A)^3 are similar over some infinite geometric  
progression disjoint from fld(A)+1.

EXOTIC COMPLEMENTATION THEOREM (finite). For all order invariant R  
containedin {1,...,n}^2k, there exists A containedin {1,...,n}^k, such  
that R<[A]^r and c(A)^r are similar over some geometric progression in  
{1,...,n}\(fld(A)+1) of length at least log(n)/8kr.

EXOTIC COMPLEMENTATION THEOREM (finite,3). For all order invariant R  
containedin {1,...,n}^2k, there exists A containedin {1,...,n}^k, such  
that R<[A]^3 and c(A)^3 are similar over some geometric progression in  
{1,...,n}\(fld(A)+1) of length at least log(n)/8k.

*DEFINITIONS*

We use Z+ for the set of all positive integers. For A containedin Z 
+^k, we write fld(A) containedin Z+ for the set of all coordinates of  
elements of A.

Let R containedin Z+^2k. We treat R as a binary relation on Z+^k. For  
A containedin Z+^k, we define

c(A) = Z+^k\A.
R[A] = {y: (therexists x in A)(R(x,y)).
R<[A] = {y: (therexists x in A)(R(x,y) and max(x) < max(y))}.

c(A) is the "complement of A".
R[A] is the "image of A under R".
R<[A] is the "upper image of A under R." Here < appears as a subscript.

We also make the above definitions for R containedin {1,...,n}^2k and  
A containedin {1,...,n}^k, viewing {1,...,n}^2k, {1,...,n}^k as the  
ambient spaces instead of Z+^2k, Z+^k. Here we simply replace all  
occurrences of Z+ with {1,...,n}.

Let x,y be finite or infinite sequences from Z+. We say that x,y are  
order equivalent if and only if

i. 1 <= lth(x) = lth(y) <= infinity.
ii. for all 1 <= i,j < lth(x)+1, x_i < x_j iff y_i < y_j.

Let A containedin Z+^k. We say that A is order invariant if and only  
if for all order equivalent x,y in Z+^k, x in A implies y in A.

Let A containedin {1,...,n}^k. We say that A is order invariant if and  
only if for all order equivalent x,y in {1,...,n}^k, x in A implies y  
in A.

We work with order invariant R containedin Z+^2k and order invariant R  
containedin {1,...,n}^2k, viewed as order invariant binary relations  
on Z+^k, and order invariant binary relations on {1,...,n}^k.

Note that the number of order invariant subsets of Z+^k, or  
{1,...,n}^k, is finite and depends only on k.

Let x,y be finite sequences from Z+. We say that x,y are order  
equivalent over E if and only if

i. E is a subset of Z+.
ii. lth(x) = lth(y) >= 1.
iii. (x,alpha), (y,alpha) are order equivalent.

where alpha is the strictly increasing enumeration of E. Here any  
enumeration of E can be used.

Let A,B be subsets of Z+^k. We say that A,B are similar over E if and  
only if

i. E is a subset of Z+.
ii. every element of A union B is order equivalent over E to some  
element of A intersect B.

Note that similarity over E is stronger (and shorter to write down)  
than order equivalence over E, which is "every element of A is order  
equivalent over E to some element of B, and every element of B is  
order equivalent over E to some element of A".

*RESULTS*

THEOREM 1. The Complementation Theorem (infinite) is provable in  
RCA_0. The Complementation Theorem (finite) is provable in EFA =  
exponential function arithmetic.

THEOREM 2. The Exotic Complementation Theorem (infinite), Exotic  
Complementation Theorem (concrete infinite), Exotic Complementation  
Theorem (finite), and Exotic Complementation Theorem (finite,3), are  
each provably equivalent to Con(SMAH) over ACA'. They are provable are  
provable in SMAH+, but not in any consistent fragment of SMAH that  
proves ACA'.

SMAH+ = ZFC + "for all k there exists a strongly k-Mahlo cardinal".

SMAH = ZFC + {there exists a strongly k-Mahlo cardinal}_k.

*TEMPLATES*

We can set up a template for each of the six Propositions:

TEMPLATE 1. For all R containedin Z+^2k, there exists a unique A  
containedin Z+^k, such that EXPRESSION(R,A) = EXPRESSION'(R,A).

TEMPLATE 2. For all R containedin {1,...,n}^2k, there exists a unique  
A containedin {1,...,n}^k, such that EXPRESSION(R,A) = EXPRESSION'(R,A).

TEMPLATE 3. For all R containedin Z+^2k, there exists A containedin Z 
+^k, such that EXPRESSION(R,A)^r and EXPRESSION'(R,A)^r are similar  
over some infinite set disjoint from fld(A)+1.

TEMPLATE 4. For all order invariant R containedin Z+^2k, there exists  
A containedin Z+^k, such that EXPRESSION(R,A)^3 and EXPRESSION'(R,A)^3  
are similar over some infinite geometric progression disjoint from  
fld(A)+1.

TEMPLATE 5. For all order invariant R containedin {1,...,n}^2k, there  
exists A containedin {1,...,n}^k, such that EXPRESSION(R,A)^r and  
EXPRESSION'(R,A)^r are similar over some geometric progression in  
{1,...,n}\(fld(A)+1) of length at least log(n)/8kr.

TEMPLATE 6. For all order invariant R containedin {1,...,n}^2k, there  
exists A containedin {1,...,n}^k, such that EXPRESSION(R,A)^3 and  
EXPRESSION'(R,A)^3 are similar over some geometric progression in  
{1,...,n}\(fld(A)+1) of length at least log(n)/8k.

We can investigate these Templates for various natural finite sets of  
expressions in R,A. The finite sets of expressions can be expanded to  
create greater challenges.

It would seem that for natural finite sets of expressions in R,A, all  
six of these Templates have equivalent truth values.

A good start is to use the Boolean combinations of A,R<[A], and then  
graduate to the Boolean combinations of A,R<[A],R[A].

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 481st 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
474: Invariant Maximal Squares  01/12/12  9:46AM
475: Invariant Functions and Incompleteness  1/16/12  5:57PM
476: Maximality, CHoice, and Incompleteness  1/23/12  11:52AM
477: TYPO  1/23/12  4:36PM
478: Maximality, Choice, and Incompleteness  2/2/12  5:45AM
479: Explicitly Pi01 Incompleteness  2/12/12  9:16AM
480: Order Equivalence and Incompleteness

Harvey Friedman