FOM: 52:Cardinals and Cones

[Harvey Friedman]

This is the 52nd 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
32:Greedy Constructions/Large Cardinals  3/2/99  11:21PM
33:A Variant  3/4/99  1:52PM
34:Walks in N^k  3/7/99  1:43PM
35:Special AE Sentences  3/18/99  4:56AM
35':Restatement  3/21/99  2:20PM
36:Adjacent Ramsey Theory  3/23/99  1:00AM
37:Adjacent Ramsey Theory/more  5:45AM  3/25/99
38:Existential Properties of Numerical Functions  3/26/99  2:21PM
39:Large Cardinals/synthesis  4/7/99  11:43AM
40:Enormous Integers in Algebraic Geometry  5/17/99 11:07AM
41:Strong Philosophical Indiscernibles
42:Mythical Trees  5/25/99  5:11PM
43:More Enormous Integers/AlgGeom  5/25/99  6:00PM
44:Indiscernible Primes  5/27/99  12:53 PM
45:Result #1/Program A  7/14/99  11:07AM
46:Tamism  7/14/99  11:25AM
47:Subalgebras/Reverse Math  7/14/99  11:36AM
48:Continuous Embeddings/Reverse Mathematics  7/15/99  12:24PM
49:Ulm Theory/Reverse Mathematics  7/17/99  3:21PM D.A. Martin is the
originator of cone theorems involving Turing degrees.
50:Enormous Integers/Number Theory  7/17/99  11:39PN
51:Enormous Integers/Plane Geometry  7/18/99  3:16PM

This posting concerns cone theorems involving structures from other areas
of mathematics such as model theory and descriptive set theory.

1. Cones of relational structures.

A reasonable measure of the complexity of a relational structure is the
class of structures that are interpretable in that structure. All
structures will be assumed to have a finite relational type, with standard
equality.

We will use the following definition. Let M,N be relational structures in a
finite relational type. An exact interpretation of M in N is an
interpretation of M in N where the domain of the interpretation is the
whole domain of N and equality is interpreted as equality. I.e., an exact
interpretation of M in N is given by

i) formulas with one free variable for each constant of M, which is to have
a unique solution in M, and which serves as the interpretation of that
constant;
ii) formulas with n free variables for each n-ary relation of M, whose
extension in N is a set of n-tuples of the domain of N, and which serves as
the interpretation of that relation;
iii) formulas with n+1 free variables for each n-ary function of M, whose
extension in N is the graph of an n-ary function on the domain of the
interpretation, and which serves as the interpretation of that relation;
vi) there is an isomorphism from M onto the relational structure defined in
N using i) - iii).

We write M <= N if and only if there is an exact interpretation of M in N.
We write M == N if and only if M <= N and N <= M. A cone of structures is a
class of relational structures of the form {M: M >= N}. A cone of countable
structures is a class of countable relational structures of the form {M: M
is countable and M >= N}. There can be no confusion since obviously no cone
can consist entirely of countable structures. Also, proper classes are
unnecessary for the treatment of cones of countable structures since we
can, without loss of generality, insist that all countable structures have
domain omega.

THEOREM 1.1. Every first order class of countable structures contains or is
disjoint from a cone of countable structures.

THEOREM 1.2. Theorem 1.1 is provable in Zermelo set theory but not in
Zermelo set theory with bounded separation. It is necessary and sufficient
to use infinitely many uncountable cardinals in order to prove Theorem 1.1.
These assertions hold even if only finitely axiomatized first order classes
of countable structures are considered.

Intuitively, Theorem 1.1 says that if a first order theory has arbitrarily
complicated countable models then it has countable models of every
sufficiently complicated kind.

2. Cones in Borel orderings.

We now consider quasi orderings <=* on the reals, R (transitive and
reflexive). We say that <=* has the Borel cone property if and only if the
following holds. Let A be a Borel subset of R such that every element of R
is <=* some element element of A. There exists x in R such that for all y
>=* x, y is ==* some element of A.

We say that <=* is locally countable if and only if for all x in R, {y: y
<=* x} is countable.

THEOREM 2.1. The following are provably equivaent in ATR_0.
i) every sufficiently inclusive locally countable Borel quasi ordering has
the Borel cone property;
ii) some locally countable Borel quasi ordering in which any two elements
have an upper bound has the Borel cone property;
iii) for all x containedin omega and countable limit ordinals lambda, there
exists a countable model of V(lambda) which contains x.

This uses D.A. Martin's cone theorem for Turing degrees and my work on the
metamathematics of the cone theorem for Turing degrees and other degrees.

3. Cones with real functions.

Let K be a set of unary functions on the reals, R, which is closed under
composition. For x,y in R, we write x >=K y if and only if y = x or y is
the value of an element of K at x. Note that <=K is a quasi ordering
(reflexive and transitive). Write x ==K y for x <=K y and y <=K x. R is the
set of all real numbers.

THEOREM 3.1. The following are provably equivaent in ATR_0.
i) for every sufficiently inclusive countable set K of unary continuous
functions on R closed under composition, <=K has the Borel cone property;
ii) for every sufficiently inclusive countable set K of unary continuous
functions on R closed under composition and finitely generated under
composition, <=K has the Borel cone property;
iii) for every sufficiently inclusive countable set K of unary Borel
functions on R closed under composition, <=K has the Borel cone property;
iv) for all x containedin omega and countable limit ordinals lambda, there
exists a countable model of V(lambda) which contains x.
Furthermore, this result holds if R is replaced by the closed unit
interval, the Cantor set, or even any uncountable complete separable metric
space.