3
$\begingroup$

In the wikipedia article on Model Theory in the section on Categoricity it is said that:

As observed in the section on first-order logic, first-order theories cannot be categorical, i.e. they cannot describe a unique model up to isomorphism, unless that model is finite.

And in the linked article on first order logic they refer to the Löwenheim-Skolem-Theorem, which states that every first order sentence that has an infinite model, already has a countable model. But what if the only model is already countable, then Löwenheim-Skolem does not give anything new, so why then could this sentence not be categorical?

$\endgroup$
10
$\begingroup$

The compactness theorem for first-order logic gives us the upwards Löwenheim–Skolem theorem, and that means that if $T$ is a theory that has an infinite model, then it has an infinite model of every cardinality. In particular, assuming $\sf ZFC$, there is a proper class of different cardinalities, so there are at least two. And two models of two different cardinalities cannot be isomorphic.

What is surprising, however, is that for uncountable cardinals, if $T$ is a theory that is $\kappa$-categorical for one uncountable cardinal (namely, all models of size $\kappa$ are isomorphic), then it is $\kappa$-categorical for all uncoutnable cardinals.


What the downwards Löwenheim–Skolem does tell us is that as far using models to determine provability, or consistency, countable models are enough.

$\endgroup$
7
$\begingroup$

The term "Löwenheim-Skolem theorem" refers to several different related theorems. One of these theorems (the one that was actually proved by Löwenheim and Skolem) is the theorem you mentioned, that any first-order theory (in a countable language) which has an infinite model also has a countable model. This is known as (a weak form of) the "downward" Löwenheim-Skolem theorem, since it lets you decrease the cardinality of your models to $\aleph_0$. But there is also an "upward" Löwenheim-Skolem theorem, which says that if a first-order theory (in a countable language) has a model of a given infinite cardinality $\kappa$ and $\lambda\geq\kappa$, then it also has a model of cardinality at least $\lambda$. This immediately implies a failure of categoricity for theories with countable models as well.

There are also stronger forms of these theorems: for instance, a stronger version of downward Löwenheim-Skolem is that if $M$ is any infinite model of a first-order theory over a language of cardinality $\kappa$ and $A\subseteq M$ is a substructure, then there exists an elementary submodel $N\preceq M$ containing $A$ with $|N|\leq |A|+\kappa$. This implies in particular that over a countable language, if there exists a model of an infinite cardinality then there exists a model of any smaller infinite cardinality. Combined with the upward Löwenheim-Skolem theorem, this says that if a first-order theory over a countable language has an infinite model, it has models of every infinite cardinality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.