3

Fix an algebraic signature $\Omega$. Let $F$ be a finite set of equations in $\Omega$. Is it decidable if the set $F$ has only trivial models? By trivial models, I mean one-element models. For example, if the set $F$ contains the equation $x=y$ then certainly it has only trivial models. However, perhaps the set $F$ does not contain $x=y$ but it still has only trivial models. I am wondering if the problem is decidable either way.

user107952
  • 20,508
  • It immediately follows from the completeness theorem that the set of finite equational theories with only the trivial model is c.e. (just ask whether the theory in question entails $\forall x,y(x=y)$). I suspect that it is in fact c.e. complete (similarly to how the triviality problem for group presentations is c.e. complete) but I don't see how to prove this immediately. – Noah Schweber Feb 20 '22 at 22:53

1 Answers1

7

No.

Perkins, Peter
Unsolvable problems for equational theories.
Notre Dame J. Formal Logic 8 (1967), 175-185.

states

Theorem 14. There is no effective method for determining whether or not an arbitrary finite set of equations in one binary operation symbol and no constants is consistent.

Keith Kearnes
  • 13,798
  • But how does this answer my specific question? What is the connection? – user107952 Feb 22 '22 at 00:47
  • 2
    Every set of identities has a 1-element model, so a "consistent set of identities" is typically taken to mean a set of identities with a model of more than one element. What Perkins is saying is that it is undecidable whether a finite set of identities has a model of more than one element. – Keith Kearnes Feb 22 '22 at 00:50
  • So, then, that means the converse problem of whether it has only 1-element models is also undecidable? – user107952 Feb 22 '22 at 00:51
  • 2
    Yes. If you can effectively decide the answer to a problem, then you can effectively decide the answer to the complementary problem with the same algorithm by changing how you report the answer (interchange True $\leftrightarrow$ False). – Keith Kearnes Feb 22 '22 at 03:17