[FOM] CATEGORICITY and STRONGLY MINIMAL SETS

[Harvey Friedman]

Reply to Baldwin 8:46AM 6/21/03.

>The study of categoricity dates (at least) from the work of
>Huntington around the turn of the 20th century.

Who is Huntington, and what did he do at that surprisingly early date?

>While a second
>order sentence can be categorical -- have exactly one infinite
>model, the Lowenheim Skolem theorem shows that a first order
>sentence which has an infinite model has one in every infinite
>cardinality.

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.

The answer is no in general.

THEOREM. (ZF, or even a very weak fragment of ZF). Let D be a set. 
The following are equivalent.
a) every sentence in predicate calculus with equality that has an 
infinite model has a model with domain D;
b) every set of sentences in in predicate calculus with equality in a 
countable language, that has an infinite model has a model with 
domain D;
c) D has a linear ordering and there is a one-one map from DxD into D.

COROLLARY. "Every sentence in predicate calculus with equality which 
as an infinite model has a model whose doamin is any given infinite 
set" is provably equivalent to ZFC over ZF.

ZFC is stronger than ZF + "every set can be lineary ordered".

NOTE: This turns out not to be a crude question about what can be 
done without the axiom of choice, but rather a question about the 
explicitness of a construction in a very strong sense.

NOTE: One can also formulate things in terms of definability and 
ordinal definability in ZFC.

>Understanding the nature of  sentences or theories
>which are categorical in kappa (have only one model of cardinality
>kappa) has been a major theme in model theory since the 50's. This
>study evolved through the methods of stability theory into
>understanding which models admit a nice structure theory (in the
>sense of an algebraist).  This structure theory is built around a
>dimension theory which is incompatible with Godelian phenomena, so
>categorical structures are `tame' in the sense of Van den Dries. I
>may say more about this in a later note.  The tameness
>observation, although implicit since at least the 70's, has not
>played a significant explicit role in the development.

I think it was shown some time ago that there are nonfinitely 
axiomatizable theories in a countable language which are aleph 0 
categorical? Glassner, a student of Cohen??

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?

>
>Any aleph one categorical theory is determined by its so-called
>strongly minimal sets. In this note I will sketch some background
>information about strongly minimal sets.


>
>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.

>
>
>the `little Vaught conjecture': an aleph_1 categorical theory has
>either 1 or aleph_0 countable models.


Same questions.

>
>Morley's conjecture:  No aleph_1 categorical theory is finitely
>axiomatized.
>

Same questions.

>
>Basic properties of strong minimality:
>
>A set is minimal (strongly minimal) if every definable set (in
>every elementary extension) is finite or cofinite.

Do you mean

definable subset

instead of

definable set?

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

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?

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?
>
>
>
>Model theorists generalize the field theoretic notion of algebraic
>closure by saying a is in the algebraic closure of X in M if M
>models phi(a,xbar) for some formula with parameters from X that
>has only finitely many solutions.  It is easy to see that in a
>strongly minimal set, algebraic closure has the properties of a
>closure relation studied in linear algebra (or of transcendence
>degree). (An account of generalized closure relations will be
>another post.) Thus there is a natural notion of dimension,
>invariance of basis number etc. and this implies that every
>strongly minimal theory is categorical in all uncountable powers.

What about explicitness, and provability in ZF, and definability over 
ZFC, etc.?

>
>Listing the strongly minimal sets:
>
>The standard strongly minimal models are (Z,S), vector spaces over
>any fixed field, algebraically closed fields.  Zilber conjectured
>that in some sense this was all.  The Hrushovski construction
>refutes that conjecture.
>
>Zilber proved that every strongly minimal set that is
>aleph_0-categorical is essentially a vector space over a finite
>field.  (The `essentially' hides some rather interesting technical
>mathematics of Cherlin-Harrington-Lachlan, Ahlbrandt-Ziegler,
>Pillay-Hodges which involves both cohomology and
>well-quasi-orderings.)

If there are wqo's, there is fire. So can you state the most model 
theoretically relevant fact that involves wqo's for us?

Harvey Friedman