[FOM] 480:Order Equivalence and Incompleteness
Harvey Friedman
friedman at math.ohio-state.edu
Sun Feb 12 22:31:15 EST 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
****************************************
For explicitly Pi01 Incompleteness, we now prefer Proposition 4,
below, to all previous versions.
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).
ORDER EQUIVALENCE AND INCOMPLETENESS
by
Harvey M. Friedman
February 12, 2012
1. R<A = c(A).
2. Order equivalence.
3. Pi01 incompleteness.
4. Templates.
1. R<A = c(A).
Here < appears as a subscript.
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.
RA = {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".
RA is the "image of A under R".
R<A is the "upper image of A under R."
We also make the above definitions for R containedin {1,...,n}^2k and
A containedin {1,...,n}^k, treating {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}.
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).
The first is provable in RCA_0. The second is provable in EFA =
exponential function arithmetic.
2. ORDER EQUIVALENCE.
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 x,y be finite sequences from Z+, and alpha be a finite or infinite
sequence from Z+. we say that x,y are order equivalent over alpha if
and only if
i. lth(x) = lth(y).
ii. (x,alpha), (y,alpha) are order equivalent.
Let A containedin Z+^m. We say that A is order invariant if and only
if for all order equivalent x,y in Z+^m, x in A implies y in A.
Let A containedin {1,...,n}^m. We say that A is order invariant if and
only if for all order equivalent x,y in {1,...,n}^m, x in A implies y
in A.
We will focus on order invariant R containedin Z+^2k and order
invariant R containedin {1,...,n}^2k, 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+^m, or
{1,...,n}^m, is finite and depends only on m.
3. Pi01 INCOMPLETENESS.
We start with the infinite version. The finite version is virtually
identical. Just as in the case of the Complementation Theorem
(infinite) and the Complementation Theorem (finite).
The following is a weakening of the Complementation Theorem (infinite).
THEOREM 1. For all order invariant R containedin Z+^2k, there exists
nonempty A containedin Z+^k, such that A x A x R<A and A x A x c(A)
are order equivalent over 1!,2!,... .
In fact, the two triple products can be taken to be identical, by the
Complementation Theorem (infinite).
PROPOSITION 2. For all order invariant R containedin Z+^2k, there
exists nonempty A containedin {1,...,(8k)!-2,(8k)!,...,}^k, such that
A x A x R<A and A x A x c(A) are order equivalent over 1!,2!,... .
Now for the finite statements.
THEOREM 3. For all order invariant R containedin {1,...,n}^2k, there
exists nonempty A containedin {1,...,n}^k, such that A x A x R<A and A
x A x c(A) are order equivalent over 1!,2!,...,n!.
In fact, the two triple products can be taken to be equal, by the
Complementation Theorem (finite).
PROPOSITION 4. For all order invariant R containedin {1,...,n}^2k,
there exists nonempty A containedin {1,...,(8k)!-2,(8k)!,...,n}^k,
such that A x A x R<A and A x A x c(A) are order equivalent over 1!,
2!,...,n!.
Here we use (8k)! as an extremely crude but safe quantity. As things
stabilize, we will see what we really need here.
THEOREM 5. Propositions 2,4 are provably equivalent to Con(SMAH) over
ACA'. Propositions 2,4 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.
4. TEMPLATES.
The structure of Proposition 4 suggests that we can template the
specialized features that appear, and ask for a complete determination
of what can be used.
For this purpose, it makes sense to do a little more streamlining.
First all, let us first consider the following alternative form.
PROPOSITION 6. Let p,n >> k >= 1. For all order invariant R
containedin {1,...,n}^2k, there exists A containedin
{1,...,p-2,p,...,n}^k, such that A x A x R<A and A x A x c(A) are
order equivalent over 1,p,p^2,...,p^n.
In Proposition 6, e.g., p,n >= (8kr)! more than suffices - or just p
>= (8kr)!. Theorem 5 also holds for Proposition 6.
We can also make this change, among many others, without affecting the
metamathematical status:
PROPOSITION 7. Let p,n >> k >= 1. For all order invariant R
containedin {1,...,n}^2k, there exists A containedin {1,...,n}^k, such
that A x A x R<A and A x A\{p-1}^k x c(A) are order equivalent over
1,p,p^2,...,p^n.
This suggests the following informal template:
INFORMAL TEMPLATE. Let p,n >> k >= 1. For all order invariant R
contained in {1,...,n}^2k, there exists A containedin {1,...,n}^k,
such that EXPRESSION and EXPRESSION' are order equivalent over
1,p,p^2,...,p^n.
It is natural to consider the expressions to be Cartesian products of
a modest finite list of basic expressions involving A,R,p. Then
enlarging the basic expressions. It makes sense to control the list of
basic expressions, and the length of the Cartesian products. Also,
considering more than one pair of expressions in template instances.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 480th 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
Harvey Friedman
More information about the FOM
mailing list