# Weak categoricity in first order logic

In a certain sense, only finite structures are definable up to isomorphism in first order logic. But if we rely on a metatheory containing a sufficient strong set theory (like required for second order logic), would it be possible to also define certain infinite structures up to isomorphism by requiring additional conditions like minimality (i.e. conditions independent of the syntax and axioms)? The set theory would be required here in order to give meaning to the additional conditions (i.e. minimal might mean here that no proper subset of the model satisfies the given first order theory).

-

If you allow ANY kind of set-theoretic notions, then of course you can describe any model up to isomorphism, even without using any model-theoretic notions, by simply defining the set.

As for your question, there is actually a notion of minimal model, that is, a model which has no proper elementary substructure, but it is not in general unique up to isomorphism. For example, the theory of additive group of integers has $\mathfrak c$ nonisomorphic minimal models. On the other hand, some theories do have a unique minimal model, for example the theory of natural numbers with successor.

There are also other model-theoretic notions which are strong enough to uniquely define a model of a given complete theory, such as:

• a primal model of any theory, which can intuitively be described as one which can be inductively constructed by blocks defined in terms of all the previous ones by a simple formula
• a prime model of a countable theory, which is a model such that it can be embedded as an elementary substructure into any other model of the theory (nb a primal model is always prime)
• a saturated model in a given cardinalty, which can be seen as a very rich model, which has elements having any noncontradictory set of properties you can define without using very many elements of the model (I'm not entirely sure if we need any stronger assumptions if the theory is uncountable, but for countable complete theories a saturated model in a given cardinality is unique)

Note that, however, not every theory has a minimal, prime, or primal model, for example the theory of additive integers has no prime model, and the theory of countably infinitely many independent equivalence relations with two classes has no minimal model.

Assuming existence of a strongly inaccessible cardinal, every theory has a saturated model in a strongly inaccessible cardinality (I know it to be true for countable theories, but it should probably still hold for any theories whose languages are smaller than some strongly inaccessible cardinal), but without it I think there might be theories without any (or at least I haven't heard of a theorem that would provide them for arbitrary theories without large cardinal assumptions).

As Benedict pointed out, there are also some theories which have a unique model in a given cardinality $\kappa$, which are called $\kappa$-categorical. If a theory is $\kappa$-categorical (and $\kappa\geq \lvert T\rvert$), then the sole model of cardinality $\kappa$ is necessarily saturated, but cardinality is of course a more set-theoretic description.

Another, more algebraic notion which can sometimes be used to uniquely describe a model of some theories is the acl-dimension. Some theories, called strongly minimal theories (examples of which are vector spaces over a fixed field or algebraically closed fields of fixed characteristic) have a well-behaved notion of independence generalizing both linear and algebraic independence, and for those theories a model of the theory is uniquely (up to isomorphism) determined by its dimension.

In yet another direction, you can use infinitary logic. Similarly to how regular first-order logic can uniquely define finite models with a single sentence, if you allow countably infinite conjunctions you can uniquely define countable models with a single sentence (that is Scott's isomorphism theorem). For stronger infinitary languages, it it also possible for larger cardinalities. However, infinitary logic is quite a bit more messy than the usual first-order logic as far as I know.

-
Thanks for your answer. I have some questions/remarks: I don't understand what you mean with your first sentence. I don't understand the example with the additive group of integers. I don't understand the notion of "primal model", and couldn't find it via googling. Is it correct that if the minimal model exists and is unique, then it is also a prime model? Does infinitary logic requires a sufficiently strong set theory (like required for second order logic)? –  Thomas Klimpel Jul 9 '12 at 8:29
@ThomasKlimpel: for the additive group of integers, the minimal models can be defined expliclitly in a way similar to this question; as for primal model, I think I've seen it in some book or paper, but I can't remember where, I'll try to link it later if I find it. To be more exact, it is a model such that it can be written as a sequence $a_\alpha$, where for each $a_\alpha$, its type over the previous elements is isolated. I can't tell you much about this topic, as it was only a short side discussion during one of my courses. –  tomasz Jul 9 '12 at 11:57
@ThomasKlimpel: as for minimal models, if a prime model and a minimal model both exist, then they coincide and are unique, but I'm not sure about the unique minimal model situation -- you might want to ask a question about it here; as for infinitary logic, it is naturally strongly dependent on set theory (after all, it uses infinite cardinals in its definition), but if you ask about dependence on e.g. continuum hypothesis, restricting yourself to $L_{\omega_1,\omega}$, for example, shouldn't be that dangerous, but again, I'm quite inexperienced with infinitary logic. –  tomasz Jul 9 '12 at 12:11
@ThomasKlimpel: with the first sentence I meant that you can simply "define" a model as a specific set (or a model isomorphic to it), then it will be unique. :) –  tomasz Jul 9 '12 at 12:49
Lots of interesting stuff in here, thanks @tomasz. –  Benedict Eastaugh Jul 9 '12 at 16:22

Suppose $T$ is a first order theory in a countable language $\mathcal{L}$. $T$ is $\kappa$-categorical iff for an infinite cardinal $\kappa$, $T$ has only one $\kappa$-sized model (up to isomorphism). By Morley's categoricity theorem, if $T$ is $\delta$-categorical for some $\delta > \omega$, then $T$ is $\gamma$-categorical for all $\gamma > \omega$.

So for theories which are $\kappa$-categorical for uncountable $\kappa$, if you can fix the cardinality of the structures satisfying $T$ in the metatheory to be at least $\omega_1$, then you will have only one model of $T$ up to isomorphism. Similarly if you have an $\omega$-categorical theory and fix the cardinality of $T$-structures as $\aleph_0$.

-
Note that if a theory is $\omega$-categorical, then its only countable model is prime and saturated, and when it is $\kappa$-categorical for uncountable $\kappa$, the only model of cardinality $\kappa$ is saturated, so it kind of overlaps with my answer. Still, good point. –  tomasz Jul 9 '12 at 2:08

During reading Ebbinghaus et al., I realized that there is a set of formulas which defines the class of non standard natural numbers. Of course, there is also a set of formulas which defines the class of natural numbers (both standard and non standard). By taking the "class difference" of these two classes, it should be possible to define the "standard natural numbers" up to isomorphism without reference to any underlying "strong" set theory.

-
Set of formulas in what language? Defines as a subclass of what? –  tomasz Sep 26 '12 at 14:05
@tomasz Using the notation and conventions of Ebbinghaus et al., a set of formulas in the language $L^S$ for $S=\{ \boldsymbol{\sigma}, 0 \}$ would suffice. However, it's probably better to work with a set of sentences instead of a set of formula (free variables are a subtle issue), in which case a set of sentences in the language $L_0^S$ for $S=\{ \boldsymbol{\sigma}, 0, \omega \}$ would suffice. (The sentences would be such that the constant $\omega$ is either equal to the constant $0$, or else a non-standard number.) However, I wonder more about the other part... –  Thomas Klimpel Sep 26 '12 at 15:12
... The "subclass of what" would have to be defined with respect to some "universe". The question would be whether the definition works for any "universe", even much weaker ones than ZFC. However, if the "universe" doesn't allow to talk about "isomorphism", then we can't say that we have defined the "standard natural numbers" up to isomorphism. So whether the definition succeeds in defining the natural numbers up to isomorphism depends at least a bit on the underlying set theory. –  Thomas Klimpel Sep 26 '12 at 15:22
I think you also need the notion of subset and and the image of a set by a function to pull that off. If you're using set theory freely, I think all you really need is the Zermelo set theory without choice or replacement. You can then define $\omega$ as a set and then define natural numbers up to isomorphism as a set, together with an unary function and an element, which is isomorphic to $(\omega,x\mapsto x\cup \{x\},\emptyset)$. But that's pretty much the first thing I wrote in my post: you just specify a model! :) In this case you can do it without parameters, though. –  tomasz Sep 26 '12 at 17:18