[FOM] 264:Pi01/digraphs 2

[Harvey Friedman]

This is self contained, and is a simplification of Pi01/Digraphs 1.

There are a lot of leads for simpler versions.

ALSO: It appears that I have a method for creating a lot of substantially
simpler statements that can be proved using large cardinals, but where I
don't yet know if they are independent of ZFC.

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

Pi01 INCOMPLETENESS: simple digraphs 2
by
Harvey M. Friedman
January 27, 2006

In this abstract, a digraph is a directed graph with no loops and no
multiple edges. Thus all digraphs will be simple.

A dag is a directed graph with no cycles.

Let G be a digraph, and A containedin V(G). We write A' for V(G)\A. We write
GA for the set of all destinations of edges in G whose origins lie in A.

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 = 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 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 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 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 k^k.

Let G be a digraph and A,B containedin V(G). We say that A,B are G
isomorphic if and only if the subdigraph of G induced by A is isomorphic to
the subdigraph of G induced by B. I.e., there is a bijection h:A into B such
that for all x,y in A,

(x,y) in E(G) iff (hx,hy) in E(G).

A power of 2 is a number 2^i, where i is a nonnegative integer.

A vector power of 2 is a vector all of whose coordinates are powers of 2.

We say that c does not appear in a set of vectors if and only if c is not a
coordinate of any vector in that set.

PROPOSITION A. For all n,k,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every <= r element subset of A'
is G isomorphic to a <= r element subset of GA, with the same vector powers
of 2, in which the integer 2^((4kr)^2) - 1 does not appear.

Here is a weakening of Proposition A where only a single vector is excluded.

PROPOSITION B. For all n,k,r >= 1, every order invariant upgraph G on
[1,n]^k has an independent set A such that every <= r element subset of A'
is G isomorphic to a <= r element subset of GA, with the same vector powers
of 2, in which the diagonal vector (2^((4kr)^2) - 1,...,2^((4kr)^2) -1) does
not appear. 

Note that if we remove the exclusionary clauses in Proposition A or B, then
we obtain a trivial consequence of the Complementation Theorem (finite
upgraphs). What a difference a single vector or integer makes!

Propositions A,B can be proved with large cardinals but not without.
Propositions A,B are 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 RCA_0.

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 264th 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

Harvey Friedman