[FOM] 478:Maximality, Choice, and Incompleteness

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


THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

We restate http://www.cs.nyu.edu/pipermail/fom/2012-January/ 
016155.html using improved terminology for the finite form, a better  
typo correction than http://www.cs.nyu.edu/pipermail/fom/2012-January/016156.html 
, small changes in wording, and a little bit of extra material in the  
Notes.

We define f,g commute (f is g commuting) if and only if fog and gof  
agree on dom(fog) intersect dom(gof).

Let k,r,n >= 1. We say that a partial f:Q^n into Q^n is k,r-exact if  
and only if dom(f) is the set of all n-tuples of values of expressions  
involving 1,...,k and < r applications of the various k coordinate  
functions of f.

Obviously k,r-exact f have finite domain, and all expressions  
involving 1,...,k and <= r applications of the k coordinate functions  
of f are defined.

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

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 Z+up commuting detached choice function.

INFINITE UNPROVABLE THEOREMS WITH k,n.

C1. For all k,n >= 1, every order invariant subset of Q[0,k]^2n  
contains a completely Z+up invariant maximal square.

C2. For all k,n >= 1, every order invariant graph on Q[0,k]^n has a  
completely Z+up invariant maximal clique.

C3. For all k,n >= 1, every order invariant reflexive symmetric  
relation on Q[0,k]^n has a Z+up commuting detached choice function.

USING UPPER INTEGRAL INVARIANCE.

B1'. Every order invariant subset of Q[0,16]^32 contains an upper  
integral invariant maximal square.

B2'. Every order invariant graph on Q[0,16]^16 has a an upper integral  
invariant maximal clique.

C1'. For all k,n >= 1, every order invariant subset of Q[0,k]^2n  
contains an upper integral invariant maximal square.

C2'. For all k,n >= 1, every order invariant graph on Q[0,k]^n has an  
upper integral invariant maximal clique.

FINITE UNPROVABLE THEOREM.

D. For all k,n,r >= 1, every order invariant reflexive symmetric  
relation on Q[0,k]^n contains a k,r-exact Z+up commuting detached  
function.

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

DEFINITIONS

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.

We distinguish four 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.
iv. Functions f,g commute. Equivalently, f is g commuting.

The first three notions depend on the set S being a subset of an  
ambient space K. The fourth notion does not involve an ambient space.

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.

f,g commute (f is g commuting) if and only if fog and gof agree on  
dom(fog) intersect dom(gof).

The relevant ambient spaces for order invariance are Q[0,k]^2n,  
Q[0,16]^32.

The relevant ambient spaces for Z+up invariance are Q[0,k]^2n,  
Q[0,16]^32 for the statements with squares, and Q[0,k]^n, 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,n >= 1. We say that a partial f:Q^n into Q^n is k,r-exact if  
and only if dom(f) is the set of all n-tuples of values of expressions  
involving 1,...,k and < r applications of the various k coordinate  
functions of f.

Obviously k,r-exact f have finite domain, and all expressions  
involving 1,...,k and <= r applications of the k coordinate functions  
of f are 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,D,B1',B2',C1',C2' are provable using suitable large  
cardinals but not in ZFC. They are provable if we assume k = 2 or n = 2.

All of these 11 statements, other than D, can easily be seen to be  
Pi01 through the Goedel completeness theorem for predicate calculus.

In particular, note that B1,B2,C1,C2,B1',B2',C1',C2' assert the  
satisfiability of each of (in)finitely many A...AE...E sentences in  
predicate calculus with equality, whereas B3,C3 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
k,r-exact functions is a simple way of giving such familiar finite  
forms.

D is explicitly Pi02. Moreover, using the obvious upper bound on the  
size of k,r-exact functions, D is 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 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,C2,C3,D,C1',C2' are provably equivalent to Con(SRP) over ACA'.  
B1,B2,B3,B1',B2' are provable from Con(SRP) in ACA'. B1,B2,B3,B1',B2'  
are not provable in ZFC.

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

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

Harvey Friedman


More information about the FOM mailing list