[FOM] 482:Maximality, Choice, and Incompleteness 2
Harvey Friedman
friedman at math.ohio-state.edu
Sat Feb 18 17:40:55 EST 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
****************************************
The way we stated B3 and C3 in http://www.cs.nyu.edu/pipermail/fom/2012-February/016165.html
is too strong. The Z+up commuting function notion is too strong in
this context.
The obvious fix is to use "completely Z+up invariant detached choice
function" just as we used "completely Z+up invariant maximal square"
and "completely Z+up invariant maximal clique".
We restate http://www.cs.nyu.edu/pipermail/fom/2012-February/
016165.html with changes of terminology and notation.
I am no longer convinced that the finite statement in http://www.cs.nyu.edu/pipermail/fom/2012-February/016180.html
is more convincing than the present finite statement D. Usually,
these rivalries get settled when there is a later substantial advance
in one of them.
*****************************************
BASIC THEOREMS.
A1. Every binary relation contains a maximal square.
A2. Every graph has a maximal clique.
A3. Every reflexive symmetric relation has a detached choice function.
NOTE: We only care about the countable case, which can be proved very
explicitly - see the NOTES below.
INFINITE UNPROVABLE THEOREMS WITH 16,16.
B1. Every order invariant subset of Q[0,16]^32 contains a completely Z
+up invariant maximal square.
B2. Every order invariant graph on Q[0,16]^16 has a completely Z+up
invariant maximal clique.
B3. Every order invariant reflexive symmetric relation on Q[0,16]^16
has a completely Z+up invariant detached choice function.
INFINITE UNPROVABLE THEOREMS WITH k,n.
C1. Every order invariant subset of Q[0,n]^2k contains a completely Z
+up invariant maximal square.
C2. Every order invariant graph on Q[0,n]^2k has a completely Z+up
invariant maximal clique.
C3. Every order invariant reflexive symmetric relation on Q[0,n]^k has
a completely Z+up invariant detached choice function.
FINITE UNPROVABLE THEOREMS.
D1. Every order invariant reflexive symmetric relation on Q[0,16]^16
contains a finite completely Z+up invariant detached function r-
defined over {1,...,16}.
D2. Every order invariant reflexive symmetric relation on Q[0,n]^k
contains a finite completely Z+up invariant detached function r-
defined over {1,...,n}.
USING UPPER INTEGRAL INVARIANCE.
Replace "completely Z+up invariant" with "upper integral invariant".
********************************************
Q[0,k] is the set of rationals in [0,k].
A binary relation is a set of ordered pairs. A square in a binary
relation is a subset of the form A x A. A maximal square contained in
a binary relation is a square contained in the binary relation which
is not properly contained in any square contained in the binary
relation.
A graph is a pair (V,E), where V is a set and E is an irreflexive
symmetric binary relation on V (the adjacency relation). A clique in a
graph is a set of vertices, where any two distinct elements are
adjacent. A maximal clique in a graph is a clique in the graph which
is not properly contained in any clique in the graph.
A choice function for a relation is a function whose graph is
contained in the relation and which has the same domain as the
relation. A detached function for a relation is a function where no
two distinct values are related. Detached choice functions play an
important role in the theory.
We distinguish three kinds of relevant invariance conditions.
i. A set is invariant under a relation.
ii. A set is invariant under a function.
iii. A set is completely invariant under a function.
These notions depend on the set S being a subset of an ambient space K.
S is R invariant if and only if for all x,y in K with R(x,y), we have
x in S implies y in S.
S is f invariant if and only if for all x,f(x) in K, we have x in S
implies f(x) in S.
S is completely f invariant if and only if for all x,f(x) in K, we
have x in S iff f(x) in S.
In addition, we use
iv. A function is completely invariant under a function.
Here the first function is treated as a set contained in the Cartesian
product of two ambient spaces. In our use of iv, the first function
maps some Q[0,n]^k into Q[0,n]^k, and so it is treated as a subset of
the ambient space Q[0,n]^2k.
The relevant ambient spaces for order invariance are Q[0,n]^2k, and
Q[0,16]^32.
The relevant ambient spaces for Z+up invariance are Q[0,n]^2k,
Q[0,16]^32 for the statements with squares and detached choice
functions, and Q[0,n]^k, Q[0,16]^16 for the statements with cliques.
Order invariance refers to the relation of order equivalence on Q* =
the set of all nonempty finite sequences from Q. x,y in Q* are order
equivalent if and only if x,y have the same length, and for all 1 <=
i,j <= lth(x), x_i < x_j iff y_i < y_j.
Z+up invariance refers to the function Z+up:Q* into Q*. For x in Q*, Z
+up(x) is the result of adding 1 to all coordinates of x greater than
all coordinates outside Z+.
Let k,r >= 1 and A be a subset of Q. We say that a partial f:Q^k into
Q^k is r-defined over A if and only if every expression involving
elements of A and r applications of the various k coordinate functions
of f is defined.
Upper integral invariance refers to the relation of upper integral
equivalence on Q*. 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=
y_i then every x_j >= x_i lies in Z+ and every y_j >= y_i lies in Z+.
NOTES
A1,A2,A3 are theorems of ZFC, and are equivalent to the axiom of
choice over ZF. However, we will only care about the countable case,
where there is no problem proving these in RCA_0. There are important
sharpened forms that are provably equivalent to ACA_0 over RCA_0.
B1-B3,C1-C3,D1,D2 are provable using suitable large cardinals but not
in ZFC. The ones with k,n are provable in ZFC if we assume k = 2 or n
= 2. The same is true for the variants using upper integral invariance.
All of these 16 statements, other than D1,D2, and their variants using
upper integral invariance, can easily be seen to be Pi01 through the
Goedel completeness theorem for predicate calculus.
In particular, note that B1,B2,C1, and its variants using upper
integral invariance, assert the satisfiability of each of (in)finitely
many A...AE...E sentences in predicate calculus with equality, whereas
B3,C3, and their variants using upper integral invariance, assert the
satisfiability of each of (in)finitely many A...A sentences in
predicate calculus in predicate calculus with equality. Finite forms
of satisfiability of A...A sentences are familiar in general algebra,
and our use of r-defined functions over {1,...,n} is a simple way of
giving such familiar finite forms.
D1,D2, and their variants using upper integral invariance, are
explicitly Pi02. Moreover, using the obvious upper bound that can be
placed on the size of functions r-defined over {1,...,n}, D1,D2, and
their variants using upper integral invariance, are easily seen to be
Pi01 through the well known decision procedure for dense linear
orderings with endpoints. Alternatively, double exponential upper
bounds can be placed directly on the numerators and denominators of
the rationals involved.
LARGE CARDINALS INVOLVED
"SRP" is read stationary Ramsey property. The k-SRP for lambda asserts
that every partition of the unordered k-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}.
C1-C3,D2, and their variants using upper integral invariance, are
provably equivalent to Con(SRP) over ACA'. B1-B3,D1, and their
variants using upper integral invariance, are provable from Con(SRP)
in ACA', but not in ZFC (assuming ZFC is consistent).
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 482nd 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
481: Complementation and Incompleteness 2/15/12 8:40AM
Harvey Friedman
More information about the FOM
mailing list