                                              Notes prepared by
                                                 Stanley Burris
                                                   July 3, 2001

1 Quasi-Identity Logic

symbols  ≈

function symbols constant symbols variables

In Chapter III of LMCS we looked at Birkhoff’s study of equational logic. The next larger interesting fragment of first-order logic with equality is the logic of quasi-identities.

Quasi-identities are universal Horn formulas of the form

∀x⃗ [p_{1} ≈ q_{1} ∧ ⋯ p_{n} ≈ q_{n} ⟹ p ≈ q],

including the possibility that n = 0 and we simply have an equation. As with identities, we usually omit writing the universal quantifiers. The study of quasi-identities, and the corresponding model classes called quasi-varieties, has been pursued mainly in Eastern Europe, following the lead of Mal’cev. In Western Europe and North America the focus has been on identities and varieties, a direction initiated by Birkhoff. The rules for working with quasi-identities are not as simple, or standardized, as the rules of Birkhoff. Of course the usual rules of first-order logic suffice to derive all the quasiidentity consequences of a set of quasi-identities, but one might prefer to have a logical system which only produces quasi-identities from quasi-identities. One such was given by Selman [5] in 1972 with four axiom schemes and six rules of inference. By considering a conjunction p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} as a set of equations, rather than an abbreviation for some particular way of inserting parentheses, we can omit his fifth rule (which handles rearranging the parentheses and repeat copies of equations):

AXIOMS:

(a) p ≈ q ∧ r ≈ s ⟹ r ≈ s

(b) p ≈ p

(c) p ≈ q ∧ q ≈ r ⟹ r ≈ p

(d) p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ⟹ f(p_{1}, …, p_{n}) ≈ f(q_{1}, …, q_{n}).

RULES:

(a) \frac{r ≈ s}{p ≈ q ⟹ r ≈ s}

(b) \frac{p ≈ q, p ≈ q ⟹ r ≈ s}{r ≈ s}

(c) \frac{p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ⟹ p ≈ q, p ≈ q ⟹ r ≈ s}{p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ⟹ p ≈ q, ⟹ r ≈ s}

(d) \frac{p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ⟹ p ≈ q, p ≈ q ∧ r_{1} ≈ s_{1} ∧ ⋯ ∧ r_{n} ≈ s_{n} ⟹ r ≈ s}{p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ∧ r_{1} ≈ s_{1} ∧ ⋯ ∧ r_{n} ≈ s_{n} ⟹ r ≈ s}

(e) \frac{p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ⟹ p ≈ q}{σ(p_{1} ≈ q_{1} ∧ ⋯ ∧ p_{n} ≈ q_{n} ⟹ p ≈ q)  (σ a substitution)}

We will not go into quasi-identity logic except to make some remarks on the complexity of quasi-identity theories. We note that the quasi-identity theory of a class K of algebras is the same as that of the quasi-variety Q(K) generated by K, as well as of the variety V (K) generated by K. In the latter context the study of quasi-identity theory is better known as the uniform word problem for the variety.

1.1 Presentations and word problems

Word problems were one of the first places in mathematics where mathematicians were able to apply the concepts of algorithm (developed in the mid 1930’s) to obtain undecidability results. Let Σ be a set of equations in the language F ∪ C.

DEFINITION 1 A presentation Π with respect to Σ is an ordered pair (G, R) where G is a set of constant symbols disjoint from C, called the set of generators, and R is a set of ground equations over G called the defining relations.

Presentations of groups came early in the century in the study of algebraic topology. Of course associated with the presentation one had a group.

LEMMA 2 Given a presentation Π = (G, R) with respect to Σ, the relation θ_{Π} = {(t_{1}, t_{2}) ∈ T_{G∪C} × T_{G∪C} : Σ ∪ R ⊢ t_{1} ≈ t_{2}} is a congruence on T_{G∪C}.

Proof. We observed this fact in the proof of the Birkhoff completeness theorem. .

DEFINITION 3 Given a presentation Π over Σ, let A_{Π} be the algebra T_{G∪C}/θ_{Π}, the algebra defined by the presentation.

EXAMPLE 4 Up to isomorphism we have

(a) ({a, b}, {ab ≈ ba}) over groups^{1} defines Z × Z

(b) (X, Ø) over Σ defines the free algebra F_{Σ}(X) in the equational class determined by Σ

(c) (X, Ø) over rings^{2} defines the polynomial ring Z[X]

(d) (Ø, \{\underbrace{1 + ⋯ + 1}_{n} ≈ 0\}) over rings defines Z_{n}, the integers modulo n.

(e) ({a}, {a^{2} + a + 1 ≈ 0, 1 + 1 ≈ 0}) over rings defines GF(4), the 4element Galois field.

DEFINITION 5 The problem of determining which ground equations over G follow from Σ ∪ R is called the word problem for Π. If there is an algorithm for this problem then the word problem for Π is solvable) (or decidable); otherwise it is unsolvable (or undecidable).

1In groups one can write all the defining relations in the form w ≈ e, e the identity element, and thus one can consider the set R (of defining relators) as a set of words (i.e., terms) w.

2In rings one can write all the defining relations in the form w ≈ 0, and thus one can consider R as a set of words w (i.e., terms) from T_{G∪C}.

DEFINITION 6 If there is a single algorithm for solving the word problem for any presentation Π over Σ we say the word problem for Σ is (uniformly) solvable (or decidable); otherwise it is unsolvable^{3} (or undecidable).

A simple example of a semigroup presentation with unsolvable word problem was found by Tsentin:

generators  relations
a b c d e ac ≈ ca ad ≈ da
bc ≈ cb  bd ≈ db
abac ≈ abacc
eca ≈ ae  edb ≈ be

A. Mekler, E. Nelson, and S. Shelah [4] have proved that there is a finite Σ such that the word problem for Σ is unsolvable, but for each presentation Π over Σ the word problem is solvable.

The use of finite partial algebras is popular in methods for showing the word problem is solvable; in particular the following are equivalent for a variety V:

• The uniform word problem for V is solvable.

• There is an algorithm to determine which finite partial algebras can be embedded into some member of V.

• One has an algorithm to find the smallest congruence θ of a finite partial algebra P such that P/θ embeds into some member of V.

One can also show that the uniform word problem for V is polynomial time solvable iff one can find the congruence θ in the last item above in polynomial time. And if the universal theory of V^{⋆}, the relational version of V, is finitely axiomatizable then the uniform word problem is solvable in polynomial time. (See Burris [1].)

An interesting example is that of commutative semigroups, where each finite presentation Π has a word problem solvable in polynomial time, but the uniform word problem for commutative semigroups is exponential space complete (due to Mayr & Meyer [3]; see also Kharlampovich & Sapir [2]).

In the table below we give a few examples concerning the solvability of the word problem for finite presentations. Rather than give a defining set of equations Σ it is simpler to specify the class determined by the intended Σ.

3Warning: this eminently sensible definition has not been commonly used — the word problem for Σ has been called unsolvable provided there is a single presentation with unsolvable word problem

Σ  discovered by
semigroups  undecidable Post/Markov 1947
groups  undecidable Novikov 1955
lattices  decidable Skolem 1920
modular lattices undecidable Hutchinson 1973
quasigroups  decidable Evans 1953
loops  decidable Evans 1953

Exercises

Problem 1 Show that Example 4 (a) has a solvable word problem.

Problem 2 Show that Example 4 (c) has a solvable word problem.

Problem 3 If A_{Π} is finite, show Π has a solvable word problem.

Problem 4 If A_{Π} is residually finite, show Π has a solvable word problem.

Problem 5 If A_{Π} is simple, show Π has a solvable word problem.

References

[1] S. Burris, Polynomial time uniform word problems. Math. Logic Quarterly 41 (1995), 173–182.

[2] O.G. Kharlampovich and M.V. Sapir, Algorithmic problems in varieties. Internat. J. Algebra Comput. 5 (1995), no. 4-5, 379–602.

[3] E.W. Mayr and A.R. Meyer, The complexity of the word problem for commutative semigroups and polynomial ideals. Adv. in Math. 46 (1982), 305–329.

[4] A.H. Mekler, E. Nelson, and S. Shelah, A variety with solvable, but not uniformly solvable, word problem. Proc. London Math. Soc. 66 (1993), 225–256.

[5] A. Selman, Calculii for axiomatically defined algebras. Algebra Universalis 2 (1972), 20–32.