8
$\begingroup$

Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity?

Here, arbitrarily high (computational) complexity means that for every computable predicate $P$ one can choose a theory $T$ (as above) such that $P$ is polynomial time computable from $T$.

Variations:
- A variation is to drop equality.
- A natural weakening is to replace 'complete' with 'decidable'.
- Existence of finitely axiomatizable theories with arbitrary c.e. Turing degrees was proved by William Hanf in "Model-theoretic methods in the study of elementary logic". The proof might be adaptable to give complete (or at least decidable) finitely axiomatizable theories with arbitrarily high complexity.

Without finite axiomatization, there are examples:
- If $P⊆ℕ$ is decidable and every finite pattern occurs in $P$, i.e. $∀k \, ∀S⊆k \, ∃n \, ∀k'<k \, (P(n+k') ⇔ S(k'))$, then the monadic second order theory of $(ℕ, <, P)$ is decidable. Proof sketch: Reduce a sentence to acceptance of $P$ by a deterministic infinite automaton; the structure of $P$ ensures that we eventually reach a terminal strongly connected component of states, and reach all of its states infinitely often.
- We can also encode (with linear time encoding and decoding) a decidable predicate on strings for decidability together with S2S (the monadic second order theory of binary strings with functions $s→s0$ and $s→s1$ but no other operations). I suspect S2S with a decidable predicate $P$ is decidable if $P$ is sufficiently generic, specifically $∀S \, ∀k∈ℕ \, ∀(\text{infinite branch } T)$ $∃t∈T \, ∀v (|v|<k) (P(tv) ⇔ S(v))$ where $|v|$ is the length of $v$.

Without first order logic, there are finitely presented equational theories of arbitrarily high complexity, including I believe the word problem for a finitely presented group.

With first order logic, for appropriate computations I think the theory of the computation graph with a sequential write-only output tape is decidable, but I am not sure how to formalize and prove it. Note that first order logic can only express local properties, and for bounded graph degree, formulas can be converted to Hanf normal form. Perhaps, there are also groups with finitely axiomatizable theories of arbitrarily high complexity.

As an aside, for "natural" (not necessarily finitely axiomatizable) decidable theories, the highest complexity that I know is iterated exponential, which occurs for S2S, S1S, WS2S, WS1S, and related theories. For natural decidable problems more generally, reachability in vector addition systems has Ackermann complexity.

$\endgroup$
9
  • $\begingroup$ I think one could produce the theories of arbitrary high complexities using the computation graph idea. Consider the theory $T_{n,m}$ of $n$ unary predicates and $2m$ unary functions $f_{i,j}$, $i<m$, $j<2$ s.t. $f_{i,j}(x)\ne x\to f_{i,1-j}(f_{i,j}(x))=x$. Observe that over it any $\Pi_2$-formula is equivalent to a $\Sigma_2$-formula and hence any formula is equivalent to a $\Sigma_2$-formula. $\endgroup$ Aug 17, 2022 at 15:04
  • $\begingroup$ Over $T_{n,2}$ we could finitely axiomatize something like computation protocols for a fixed Turing machine (by computation protocol I mean a grid, whose rows are states of the machine; we use four unary functions to walk within the grid). Then from one hand we would be able to express that the machine terminates with accepting state starting from a given input and perhaps under some assumptions about the machine we would be able to decide the resulting theory (the language of the theory should allow essentially to talk only about possible local parts of computations). $\endgroup$ Aug 17, 2022 at 15:17
  • $\begingroup$ @FedorPakhomov I updated the question — you comments led me to learn about Hanf normal form and related constructs. $\endgroup$ Aug 17, 2022 at 20:37
  • 1
    $\begingroup$ I'm under the impression that a complete finitely axiomatizable first-order theory is always decidable. Is this not the case? $\endgroup$ Aug 17, 2022 at 22:57
  • $\begingroup$ @DmytroTaranovsky I didn't knew about Hanf work. Indeed, seems to be quite similar to the ideas I was expressing. $\endgroup$ Aug 17, 2022 at 23:00

1 Answer 1

7
$\begingroup$

There are complete decidable finitely axiomatizable theories of arbitrary high computational complexity.

As Dmytro already sketched in his question there are complete decidable theories of arbitrary high computational complexity. Now we want to switch to finitely axiomatizable theories. This could be achieved using a theorem of Peretyatkin (see his book [1] and also a review of his book [2]; I haven't read the book myself and taking the formulation of the theorem from [2]):

Theorem(Peretyat'kin) There is a method of constructing, effectively in the c.e. index m of T, a finitely axiomatizable model-complete theory F(m) and an effective interpretation I of the theory T in F(m) such that I induces one-one correspondece between the completions of T and F(m).

Since a theory is complete and consistent iff it has a unique completion, if we apply this to a complete decidable theory $T$, then we would get a complete finitely axiomatizable theory $T'$ interpreting $T$. And, of course, the presence of the interpretation guarantees that $T$ is polynomial time reducible to $T'$. As James Hanson pointed in the comments, any complete finitely axiomatizable theory is decidable, hence we get complete decidable finitely axiomatizable theories of arbitrary high computational complexity.

Comment: Dmytro's example of complete decidable theories of arbitrary high computational complexity could be slightly simplified if instead of the monadic theory of $(\mathbb{N},<,P)$ the elementary theory of $(\mathbb{N},S,P)$ would be considered; then decidability could be proved by a more elementary quantifier elimination argument instead of Büchi automatons, see https://mathoverflow.net/a/426389/36385. There also an option to use the technique from my paper with Juvenal Murwanashyaka and Albert Visser [3]. There we define theory $\mathsf{J}$ (based on a theory earlier considered by Janiczak) and a polynomial time computable sequence of sentences $\mathsf{A}_i$ indexed by naturals $i$ such that $\mathsf{J}$ is consistent with any propositionally consistent Boolean combination of $\mathsf{A}_i$ and over $\mathsf{J}$ any sentence is equivalent to a Boolean combination of $\mathsf{A}_i$. Now given a decidable set $P$ we could consider theory $$\mathsf{J}+\{\mathsf{A}_i\mid i\in P\}\cup\{\lnot\mathsf{A}_i\mid i\not\in P\},$$ that is a complete consistent decidable theory such that $P$ is polynomial time reducible to it.

P.S. As I already indicated in the comments, I have learned about the book of Peretyat'kin from Albert Visser.

[1]Mikhail, G. Peretyat'kin. "Finitely Axiomatizable Theories." Siberian School of Algebra and Logic. Consultants Bureau, New York (1997).

[2]Vivienne Morley. Review of M.G. Peretyat'kin "Finitely Axiomatizable Theories.". https://doi.org/10.2307/2586818

[3]Juvenal Murwanashyaka, Fedor Pakhomov, and Albert Visser. "There are no minimal essentially undecidable Theories." arXiv preprint arXiv:2207.08174 (2022). https://arxiv.org/abs/2207.08174v2

$\endgroup$
0

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.