# Undecidability degree of some elementary theories (two equivalence relations, …)

I have a question about some results in the paper

• I. A. Lavrov. Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain theories (in Russian). 1963. Algebra i Logika Sem. Vol 2, pp. 5-18. MR0157904 (28 #1132).

The question concerns the undecidability degree of the theories considered in this paper.

I am interested in these results because they have been used several times on universal algebra papers dealing with undecidability issues; for example, in

• S. Burris and H. P. Sankappanavar. Lattice-theoretic decision problems in universal algebra. Algebra Universalis, 5(2):163-177, 1975.

• R. McKenzie. Negative solution of the decision problem for sentences true in every subalgebra of $\langle N,+\rangle$. The Journal of Symbolic Logic, 36:607-609, 1971.

• R. Willard. Hereditary undecidability of some theories of finite structures. The Journal of Symbolic Logic, 59(4):1254-1262, 1994.

Lavrov's results that are used in the previous papers concern the recursive inseparability of some elementary (i.e., first-order) theories. I remind here that a theory $T$ is recursively inseparable when there is no decidable set $X$ such that $T \subseteq X \subseteq T_{fin}$, where

$T_{fin} := \{ \varphi: \varphi \textrm{ is true in all models of } T \textrm{ which are finite} \}.$

In Lavrov's paper it is proved, among other results, that

• the theory $T^{2ER}$ of two equivalence relations is recursively inseparable,

• the theory $T^{2LO}$ of two linear orders is recursively inseparable.

In particular, from these results, it follows that

• $T^{2ER}$ is undecidable,

• $T^{2ER}_{fin}$ is undecidable,

• $T^{2LO}$ is undecidable,

• $T^{2LO}_{fin}$ is undecidable.

My question concerns whether it is known what is the exact complexity of these theories. In other words,

• Is it known whether $T^{2ER}$ is $\Sigma_1$-complete?

• Is it known whether $T^{2ER}_{fin}$ is $\Pi_1$-complete?

• Is it known whether $T^{2LO}$ is $\Sigma_1$-complete?

• Is it known whether $T^{2LO}_{fin}$ is $\Pi_1$-complete?

Or more in general,

• are all elementary theories $T$ considered in Lavrov's paper $\Sigma_1$-complete?

• are all elementary theories $T_{fin}$ considered in Lavrov's paper $\Pi_1$-complete?

NOTE: I have not been able to find any place where these questions are answered (neither positively nor negatively). My conjecture is that the answer to the previous questions is known to be "YES". Indeed, it would be enough to check that Lavrov proved his results using a reduction from the theory

$\{ \varphi: \varphi \textrm{ is logically valid in all structures with one binary symbol} \}$

into its theories. I suspect this to be the case, but unfortunately I cannot check this myself; firstly because I do not have access to the paper, and secondly because the paper is written in Russian. I have checked the available reviews at Mathscinet and Zentralblatt but nothing it is said there about how Lavrov proved the results.

-
I haven’t seen Lavrov’s paper, but I am pretty sure that as with other such results in the literature, when someone claims that r.e. sets A and B are recursively inseparable, he actually proves that they are effectively recursively inseparable, and therefore both are $\Sigma_1^0$-complete. That is, the answers to all your questions should be “yes”. –  Emil Jeřábek Sep 14 '11 at 15:49