[FOM] 263:Pi01/digraphs 1

[Harvey Friedman]

I have done enough checking to post this under normal circumstances.
However, the unusual content of the results warrants much greater than the
usual amount of checking. By this standard, current checking falls short.

This state of affairs is likely to continue for a while until things settle
down.

P01 INCOMPLETENESS: simple digraphs 1
by
Harvey M. Friedman
January 12, 2006

In this section, all digraphs will be directed graphs with no loops and no
multiple edges. Thus all digraphs will be simple.

A dag is a directed graph with no cycles.

We begin by quoting a well known theorem about directed acyclic graphs, or
so called dags. We call it the complementation theorem, but we have been
told that it is rather ordinary fundamental fare in dag theory.

For digraphs G and sets A containedin V(G), we write GA for the set of all
destinations of edges in G whose origins lie in A.

COMPLEMENTATION THEOREM (finite dags). Let G be a finite dag. There is a
unique set A containedin V(G) such that GA = A'.

We can look at the Complementation Theorem in terms of a large independent
set. We say that A containedin V(G) is independent in G if and only if there
is no edge connecting elements of A.

COMPLEMENTATION THEOREM (finite dags). Every finite dag has a unique
independent set A such that the following holds. Every vertex outside A lies
in GA.  

A digraph on a set A is a digraph G where V(G) = A.

We will focus on digraphs whose vertex set is of the form [1,n]k. Here k,n
>= 1 and [1,n] = {1,2,...,n}.

An upgraph on [1,n]k is a digraph on [1,n]k such that for all edges (x,y),
we have max(x) < max(y).

The following is an immediate consequence of the Complementation Theorem
(finite dags) since upgraphs are obviously dags.

COMPLEMENTATION THEOREM (finite upgraphs). For all k,n >= 1, every upgraph
on [1,n]k has a unique independent set A such that the following holds.
Every vertex outside A lies in GA.

Our development relies on what we call order invariant digraphs on [1,n]k.
These are the digraphs G on [1,n]k where only the relative order of
coordinates of pairs of vertices determine if they are connected by an edge.

More formally, the condition is that for all x,y,z,w in [1,n]k, if (x,y) and
(z,w) are order equivalent (as 2k tuples), then (x,y) is an edge if and only
if (z,w) is an edge.

Another phrase for order equivalent is "of the same order type". This notion
is very basic. Let u,v lie in {1,2,3,...}p. We say that u,v are order
equivalent if and only if for all 1 <= i,j <= p,

ui < uj iff vi < vj.

Note that an order invariant digraph on [1,n]k is completely determined,
among digraphs on [1,n]k, by the subdigraph induced by [1,2k]k - regardless
of how large n is. Thus the number of order invariant digraphs on [1,n]k is
bounded by k^k. 

PROPOSITION A. For all n,k,r >= 1, every order invariant upgraph G on [1,n]k
has an independent set A such that the following holds. Every subdigraph of
G induced by {1,2,4,...,2^n}k together with at most r vertices outside A, is
isomorphic to some subdigraph of G induced by {1,2,4,...,2^n}k together with
vertices from GA other than the diagonal vertex (2^((4kr)^2) - 1,...,
2^((4kr)^2) - 1).

We also give a sharpened form.

PROPOSITION B. For all n,k,r >= 1, every order invariant upgraph G on [1,n]k
has an independent set A such that the following holds. Every subdigraph of
G induced by {1,2,4,...,2^n}k together with at most r vertices outside A, is
isomorphic to some subdigraph of G induced by {1,2,4,...,2^n}k together with
vertices from: GA without 2^((4kr)^2) - 1.

Here 

GA without t

means GA without any vertices in which t appears as a coordinate.

Note that if we remove the exclusionary clauses at the end of Propositions A
and B, then we obtain trivial consequences of the Complementation Theorem
(finite upgraphs). What a difference a single point or single number makes!

Propositions A,B can be proved with large cardinals but not without.
Propositions A,B is explicitly Pi01.

Here is more detailed information.

Let MAH = ZFC + {there exists a strongly n-Mahlo cardinal}n.

Let MAH+ = ZFC + "for all n there exists a strongly n-Mahlo cardinal".

THEOREM 1. MAH+ proves Propositions A,B. However, Propositions A,B are not
provable in any consistent fragment of MAH that derives Z = Zermelo set
theory. In particular, Propositions A,B are not provable in ZFC, provided
ZFC is consistent. These facts are provable in RCA0.

THEOREM 2. EFA + Con(MAH) proves Propositions A,B.

THEOREM 3. It is provable in ACA that Propositions A,B are equivalent to
Con(MAH).

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 263rd 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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM
262. Correction/Restatement  12/9/05  10:13AM

Harvey Friedman