Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?

Recall that a structure $$\mathcal{M} = \langle M, I^\sigma_M \rangle$$ in a signature $$\sigma$$ is categorically axiomatized by a second-order theory $$T$$ when, for any $$\sigma$$-structure $$\mathcal{N} = \langle N, I^\sigma_N \rangle$$, $$\langle N, \mathcal{P}(N), I^\sigma_N \rangle \vDash T$$ just in case $$\mathcal{N}$$ is isomorphic to $$\mathcal{M}$$.

It is fairly easy to find a structure in a finite signature that is categorically second-order axiomatizable but not finitely categorically second-order axiomatizable. Add a single function symbol $$f$$ to the language of second-order arithmetic, and choose a non-second-order-definable $$\zeta: \mathbb{N} \rightarrow \mathbb{N}$$. Then consider the theory $$T$$ that adds to the axioms of second-order arithmetic ($$\mathsf{Z}^2$$) the sentence $$f(\bar{n}) = \overline{\zeta(n)}$$ for each natural number $$n$$, where $$\bar{m}$$ is the canonical numeral for $$m$$. (I owe the idea for this example to Andrew Bacon.)

This theory $$T$$, however, is not recursively axiomatizable. Is there a structure in a finite signature that has a recursive categorical second-order axiomatization but no finite categorical second-order axiomatization?

I believe that it is possible to find a recursively axiomatizable second-order theory $$T$$ whose spectrum (i.e., the set $$\{\kappa \in \mathsf{Card}: \exists \mathcal{M} (\mathcal{M} \vDash T$$ and $$\vert \mathscr{M} \vert = \kappa)\}$$) is shared by no finitely axiomatizable second-order theory, using partial truth predicates. (Consider the theory with $$\mathsf{Z}^2$$ relativized to some predicate $$N$$ and $$\{$$"The cardinality of the non-$$N$$s is not $$\Sigma^1_n$$-characterizable"$$: n \in \omega\}$$.) But I cannot see how to turn this into a categorical theory.

• Yes, thank you! Dec 3, 2021 at 4:12
• In that case you may want to accept one of the existing answers, to indicate that the question has been resolved. Jan 23 at 19:28

Sure - in fact, we can find a countable (and pretty concrete) example.

Let $$\mathcal{N}=(\mathbb{N};+,\times)$$ be the standard model of (first-order) arithmetic and let $$R\subseteq\mathbb{N}^2$$ be the binary relation given by $$(a,b)\in R$$ iff the $$a$$th $$\Sigma^1_b$$ sentence (in arithmetic, according to some standard enumeration) is true in $$\mathcal{N}$$. That is, $$R$$ codes the second-order theory of $$\mathcal{N}$$.

The structure $$(\mathbb{N};+,\times, R)$$ is second-order recursively axiomatizable: we use a single second-order sentence to fix the $$\{+,\times\}$$-reduct, and then recursively say that each column of $$R$$ codes the appropriate set. By the non-collapsing of the second-order hierarchy, this can't be done by a single second-order sentence.

Note that this trick can be generalized to a wide variety of logics. For logics like $$\mathcal{L}_{\kappa,\lambda}$$ which don't "fit" into $$\mathbb{N}$$ in a reasonable way, we need to $$(i)$$ shift to a different "base" and $$(ii)$$ possibly adopt a different notion of "recursive," but an analogous result should hold.

There is even an example of a cardinal $$\kappa$$ and an r.e. categorical second-order theory $$T$$ such that for no finitely axiomatized second-order theory $$U$$, the spectrum of $$U$$ has $$\kappa$$ as its least element.

Let $$T_0$$ be the theory $$\mathsf{ZC}_2+\forall x\exists \alpha(x\in V_\alpha)$$, here $$\mathsf{ZC}_2$$ is the second-order version of Zermelo set theory where in the separation scheme we allow formulas without class quantifiers, but with class variables. It is easy to see that the second-order models of this theory are precisely $$(V_\alpha,\in)$$, for limit $$\alpha>\omega$$. Further I denote by $$\mathcal{L}$$ the set of sentences of the language of this theory.

Let $$T$$ be the extension of $$T_0$$ by

1. $$\forall \alpha (\exists \varphi\in \mathcal{L}) (((V_\alpha,\in)\models_2\varphi)\land \forall \beta<\alpha ((V_\beta,\in)\not\models_2\varphi))$$.
2. $$\varphi\to\exists \alpha ((V_\alpha,\in)\models_2 \varphi)$$, where $$\varphi$$ ranges over $$\mathcal{L}$$.

Obviously the only second-order model of $$T$$ is $$(V_\alpha,\in)$$, where $$\alpha$$ is the least ordinal such that for any $$\varphi\in\mathcal{L}$$ if $$(V_\alpha,\in)\models \varphi$$, then for $$(V_\beta,\in)\models \varphi$$, for some $$\beta<\alpha$$. Clearly, $$\alpha>\omega^2$$ and hence the cardinality of this model is $$\beth_\alpha$$, which will be our $$\kappa$$.

Suppose for a contradiction that there is a second-order sentence $$\varphi$$ such that the smallest model of $$\varphi$$ is in the cardinality $$\beth_\alpha$$. Let $$\varphi'$$ be the naturally constructed sentence of second-order set theory expressing that there exists a class-model of $$\varphi$$. By construction $$(V_\alpha,\in)\models_2\varphi'$$, but for no $$\beta<\alpha$$ we have $$(V_\beta,\in)\models_2\varphi'$$, contradiction.