# [FOM] 481:Complementation and Incompleteness

Harvey Friedman friedman at math.ohio-state.edu
Wed Feb 15 01:09:41 EST 2012

```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].

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

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
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
```