FOM: 32:Greedy Constructions/Large Cardinals

[Harvey Friedman]

This is the 32nd in a series of self contained postings to fom covering a
wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98
10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM
19:Long Sequences  7/31/98  9:42AM
20:Proof Theoretic Degrees  8/2/98  9:37PM
21:Long Sequences/Update  10/13/98  3:18AM
22:Finite Trees/Impredicativity  10/20/98  10:13AM
23:Q-Systems and Proof Theoretic Ordinals  11/6/98  3:01AM
24:Predicatively Unfeasible Integers  11/10/98  10:44PM
25:Long Walks  11/16/98  7:05AM
26:Optimized functions/Large Cardinals  1/13/99  12:53PM
27:Finite Trees/Impredicativity:Sketches  1/13/99  12:54PM
28:Optimized Functions/Large Cardinals:more  1/27/99  4:37AM
28':Restatement  1/28/99  5:49AM
29:Large Cardinals/where are we? I  2/22/99  6:11AM
30:Large Cardinals/where are we? II  2/23/99  6:15AM
31:First Free Sets/Large Cardinals  2/27/99  1:43AM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of self contained postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

FAVORITE SELF CONTAINED POSTINGS: 21, 25, 27, 31, 32.

This posting concerns the greedy construction independence results. The
last posting on this was 30. This obsoletes 30.

This represents work in progress; the same caveats in 30 apply here.

******

In 30, I unfortunately veered away somewhat from the fundamental philosophy
of greedy constructions. This caused the first part "Graphs" to have a bug
in it. This posting obsoletes 30; however, for the record, we make the
small fix needed for 30. In 30, I wrote

"Let G,G' in DGR(S_k(N)). We say that G and G' are compatible if and only
if for all common vertices x,y in V(G) intersect V(G'), {x,y} is an edge in
G if and only if {x,y} is an edge in G'.

A compatibility sequence (from DGR(S_k(N))) is a finite or infinite
sequence of graphs in DGR(S_k(N)) such that

i) any two terms are compatible;
ii) each term has exactly one vertex that is not a vertex of any previous
term. This is called the new vertex of the term;
iii) the new vertex of each term is <=* the new vertex of each later term."

Here is the correction:

"A compatibility sequence (from DGR(S_k(N))) is a finite or infinite
sequence of graphs in DGR(S_k(N)) such that

i) each term has exactly one vertex that is not a vertex of any previous
term. This is called the new vertex of the term;
ii) in each term, any two vertices other than the new vertex, are connected
if and only if these vertices are connected in some previous term;
iii) the new vertex of each term is <=* the new vertex of each later term."

But we believe it is better to follow the treatment in the current posting
rather than 30.

******

GREEDY CONSTRUCTIONS AND THE NECESSARY USE OF LARGE CARDINALS
by
Harvey M. Friedman
February 28, 1999

1. Graphs.

Let N be the set of all nonnegative integers and S_k(N) be the set of all k
element subsets of N.

For each k >= 1, let GR(S_k(N)) be the set of all undirected finite graphs
without loops whose set of vertices is a finite subset of S_k(N).

More formally, GR(S_k(N)) consists of pairs G = (V,E), where V = V(G) is a
finite subset of S_k(N) and E = E(G) is a set of unordered pairs from V(G).
V(G) is the set of vertices of G and E(G) is the set of edges of G.
(Standard terminology).

Let G,G' in GR(S_k(N)). We say that G' is a point extension of G if and
only if

i) V(G') is V(G) together with the single "new" vertex x;
ii) for all y in V(G), max(y) <= max(x);
iii) E(G') is E(G) together with zero or more edges connecting x with
elements of V(G).

Thus in particular, G is an induced subgraph of G'.

Let G' be a point extension of G. We define G'/G = the new part of G' over
G, as the subgraph of G' induced by the new vertex together with all
vertices connected to the new vertex by an edge in G'. The valence of the
new vertex x in G' is the number of vertices that are connected to x by an
edge in G'. Note that this valence is one less than the same as the number
of vertices in the new part, and is also the valence of the new vertex in
the new part.

A construction sequence (from GR(S_k(N))) is a finite or infinite sequence
of graphs in GR(S_k(N)) such that each term after the first is a point
extension of the previous term.

We now wish to consider construction sequences which are minimal in an
appropriate sense. Let w:GR(S_k(N)) into N and G_1,G_2,... be a
construction sequence. We say that G_1,G_2,... is w-minimal if and only if
for all G_i+1 and construction sequences G_1,...,G_i,G_i+1', if the new
vertex of G_i+1 is the same as the new vertex of G_i+1', then w(G_i+1/G_i)
<= w(G_i+1'/G_i).

It is obvious that w-minimal construction sequences exist:

THEOREM 1.1. Let k >= 1 and w:GR(S_k(N)) into N. There is a w-minimal
construction sequence of finite length starting with the empty graph where
the vertex set of the last term is any desired finite subset of S_k(N).
There is a w-minimal construction sequence of infinite length starting with
the empty graph where the set of vertices appearing is any desired infinite
subset of S_k(N). Analogous results hold starting from a given graph.

We now present an independence result about infinite construction sequences.

PROPOSITION 1.2. Let k,r >= 1 and w:GR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence starting with the empty graph (any graph)
such that all k element subsets of some infinite set appear as new vertices
with the same valence. In fact, we can require that they appear as new
vertices in terms with isomorphic new parts.

Here isomorphisms between graphs are order preserving bijections between
the underlying integers which preserve the relevant structure.

THEOREM 1.3. In RCA_0, Proposition 1 is provably equivalent to the
1-consistency of ZFC + {there exists an n-Mahlo cardinal}_n.

There is the following obvious semi-finite form:

PROPOSITION 1.4. Let k,r,p >= 1 and w:GR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
graph (any  graph) such that the k element subsets of some p element set
appear as new vertices with the same valence. In fact, we can require that
they appear as new vertices in terms with isomorphic new parts.

This should be equivalent to the 1-consistency of type theory, or Zermelo
set theory with bounded separation. But this requires a yet more profound
reworking of the Annals paper. I see how to prove Proposition 1.3 from the
1-consistency of type theory.

Here is the way to get strong semi-finite forms (beyond ZFC). Let x,y be
finite sets of integers. We say that x is entirely lower than y if and only
if every element of x is less than every element of y. This is the concept
that I use in "Finite trees and the necessary use of large cardinals," to
appear, http://www.math.ohio-state.edu/foundations/manuscripts.html.

PROPOSITION 1.5. Let k,r,p >= 1 and w:GR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
graph (any  graph) such that the k element subsets of some p element set
appear as vertices connected to the same entirely lower vertices. We can
additionally require that they appear as new vertices in terms with
isomorphic new parts.

Even the barest form of this conclusion is enough to require large
cardinals. Let A,B in S_k(N). We say that A,B are shift related if and only
if A\min(A) = B\max(B).

PROPOSITION 1.6. Let k,r >= 1 and w:GR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
graph (any  graph) where some two shift related vertices are connected to
the same entirely lower vertices.

THEOREM 1.7. In RCA_0, Propositions 1.5 and 1.6 are provably equivalent to
the 1-consistency of ZFC + {there exists an n-subtle cardinal}_n.

The semi-finite Propositions 1.4-1.6 have obvious equivalent finite forms
by compactness. Just restrict S_k(N) to S_k([0,t]), where t is sufficiently
large relative to k,r,p. Thus they are explicitly pi-0-2.

2. Trees.

I don't know how to get independence results for construction sequences of
trees, where a single new vertex is introduced at each stage, as in the
previous two sections. However, I do have confidence that I can do this
when I allow multiple entries of the same vertex.

A tree is a partial ordering with a minimum element, where the set of
predecessors of every vertex is linearly ordered. An N-tree is a finite
tree whose vertices are elements of N. A labeled N-tree is an N-tree
together with a mapping from the set of vertices into a labeling set. For k
>= 1, let TR(S_k(N)) be the set of N-trees labeled from S_k(N).

It will be useful to consider the "empty tree" as an additiional element of
TR(S_k(N)).

Let T,T' in TR(S_k(N)). We say that T is a subtree of T' if and only if T
is the empty tree, or

i) T and T' have the same root;
ii) V(T) containedin V(T');
iii) if x is the parent of y in T then x is the parent of y in T';
iv) the label of any vertex in T is the same as its label in T'.

We say that T' is a singular extension of T if and only if

i) T is a subtree of T';
ii) all vertices of T' that are not vertices of T have the same label, x,
where x is called the new label;
iii) for all labels y of T, max(y) <= max(x).

Let T' be a singular extension of T. We define T'/T = the new part of T'
over T, as the least subtree of T' containing all vertices of T' that are
not vertices of T.

A construction sequence (from TR(S_k(N))) is a finite or infinite sequence
of trees in TR(S_k(N)) such that each term after the first is a singular
extension of the previous term.

We now wish to consider construction sequences which are minimal in an
appropriate sense. Let w:TR(S_k(N)) into N and T_1,T_2,... be a
construction sequence. We say that T_1,T_2,... is w-minimal if and only if
for all T_i+1 and construction sequences T_1,...,T_i,T_i+1', if the new
label of T_i+1 is the same as the new label of T_i+1', then w(T_i+1/T_i) <=
w(T_i+1'/T_i).

PROPOSITIOIN 2.1. Let k >= 1 and w:TR(S_k(N)) into N. There is a w-minimal
construction sequence starting with the empty tree where the label set of
the last term is any desired finite subset of S_k(N). There is an infinite
w-minimal construction sequence starting with the empty tree where the set
of labels appearing is any desired infinite subset of S_k(N). Analogous
results hold starting from a given tree.

PROPOSITION 2.2. Let k,r >= 1 and w:TR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence starting with the empty tree (any tree)
such that the k element subsets of some infinite set appear as new labels
with the same multiplicities. We can furthermore require that they also
appear as new labels in terms with isomorphic new parts.

Here isomorphisms between trees are order preserving bijections between the
underlying integers which preserve the relevant structure.

THEOREM 2.3. In RCA_0, Proposition 2.1 is provably equivalent to the
1-consistency of ZFC + {there exists an n-Mahlo cardinal}_n.

There is the following obvious semi-finite form:

PROPOSITION 2.4. Let k,r,p >= 1 and w:TR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
tree (any tree) such that the k element subsets of some p element set
appear as new labels with the same number of multiplicities. We can
furthermore require that they also appear as new labels in terms with
isomorphic new parts.

This should be equivalent to the 1-consistency of type theory, or Zermelo
set theory with bounded separation. But this requires a yet more profound
reworking of the Annals paper. I see how to prove Proposition 2.3 from the
1-consistency of type theory.

PROPOSITION 2.5. Let k,r,p >= 1 and w:TR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
tree (any tree) such that the k element subsets of some p element set
appear as new labels in terms whose new parts have the same entirely lower
labels. In fact, we can additionally require that they appear as new labels
in terms with isomorphic new parts.

Even the barest form of this conclusion is enough to require large
cardinals. Let A,B in S_k(N). We say that A,B are shift related if and only
if A\min(A) = B\max(B).

PROPOSITIOIN 2.6. Let k,r >= 1 and w:TR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
tree (any tree) such that some two shift related sets appear as new labels
in terms whose new parts have the same entirely lower labels.

THEOREM 2.7. In RCA_0, Proposition 2.4 is provably equivalent to the
1-consistency of ZFC + {there exists an n-subtle cardinal}_n.

The semi-finite Propositions 2.3 and 2.4 have obvious equivalent finite
forms by compactness. Just restrict S_k(N) to S_k([0,t]), where t is
sufficiently large.

3. Posets.

For each k >= 1, let PO(S_k(N)) be the set of all posets whose set of
vertices is a finite subset of S_k(N).

More formally, GR(S_k(N)) consists of pairs P = (V,<=), where V = V(P) is a
finite subset of S_k(N) and <= is a binary relation on V(P) obeying i) x <=
x; ii) (x <= y & y <= z) implies x <= z; iii) (x <= y & y <= x) implies x =
y.

Let P,P' in GR(S_k(N)). We say that P' is a point extension of P if and
only if

i) V(P') is V(P) together with the single "new" vertex x;
ii) for all y in V(P), max(y) <= max(x);
iii) for y,z in V(P), y <= z in P if and only if y <= z in P';
iv) x is maximal in P' with respect to the partial ordering.

Let P' be a point extension of P with new vertex x. We define P'/P = the
new part of P' over P, as the restriction of P' to the set of all y <= x.

A construction sequence (from PO(S_k(N))) is a finite or infinite sequence
of posets in PO(S_k(N)) such that each term after the first is a point
extension of the previous term.

The predecessors of a vertex x are the vertices y < x. Note that all of the
predecessors of a vertex appear when that vertex is new.

We now wish to consider construction sequences which are minimal in an
appropriate sense. Let w:PO(S_k(N)) into N and P_1,P_2,... be a
construction sequence. We say that P_1,P_2,... is w-minimal if and only if
for all P_i+1 and construction sequences P_1,...,P_i,P_i+1', if the new
vertex of P_i+1 is the same as the new vertex of P_i+1', then w(P_i+1/P_i)
<= w(P_i+1'/P_i).

It is obvious that w-minimal construction sequences exist:

THEOREM 3.1. Let k >= 1 and w:PO(S_k(N)) into N. There is a w-minimal
construction sequence starting with the empty poset where the vertex set of
the last term is any desired finite subset of S_k(N). There is an infinite
w-minimal construction sequence starting with the empty poset where the set
of vertices appearing is any desired infinite subset of S_k(N). Analogous
results hold starting from a given poset.

We now present an independence result about infinite construction sequences.

PROPOSITION 3.2. Let k,r >= 1 and w:GR(S_k(N)) into [0,r]. There is a
w-minimal construction sequence starting with the empty poset (any poset)
such that all k element subsets of some infinite set appear as vertices
with the same number of predecessors. In fact, we can require that they
appear as new vertices in terms with isomorphic new parts.

Here isomorphisms between posets are order preserving bijections between
the underlying integers which preserve the relevant structure.

THEOREM 3.3. In RCA_0, Proposition 1 is provably equivalent to the
1-consistency of ZFC + {there exists an n-Mahlo cardinal}_n.

There is the following obvious semi-finite form:

PROPOSITION 3.4. Let k,r,p >= 1 and w:PO(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
poset (any  poset) such that the k element subsets of some p element set
appear as new vertices with the same number of predecessors. In fact, we
can require that they appear as new vertices in terms with isomorphic new
parts.

This should be equivalent to the 1-consistency of type theory, or Zermelo
set theory with bounded separation. But this requires a yet more profound
reworking of the Annals paper. I see how to prove Proposition 3.3 from the
1-consistency of type theory.

PROPOSITION 3.5. Let k,r,p >= 1 and w:PO(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
poset (any  poset) such that the k element subsets of some p element set
appear as vertices with the same entirely lower predecessors. We can
additionally require that they appear as new vertices in terms with
isomorphic new parts.

Even the barest form of this conclusion is enough to require large cardinals.

PROPOSITION 3.6. Let k,r >= 1 and w:PO(S_k(N)) into [0,r]. There is a
w-minimal construction sequence of finite length starting with the empty
poset (any  poset) where some two shift related vertices have the same
entirely lower predecessors.

THEOREM 3.7. In RCA_0, Propositions 1.5 and 1.6 are provably equivalent to
the 1-consistency of ZFC + {there exists an n-subtle cardinal}_n.

The semi-finite Propositions 3.4-3.6 have obvious equivalent finite forms
by compactness. Just restrict S_k(N) to S_k([0,t]), where t is sufficiently
large. Thus they are explicitly pi-0-2.

NOTE: We expect that the associated growth rates correspond to the provably
recursive functions of the associated formal systems.