[FOM] CATEGORICITY and STRONGLY MINIMAL SETS

[Harvey Friedman]

Reply to Baldwin 7:13PM 6/29/03.

Friedman wrote:

>>
>>Let T be a first order sentence that has an infinite model. I have 
>>been interested in the question of whether you can explicitly 
>>construct a model of T whose domain is a given infinite set D.

Baldwin wrote:

>
>I am quite confused here.  What set theory are your working in and 
>what is the meaning of explicit?
>
>I guess that I rarely think about universes where c) fails; so it is 
>hard for me to grasp the question.  Reading more carefully I see 
>that this
>is explicitly a question about choice -- or maybe a more subtle 
>variant. Questions about explicitness of construction of e.g. 
>algebraic closure have
>been investitgated by Hodges and Shelah.

There is a lot of robustness to explicitness, but this robustness has 
not been systematically explored.

When interested in explicitness, it is often sensible to START 
thinking in terms of ZF.

CLAIM: If something cannot be done in ZF then normally there is a 
gross non canonicalness or nonexplicitness that is deeply disturbing 
mathematicallly.

EXAMPLE: Simply citing "let W be a well ordering of the reals" is 
deeply disturbing mathematically.

In the case of elementary model theory, something very interesting is 
ferreted out by simply doing the obvious - which is thinking in terms 
of ZF. Other formulations are equally interesting, involving ZFC, as 
I will indicate before.

If I convince you that this is a very illuminating auxiliary project 
in the case of the most elementary of the elementary of the 
elementary of model theory, then you could become convinced that is a 
good idea to look at things this way for more advanced model theory? 
Everything below is in first order predicate calculus with equality.

THEOREM 1. (ZFC). Let T be a countable theory with an infinite model. 
Let D be an infinite set. Then T has a model with domain D.

THEOREM 2. (ZF). Theorem 1 is equivalent to AxC.

This suggests that there is something horribly non canonical and 
disturbing about Theorem 1.

Which D are OK? Obviously any well ordered D is reasonably OK since 
you can actually construct the model reasonably explicitly. What 
other D?

THEOREM 3. (ZF). Let D be a set. The following are equivalent.
1. Every countable theory with an infinite model has a model with domain D.
2. Every finitely axiomatized theory with an infinite model has a 
model with domain D.
3. D is infinite, there is a one-one binary function from D into D, 
and there is a linear ordering of D.

The proof of this has some tricky points, and of course uses the 
theory of indiscernibility, and is very satisfying, model 
theoretically.

Now for other formulations over NBG + GC = von Neumann Bernays class 
theory with the global axiom of choice.

THEOREM 4. NBG + GC. Let D be a set. The following are equivalent.
1. Every countable theory T with an infinite model has a model with 
domain D which is set theoretically definable from D,T.
2. Every finitely axiomatized theory with an infinite model has a 
model with domain D which is set theoretically definable from D.
3. There is a one-one binary function from D into D and a linear 
ordering of D which are both set theoretically definable from D.

THEOREM 5. ZFC. Let D be a set. The following are equivalent.
1. Every countable theory T with an infinite model has a model with 
domain D which is ordinal definable from D,T.
2. Every finitely axiomatized theory with an infinite model has a 
model with domain D which is ordinal definable from D.
3. There is a one-one binary function from D into D and a linear 
ordering of D which are both ordinal definable from D.

The models constructed from a one-one binary function from D into D 
together with a linear ordering of D, are EXTREMELY explicit, as to 
be the exact opposite of disturbing.

There are other formulations that I won't go into now, having to do 
with "demonstrable explicitness" over ZFC.

>>
>>Also, what is the computational complexity of the set of sentences 
>>that are aleph 0 categorical? And how complicated is the unique 
>>model, up to isomorphism?
>
>I think there is a peper of 3 Poles in the early 70's Grecgorcyzk 
>(sp?) Ryll-Nardewski ???  It may come to me.  Also checl with some 
>of the recursrive
>nmodel theorists.

Any recursive model theorists here on FOM?

>>>
>>>prehistory:
>>>
>>>Los-Vaught test:  If a theory is categorical in power then it is
>>>complete.
>>>
>>>Morley's Theorem: A(countable) theory is categorical in one
>>>uncountable power iff it is categorical in all uncountable 
>>>powers.Is there an interesting version of this in ZF? Of course, 
>>>you can just restrict yourself to well ordered cardinalities and 
>>>simply repeat the statement. But that might not be the most 
>>>illuminating way to proceed.
>>>
>>>NOTE: One can also formulate this in terms of definability and 
>>>ordinal definability in ZFC.
>>
>I have never thought about any of these problems in the absence of 
>choice.  Perhaps Felgner has.
>
>Other than just sorting out details, why should one be interested in 
>the situation without choice.   The naturalness of `categoricity in 
>power' depends on
>power being well-defined.

I would think that behind every set theoretically formulated theorem 
in model theory that model theorists of the modern kind really care 
about, there is a formulation that is not very set theoretic. In 
particular, well orderings should play NO ROLE for the modern model 
theorist.

One can ferret this out by moving to a combinatorial situation that 
does not look the same as the original situation - I gather this has 
been done a lot.

Or one can look for an intermediate step in which some set theoretic 
machinery is removed by fiat. I.e., look for no axiom of choice, or 
look, with the axiom of choice, for set theoretic explicitness. The 
explicitness needed may be so strong that it immediately ties in with 
underlying combinatorics. The motivation seems obvious to me. Part of 
a very general program in f.o.m.

>>
>>Also, I gather that T, a theory, is minimal (strongly minimal) if 
>>every definable set (in every elementary extension) is finite or 
>>cofinite.
>>
>>Obviously one can define a hierarchy here according to the 
>>complexity of the definable set. Thus we have
>>
>>degree k minimal
>>degree k strongly minimal
>
>I think this is a misreading.  I mean definable subset of the model 
>in the language of the model.  Complexity questions about the 
>recursiveness of the
>model raise an entirely different set of issues.

I was not directly talking about the recursiveness of the model, but 
rather the sizes of the finite sets involved as a function of the 
definitions.

For example, for algebraically closed fields, one has something like 
a double exponential bound, I gather.

In o-minimality, something I know better, there is the famous 
question about whether one can have transexponential behavior in an 
o-minimal expansion of the field of real numbers.

>
>>
>>
>>Do we in fact get a hierarchy? If we want, say, only degree 100, 
>>then presumably there is no shortage of finitely axiomatizable 
>>examples? And what happens if we study that?

I mean that we weaken the notion of (strongly) minimal theory to 
apply only to formulas with, say, a certain number of quantifiers. 
What happens? Anything interesting? Are there examples that create a 
hierarchy here?

>>
>>Also, what can one say about effectiveness in the sense that, given 
>>a definition, what is a bound on the size of the extension or 
>>coextension, as a function of the complexity of the definition? In 
>>the paradigm case of algebraically closed fields, this is a 
>>manageable function. Otherwise?

Replace "effectiveness" with "quantitaive information; i.e., bounds".

>
>Most of us work in ZFC; as I indicated Hodges has worried about the 
>ZF situation.

But I know that most modern model theorists deeply care about explicitness...

>>
>>
>>If there are wqo's, there is fire. So can you state the most model 
>>theoretically relevant fact that involves wqo's for us?
>
>Although from Zilber and CHL we have that no totally categorical 
>structure is finitely axiomatiazable -- a dual conjecture arose.
>That totally categorical  theories werequasifinitely axiomatized: 
>i.e. axiomatized by  an zxiom of infinity (i.e. infinitely many 
>sentences saying the uiversie is infinite) +  a single senence
>
>This is obvious for vector spaces over a finite field (modular 
>aleph_0 categorical strictly minimal sets).  Certain special cases 
>of this were obtained
>by Ahlbrandt and Ziegler using a lemma of Higman (maybe wq0 was an 
>exageration);  Eventually with a suitable generalization of axiom of 
>infinity the
>quaifinitely axiomatizability of omega stable aleph_0 categorical 
>structures was established by Hrushovski.  See Chapter 3 of Pillay 
>-- Geometric stabiltiy theory
>

Yes, that "lemma of Higman" is a tiny initial segment of wqo theory, 
but still a very significant one. The use of Higman's Lemma DOES 
involve some specific kind of non explicitness (nothing to do with 
ZF/ZFC and well orderings of uncountable sets).

Harvey Friedman