[FOM] 269:Pi01,Pi011/digraphs

[Harvey Friedman]

Pi01,Pi00 INCOMPLETENESS: digraphs
by
Harvey M. Friedman
February 25, 2006

In this abstract, a digraph is a directed graph with no loops and no
multiple edges. Thus all digraphs will be simple. The results will be the
same if we allow loops.

A dag is a directed graph with no cycles.

Let G be a digraph. We write V(G) for the set of all vertices in G, and E(G)
for the set of all edges in G.

Let A containedin V(G). We write GA for the set of all destinations of edges
in G whose origins lie in A. I.e., GA = {y: (therexists x)((x,y) in E(G))}.

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.

COMPLEMENTATION THEOREM (finite dags). Let G be a finite dag. There is a
unique set A containedin V(G) such that GA = V(G)\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 any two elements of A.

COMPLEMENTATION THEOREM (finite dags). Every finite dag has a unique
independent set A such that V(G)\A containedin GA.

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

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 (x,y) in
E(G), max(x) < max(y).

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

COMPLEMENTATION THEOREM (upgraphs). For all k,n,r >= 1, every upgraph on
[1,n]^k has a unique independent set A such that V(G)\A containedin 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, 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,

u_i < u_j iff v_i < v_j.

Let G be a digraph on [1,n]^k. We say that G is order invariant if and only
if the following holds. 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) in E(G) iff (z,w) in E(G).

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 (2k)^k.

Let x_1,...,x_s,y_1,...,y_s be vertices in the digraph G. We say that
x_1,...,x_k and y_1,...,y_s are G equivalent if and only if for all 1 <= i,j
<= k, 

(x_i,x_j) in E(G) iff (y_i,y_j) in E(G).

We can add an additional clause to this definition, without affecting any of
the results. Specifically,

x_i = x_j iff y_i = y_j.

We write x! when x is a tuple of nonnegative integers. Here x! =
(x_1!,...,x_k!), where x has length k.

For A containedin [1,n]^k and m >= 1, we write A\m for the set of all
vectors in A in which m does not appear as a coordinate.

PROPOSITION A. For all k,n,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every x!,y_1,...,y_r from V(G)\A
is G equivalent to some x!,z_1,...,z_r from GA\((8kr)!-1).

PROPOSITION B. For all n,r >= 1, every order invariant upgraph G on [1,n]^8
has an independent set A such that every x!,y_1,...,y_r from V(G)\A is G
equivalent to some x!,z_1,...,z_r from GA\((8r)!-1).

(We can get away with 8r here instead of 64r).

PROPOSITION C. For all k,n,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that for all strictly increasing x,y
in [8kr,n]^k, every x!,z_1,...,z_r from V(G)\A is G equivalent to some
y!,w_1,...,w_r from GA\((8kr)!-1).

PROPOSITION D. For all n,r >= 1, every order invariant upgraph G on [1,n]^8
has an independent set A such that for all strictly increasing x,y in
[8r,n]^8, every x!,z_1,...,z_r from V(G)\A is G equivalent to some
y!,w_1,...,w_r from GA\((8r)!-1).

PROPOSITION E. For all r >= 1, every order invariant upgraph G on
[1,(8r)!!]^8 has an independent set A such that for all strictly increasing
x,y in {(8r)!,8r+1)!,...,(8r)!!}^8, every x,z_1,...,z_r from V(G)\A is G
equivalent to some y,w_1,...,w_r from GA\((8r)!-1).

PROPOSITION F. Every order invariant upgraph G on [1,8!!!!]^8 has an
independent set A such that for all strictly increasing x,y in
{8!!!,(8!!+1)!,...,8!!!!}^8, every x,z_1,...,z_7!! from V(G)\A is G
equivalent to some y,w_1,...,w_7!! from GA\(8!!!-1).

Note that if we use GA instead of GA\((8r)!-1) in Propositions A,B, then the
resulting Proposition follows immediately from the Compelementation Theorem
(finite upgraphs).

Propositions A-E can be proved with large cardinals but not without. Note
that Propositions A-E are explicitly Pi01. Note that Proposition F is
explicitly Pi00.

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-E. However, Propositions A,C are not
provable in any consistent fragment of MAH that derives Z = Zermelo set
theory. In particular, Propositions A-E are not provable in ZFC, provided
ZFC is consistent. These facts are provable in RCA_0.

THEOREM 2. MAH+ proves Propositions B,D,E. However, Propositions B,D,E are
not provable in ZFC + "there exists a strongly Mahlo cardinal".

THEOREM 3. EFA + Con(MAH) proves Propositions A-E.

THEOREM 4. It is provable in ACA that Propositions A,C are equivalent to
Con(MAH). It is provable in EFA that Proposition C is equivalent to
Con(MAH).

THEOREM 5. Proposition F can be proved in MAH+ with full abbreviation power
using at most 10^6 symbols. Every proof of Proposition F in ZFC with full
abbreviation power uses at least 10^1000 symbols.

The numbers in Proposition F are expected to come down substantially. Note
that we have chosen to use factorial notation, which does make the numbers
bigger than they would be otherwise.

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 268th 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
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM
265. Pi01/digraphs 2/more  1/28/06  2:46PM
266. Pi01/digraphs/unifying 2/4/06  5:27AM
267. Pi01/digraphs/progress  2/7/06  11:40PM
268: Finite to Infinite 1  2/22/06  9:01AM

Harvey Friedman