[FOM] 475:Invariant Functions and Incompleteness

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

The example of explicitly Pi01 incompleteness in http://www.cs.nyu.edu/pipermail/fom/2012-January/016138.html 
  started with

EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16 HAS A COMPLETELY Z+up  
INVARIANT INDEPENDENT DOMINATOR.

We then defined n-dominators based on an inequality added to the  
definition of dominator based on a norm on Q[0,16]^16, where it was  
important that there will be only finitely many elements of Q[0,16]^16  
less than or equal to a given norm. The inequality drives a crude  
counting argument, and uses the function 256^n. We formulated the  
finite form as follows.

IN EVERY ORDER INVARIANT GRAPH ON Q[0,16]^16, EVERY FINITE SET HAS A  
COMPLETELY Z+up INVARIANT INDEPENDENT 256^n-DOMINATOR.

 From some points of view, it would be nicer - or at least it would be  
an important alternative - to avoid bringing in such quantitative  
considerations.

Accordingly, we have been working with the functions associated with  
dominators. I.e., f(v) is either v or a vertex adjacent to v, where  
the fixed points of f are independent in the graph.

When we work with these functions, the dominators themselves are no  
longer needed. The set of fixed points plays the role of the dominator.

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

We now present the details.

A function on X is a function with domain X.

Let R be a binary relation. A function contained in R is said to be  
detached if and only if no two distinct values are related by R.

THEOREM 1. Every reflexive symmetric binary relation on X contains a  
detached function on X.

To see this, let A be a maximal subset of X such that any two distinct  
elements of A are not related. For x in X, define f(x) to be x if x is  
in A; otherwise, some y in A such that x,y are R related. Then dom(f)  
= X, and rng(f) is a subset of A.

Note that the set of fixed points of such a function is a dominator of  
the corresponding graph of the relation (the graph whose vertex set is  
the domain of the relation, and whose adjacency relation is the  
irreflexive part of the relation).

Theorem 1 is equivalent to the Axiom of Choice.

We have already defined order invariance for subsets of Q[0,k]^n and Z 
+up invariance for subsets of Q[0,k]^n in http://www.cs.nyu.edu/pipermail/fom/2012-January/016138.html 
  using Q[0,k]^n as the ambient space. Z+up invariance for partial  
f:Q[0,k]^n into Q[0,k]^n has also is defined, using Q[0,k]^2n as the  
ambient space - as usual, we identity functions with their graphs.

PROPOSITION 2. For all k,n >= 1, every order invariant reflexive  
symmetric relation on Q[0,k]^n contains a completely Z+up invariant  
detached function on Q[0,k]^n.

PROPOSITION 3. Every order invariant reflexive symmetric relation on  
Q[0,16]^16 contains a completely Z+up invariant detached function on  
Q[0,16]^16.

Now let f:V^n into V^n be a partial function. We use f to generate  
elements of V from any v_1,...,v_k in V in the following way.

We define f^(0)[v_1,...,v_k] = {v_1,...,v_k}. f^(i+1)(v_1,...,v_k) =  
f^(i)(v_1,...,v_k) together with the coordinates of values of f at  
arguments from f^(i)(v_1,...,v_k).

Note that if E is finite then GEN(f,t,E) is finite, and there is an at  
most double exponential blowup in cardinality.

PROPOSITION 4. For all k,n,t >= 1, every order invariant reflexive  
symmetric relation on Q[0,k]^n contains a completely Z+up invariant  
detached f on f^(t)[0,...,k]^n.

PROPOSITION 5. For all k,n >= 1, every order invariant reflexive  
symmetric relation on Q[0,k]^n contains a completely Z+up invariant  
detached f on f^(1)[0,...,k]^n.

PROPOSITION 6. For all n >= 1, every order invariant reflexive  
symmetric relation on Q[0,16]^n contains a completely Z+up invariant  
detached f on f^(1)[0,...,16]^n.

PROPOSITION 7. For all t >= 1, every order invariant reflexive  
symmetric relation on Q[0,16]^16 contains a completely Z+up invariant  
detached f on f^(t)[0,...,16]^16.

Note that Propositions 2-7 are immediate consequences of Theorem 1 if  
we remove "completely Z+up invariant".

THEOREM 8. Propositions 2,4,5 are provably equivalent to Con(SRP) over  
ACA'. Propositions 3,6,7 imply Con(ZFC) over ACA' (and more).

It is obvious that there is at most double exponential upper bound on  
the size of the functions f in Propositions 4-7. Therefore the  
statements are explicitly Pi01 relative to the usual decision  
procedure for dense linear orderings. Alternatively, one can easily  
give upper bounds on all of the numerators and denominators involved  
in f.

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

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

Harvey Friedman