6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Did my answer address your question? $\endgroup$ Dec 3, 2021 at 4:11
  • $\begingroup$ Yes, thank you! $\endgroup$ Dec 3, 2021 at 4:12
  • $\begingroup$ In that case you may want to accept one of the existing answers, to indicate that the question has been resolved. $\endgroup$ Jan 23, 2022 at 19:28

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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