FOM: 12:Finite trees/large cardinals

[Harvey Friedman]

This is the 12th in a series of positive 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

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

Below is section A of a manuscript that I have just completed. A postscript
file will be available soon. It is a sequel to the paper "Finite functions
and the necessary use of large cardinals," on which it very heavily
depends. A revised TEX version of the latter will be available shortly.

Also, there is a third paper, not in final form yet, which uses large
cardinals to prove results in graph theory that have attracted some
attention among some combinatorialists. Some are known to be independent,
and others are not known to be independent. See the first website, from
which you can access the second, and then access the four mathematical
sites from there.

http://www-cse.ucsd.edu/classes/fa97/cse21/
http://www-cse.ucsd.edu/classes/fa97/cse21/AURAS.html

FINITE TREES AND THE NECESSARY USE OF LARGE CARDINALS
by
Harvey M. Friedman
Department of Mathematics
Ohio State University
friedman at math.ohio-state.edu
www.math.ohio-state.edu/~friedman/
March 11, 1998

We introduce insertion domains that support the placement of new, higher,
vertices into finite trees. We prove that every nonincreasing insertion
domain has an element with simple structural properties in the style of
classical Ramsey theory. This result is proved using standard large
cardinal axioms that go well beyond the usual axioms for mathematics. We
also establish that this result cannot be proved without these large
cardinal axioms. We also introduce insertion rules that specify the
placement of new, higher, vertices into finite trees. We prove that every
insertion rule greedily generates a tree with these same structural
properties; and every decreasing insertion rule generates (or admits) a
tree with these same structural properties. It is also necessary and
sufficient to use the same large cardinals (in the precise sense of
Corollary D.25). The results suggest new areas of research in discrete
mathematics called "Ramsey tree theory" and "greedy Ramsey theory" which
demonstrably require more than the usual axioms for mathematics.

TABLE OF CONTENTS

A. Statement of results.
	1. Trees and insertion domains.
	2. Greedy trees and insertion rules.
	3. Decreasing insertion rules.
	4. Finite forms.
B. Logical relationships.
	1. Basic implications and equivalences.
	2. Additional implications and equivalences.
C. Proofs in Z; proofs using large cardinals.
D. Necessity of large cardinals.

A. STATEMENT OF RESULTS

A1. TREES AND INSERTION DOMAINS

We begin with the concrete representation of finite trees that is
used throughout the paper. A partial ordering is a pair (X,<=), where X
is a nonempty set, and <= is reflexive, transitive, and antisymmetric.
The ancestors of x in X are just the y < x.

For the purposes of this paper, a tree T = (V,<=) is a partial ordering
with a minimum element, where V is finite, and the ancestors of any x
in V are linearly ordered under <=. The minimum element of T is called
the root of T, and is written r(T). A tree is said to be trivial if and
only if it has exactly one vertex, which must be its root. V = V(T)
represents the set of all vertices of the tree T = (V,<=).

In a tree T, if x < y and for no z is x < z < y, then we say that y
is a child of x and x is the parent of y. Every vertex has at most one
parent. However, vertices may have zero or more children. We write p(x,T)
for the parent of x in T.

We use Ch(T) = V(T)\{r(T)} for the set of all children of T.

We write T_1 containedin T_2 if and only if

	i) r(T_1) = r(T_2);
	ii) for all x in Ch(T_1), p(x,T_1) = p(x,T_2).

This is a partial ordering on trees. Note that if T_1 containedin T_2 then
no parent/child bond is broken by going from T_1 to T_2.

Let N be the set of all nonnegative integers. For k >= 1, let [N]^k be
the set of all k element subsets of N. In this section, we focus on the
k-trees, k >= 1. These are the trees T such that

	i) r(T) = infinity;
	ii) V(T) containedin [N]^k union {infinity}.

Thus there is a special treatment of roots in k-trees. There is exactly one
trivial k-tree, which consists solely of the root infinity. We let TR(k) be
the set of all k-trees.

Note that the k-trees can be viewed as the forests whose vertices are
elements of [N]^k. I.e., we can join the roots of the components of such a
forest by the root infinity. And given any k-tree, we can remove the root
infinity and thereby obtain such a forest. The correspondence is exact if
the empty forest is allowed.

We use <=* for the standard reverse lexicographic ordering on [N]^k, in
which sets are compared according to the lexicographic ordering on N^k
after the sets are placed in strictly descending order. We extend <=* to
[N]^k union {infinity} by taking infinity to be the maximum element. We
use >=*, <*, and >* in the obvious way.

Let T in TR(k). We say that x dominates T if and only if x in [N]^k and
for all y in Ch(T), y <* x.

An insertion domain in TR(k) is a nonempty S containedin TR(k) such that
the following holds. For all T in S and x dominating T, there exists T' in
S such that T containedin T' and Ch(T') = Ch(T) union {x}.

We introduce another important partial ordering on k-trees. We write T_1
<=* T_2
if and only if for all x in Ch(T_1), p(x,T_1) <=* p(x,T_2). Note that T_1
<=* T_2 implies Ch(T_1) containedin Ch(T_2).

Let S containedin TR(k). We say that S is nonincreasing if
and only if for all T_1, T_2 in S, if T_1 <=* T_2 then T_1 containedin T_2.
I.e., there are no proper inequalities between elements of S.

In section C, we prove the following in Z = Zermelo set theory.

THEOREM A1.1. Let k,p >= 1. Every nonincreasing insertion domain in TR(k)
contains a k-tree in which all k element subsets of some p element set
are vertices with the same number of ancestors.

The system Z incorporates a rather substantial amount of abstract set
theory - infinitely many uncountable cardinals. We conjecture that
infinitely many uncountable cardinals are required to prove Theorem
A1.1. Specifically, we conjecture that Theorem A1.1 cannot be proved in
ZC with bounded separation.

Let x,y in [N]^k. We say that x is entirely lower than y if and only if
every element of x is strictly smaller than every element of y.

PROPOSITION A1.2. Let k,p >= 1. Every nonincreasing insertion domain in TR(k)
contains a k-tree in which all k element subsets of some p element set
are vertices with the same entirely lower ancestors. Moreover, these
vertices can be required to have the same number of ancestors.

In section C, we prove Proposition A1.2 in ZFC + (forall k)(there
exists a k-subtle cardinal). In section D we prove that Proposition
A1.2 (first claim) cannot be proved in ZFC + {there exists a k-subtle
cardinal}_k, provided the latter is consistent.

A2. GREEDY TREES AND INSERTION RULES

An insertion rule on TR(k) is a function f, where

	i) dom(f) = {(T,x):T in TR(k) and x dominates T};
	ii) for all (T,x) in dom(f), f(T,x) in V(T).

For T in TR(k) x in [N]^k\Ch(T), and y in V(T), we write T/x,y for the
k-tree T' such
that Ch(T') = Ch(T) union {x} and p(x,T') = y. I.e., T' is the result of
inserting x as a new vertex in T at y; i.e., with parent y.

We now see why we use the name "insertion rule on TR(k)." We can view f as
specifying how we insert x into T, where x dominates T in TR(k). Namely, by
inserting x into T so as to produce the k-tree T/x,f(T,x).

Let f be an insertion rule on TR(k). We say that a k-tree is generated by f
if and only if it lies in the least class K containedin TR(k) such that

	i) the trivial k-tree lies in K;
	ii) for all T in K and x dominating T, T/x,f(T,x) in K.

Note that the k-trees generated by f are obtained by successively inserting
elements of [N]^k in <*-increasing order into the trivial k-tree, with
parents determined by f.

In section A3 we present results about the trees generated by certain
insertion rules on TR(k).

We now introduce the related concept of "greedy generation." The term
"greedy" comes from "greedy" algorithms,
whereby optimal finite objects are sought in various contexts. In
certain important contexts, the standard efficient algorithms proceed
by building up the desired optimized object in sequentially, where at
each stage the construction extends the object built thus far in a
relatively optimal way. This kind of construction is used for the
standard efficient algorithms in such diverse contexts as minimal
spanning trees, Huffman codes, task-scheduling, shortest paths, etc.
See [CLR90] and its many references for more information.

The results of this section definitely reflect this "greedy" idea.
Moreover, we expect that further results will be obtained with yet
closer connections with greedy algorithms of the kind that figure so
prominently in the theory of algorithms.

Let f be an insertion rule on TR(k). We say that a k-tree is greedily
generated by f if and only if it lies in the least class M containedin
TR(k) such that

	i) the trivial k-tree lies in M;
	ii) for all T in M and x dominating T, T/x,min{f(T',x):T' containedin
T} in M.

We emphasize that this min is with respect to <*.

Note that the k-trees greedily generated by f are obtained by
successively minimally inserting elements of [N]^k in <*-increasing
order into the trivial k-tree, with parents minimized as determined by f.

Now consider the following analogs to Theorem A1.1 and Proposition A1.2.

THEOREM A2.1. Let k,p >= 1. Every insertion rule on TR(k) greedily
generates a k-tree in which all k element subsets of some p element set
are vertices with the same number of ancestors.

PROPOSITION A2.2. Let k,p >= 1. Every insertion rule on TR(k) greedily
generates a k-tree in which all k element subsets of some p element set
are vertices with the same entirely lower ancestors. Moreover, these
vertices can be required to have the same number of ancestors.

We make the same conjectures and prove the same claims
about Theorem A2.1 and Proposition A2.2 that we make and prove about
Theorem A1.1 and Proposition A1.2.

A3. DECREASING INSERTION RULES

Let f be an insertion rule on TR(k). We say that f is decreasing if and
only if for all T_1 containedin T_2 from TR(k) and x dominating T_2, we
have f(T_1,x) >=* f(T_2,x).

Consider the following analogs to Theorem A1.1 and Proposition A1.2.

THEOREM A3.1. Let k,p >= 1. Every decreasing insertion rule on TR(k)
generates a k-tree in which all k element subsets of some p element set are
vertices with the same number of ancestors.

PROPOSITION A3.2. Let k,p >= 1. Every decreasing insertion rule on TR(k)
generates a k-tree in which all k element subsets of some p element set are
vertices with the same entirely lower ancestors. Moreover, these vertices
can be required to have the same number of ancestors.

We make the same conjectures and prove the same claims
about Theorem A3.1 and Proposition A3.2 that we make and prove about
Theorem A1.1 and Proposition A1.2.

An insertion rule in TR(k) is a pair (S,f), where

	i) S is a nonempty subset of TR(k);
	ii) dom(f) = {(T,x):T in S and x dominates T};
	iii) for all (T,x) in dom(f), f(T,x) in V(T);
	iv) for all (T,x) in dom(f), T/x,f(T,x) in S.

We say that (S,f) admits T if and only if T in S. We say that (S,f) is
decreasing if and only if for all T_1 containedin T_2 from S and x
dominating T_2, we have f(T_1,x) >=* f(T_2,x).

Consider the following analogs to Theorem A1.1 and Proposition A1.2.

THEOREM A3.3. Let k,p >= 1. Every decreasing insertion rule in TR(k) admits
a k-tree in which all k element subsets of some p element set are vertices
with the same number of ancestors.

PROPOSITION A3.4. Let k,p >= 1. Every decreasing insertion rule in TR(k)
admits a k-tree in which all k element subsets of some p element set are
vertices with the same entirely lower ancestors. Moreover, these vertices
can be required to have the same number of ancestors.

A4. FINITE FORMS

We now present straightforward finite forms of the above results. Let
[n]^k = {0,...,n}^k.

Let k,n >= 1. The k,n-trees are the k-trees all of whose children lie in
[n]^k. We write TR(k,n) for the set of all k,n-trees.

An insertion domain in TR(k,n) is a nonempty S containedin TR(k,n) such
that the following holds. For all T in S, x in [n]^k, x dominating T, there
exists
T' in S such that T containedin T' and Ch(T') = Ch(T) union {x}.

An insertion domain in TR(k,n) is said to be initial if and only if it
includes the trivial k-tree. This definition is also made for insertion
domains in TR(k).

An insertion rule on TR(k,n) is a function f, where

	i) dom(f) = {(T,x):T in TR(k,n), x in [n]^k, and x dominates T};
	ii) for all (T,x) in dom(f), f(T,x) in V(T).

Let f be an insertion rule on TR(k,n). We say that a k,n-tree is generated
by f if and only if it lies in the least class K containedin TR(k,n) such
that

	i) the trivial k-tree lies in K;
	ii) for all T in K, x in [n]^k, x dominating T, T/x,f(T,x) in K.

Let f be an insertion rule on TR(k,n). We say that a k,n-tree is greedily
generated by f if and only if it lies in the least class M containedin
TR(k,n) such that

	i) the trivial k-tree lies in M;
	ii) for all T in M, x in [n]^k, x dominating T,
T/x,min{f(T',x):T' containedin T} in M.

Let f be an insertion rule on TR(k,n). We say that f is decreasing if and
only if for all T_1 containedin T_2 from TR(k), x in [n]^k, x dominating
T_2, we have f(T_1,x) >=* f(T_2,x).

An insertion rule in TR(k,n) is a pair (S,f), where

	i) S is a nonempty subset of TR(k,n);
	ii) dom(f) = {(T,x):S in S, x in [n]^k, and x dominates T};
	iii) for all (T,x) in dom(f), f(T,x) in V(T);
	iv) for all (T,x) in dom(f), T/x,f(T,x) in S.

We say that (S,f) admits T if and only if T in S. We say that (S,f) is
decreasing if and only if for all T_1 containedin T_2 from S, x in [n]^k, x
dominating T_2, we have f(T_1,x) >=* f(T_2,x).

We say that (S,f) is initial if and only if the trivial k-tree lies in S.
This definition is also made for insertion rules in TR(k).

Here are the natural finite forms of the previously cited results. Not that
"initial" is used in Theorems A1.1' and A3.3', as well as in Propositions
A1.2' and A3.4'. This is needed.

THEOREM A1.1'. For all k,p >= 1 there exists n such that the following
holds. Every nonincreasing initial insertion domain in TR(k,n)
contains a k,n-tree in which all k element subsets of some p element set
are vertices with the same number of ancestors.

PROPOSITION A1.2'. For all k,p >= 1 there exists n such that the following
holds. Every nonincreasing initial insertion domain in TR(k,n)
contains a k,n-tree in which all k element subsets of some p element set
are vertices with the same entirely lower ancestors. Moreover, these
vertices can be required to have the same number of ancestors.

THEOREM A2.1'. For all k,p >= 1 there exists n such that the following
holds. Every insertion rule on TR(k,n) greedily generates a k,n-tree in
which all k element subsets of some p element set are vertices with the
same number of ancestors.

PROPOSITION A2.2'. For all k,p >= 1 there exists n such that the following
holds. Every insertion rule on TR(k,n) greedily generates a k,n-tree in
which all k element subsets of some p element set are vertices with the
same entirely lower ancestors. Moreover, these vertices can be required to
have the same number of ancestors.

THEOREM A3.1'. For all k,p >= 1 there exists n such that the following
holds. Every decreasing insertion rule on TR(k,n) generates a k,n-tree in
which all k element subsets of some p element set are vertices with the
same number of ancestors.

PROPOSITION A3.2'. For all k,p >= 1 there exists n such that the following
holds. Every decreasing insertion rule on TR(k,n) generates a k,n-tree in
which all k element subsets of some p element set are vertices with the
same entirely lower ancestors. Moreover, these vertices can be required to
have the same number of ancestors.

THEOREM A3.3'. For all k,p >= 1 there exists n such that the following
holds. Every decreasing initial insertion rule in TR(k,n) admits a k,n-tree in
which all k element subsets of some p element set are vertices with the
same number of ancestors.

PROPOSITION A3.4'. For all k,p >= 1 there exists n such that the following
holds. Every decreasing initial insertion rule in TR(k,n) admits a k,n-tree in
which all k element subsets of some p element set are vertices with the
same entirely lower ancestors. Moreover, these vertices can be required to
have the same number of ancestors.