Are there any complete, first-order and unstable theories which have non-categorical second-order formulations? - MathOverflow

Are there any complete, first-order and unstable theories which have non-categorical second-order formulations?

2012-05-02T11:37:44Z

Since it's not stable, $PA$ fails at being categorical in a power in the worst possible way, having $2^{\lambda}$ models in any uncountable $\lambda$. But $PA$ regains its categoricity in the move to second order logic, by which I mean, once we replace the induction schema with a single, second-order axiom. Are there natural examples of unstable first-order theories for which categoricity is not recoverable in this way?

If the restriction to unstable $T$ is too strong, are there natural examples of complete, non-categorical first-order $T$ which are also non-categorical as second-order theories?

I'm struggling to think of such examples because I don't know of any axiomatizable, semantically complete but non-categorical second-order theory. Also, of course, unlike $PA$, not every theory has a natural second-order extension.

Thanks.

Answer by Joel David Hamkins for Are there any complete, first-order and unstable theories which have non-categorical second-order formulations?

2012-05-02T12:19:27Z

You had asked for theories that do not have a categorical second-order completion, but here is an answer to the dual question:

Theorem. Every consistent first order theory $T$ with an infinite model has a second-order completion that is not categorical.

Proof. Consider all the models of $T$. By the Lowenheim-Skolem theorem, there are such models of every infinite cardinality above the size of the language. For any such model $M\models T$, consider the second order theory $\text{Th}_2(M)$ of this model. Since there are a proper class of models $M$, but only a set of possible second-order theories, it follows by the infinitary pigeon-hole principle that there must be two models $M$ and $N$ of $T$ with the same second-order theory $\bar T=\text{Th}_2(M)$. Indeed, there must be such a theory $\bar T$ with a proper class of distinct models. Thus, $\bar T$ is a second-order completion of $T$, but not categorical because it has non-isomorphic models. QED

The move from PA to the second-order Peano theory is not really one of deduction so much as family resemblence---we choose the second-order Peano theory, which is categorical, because it is true in the intended model we had in mind for the first theory. But my argument above shows that we might have chosen differently, and arrived at a non-categorical second-order completion of PA or even of TA = True Arithmetic (first-order).

Meanwhile, if you are willing to expand the language to include an order relation, then indeed one can always find a categorical second-order completion.

Theorem Every consistent theory $T$ with a countable model has a second-order completion $\bar T$, in an expansion of the language by an order relation, such that $\bar T$ is categorical.

Proof. Suppose $M$ is a countable model of $T$. Let $\lt$ be an order relation on $M$ with order type $\omega$, or finite if $M$ is finite, and let $\bar T$ be the second-order theory of $\langle M,\lt\rangle$. Note that every element of $M$ is definable in $\langle M,\lt\rangle$, and further by the categoricity of second-order Peano, all models of $\bar T$ come equipped with an order $\lt$ of order type $\omega$ (or finite if $M$ is finite), and this provides an isomorphism of that model to $\langle M,\lt\rangle$. So $\bar T$ is categorical as a second-order theory. QED

Update. Here is an example perhaps along the lines you want. The ZFC axioms of set theory are first order, but have a second-order analogue ZFC₂ which is obtained in much the same way as your move from PA to second-order PA, namely, we replace the first-order schemes of ZFC, such as the replacement axiom scheme, with the natural second-order counterpart. Now, Zermelo famously proved that the models of ZFC₂ are precisely the models of the form $\langle V_\kappa,{\in}\rangle$, where $\kappa$ is an inaccessible cardinal. If there are at least two inaccessible cardinals, then ZFC₂ is not categorical, since these models disagree with each other on the number of inaccessible cardinals. But if there is only one inaccessible cardinal, then ZFC₂ IS categorical. So in the case of ZFC, the answer to your question is that it depends on the large cardinal background.

Answer by Dave Marker for Are there any complete, first-order and unstable theories which have non-categorical second-order formulations?

2012-05-02T18:13:13Z

Another spin on this question, that gets around the fact that there are only countably many second order sentences, is to look at categoricity in $L^2_{\kappa,\omega}$ where we allow conjunctions of size less that $\kappa$ and second order quantifiers. Hyttinen, Kangas and Vaananen (see http://www.math.helsinki.fi/logic/people/jouko.vaananen/HytKanVaa.pdf) show that, for suitable cardinals $\kappa$, all models of a complete first order theory $T$ of size $\kappa$ are characterized by and $L^2_{\kappa,\omega}$-sentence if and only if $T$ is ``classifiable" in the sense of Shelah's Main-Gap i.e., $T$ is stable, NDOP, shallow, and NOTOP.