[FOM] 476:Maximality, Choice, and Incompleteness

Sun Jan 22 23:49:21 EST 2012

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

We now officially adopt "detached choice" as a path to ZFC  
independence, in addition to the "maximality" that we have been using.

We now prefer to use "detached choice" for all of the explicitly Pi01  
forms. we have been using independent dominators not as a competitor  
for maximal cliques - but for motivating certain explicitly Pi01  
forms. Now that we are using "detached choice" instead, we have (at  
least at present) no need for independent dominators - maximal cliques  
are much more widely known than the dual notion of independent  
dominators.

Below we give an organized list of all of the main independent  
statements, including ones based on "detached choice" - without  
definitions. We will give the definitions after we give the list.

As usual, all of the infinite incompleteness statements are Pi01 via  
satisfiability in predicate calculus - see the NOTES below.

BASIC THEOREMS.

A1. Every binary relation has 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 has 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 has 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.

FINITE UNPROVABLE THEOREM.

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

USING UPPER INTEGRAL INVARIANCE.

In B1,B2,C1,C2, we replace "completely Z+up invariant" we can replace  
by the stronger "upper integral invariant". These are B1',B2',C1',C2'.

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

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 in a binary  
relation is a square in the binary relation which is not properly  
contained in any square 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(f) intersect rng(f).

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

The relevant ambient spaces for Z+up invariance is 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 f:A^n into A^n be partial. The composites of f are the partial  
functions from A^n into A given by expressions involving f_1,...,f_n,  
and variables x_1,...,x_n. The r-composites are the composites that  
use at most r functions, counting multiplicities.

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. All of these, 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
r-composites in D is a simple way of giving such familiar finite forms.

D is explicitly Pi02. Moreover, D is easily seen to be Pi01 through  
the well known decision procedure for dense linear orderings with  
endpoints. Alternatively, at most double exponential upper bounds can  
be placed on the numerators and denominators of the rationals involved.

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

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

Harvey Friedman