FOM: 30:Large Cardinals/where are we? II

[Harvey Friedman]

This is the 30th 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

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

Clarification: In 29:Large Cardinals/where are we? I, in Propositions 13
and 15, I neglected to define the cardinality of an R-tower as the
cardinality of its last term. (This is of course clear from the context,
but I should have said it).

******

In 29:Large Cardinals/where are we? I, I discussed the second of the
developments jumping off of the Annals paper. As promised, this posting
discusses the first of these developments - involving greedy constructions.
These independence results are probably more natural for algorithmically
oriented mathematicians (and computer scientists) than the ones in 29.

As of this time, the state of the art on discrete/finite independence
results from ZFC and higher is represented by 29 and this posting, 30. 27
represents the current state of the art on finite independence results from
predicative systems. See also my posting 2:46AM 2/5/99, "Perfect"
statements, and Simpson's posting 8:48PM 2/22/99, Harvey's `perfect'
statement; Feferfest volume.

For yet more elementary independence phenomena, see 21. So you can look at
just 21, 27, 29, 30, and the other two just mentioned. Relevant work
published or prepared for publication is cited in these postings.

As in postings 28 and 28' - which this posting replaces - regard this as
work in progress. ***I follow my usual procedure to mine out all my ideas
for simplifications and improvements, and only then to go into all of the
details in a finished manuscript. This process has been pretty reliable so
far.***

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 x,y in S_k(N), we write x <* y if and only if
max(x) < max(y). We also write x <=* y if and only if max(x) <= max(y).

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
S_k(N). V(G) is the set of vertices of G and E(G) is the set of edges of G.
(Standard terminology).

We focus on the subclass DGR(S_k(N)) of GR(S_k(N)) consisting of the
elements of GR(S_k(N)) such that for all edges {x,y}, either max(x) <
max(y) or max(y) < max(x). It is convenient to

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.

A compatibility sequence can obviously be viewed as a construction of a
single graph. What graph? The union of the terms, in the obvious sense.
I.e., the vertices are the  vertices of the terms, and the edges are the
edges of the terms. Note that every vertex of every term first appears in
the compatibility sequence as the new vertex of a term.

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

We begin with an independence result about infinite compatibility sequences.

PROPOSITION 1.1. Let k,r >= 1 and w:DGR(S_k(N)) into [0,r]. There is a
w-minimal compatibility sequence such that the k element subsets of some
infinite set appear as new vertices in terms with the same number of
vertices. We can furthermore require that there is a finite bound to the
number of vertices in each term.

THEOREM 1.2. 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.3. Let k,r,p >= 1 and w:DGR(S_k(N)) into [0,r]. There is a
w-minimal compatibility sequence such that the k element subsets of some p
element set appear as new vertices in terms with the same number of
vertices.

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. 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.4. Let k,r,p >= 1 and w:DGR(S_k(N)) into [0,r]. There is a
w-minimal compatibility sequence such that the k element subsets of some p
element set appear as new vertices in terms with the same entirely lower
vertices.

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

The semi-finite Propositions 1.3 and 1.4 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.

2. Trees.

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

There are several ways to set this up. We choose the following setup. 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 DTR(S_k(N)) be the set of N-trees labeled from S_k(N), where the
label of any vertex is >* the label of any of its predecessors.

Two N-trees are compatible if and only if they have the same minimum
element and the partial ordering agrees on the common vertices. Two
elements of DTR(S_k(N)) are compatible if and only if they are compatible
as N-trees, and their labeling functions agree on their common vertices.

We need to place a bound on the multiplicities in trees. Thus we define
DTR(S_k(N);m) as the set of all elements of DTR(S_k(N)) such that no label
appears more than m times in the tree.

The notions of compatibility sequences and w-minimal compatibility
sequences are defined completely analogously to section 1.

PROPOSITION 2.1. Let k,m,r >= 1 and w:DTR(S_k(N);m) into [0,r]. There is a
w-minimal compatibility sequence such that the k element subsets of some
infinite set appear as new labels in terms with the same number of
vertices. We can furthermore require that there is a finite bound to the
number of vertices in each term.

THEOREM 2.2. 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.3. Let k,r,m,p >= 1 and w:DGR(S_k(N);m) into [0,r]. There is
a w-minimal compatibility sequence such that the k element subsets of some
p element set appear as new labels in terms with the same number of
vertices.

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.

Here is the way to get strong semi-finite forms. 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 2.4. Let k,r,m,p >= 1 and w:DGR(S_k(N);m) into [0,r]. There is
a w-minimal compatibility sequence such that the k element subsets of some
p element set appear as new labels in terms with the same entirely lower
labels.

THEOREM 2.5. 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.

Thus they are explicitly pi-0-2. Associated enormous growth rates can be
ferreted out, also.

In addition, there is an appropriate formulation involving compatibility
sequences of posets (with no multiple copies).