FOM: background for Friedman's results

[Stephen G Simpson]

This is in response to Torkel Franzen's recent posting.  I want to
help Franzen understand Friedman's results.  One difficulty here is
that I'm not sure how strong Franzen's mathematical background is.

Torkel Franzen 16 Mar 1998 17:45:23 writes:
 > how much of a foundational advance this is depends strongly on what
 > applications can be found of the combinatorial principles at issue.

Are you aware that there are many well known theorems in pure
mathematics and f.o.m. that have no applications at all?  An example
in number theory is Fermat's last theorem.  An example in f.o.m. is
the independence of the continuum hypothesis (G"odel/Cohen).

 > it also depends strongly on the epistemological status of the large
 > cardinal principles involved.

Are you aware that there is a hierarchy of large cardinal principles
which is well-ordered by consistency strength?  Since you don't know
what a subtle cardinal is, let me mention that subtle cardinals are
stronger than inaccessible cardinals but nevertheless fairly low down
in the hierarchy.  In particular, they are consistent with the
so-called axiom of constructibility, V=L, which occurred in G"odel's
work on the continuum hypothesis.  By way of contrast, measurable
cardinals are stronger and contradict V=L.

In view of your difficulty in understanding Friedman's combinatorial
statements, it occurred to me that you may be unfamiliar with
combinatorial topics such as trees and Ramsey's theorem.

A tree is a connected, undirected graph with no cycles.  There is an
extensive combinatorial and graph-theoretic literature on trees,
including e.g. Kruskal's theorem, which says that there is no infinite
pairwise nonembeddable set of trees.

Finite trees are used in computer science as data structures to hold
information for retrieval.  In this context, insertion of new nodes is
relevant, because it corresponds to adding a new piece of information
to a database.  Friedman's independent statements involve inserting
nodes into labeled trees.

Ramsey's theorem is a famous combinatorial theorem.  It reads as
follows: Given a coloring of the k-element subsets of N with finitely
many colors, we can find an infinite subset X of N all of whose
k-element subsets have the same color.  There is an extensive
literature on this.  See for instance the book by Graham, Rothschild
and Spencer on Ramsey theory.

-- Steve