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

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