I was told to ask this question on mathoverflow. I asked on math stack exchange whether there is a computably axiomatizable theory that can't be axiomatized by a finite number of axiom schemas. I got an answer, but it was a theory in an infinite language. Now, I am asking whether there is an example in a finite language.




---


*EDIT by non-OP: [this](https://math.stackexchange.com/questions/3701716/is-there-a-computably-axiomatizable-first-order-theory-which-is-not-finitely-axi?noredirect=1&lq=1) is the above-mentioned MSE question, and [this](https://math.stackexchange.com/a/3594021/28111) answer gives the definition of "scheme" being used.*



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.


