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

Solutions Collecting From Web of "Weak categoricity in first order logic"

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.

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

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.