[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*Subject*: FOM: 52:Cardinals and Cones*From*: Harvey Friedman <friedman@math.ohio-state.edu>*Date*: Sun, 18 Jul 1999 15:33:01 +0100*Sender*: owner-fom@math.psu.edu

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.

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]