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.


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.