Is there a theory in a finite language that is computably axiomatizable but not by a finite number of axiom schemas?

Let me give an example of a theory that is computably axiomatizable but isn't axiomatizable by finitely many schemas.

Fix any finite signature $\Omega$ with equality. Further by finite $\Omega$-models I'll mean models encoded by binary strings in a natural way. Observe that for any $\Omega$-theory $T$ axiomatized by finitely many schemas the set of all finite models of $T$ is $\mathtt{co}\text{-}\mathtt{NP}$. And observe that given a finite $\Omega$-model $\mathfrak{M}$ we could effectively construct an $\Omega$-sentence $\chi_{\mathfrak{M}}$ such that for any $\Omega$-model $\mathfrak{N}$ we have $$\mathfrak{N}\models \chi_{\mathfrak{M}}\iff \mathfrak{N}\simeq\mathfrak{M}.$$ Consider arbitrary computable set of finite $\Omega$-models $A$ that is closed under isomorphisms and isn't $\mathtt{NP}$. Let $U_A$ be the theory axiomatized by sentences $\lnot\chi_{\mathfrak{M}}$ for $\mathfrak{M}\in A$. Clearly $U_A$ is computably axiomatizable. However, the set of finite models of $U_A$ is the complement of $A$ and thus isn't $\mathtt{co}\text{-}\mathtt{NP}$. Hence $U_A$ couldn't be axiomatized by finitely many schemas.


This answers complements Fedor Pakhamov's, who provided an example of a computable theory that is not axiomatizable by finitely many schemas.

Following up on the comment by Andreas Blass to the question: Vaught proved that if a theory $T$ is computable and has "a modicum of coding", then $T$ is axiomatizable by a scheme. Vaught's result was improved by Albert Visser, in the paper below, where "the modicum of coding" used by Vaught is reduced to the modest demand that $T$ interprets a non-surjective unordered pairing, where pairing need not be functional.

A. Visser, Vaught's theorem on axiomatizability by a scheme, The Bulletin of Symbolic Logic, vol. 18 (2012), pp. 382-402.

A preprint of Visser's paper can be found here.

Tags:

Lo.Logic