[FOM] 507: Finite Embedded Dominators

Tue Nov 6 06:59:38 EST 2012

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING CONTINUES FROM
http://www.math.osu.edu/~friedman.8/manuscripts.html #72, Embedded
Maximal Cliques and Incompleteness, extended abstract, 17 pages,
September 26, 2012.

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

This posting supersedes
http://www.cs.nyu.edu/pipermail/fom/2012-October/016754.html . That
posting is inaccurate and has to be fixed, but I have come around to
using estimates in connection with independent dominators. This is an
idea that I considered before, but is not present in

[1] http://www.math.osu.edu/~friedman.8/manuscripts.html #72, Embedded
Maximal Cliques and Incompleteness, extended abstract, 17 pages.

Also, I will be updating [1] with some small changes in notation and
presentation, and with the direct finite forms presented here.

Recall that [1] already has finite forms, of the algorithmic kind.
These algorithmic finite forms remain crucially important, as they
lead to computer investigations that seem to bring large cardinals
into your desktop computer - as explained in [1].

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

Let G be a graph. We say that S is a dominator in G if and only if
every v in V\S is adjacent to some w in S. We say that S is
independent in G if and only if no two elements of S are adjacent.

Independent dominators are dual to maximal cliques. Every graph has an
independent dominator.

But there is a conceptual difference that motivates the placement of
estimates. Note that the independent dominator concept has a different
emphasis than the maximal clique concept. The emphasis is on the
positive act of "dominating". It is natural to require that every v
outside S be adjacent to some w in S that bears some relation to v.
Below we use a numerical relation, and have not begun to explore the
use of other kinds of relations.

Thus we have the following version of the Embedded Maximal Clique
Theorem from [1] and its dual - the Embedded Independent Dominator
Theorem.

EMCT. Every order invariant graph on Q>=0^k has a LSH[n] embedded
maximal clique.

EIDT. Every order invariant graph on Q>=0^k has a LSH[n] embedded
independent dominator.

Here SH[n] +1 on {0,...,n}, and LSH[n] is LSH[n] extended by
the identity on Q>n+1.

The norm of x in Q>=0^k is the least r such that x can be written with
numerators and denominators <= r.

Let G be a graph on Q>=0^k. We say that S is an r-dominator if and only if

every v in Q>=0^k\S of norm i <= r is adjacent to some w in S of norm <= (8i)^k.

Compare this with: S is a dominator if and only if

every v in Q>=0^k\S is adjacent to some w in S.

FEIDT. Every order invariant graph on Q>=0^k has a finite LSH[k]
embedded independent k-dominator.

FEIDT. Every order invariant graph on Q>=0^k has a finite LSH[n]
embedded independent r-dominator.

The above are explicitly Pi02. However, we can obviously exponentially
bound the norms of the vectors involved, thereby arriving at
explicitly Pi01 statements.

THEOREM 1. EMCT, EIDT are provably equivalent to Con(SRP) over WKL_0.
FEIDT (both forms) is provably equivalent to Con(SRP) over EFA.

The expression (8i)^k is chosen to be crude and safe. It will be
revisited in due course, as things settle down.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 507th 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
482: Maximality, Choice, and Incompleteness 2  2/19/12 7:43AM
483: Invariance in Q[0,n]^k  2/19/12  7:34AM
484: Finite Choice and Incompleteness  2/20/12  6:37AM__
485: Large Large Cardinals  2/26/12  5:55AM
486: Naturalness Issues  3/14/12  2:07PM
487: Invariant Maximality/Naturalness  3/21/12  1:43AM
488: Invariant Maximality Program  3/24/12  12:28AM
489: Invariant Maximality Programs  3/24/12  2:31PM
490: Invariant Maximality Program 2  3/24/12  3:19PM
491: Formal Simplicity  3/25/12  11:50PM
492: Invariant Maximality/conjectures  3/31/12  7:31PM
493: Invariant Maximality/conjectures 2  3/31/12  7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv  4/5/12  4:17PM
495: Invariant Finite Choice  4/5/12  4:18PM
496: Invariant Finite Choice/restatement  4/8/12  2:18AM
497: Invariant Maximality Restated  5/2/12 2:49AM
498: Embedded Maximal Cliques 1  9/18/12  12:43AM
499. Embedded Maximal Cliques 2  9/19/12  2:50AM
500: Embedded Maximal Cliques 3  9/20/12  10:15PM
501: Embedded Maximal Cliques 4  9/23/12  2:16AM
502: Embedded Maximal Cliques 5  9/26/12  1:21AM
503: Proper Classes of Graphs  10/13/12  12:17PM
504. Embedded Maximal Cliques 6  10/14/12  12:49PM
505: Function Transfer Theory 10/21/12  2:15AM
506: Finite Embedded Weakly Maximal Cliques  10/23/12  12:53AM

Harvey Friedman