Lecture Notes

Universal Algebra 2
Spring term 2025

Michael Kompatscher

Monday 24th February, 2025 21:23

 These are the lecture notes for Universal Algebra 2 in spring term 2025. Chapter 1 on
term rewriting is based on Libor Barto’s lectures notes and Jaroslav Ježek [1]; Chapter 2 is
based on Chapters 7.2-7.4 in Bergman’s book [2] and parts of [3]. Chapter 3 corresponds to
Chapter 5.4 and 5.5. in [2]. Chapter 4 is based on Libor Barto’s lectures notes and [8].

1
Contents

1 Equational logic 3
1.1 The equational completeness theorem . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Term rewriting systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Knuth-Bendix algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Commutator theory 14
2.1 Affine and Abelian algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 The fundamental theorem of Abelian algebras . . . . . . . . . . . . . . . . . . 17
2.3 The term condition commutator . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Commutator and varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Nilpotent algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Finitely based algebras 30

3.1 Park’s conjecture and McKenzies DPC theorem . . . . . . . . . . . . . . . . . 33
3.2 Congruence distributive varieties . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 CSPs and Maltsev conditions 42

4.1 Constraint satisfaction problems (CSP) . . . . . . . . . . . . . . . . . . . . . 42
4.2 Clone and minion homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Taylor operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4 Siggers operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2
Chapter 1

Equational logic

In the first chapter, we discuss the problem of checking if an identity holds in a fixed variety
or not. The variety in question is given as Mod(E), the models of some fixed finite set of
identities E (in similarity type τ ). So, our goal is to decide the equational theory of E, i.e. to
solve the following problem:

Decide(E)
Input: An identity s ≈ t (in type τ )
Question: Does E |= s ≈ t? (i.e. does s ≈ t hold in all models of E?)

In particular, we would like to find an algorithm that solves Decide(E). Unfortunately

this is not possible in general: there is no algorithm that would solve it uniformly for every
E, and even for fixed E the problem can be undecidable (e.g. [1, Chapter 12] constructs an
example with two unary function symbols).
However for the following examples there are straightforward algorithms:
Example 1.1. Let E = ∅. Then E |= s ≈ t, if and only if the two terms are equal (otherwise
they induce different term operations in the totally free algebra). So return ’Yes’ if and only
if s = t and ’No’ otherwise.
Example 1.2. Let E be the set of identities in type τ = (+, 0, −, ·) that axiomatize the variety
of commutative rings, so E = {x + y ≈ y + x, 0 + x ≈ x, x · (y + z) ≈ x · y + x · z, . . .}. Then
Decide(E) is the problem of deciding whether an input identity s(x1 , . . . , xn ) ≈ t(x1 , . . . , xn )
holds in every commutative ring.
Clearly E |= s ≈ t if and only if E |= s − t ≈ 0. By using the identities in E we can
rewrite the left side into an equivalent term that is a sum of monomials (e.g. a1 x1 + a11 x21 +
a2 x2 + a12 x1 x2 + . . .). We output ‘Yes’ if all of the coefficients of all monomials are 0 and
‘No’ otherwise. This algorithm is correct, since in the ‘No’ case the two terms induce different
operations in the ring (Z, +, 0, −, ·).
The algorithm described in Example 1.2 uses the ring identities in E as ‘rewriting rules’ to
rewrite an arbitrary term into an equivalent ‘normal form’, namely the sum of monomials. We
can then check if E |= s ≈ t, by simply checking if s and t have the same normal form. We are
going to formalize this term rewriting approach and investigate for which identities/rewriting
rules E it works.
After that we discuss the Knuth-Bendix algorithm, a procedure to modify the sets of
identities E into an equivalent set F for which the term rewriting approach works.

3
1.1 The equational completeness theorem
We start by giving a syntactic characterization of E |= s ≈ t, which will be the base of our
algorithm. Let us recall some definitions from UA1 (see also [2] Section 4.3-4.4).

Definition 1.3. Let τ be a similarity type. Then

• A term is an element of the totally free algebra Fτ (x1 , x2 , . . .). For short we write
F = Fτ (x1 , x2 , . . .).
• An identity (of type τ ) is an ordered pair (s, t) ∈ F2 . We will also write s ≈ t for the
identity (s, t). Note that according to this definition s ≈ t and t ≈ s are two different
identities.
• An algebra A satisfies an identity s ≈ t (short A |= s ≈ t) iff for all a1 , . . . , an ∈ A :
sA (a1 , . . . , an ) = tA (a1 , . . . , an )

The relation |= induces a Galois connection between classes of algebras K and sets of
identities E (of type τ ), with the operators

Id(K) = {s ≈ t : K |= s ≈ t}
Mod(E) = {A : A |= E}

We saw in Universal Algebra 1 that the Galois closure Mod(Id(K)) is equal HSP(K), i.e.
the variety generated by K.

The Galois-closed sets Id(Mod(E)) ⊆ F 2 on the identity side are called equational theories.
For short, we write E |= s ≈ t (and say E semantically implies s ≈ t) if (s ≈ t) ∈ Id(Mod(E)),
or in other words, if s ≈ t is satisfied in all models of E.

Observation 1.4. An equational theory D ⊆ F2 has three natural properties (which we

discuss for the example τ = {·})
1. D is an equivalence relation
2. D is a congruence of F (D |= s ≈ t and D |= u ≈ v implies D |= s · u ≈ t · v)
3. D is invariant under substitutions.
(e.g. D |= (x1 · x2 ) ≈ (x1 · x1 ) implies that D |= ((x1 · x2 ) · (x3 · x1 )) ≈ ((x1 · x2 ) · (x1 · x2 ))
by substituting x1 7→ (x1 · x2 ), x2 7→ (x3 · x1 ).)
Note that a substitution can be seen a map θ : {x1 , x2 , . . .} → F. By the properties of the
totally free algebra F, this map θ extends to a unique homomorphism θ : F → F. Thus
(3) says that D is closed under endomorphisms θ ∈ End(F). This motivates the following
definition.

Definition 1.5. Let A be an algebra. We call a congruence D ∈ Con(A) fully invariant, if

for every endomorphism θ ∈ End(A) we have (s, t) ∈ D ⇒ (θ(s), θ(t)) ∈ D.

We next show that the properties (1)-(3) from Observation 1.4 already completely char-
acterize equational theories:

Proposition 1.6. A binary relation D ⊆ F2 is an equational theory if and only if it is a fully

invariant congruence of F.

4
Proof. As in Observation 1.4, one can see that every equational theory is a fully invariant
congruence of F.
For the opposite direction, let D be a fully invariant congruence of F. We then need to
prove that D = Id(Mod(D)). Clearly D ⊆ Id(Mod(D)), so it is enough to prove the inclusion
D ⊇ Id(Mod(D)).
Consider the quotient A = F/D. This quotient is well-defined, since D is a congru-
ence of F. We claim that an identity is in D, if and only if it satisfied in A. Sup-
pose s(x1 , . . . , xn ) ≈ t(x1 , . . . , xn ) ∈ D. Since D is fully invariant, this is equivalent to
s(u1 , . . . , un ) ≈ t(u1 , . . . , un ) ∈ D, for all terms u1 , . . . , un ∈ F. By definition of A, this is
equivalent to sA (u1 , . . . , un ) = tA (u1 , . . . , un ), for all u1 , . . . , un ∈ A. In other words, it is
equivalent to A |= s(x1 , . . . , xn ) ≈ t(x1 , . . . , xn ), which is what we claimed.
Since A is a model of D, we obtain Id(Mod(D)) ⊆ Id({A}) = D.

By Proposition 1.6, E |= s ≈ t, if s ≈ t lies in the fully invariant congruence generated by

E; this can already be seen as a syntactic characterization of the equational theory generated
by E. In order to further simplify it, we introduce immediate consequences of E as those
identities that follow from “applying” an identity of E to a given term (or a subterm of it).

Example 1.7. Let l = (x1 · x2 ) ≈ (x2 · x1 ) = r be the identity describing the commutativity
law. Then, the identity u = x3 · (x1 · (x1 · x2 )) ≈ x3 · ((x1 · x2 ) · x1 ) = v is an immediate
consequence of l ≈ r, since it follows from applying the commutativity law to the subterm
(x1 · (x1 · x2 )) of u. Note that this subterm is equal to θ(l) for the substitution θ(x1 ) =
x1 , θ(x2 ) = x1 · x2 .

Next, a more definition of immediate consequences (see also [1], Section 6.3):

Definition 1.8. Recall from UA1 that terms t can be represented by a term tree. If we label
the vertices of a term tree t by sequences of natural numbers a ∈ ω <ω in a natural way (see
Figure 1.1), every such label is called a valid address of t. The subterm at address a, or t[a],
is the term that corresponds to the subtree with root a.
Assume that t[a] = s. By t[a : s → r] we denote the term that we obtain by replacing the
subterm s by r. Then every identity of the form u ≈ u[a : θ(l) → θ(r)] for some θ ∈ End(F)
is called an immediate consequence of l ≈ r.

We finish this section by proving that all identities in the equational theory generated
by E lie in the equivalence relation generated by immediate consequences of E. This result
was shown by Birkhoff, and is also known as equational completeness theorem (in analogy to
Gödel’s completeness theorem in first order logic).

Definition 1.9. We say E syntactically implies s ≈ t, and write E ⊢ s ≈ t, if there is a

sequence of terms s = u1 , . . . , un = t, such that for every i = 1, . . . , n − 1, either (ui , ui+1 ), or
(ui+1 , ui ) is a immediate consequence of an identity from E.

5
 t t[21 : x + y → f (z)]

+∅ +∅

f1 +2 t[21] f1 +2

x11 +21 z 22 +21 x11 f 21 z 22

x211 y 212 x211 y 212 z 211

Figure 1.1: The term tree of t = f (x) + ((x + y) + z) with labels for its valid addresses; its
subterm t[21] = (x + y), and the substitution t[21 : x + y → f (z)]

u u[a : θ(l) → θ(r)]

· ·

x3 ·a x3 ·

x1 x1 · x2 x1 · x2 x1

Figure 1.2: Example 1.7 revisited: x3 · (x1 · (x1 · x2 )) ≈ x3 · ((x1 · x2 ) · x1 ) is an immediate

consequence of x1 · x2 ≈ x2 · x1 with a = 2 and θ(x1 ) = x1 , θ(x2 ) = x1 · x2 .

Theorem 1.10 (Birkhoff’s equational completeness theorem). E |= s ≈ t if and only if

E ⊢ s ≈ t.

Proof. It is straightforward to see that E ⊢ s ≈ t implies E |= s ≈ t (as in Observation 1.4).

For the opposite direction, we simply need to show that {s ≈ t : E ⊢ s ≈ t} is a fully invariant
congruence - this is left as exercise (Exercise 1.7). By Proposition 1.6 it is an equational
theory. As it contains E it also needs to contain {s ≈ t : E |= s ≈ t}, so we are done.

1.2 Term rewriting systems

Term rewriting systems are a tool that sometimes allows us to algorithmically solve Decide(E).
In term rewriting algorithms we regard the identities in E as a set of rules on how to rewrite
terms: For an input term s, if there is an immediate consequence s ≈ s′ of E, we replaces s
by s′ , and repeat this process as long as possible. For certain rewriting rules E this algorithm
terminates after finitely many steps and computes a unique term that is equivalent to s (its
’normal form’). If this is the case, we can solve Decide(E) by rewriting both s and t into
their normal forms, and then check if they are equal (as in Example 1.2). In the exercises,
we discuss some other easy examples, for which this algorithm works or does not work (see
Exercises 1.1, 1.2, 1.3).

6
 We will use the following notation:
Definition 1.11. For a set of identities E (of type τ ), we define a digraph D(E) that has F
(the terms of type τ ) as vertex set and has an edge s → t if and only if s ≈ t is an immediate
consequence of some identity (l ≈ r) ∈ E.
Definition 1.12. Let D be a digraph with edge relation →.
• A vertex s is called terminal if there is no t with s → t.
• We write s →∗ t, if (s, t) is in the transitive, reflexive closure of →
• We write s ↔∗ t, if (s, t) is in the symmetric, transitive, reflexive closure of →.
By definition E ⊢ s ≈ t if and only if s ↔∗ t in D(E).
Definition 1.13. We say that a digraph D
• is finitely terminating if it contains no infinite directed path t0 → t1 → t2 → · · ·
• is normal, if for all s, t ∈ D such that s ↔∗ t there is a u ∈ D with s →∗ u and t →∗ u.
• is convergent, if it is normal and finitely terminating
Note that being finitely terminating also forbids cycles or loops. The following lemma
shows that if D(E) is convergent, then every vertex is connected to a unique terminal vertex.
And in fact it is connected to such vertex via a directed path.
Lemma 1.14. Let D be a digraph that is convergent. Then
1. For every t ∈ D there is a unique terminal vertex N F (t), such that t →∗ N F (t) (this
is the normal form of t).
2. s ↔∗ t if and only if N F (s) = N F (t)
Proof. 1. Let t ∈ D. Since D is finitely terminating, there is a terminal vertex a, such
that t →∗ a. For the uniqueness, let b be another terminal vertex, such that t →∗ b.
So clearly a ↔∗ b. By normality, there is a u with a →∗ u, b →∗ u. Since a and b are
terminal, this can only happen if a = b = u.
2. By normality s ↔∗ t implies that there is an u with s →∗ u, t →∗ u. By the uniqueness
in (1) we obtain N F (u) = N F (s) = N F (t).

Note that by Lemma 1.14, the term rewriting algorithm described at the beginning of this
section works, if D(E) is convergent. In order to find out, for which sets of identities E this
is true, we need to answer two questions: When is D(E) is finitely terminating and when is
it normal?
We start by discussing finite termination, by looking at some examples.
Example 1.15. Is D(E) finitely terminating?
1. E = {f (f (x)) ≈ f (x)} Yes: the number of f ’s in every immediate consequence decreases
2. E = {x ≈ x · x} No: x → xx → (xx)x → · · ·
3. E = {x · x ≈ x} Yes: the number of variables in every immediate consequence decreases
4. E = {(x · x) · y ≈ (y · y)} No: there is a loop (x · x) · (x · x) → (x · x) · (x · x)

7
 In the finitely terminating cases 1 and 3 in Example 1.15, we can see that for all pairs
s → t in D(E), the left side s is “more complex” than t. This can be measured by so called
reduction orders:

Definition 1.16. A strict (partial) order < on the set of terms F is called a reduction order
if
1. s > t implies that for all θ ∈ End(F): θ(s) > θ(t)
2. s > t implies that, for all u with u[a] = s we have u > u[a : s → t]
3. < is well-founded, so there is no infinite chain t1 > t2 > t3 > · · ·

Observation 1.17. If there is a reduction order < such that l > r for all identities (l ≈ r) ∈ E,
then D(E) is finitely terminating. For the proof, note that (1) and (2) imply that u > v for all
immediate consequences of identities in E. From (3) it follows that there is no infinite chain
t1 → t2 → t3 → · · · in D(E).

• Example 1.15 (1) is compatible with the reduction order defined by s < t if and only if
the number of f symbols in s is smaller than the number of f ’s in t.
• A reduction order compatible with Example 1.15 (3) is the order that sets s < t, if for
all variables xi , the number of xi appearing in s is less or equal to the number for t and
for some index i it is strictly less.
• Ordering terms by the total number of variables is not a reduction order, since it is not
compatible with substitutions (as you can see in Example 1.15 (4), and the substitution
y 7→ x · x).

Other reduction orders may take into account (weighted) number of function symbols and
variables, but also their appearance/order within a term (see Exercise 1.3). A big family of
rewriting orders to pick for a given E are the Knuth-Bendix-orders, which we are not going
to define here (see [1], Section 13.7).

Remark 1.18. According to our definitions, the identity x + y ≈ y + x prohibits finite

termination, since it induces a cycle in D(E). So e.g. also for the variety of commutative
rings in Example 1.2, D(E) is not finitely terminating. We leave it as an exercise to think
about possible generalizations to fix this problem (Exercise 1.11).

We next discuss the normal digraphs. By the following theorem, for finitely terminating
digraph, we only need to check the definition of normality for specific sub-cases.

Theorem 1.19. Let D be a finitely terminating digraph. Then TFAE

1. D is normal.
2. D is confluent: For all r, s, t ∈ D such that r →∗ s and r →∗ t there is an u ∈ D with
s →∗ u, t →∗ u.
3. D is locally confluent: For all r, s, t ∈ D such that r → s and r → t there is an u ∈ D
with s →∗ u, t →∗ u.

Proof. (1)→(2)→(3) holds by definition.

For (2)→(1), assume that there are vertices a ↔∗ b such that there is no u with a →∗ u
and b →∗ u. By definition of ↔∗ there are elements t0 , . . . , t2n ∈ D, such that a = t0 ←∗

8
Figure 1.3: If the immediate consequences affect disjoint subterms, they are always confluent.

t1 →∗ t2 ←∗ · · · →∗ t2n = b. Without loss of generality, let a, b be a pair such that the

number n is minimal. By minimality there exists an u′ with a →∗ u′ and t2n−1 →∗ u′ . But
by confluence there is also an u with u′ →∗ u and b →∗ u. Thus a →∗ u′ →∗ u and b →∗ u -
contradiction!
For (3)→(2), let D be locally confluent, and let P be the set of vertices of D, such that
v ∈ P if v has directed paths to more than one terminal vertex. If P = ∅, every vertex of D
has (by finite termination) a directed path to exactly one terminal vertex. So in this case D
is confluent.
So for contradiction assume that P ̸= ∅. Then there is an element v ∈ P such that for
every u ∈ P , v →∗ u implies v = u (otherwise D would contain an infinite directed path,
contradicting finite termination). Let s, t be two distinct terminal vertices with v →∗ s and
v →∗ t. By minimality of v there are distinct s0 , t0 with v → s0 →∗ s, and v → t0 →∗ t. By
local confluence, there is an u with s0 →∗ u, t0 →∗ u. Since D is finitely terminating we can
pick u to be terminal. Since s0 , t0 ∈
/ P we get s = u and u = t, which is a contradiction to
the assumption that s and t are distinct.

Local confluence is an easier property to check than normality. In cases, where the rewrit-
ing affects ’disjoint’ subterms, we always get local confluence (see Figure 1.3). The only
obstacles to local confluence are immediate consequences r → s and r → t that affect ’over-
lapping’ subterms. We give some examples.

Example 1.20. The example E = {f (f (x)) ≈ f (x)} is locally confluent, while E = {f (f (x)) ≈
g(x)} is not (see Exercise 1.2).

Example 1.21. Let E = {x · (y · y) ≈ x · y}.

The term s = (x(yy))(x(zz)) rewrites to both (xy)(x(zz)) and (x(yy))(xz). Both of these
terms rewrite to (xy)(xz). Note that corresponding immediate consequences affected the
disjoint subterms s[1] = (x(yy)) respectively s[2] = (x(zz)), therefore we had no problems.
However D(E) is not locally confluent: for this consider the term t = (xy)((uu)(uu)). By
applying the identity on the subterm t[2] we obtain (xy)((uu)(uu)) → (xy)((uu)u), which is
terminal. If we apply the identity on t[∅] we can only rewrite to (xy)((uu)(uu)) → (xy)(uu) →
(xy)u.

The term (xy)((uu)(uu)) in Example 1.21 is a witness that D(E) is not locally confluent.
However it is not a ’minimal’ example, since the same problem already appears when starting

9
with the term x((uu)(uu)). We call the two terms x((uu)u) and xu that result from a ’minimal’
such example critical pairs. We give a more formal definition of critical pairs below.

Definition 1.22. Let t and s be two terms. A unifier of t and s is an endomorphism

θ ∈ End(F), such that θt = θs. A most general unifier of t and s is a unifier α ∈ End(F),
such that for all other unifiers θ, we have that θ = β ◦ α, for some β.

If a unifier exists, there exists also a most general unifier, which is unique (up to renaming
variables). We are not giving a proof, it can be found in [1], Section 13.1.

Example 1.23. Let t(x, y) = (x · x) · (y · y) and s(u, v) = u · (u · v). Then any unifier θ of t
and s must satisfy θ(u) = θ(x) · θ(x) and θ(y) = θ(u) = θ(v). If we set θ(x) = x, this gives us
the most general unifier θ(t) = (xx)((xx)(xx)) = (xx)((xx)(xx)).

Example 1.24. The terms t(x, y) = (x · y) · x and s(u, v) = u · (u · v), do not have a unifier.
If there was a unifier θ, it would need to satisfy θ(u) = θ(x · y) = θ(x) · θ(y), but also
θ(x) = θ(u) · θ(v). This implies θ(u) = (θ(u) · θ(v)) · θ(y), which is however not possible for
any θ(u) ∈ F.

Definition 1.25. Let l1 ≈ r1 and l2 ≈ r2 be two identities in E. Also let us assume that
they contain no common variables (otherwise rename the variables of one identity). Let
l′ be a subterm of l1 , and let θ be the most general unifier of l′ and l2 . Then the pair
(θr1 , θ(l1 )[a : θl′ → θr2 ]) is called a critical pair. This corresponds to the output we get by
applying the rewriting rules l1 ≈ r1 and l2 ≈ r2 to θl1 , respectively its subterm θl′ = θl2 .

θ(r1 )
·

θ(l1 ) x ·
·
v v
x ·a

· · θ(l1 )[a : θl′ → θr2 ]

·
v v v v
x ·

v ·

v v

Figure 1.4: The critical pair in Example 1.26

Example 1.26. We discuss the definition of critical pair for Example 1.21. In both immediate
consequences we apply the rule x(yy) ≈ xy. So l1 (x, y) = x(yy) and (after renaming variables)
l2 (u, v) = u(vv). The subterm l′ of l1 is equal to yy. The most general unifier of l′ = yy and

10
l2 = u(vv) is given by the map θ(x) = x, θ(v) = v and θ(y) = θ(u) = vv. Thus the terms
θ(r1 ) = x(vv) and θ(l1 )[a : θl′ → θr2 ] = x((vv)v) form a critical pair.

Without a proof we claim the following:

Theorem 1.27 (Theorem 3.1. in Chapter 13 of [1]). Let E be a set of identities. Then D(E)
is locally confluent, if and only if it is locally confluent at all critical pairs.

Note that, if E is finite, then there are only finitely many critical pairs. Thus by just
checking local confluence for finitely many pairs, we can check if D(E) is locally confluent.

1.3 Knuth-Bendix algorithm

The Knuth-Bendix completion algorithm is an algorithm that takes as input a set of identities
E and tries to modify them in a way to obtain an equivalent set of identities F, such that
D(F) is convergent.

Algorithm 1: This algorithm takes as input a finite set of identities E and a rewriting
order <. If the algorithm terminates, it either outputs “Fail”, or a set of identities
F equivalent to E such that D(F) is convergent.
1 Algorithm Knuth-Bendix(E,<)
2 for (l, r) ∈ E do
3 if ¬(l < r) ∧ ¬(r < l) then return “Fail”
4 if l < r then E := E \ {(l, r)} ∪ {(r, l)}
5 end
6 Compute C := {critical pairs (s, t) of E}.
7 for (s, t) ∈ C do
8 if D(E) not locally confluent at (s, t) then
9 Compute terminal vertices s0 , t0 with s →∗ s0 , t →∗ t0
10 return Knuth-Bendix(E ∪ {(s0 , t0 )}, <)
11 end
12 end
13 return E

Conceptually the Knuth-Bendix algorithm is relatively simple: In the first loop (line 2-5),
we reorder the identities in E such that they are compatible with the reduction order <. If
this is not possible we output “Fail”. In the next loop (line 7-12) we check if D(E) is locally
confluent at all critical pairs (note that there are only finitely many). If this is not true at
some critical pair, we add it (respectively a pair corresponding to terminal vertices) to the
set of our identities and recursively run the algorithm again from the beginning. If we are
locally confluent at all such pairs, we output E.
Note that there are three possible outcomes:
(1) The algorithm outputs “Fail”, since E is incompatible with the reduction order.
(2) The algorithm enters an infinite loop, adding more and more identities to E.
(3) The algorithm stops after finitely many steps, and outputs a finite set of identities F.

11
 In case (3) we clearly obtain what we wanted: D(F) is finitely terminating since we did
not output “Fail” in the first loop, and locally confluent at all critical pairs, since we finished
the second loop. Thus D(F) is convergent. However both case (1) and (2) can appear even in
situations where we know that E is equivalent to some convergent term rewriting system F.
In practice such problems can sometimes be avoided by picking the correct reduction order,
or specifying details of the algorithm (e.g. how to pick terminal vertices in Step 2). However
we remind that there are sets E such that Decide(E) is undecidable and there is no convergent
term rewriting system equivalent to E. For such E the Knuth-Bendix algorithm will always
result in outcome (1) or (2).

1.4 Exercises
Exercise 1.1. Let E = {f (x) ≈ f (f (x))}. Draw D(E), and explain why the term rewriting
algorithm does not work. What is the problem and how can it be fixed?

Exercise 1.2. Let E = {f (f (x)) ≈ g(x)}.

1. Show that (with respect to Id(Mod(E))) every term t(x) is equivalent to a term of the
form g n (x) or g n f (x)
2. Show that the term rewriting algorithm does not work in computing the above normal
from. What seems to be the problem?
3. Add an identity to E to fix this problem.

Exercise 1.3. Let E = {f (x + y) ≈ x + f (y), f (f (x)) ≈ f (x)}.

1. Show that (with respect to Id(Mod(E))) every term is equivalent to a term, which has
f symbols only at its branches.
2. Show that every term is equivalent to exactly one such term.
3. Show that the ’term rewriting’ algorithm solves Decide(E).
4. Find a rewriting order compatible with E.

Exercise 1.4. Find an example of a digraph that is locally confluent, but not confluent.

Exercise 1.5. Find a convergent rewriting system equivalent to the identity (x · y) · (y · z) ≈ y

(Hint: Knuth-Bendix will produce 2 additional rules.)

Exercise 1.6. Consider the two rewriting rules

E = {f (x) + (y + z) ≈ x + (f (f (y)) + z), f (x) + (y + (z + w)) ≈ x + (y + (z + w))}.

Show that D(E) is finitely terminating.

Exercise 1.7. Finish the proof of the equational complete theorem (Theorem 1.10). For
simplicities sake, you may assume that τ consists only of a binary operation ·.

Exercise 1.8. Let E1 = {(xy)z ≈ x(yz)}, E2 = E1 ∪ {(xy)z ≈ x(yz), xx ≈ x} and E3 =

E2 ∪ {(xy)z ≈ xz, x(yz) ≈ xz}. (We remark that E1 defines the variety of all semigroups,
E2 bands (idempotent semigroups), and E3 the so called rectangular bands and all D(Ei ) are
finitely terminating).

12
 • Show that D(E1 ) and D(E3 ) are locally confluent, but D(E2 ) is not.
• (*) Try to argue that our version of Knuth-Bendix algorithm will enter an infinite loop
for E2 .

Exercise 1.9. Try to come up with a convergent rewriting system for the variety of groups
(Hint: Think of a normal form of group terms first; then write down the rewriting system.
Don’t get stuck in technical details).

Exercise 1.10. An alternative way to encode terms is by circuits. Instead of labeling trees
with operation symbols, they are obtained by labeling directed acyclic graphs. For instance,
the term t = ((x1 · x2 ) · x3 ) · (x1 · x2 ) can be represented as

· x3

x1 x2

Circuits are often more efficient at encoding terms, since subterms (such as x1 · x2 in the
example) can be reused in their construction.
1. Try to give a proper definition of circuits over arbitrary language τ
2. Find a family of group (or ring) terms (tn )n∈N that have linear size O(n) when expressed
as circuits, but require exponential size O(2n ) when expressed by term trees.

Exercise 1.11. The version of term rewriting we discussed in this chapter is quite limited.
1. Show that, D(E) is not convergent, for any axiomatisation E of the variety of commu-
tative rings (Hint: x + y ≈ y + x).
2. Still, in Example 1.2 we saw an algorithm that decides if E |= s ≈ t. Discuss how to
weaken the definition of convergence, normal forms, and reduction order, in order to
describe it as a term rewriting algorithm.
3. A general strategy to fix this problem is to allow not only partial orders, but also
pre-orders in the definition of reduction orders. For details see e.g. Section 13.7. in [1].

Exercise 1.12. It is a well-known fact in logic, that every propositional formula ϕ(x1 , . . . , xn )
(i.e. every formula using ∧, ∨, ¬, 0, 1) can be rewritten into a conjunctive normal form (CNF),
i.e. a formula C1 ∧ C2 ∧ C3 ∧ . . . ∧ Ck , with Ci = li,1 ∨ li,2 ∨ · · · ∨ li,ji , where every li,j is either
equal to a variable or negation of a variable. Describe a term rewriting system E that rewrites
every formula to a CNF. What is the variety Mod(E)?

Exercise 1.13. Based on the examples we saw, design an algorithm that, for two input terms
t, s ∈ F returns θ(t) = θ(s) if the terms have a most general unifier θ, and “False” otherwise.

13
Chapter 2

Commutator theory

Commutative groups, vector spaces and modules are examples of algebras that are well under-
stood in both their structural properties (e.g. classification results), but also computational
ones (e.g. solving equations by Gauss elimination). This stems mainly from the fact that all
their term and polynomial operations are affine. More generally, many results in group theory
are based on measuring how close a group or its subgroups are to being commutative (think
of definitions like commutator subgroups, centralizers, nilpotent and solvable groups...).
Commutator theory is the part of universal algebra that tries to generalize such group
theoretic definitions and results to arbitrary algebras. Its development started in the 1970ies
with results of Gumm and Smith. A standard reference for commutator theory is the book of
Freese and McKenzie that discusses commutator theory in congruence modular varieties [3];
for such varieties commutator theory works particularly well.
In this chapter we are going to discuss some basics of commutator theory. We start with
the definition of Abelianness for general algebras and prove Herrmann’s fundamental theorem,
which characterizes Abelian algebras in congruence modular varieties.
After that we define the commutator of two congruences and show that it generalizes
the commutator subgroup (in groups) and the product of two ideals (in commutative rings).
We further show how the commutator can be used to characterize congruence distributive
varieties.
All presented results hold for algebras from congruence modular varieties; we are however
only going to discuss algebras with a Maltsev operations, which is a stronger assumption that
makes many proofs easier. Most of the results presented here can also be found in Chapter
7.2-7.4 of Bergman’s book [2] (however in different notation).

2.1 Affine and Abelian algebras

We start by recalling some definitions from the Universal Algebra 1 lecture:

Definition 2.1. Let A be an algebra with universe A. A polynomial operation of A is an

operation of the form p(x1 , . . . , xn ) = t(x1 , . . . , xn , a1 , . . . , ak ) where t ∈ Clo(A) is a term
operation of A and a1 , . . . , ak ∈ A. The set of all polynomial operations of an algebra forms
a clone, which is sometimes denoted by Pol(A). 1
1
Attention: this should not be confused with the polymorphism clone Pol(A) of a relational structure A in
Definition 4.7

14
 Two algebras A and A′ on the same universe are called polynomially equivalent if they
have the same clone of polynomial operations.
So a polynomial operation is an operation that can be built from variables, constants from
A, and basic operations of A. If for instance A = ({0, 1}, +, ·) is the 2-element ring; then
p(x, y) = (1 + x) · (y · y + x) + 1 is a polynomial operation of A.
Next, recall from UA1 that we represented R-modules as algebras A = (A, +, 0, −, (r)r∈R ),
where (A, +, 0, −) is the underlying group, and every ring element r ∈ R corresponds to the
unary scalar multiplication r(x) = r · x. It is easy to see that every polynomial operation
p(x
Pn1 , . . . , xn ) of an R-module A is an affine combination of variables, so p(x1 , . . . , xn ) =
i=1 αi xi + c with αi ∈ R and c ∈ A. This motivates the following definition:

Definition 2.2. We call an algebra A affine if it is polynomially equivalent to an R-module

(for some ring R with identity).
Note that according to this definition also every commutative group is affine (by picking
R = Z as the ring; and defining the scalar multiplication n · x := |x + x +
{z· · · + x}).
n times
Our goal in this section is to characterize affine algebras in more ”‘universal algebraic”’
terms. We start by observing that affine algebras have two nice properties, namely that they
they are Abelian, and that have a unique Maltsev polynomial, which is central.
Definition 2.3. A Maltsev (also Mal’cev ) operation m(x, y, z) is a ternary operation satis-
fying the identities m(y, x, x) ≈ m(x, x, y) ≈ y.
Maltsev operations were already defined in the UA1 lecture. Note that every group has a
Maltsev term: m(x, y, z) = xy −1 z. Similarly also every ring and module has a Maltsev term
m(x, y, z) = x − y + z.
Definition 2.4. Let A be an algebra. A polynomial p : A3 → A of A is called central if it
satisfies

p(f (x1 , . . . , xn ), f (y1 , . . . , xn ), f (z1 , . . . , zn )) = f (p(x1 , y1 , z1 ), . . . , p(xn , yn , zn )),

for all basic operations f of A. Note that this is equivalent to saying that p is a homomorphism
A3 → A, or to the characterization in Figure 2.1.

x1 y1 z1 → p(x1 , y1 , z1 )
x2 y2 z2 → p(x2 , y2 , z2 )
.. .. .. .. ..
. . . . .
xn yn zn → p(xn , yn , zn )
↓ ↓ ↓ ↓
f (x̄) f (ȳ) f (ȳ) → ⋆

Figure 2.1: If p is central, the result ⋆ is the same, no matter if we evaluate the rows (under
p) or the columns (under f ) first.

Observation 2.5. Let A be affine. Then A has a unique Maltsev polynomial operation
m(x, y, z). Moreover m(x, y, z) is central.

15
Proof. By definition A is is polynomially equivalent to an R-module A′ = (A, +, 0, −, (r)r∈R ).
Therefore it has a Maltsev polynomial m(x, y, z) = x − y + z. We claim that this is the only
ternary polynomial satisfying the Maltsev identities.
So let p(x, y, z) be some other polynomial of A satisfying the Maltsev identities. Since A is
affine, we know that p(x, y, z) = αx + βy + γz + c for some scalars α, β, γ ∈ R and c ∈ A. By
the equality p(0, 0, 0) = 0, we obtain c = 0. For all x we further have x = p(x, 0, 0) = αx;
analogously we can prove γx = x. At last note that for all x ∈ A: p(x, x, 0) = x + βx = 0;
therefore βx = −x. We conclude that p(x, y, z) = x − y + z = m(x, y, z).
For the centrality, let f (x1 , . . . , xn ) be a basic operation P
of A. Since A is affine we know
that f is an affine combination of variables f (x1 , . . . , xn ) = ni=1 αi xi + c. Therefore

n
X n
X n
X
m(f (x̄), f (ȳ), f (z̄)) = ( αi xi + c) − ( αi yi + c) + ( αi zi + c)
i=1 i=1 i=1
n
X
= αi (xi − yi + zi ) + c
i=1
= f (m(x1 , y1 , z1 ), . . . , m(xn , yn , zn )),

so m is central.

We next discuss Abelianness, which is defined by the following condition on the term
operations of A:

Definition 2.6. An algebra A is called Abelian if all term operations t ∈ Clo(A) (of arbitrary
arity n + 1) satisfy the condition

∀x, y ∈ A, ∀ū, v̄ ∈ An : t(x, ū) = t(x, v̄) ⇒ t(y, ū) = t(y, v̄). (2.1)

Observation 2.7. Let A be affine. Then A is Abelian.

Let t ∈ Clo(A). Then t can be written as an affine combination t(x, z1 , . . . , zn ) =

Proof. P
α0 x + ni=1 αi zi + c. Now it is an easy computation that, for all x, y ∈ A and ū, v̄ ∈ An :
n
X n
X
t(x, u1 , . . . , un ) = t(x, v1 , . . . , vn ) ⇔ αi ui = αi vi ⇔ t(y, u1 , . . . , un ) = t(y, v1 , . . . , vn ),
i=1 i=1

thus A is Abelian.

We give some more examples of Abelian algebras:

Example 2.8.
1. Every unary algebra A = (A, f (x)) is Abelian.
2. every affine algebra is Abelian.
3. A semilattice (L, ∧) is Abelian if |L| = 1.
4. a group (G, ·, e,−1 ) is Abelian if and only if x · y ≈ y · x.
5. a ring (R, +, 0, −, ·) is Abelian if and only if x · y ≈ 0.

16
Proof (Solution to Exercise 2.2).
1. Every term is of the form t(x1 , . . . , xn ) = f k (xi ), and therefore only depends on one
coordinate. Because of this the term condition (2.1) holds.
2. We showed this in Observation 2.7.
3. We apply the term condition (2.1) to the term t(z1 , z2 ) = z1 ∧ z2 . If |L| > 1 there are
two elements x, y ∈ L with x < y. Then we have x = t(x, x) = t(x, y). By (2.1) we
obtain t(y, x) = t(y, y), which is equivalent to x = y - a contradiction!
4. Let us consider the term operation [z1 , z2 ] := z1−1 z2−1 z1 z2 , and let x, y ∈ G. Then clearly
e = [e, y] = [e, e] = e. By applying the term condition (2.1), we can exchange the first
coordinate on both sides of this equation by x, obtaining [x, y] = [x, e] = e. Thus
[x, y] = e for all x, y ∈ G, or in other words, the multiplication is commutative. For
the converse note, that we already saw before that commutative groups are affine, and
therefore also Abelian.
5. For a ring (R, +, 0, −, ·), let us look at the term t(z1 , z2 ) = z1 · z2 . Let x, y ∈ R. Then
clearly t(0, y) = t(0, 0) = 0. By applying (2.1) to this equation we get t(x, y) = t(x, 0) =
0. For the other direction, note that if x · y ≈ 0, then the ring is polynomially equivalent
to the commutative group (R, +, 0, −), which is Abelian.

2.2 The fundamental theorem of Abelian algebras

As you can see from Example 2.8 (1), Abelian algebras need not to be affine (for another
example see Exercise 2.7). The fundamental theorem of Abelian algebras (Herrmann ’79)
however states, that, under the additional assumption of A being from a congruence modular
variety, Definition 2.6 is indeed equivalent to A being affine. We are only going to prove this
theorem for the special case of algebras with a Maltsev polynomial m (already discussed by
Smith ’75, Gumm ’79). In this case Abelianness is moreover equivalent to m being central.

Theorem 2.9 (Fundamental theorem). Let A be an algebra with a Maltsev polynomial

m(x, y, z). Then the following are equivalent:
1. A is Abelian
2. A is affine
3. m is central

Proof. We already saw the implications (2) → (1),(3) in Observations 2.5 and 2.7.
For the implication (3)→(1) assume that m is central; let t be a term operation, and let
x ∈ A, ū, v̄ ∈ An such that t(x, ū) = t(x, v̄). We then want to show that t(y, ū) = t(y, v̄) for
arbitrary y.
For this consider the expression m(t(y, ū), t(x, ū), t(x, v̄)). Since t(x, ū) = t(x, v̄) and m is
Maltsev, it is equal to t(y, ū). On the other hand, using the centrality of m, we can rewrite the
expression into t(m(y, x, x), m(u1 , u1 , v1 ), . . . , m(un , un , vn )), which is equal to t(y, v1 , . . . , vn )
by the Maltsev identities. So we obtain t(y, ū) = t(y, v̄), which is what we wanted to show.
For the implication (1)→(2), we need to construct a module that is polynomially equivalent
to A. Let us fix an arbitrary element 0 ∈ A. We then define the group operations + and −

17
by the polynomials x + y = m(x, 0, y) and −x = m(0, x, 0). The ring R is defined as R = {f
unary polynomial : f (0) = 0}. We first verify the module axioms for (A, +, 0, −, (r)r∈R ).
It is easy to see that 0 is the neutral element of +, since x = m(0, 0, x) = 0 + x =
m(x, 0, 0) = x + 0 by the Maltsev identities. To prove associativity, consider the term
t(x1 , x2 , x3 , x4 ) = (x1 +x2 )+(x3 +x4 ). By the neutrality of 0, t(0, 0, b, c) = t(0, b, 0, c) holds for
all b, c ∈ A. Note that the first coordinate on both sides of the equation is set to 0. Thus we
can apply the term condition (2.1) to this equation, and obtain that t(a, 0, b, c) = t(a, b, 0, c)
for arbitrary a. This is equivalent to a + (b + c) = (a + b) + c, hence + is associative.

— (Solution to Exercise 2.4)

For commutativity, note that m(a, a, b) = m(b, a, a) for every a, b ∈ A. By the term
condition (2.1), this is still true if we substitute the middle a by 0, thus we obtain m(a, 0, b) =
m(b, 0, a), which is equivalent to a + b = b + a.
To see that −a = m(0, a, 0) is the inverse of a, consider the polynomial t(x, u1 , u2 ) =
u1 + m(x, u2 , 0). For every a ∈ A we then have t(a, a, a) = t(a, 0, 0) = a. By the term
condition (2.1) we obtain t(0, a, a) = t(0, 0, 0); in other words a + (−a) = 0.
Thus (A, +, 0, −) is a commutative group. Next let r ∈ R. Then, note that it is distribu-
tive with respect to + iff t(x, y) = r(x+y)−r(x)−r(y) is the constant 0 function. Let a, b ∈ A.
Clearly t(0, b) = t(0, 0) = 0 for all b ∈ A. By the term condition we get t(a, b) = t(a, 0) = 0,
which is what we wanted to prove.
—

It is still left to prove that every polynomial p(x1 , . . . , xn ) of A is affine. We show it by

an induction on the arity n. For n = 1 the statement is clearly true (since by the definition
of R, p(x) = r(x) + p(0), for some r ∈ R).
For an induction step, let us look at the polynomial t(x1 , . . . , xn ) = p(x1 , x2 , . . . , xn ) −
p(0, x2 , . . . , xn ) − p(x1 , 0, . . . , 0) + p(0, . . . , 0).Using the term condition (2.1) (as in the proof of
the distributivity of r ∈ R) we see that t is the constant 0 function. Thus p(x1 , x2 , . . . , xn ) =
p(0, x2 , . . . , xn ) + p(x1 , 0, . . . , 0) − p(0, . . . , 0); the latter three summands are affine because of
the induction hypothesis, hence p is also affine.

Using the observation that every affine algebra has a Maltsev term, we obtain the following
corollary:

Corollary 2.10. An algebra is affine if and only if it is Abelian and has a Maltsev polynomial.

2.3 The term condition commutator

The actual strength of commutator theory is to give us tools for analyzing the congruences of
an algebra and how they interact with each other. These tools are primarily the centralizer
relation C and the commutator [α, β] of two congruences α, β.
In this section we are going to define them by a term condition similar to the condition
(2.1) in the definition of Abelianness and show that in the group setting, the commutator
of two congruences corresponds to the commutator subgroups of two normal subgroups. In
the next section, however, we will see that the commutator is also very useful in discussing
algebras that are far from being ”group like”.

18
Definition 2.11. Let A be an algebra, and let α, β, δ ∈ Con(A).
We then say that α centralizes β modulo δ, and write C(α, β; δ), if, for all terms t ∈ Clo(A)
(of arbitrary arity n + 1), for all x, y ∈ A and ū, v̄ ∈ An with x α y and ui β vi (for all indices
i = 1, . . . , n):

t(x, ū) δ t(x, v̄)

(2.2)
⇒ t(y, ū) δ t(y, v̄)

If δ = 0A , we say that α centralizes β.

Comparing Definition 2.11 with Definition 2.6 observe that A is Abelian, if and only if
C(1A , 1A ; 0A ). If instead of single elements x and y, we also allow tuples x̄, ȳ such that xi α yi
holds for all entries, we still define the same relation C (see Exercise 2.15). For simplicity let
us from now on write ū β v̄ if ū and v̄ are two tuples of the same length n, and for every index
and ui β vi holds for every i = 1, . . . , n.

We start by discussing the relation C for groups. Recall that the congruences of a group
(G, ·, e,−1 ) correspond to its normal subgroups. We are going to show that in groups α
centralizes β, if and only if the corresponding normal subgroups centralize each other in the
classical group theoretical sense:
Proposition 2.12. Let α, β be two congruences of a group G = (G, ·, e,−1 ), and let A = [e]α
and B = [e]β be the corresponding normal subgroups. Then α centralizes β if and only if
a · b = b · a, for all elements a ∈ A and b ∈ B.
Proof. To see that C(α, β; 0) implies a · b = b · a for all a ∈ A and b ∈ B, we can use
the same proof idea as in Example 2.8 (4), applying the term condition (2.2) to the term
[x, y] = x−1 y −1 xy.
Proving the converse is more work. Assume that a · b = b · a, for all elements a ∈ A and
b ∈ B. Our proof of C(α, β; 0) then uses the following two observations:
• Observation 1: for every term s ∈ Clo(G) and tuples ū, v̄ such that ū β v̄ we have that
s(ū)(s(v̄))−1 ∈ B. This follows straightforward from β being a congruence.
• Observation 2: For all u, v ∈ G with u α v, and b ∈ B: u−1 bu = v −1 bv.
This follows from b = (u−1 v)(v −1 u)b = (u−1 v)b(v −1 u), where the last equality uses the
assumption that elements of A and B commute.
To check the term condition for C(α, β; 0) let t ∈ Clo(G) be a group term, let x, y ∈
G, ū, v̄ ∈ Gn such that x α y and ū β v̄. We are going to prove that

t(x, ū)(t(x, v̄))−1 = t(y, ū)(t(y, v̄))−1 . (2.3)

Note that the above equation directly implies the term condition (2.2); in that case both sides
of the equation are equal to e.
Since t is a group term, it can be represented as product of variables or their inverses,
so t(x1 , x2 , . . . , xn ) = z1 · z2 · · · zm , with zi ∈ {xd1 , . . . , xdn | d ∈ {−1, 1}}. We prove (2.3) by
induction on the length m.
For m = 1 the statement clearly holds: If t(x, ū) = x we get that

t(x, ū)(t(x, v̄))−1 = xx−1 = e = yy −1 = t(y, ū)(t(y, v̄))−1 ;

19
the proof is analogue for x−1 . If t(x, ū) = ui for some i, we have t(x, ū)(t(x, v̄))−1 = ui vi−1 =
t(y, ū)(t(y, v̄))−1 ; the proof is analogous for u−1
i .

For an induction step m − 1 → m let t = z1 · s. Note that s(x, ū)(s(x, v̄))−1 is in B by

Observation 1, and equal to s(y, ū)(s(y, v̄))−1 by the induction hypothesis (IH). We do a case
distinction, depending on z1 .
If t(x, ū) = ui s(x, ū), for some i, we get
IH
t(x, ū)(t(x, v̄))−1 = ui s(x, ū)(s(x, v̄))−1 vi−1 = ui (s(y, ū)(s(y, v̄))−1 )vi−1 = t(y, ū)(t(y, v̄))−1 .

If t(x, ū) = xs(x, ū), we get that

t(x, ū)(t(x, v̄))−1 = xs(x, ū)(s(x, v̄))−1 x−1

IH
= xs(y, ū)(s(y, v̄))−1 x−1
Ob2
= ys(y, ū)(s(y, v̄))−1 y −1 = t(y, ū)(t(y, v̄))−1 .

If z1 is an inverse of a variable the proof is analogous.

So we proved (2.3) for all x α y and ū β v̄. This in turn implies that the term condition
(2.2) holds; thus α centralizes β.

There are a few observations that follow straightforward from the definition of C(α, β; δ),
and allow us to define the commutator.

Observation 2.13.
1. If α ≥ α′ , β ≥ β ′ and C(α, β; δ), then C(α′ , β ′ ; δ).
2. C(α, β; δ) in A if and only if C(α/δ, β/δ; 0A ) in A/δ
3. C(α, β; α) and C(α, β; β)
V
4. Let ∆ be a set of congruences. If C(α, β; δ) for all δ ∈ ∆ then C(α, β; ∆)

Proof. left as Exercise 2.12.

Definition 2.14. The commutator of α and β, short [α, β], is the smallest δ ∈ Con(A), such
that C(α, β; δ).

Note that the commutator is well defined: By Observation 2.13 (3), there is always a δ,
such that α centralizes β modulo δ. By Observation 2.13 (4) the infimum γ of all such δ’s has
also the property that C(α, β; γ). In other words this infimum γ is the commutator [α, β].
Note also that, by Observation 2.13 (3) and (4) we have [α, β] ≤ α ∧ β.
In the literature, the commutator appears more commonly than the relation C; we are
going to prove later that in the Maltsev case one can be defined via the other by C(α, β; δ) ⇔
[α, β] ≤ δ.
We give some examples:

Example 2.15. Let α, β two congruences of a group G = (G, ·, e,−1 ), and let A = [e]α and
B = [e]β the corresponding normal subgroups. Then [α, β] corresponds to the commutator
subgroup [A, B], i.e. the normal subgroup generated by {a−1 b−1 ab : a ∈ A, b ∈ B}.

20
Proof. By Proposition 2.12 we have that C(α, β; δ) if and only if (a · b) δ (b · a) for all a ∈ A,
b ∈ B. If we set D = [e]δ , this is equivalent to a−1 b−1 ab ∈ D. Now the smallest normal
subgroup D such that this holds is clearly the normal subgroup generated by all elements
a−1 b−1 ab, which by definition is the commutator subgroup [A, B].

Example 2.16. Let (R, +, 0, −, ·) be a commutative ring. Recall that its congruences α are
uniquely determined by the ideals Iα = [0]α . We claim that then α centralizes β if and only
if Iα · Iβ = 0. The congruence [α, β] corresponds to the ideal Iα · Iβ .

Proof. Exercise 2.13.

Example 2.17. Let L = (L, ∧, ∨) be a lattice. Then [α, β] = α ∧ β for all congruences
α, β ∈ Con(L).

Proof. We already know by Observation 2.13 that [α, β] ≤ α ∧ β. So it is only left to show
that C(α, β; δ) implies δ ≥ α ∧ β.
Let x (α ∧ β) y. Without loss of generality we can assume that x ≤ y (since from UA1 we
know that for any congruence γ ∈ Con(L) we have (x, y) ∈ γ if and only if (x ∧ y, x ∨ y) ∈ γ).
Then, for the term t(z1 , z2 ) = z1 ∧ z2 clearly t(x, x) = t(x, y) holds. In particular this implies
that t(x, x) δ t(x, y). By the term condition for C(α, β; δ), we can exchange the first coordinate
by y, and obtain x = t(y, x) δ t(y, y) = y. Thus α ∧ β ≤ δ, which concludes the proof.

In general the commutator does not need to satisfy [α, β] = [β, α], as one might think
after Examples 2.15, 2.16, 2.17. However in the Maltsev case commutativity holds. In the
following we give a proof and show a few other additional properties of the commutator in
the Maltsev case.
We need the following helpful lemma first.

Lemma 2.18. Assume A has a Maltsev polynomial m(x, y, z), and let α, β ∈ Con(A)
such that [α, β] = 0A . Let t ∈ Clo(A) and x̄, ȳ such that x̄ α ȳ and ū β v̄. Then t(ȳ, v̄) =
m(t(ȳ, ū), t(x̄, ū), t(x̄, v̄)).

Proof. Since m is a Maltsev operation, the following equation holds.

m(t(x̄, v̄), t(x̄, ū), t(x̄, ū)) = m(t(x̄, ū), t(x̄, ū), t(x̄, v̄))

By applying the term condition for C(α, β; 0) we can exchange the first x̄ by ȳ, and obtain:

m(t(ȳ, v̄), t(x̄, ū), t(x̄, ū)) = m(t(ȳ, ū), t(x̄, ū), t(x̄, v̄))

But since m is a Maltsev operation, the left side is equal to t(ȳ, v̄), which finishes the proof.

Note that Lemma 2.18 can be seen as a generalization of the centrality of the Maltsev
operation in the case where [1A , 1A ] = 0A .We can use Lemma 2.18 to prove some useful
properties of the commutator:

Lemma 2.19. Let A be an algebra with a Maltsev polynomial. Then

1. C(α, β; δ) holds if and only if [α, β] ≤ δ
2. The commutator is commutative: [α, β] = [β, α]
W W
3. The commutator is distributive: [ Γ, α] = γ∈Γ [γ, α]

21
Proof.
1. If follows from the definition of the commutator, that C(α, β; δ) implies [α, β] ≤ δ. For
the opposite direction, assume that [α, β] ≤ δ; we then want to verify the term condition
for C(α, β; δ).
Without loss of generality we can assume that [α, β] = 0 (otherwise we work in the
quotient A/[α, β] by Observation 2.13(2)). Let x̄ α ȳ and ū β v̄, and t ∈ Clo(A) such
that t(x̄, ū) δ t(x̄, v̄).
By Lemma 2.18 we know that t(ȳ, v̄) = m(t(ȳ, ū), t(x̄, ū), t(x̄, v̄)), which is δ-related to
m(t(ȳ, ū), t(x̄, v̄), t(x̄, v̄)) = t(ȳ, ū). Thus t(ȳ, ū) δ t(ȳ, v̄), which is what we wanted to
prove.
2. By (1) this is equivalent to showing C(α, β; δ) ⇔ C(β, α; δ) in A. By Observation 2.13
(2) we further can assume that δ = 0. So let us assume that C(α, β; 0). Our goal is
then to prove that for all terms t and for all x̄, ȳ such that x̄ α ȳ and ū β v̄, the equation
t(x̄, ū) = t(ȳ, ū) implies t(x̄, v̄) = t(ȳ, v̄). By Lemma 2.18:
t(ȳ, v̄) = m(t(ȳ, ū), t(x̄, ū), t(x̄, v̄)) = t(x̄, v̄),
where the second identity follows from the Maltsev identities.
W
3. Note that [ Γ, α] ≥ [γ, α] holds forWevery γ ∈ WΓ by Observation 2.13 (1). By taking the
supremum over all such γ we get [ Γ, α] ≥ γ∈Γ [γ, α].
W
For
W the other direction, let β = γ∈Γ [γ, α]. ToW complete the proof we need W to show
[ Γ, α] ≤ β, which by (1) is equivalent to C( Γ, α; β).W So let (x, y) ∈ Γ, and ū, v̄
such that (ui , vi ) ∈ α, and let t ∈ Clo(A). Since (x, y) ∈ Γ there is a chain of elements
a0 , . . . , ak ∈ A and congruences γ1 , . . . , γk ∈ Γ such that x = a0 γ1 a1 γ2 a2 · · · γk ak = y.
By (1) β ≥ [α, γi ] is equivalent to C(α, γi ; β). Using the corresponding term condition
for every i = 1, . . . , k, we get
t(x, ū) β t(x, v̄) ⇒ t(a1 , ū) β t(a1 , v̄) ⇒ t(a2 , ū) β t(a2 , v̄) ⇒ . . . ⇒ t(y, ū) β t(y, v̄),
W
which completes the proof of the term condition for C( Γ, α; β).

Here is a short overview over all the properties of the commutator proved in this section:

Summary
α′ ≤ α, β ′ ≤ β ⇒ [α′ , β ′ ] ≤ [α, β] by Observation 2.13 (1)
[α, β] ≤ α ∧ β by Observation 2.13 (3), (4)
If A has Maltsev polynomial:
C(α, β; δ) ⇔ [α, β] ≤ δ Lemma 2.19 (1)
[α/γ, β/γ] = [α, β]/γ in A/γ Lemma 2.19 (1) + Obs. 2.13 (2)
[α, β] = [β, α] Lemma 2.19 (2)
W W
[ Γ, α] = γ∈Γ [γ, α] Lemma 2.19 (3)

22
Remark 2.20. There are several other concepts from group theory that, building on this
framework, can be directly generalized to arbitrary algebras:
• A congruence α is called Abelian if [α, α] = 0A
• The centralizer of a congruence α is the biggest β, such that C(α, β; 0)
• The center ζA of an algebra A is the centralizer of 1A .
• A central series is a series of congruences 0A = α0 ≤ α1 ≤ · · · ≤ αn = 1A , such that
[1A , αk ] ≤ αk−1 , for all k = 1, . . . , n.
• An algebra is called (n-)nilpotent if it has a central series (of length n).
• An algebra is called (n-)solvable if there is a series 0A = α0 ≤ α1 ≤ · · · αn = 1A , with
[αk , αk ] ≤ αk−1 .

2.4 Commutator and varieties

Commutators allow us to characterize certain properties of varieties. We already saw an
example in Corollary 2.10: A variety V with Maltsev term is affine, if and only if [1A , 1A ] = 0A
holds in every algebra A ∈ V.
A more involved result is the following theorem by Freese and McKenzie that discusses
the subdirectly irreducible elements of an algebra:

Theorem 2.21 (Freese, McKenzie [3]). Let A be an algebra, such that V = HSP(A) is
congruence modular. Then V contains only finitely many subdirectly irreducible elements,
which are all finite 2 if and only if for all α, β ∈ Con(A): α ≤ [β, β] ⇒ α = [α, β].

In this section we give another example of commutators neatly describing the properties
of a variety. We already saw in Example 2.17 that in the variety of lattices [α, β] = α ∧ β
holds. By the same argument this is also true in the variety of Boolean algebras. Both are
congruence-distributive variety; and in fact in the Maltsev case, congruence distributivity is
equivalent to to the ”commutator identity” [α, β] ≈ α ∧ β:

Theorem 2.22 (Hagemann, Herrmann ’79). Let V be a variety with Maltsev term. Then V
is congruence-distributive if and only if [α, β] = α ∧β holds for all congruences α, β ∈ Con(A)
of all A ∈ V.

Before reading the proof of the theorem, I suggest that you have a look at Exercise 2.18,
which proves it for any group variety.

Proof. Suppose that [α, β] = α ∧ β holds for all congruences of an algebra A with Maltsev
polynomial. Then, by the distributivity of the commutator, this algebra has also a distributive
congruence lattice: (α ∨ β) ∧ γ = [α ∨ β, γ] = [α, γ] ∨ [β, γ] = (α ∧ γ) ∨ (β ∧ γ). Thus, if all
congruences of all algebras in V satisfy [α, β] = α ∧ β then V is congruence-distributive.
For the converse, suppose that there is an algebra A ∈ V and congruences α, β ∈ Con(A)
such that [α, β] < α ∧ β. Our goal is to prove that V is not congruence distributive.
Let us define γ ′ = α ∧ β. Then, by the monotonicity of the commutator we have [γ ′ , γ ′ ] ≤
[α, β] < γ ′ . The quotient B = A/[α, β] also lies in the variety V. Let γ = γ ′ /[α, β]. Then γ
is a non-trivial congruence of B with [γ, γ] = 0B .
2
Such varieties are called residually finite

23
 We can regard γ as a subalgebra of B2 . Hence also γ is an element of the variety V. To
make it clear that we consider γ as an algebra, we write B(γ) instead of γ, and write its
element by column vectors, so B(γ) = { ab : a, b ∈ B, a γ b}.

We then claim that the congruence lattice of B(γ) contains the following sublattice:

γ1 = γ2

η1 ∆ η2

If we can prove this claim, Con(B(γ)) is not distributive, since this sublattice is not
distributive.
a

c
a

c

We define the congruences b η 1 d if and only if a = c, and b η2 d if and only if b = d.
Similarly we define ab γ1 dc , if aγc. Note that this is equivalent to all four elements a, b, c, d

being in the same γ-class. It is easy to see that η1 ∧ η2 = 0 and η1 ∨ η2 = γ1 .

The last congruence ∆ is defined by
    
t(x̄, ū) t(x̄, v̄)
∆= , : x̄ γ ȳ, ū γ v̄, t ∈ Clo(B) .
t(ȳ, ū) t(ȳ, v̄)

By a lemma of Maltsev (Exercise 2.19), ∆ is indeed a congruence of B(γ).

a c



If b (η1 ∧ ∆) d , there is a term t and tuples x̄, ȳ, ū, v̄ such x̄ γ ȳ, ū γ v̄ and a = t(x̄, ū) =
t(x̄, v̄) = c, b = t(ȳ, ū) and d = t(ȳ, v̄).
By the
term condition for [γ, γ] = 0 it follows that
b = t(ȳ, ū) = t(ȳ, v̄) = d, and therefore ab = dc . So η1 ∧ ∆ = 0. Symmetrically we can prove
that η2 ∧ ∆ = 0.
η1 ∨ ∆ = γ1 , simply observe that aa ∆ cc holds for all a γ c. Therefore, for all



To see that
pairs ab , dc ∈ γ we have:

       
a a c c
η1 ∆ η1 ,
b a c d
showing that η1 ∨ ∆ = γ1 . Symmetrically η2 ∨ ∆ = γ1 holds. Thus B(γ) is not congruence
distributive. Since it is an element of V, V is not congruence distributive, which finishes our
proof.

Remark 2.23. Our version of Theorem 2.22 does not cover varieties of lattices (Exam-
ple 2.17), since lattice varieties usually don’t have a Maltsev term. But it is known that
Theorem 2.22 holds for all congruence modular varieties V (and thus also for lattices), see [3].
Even more generally, Andrew Moorehead (who was until recently a member of our depart-
ment) showed in [4], that the commutator identity [α, β]H ≈ α ∧ β is equivalent to a variety V
being congruence meet-semidistributive, where his ’hypercommutator’ [α, β]H coincides with
our normal ’term condition commutator’ [α, β] on congruence modular varieties.

2.5 Nilpotent algebras

In this last section we shortly discuss a few open problems in commutator theory. This is not
part of the core (or exam) material of the lecture, but meant to show you that commutator

24
theory (despite being developed in the 80ies) is still an active field of research today. Recent
development indicates that it can be a useful tool in tackling certain problems from theoretical
computer science. One such example is the concept of ’similarity’ / ’bridges’, which appears
in the Zhuk’s proof of the CSP dichotomy conjecture [6].
In this section we are discussing another example, namely the (polynomial) equivalence
problem over a fixed algebra A, which is defined as follows:

PolEQV(A)
Input: Two polynomials s(x1 , . . . , xn ), t(x1 , . . . , xn ) over A
Question: Does A |= s(x1 , . . . , xn ) ≈ t(x1 , . . . , xn )?

Note that, if the algebra A is finite, there is always an algorithm solving PolEQV(A):
Evaluate s and t at every tuple ā ∈ An , and check if the result is the same. However this
algorithm is not very efficient, since its running time is O(|A|n ), exponential in the input size!
It would be nice to have a characterization of all finite algebras A, for which PolEQV(A)
is in P, so for which there is a deterministic polynomial time algorithm solving PolEQV(A).
But at the current state we are far from such a classification.
However for algebras with Maltsev term much more is known. There seems to be a very
close connection between the complexity of PolEQV(A) and commutator properties. It is for
instance easy to see, that affine algebras have an easy equivalence problem:

Example 2.24. Let A be an affine algebra. Then A |= s ≈ t is equivalent to A |= m(s, t, 0) ≈

0. So we can reduce the equivalence problem PolEQV(A) to the problem of deciding whether
an input polynomial is equivalent to the constant 0 function.
By Exercise 2.5, a polynomial operation of A of arity n ≥ 2 is constant 0, if and only if
it is 0-absorbing. This implies that p(x1 , x2 , . . . , xn ) ≈ 0, if and only if all of the unary poly-
nomials p(x1 , 0, . . . , 0), p(0, x2 , 0, . . . , 0), . . . , p(0, . . . , 0, xn ) describe the constant 0 function.
Thus p(x1 , x2 , . . . , xn ) ̸≈ 0 if and only if there is a tuple ā, that has at most one non-0 entry,
such that p(ā) ̸= 0. There are only n · |A| many such tuples; evaluating p at them takes only
linear time. So PolEQV(A) is in P.

On the other hand, by results of Idziak and Krzaczkowski [5], finite Maltsev algebras A
with trivial center ζA = 0A are polynomially equivalent to an A′ , for which PolEQV(A′ ) is
coNP-complete (and therefore not in P, unless P = NP).
This leaves essentially only nilpotent algebras as possible candidates, for which PolEQV
is in P. Recall that an algebra is n-nilpotent if there is a series of congruences, such that
0A = α0 ≤ α1 ≤ · · · ≤ αn = 1A , such that [1A , αk ] ≤ αk−1 , for all k = 1, . . . , n. Note that
this is equivalent to [· · · [[1A , 1A ], 1A ], . . . , 1A ] = 0A .
| {z }
n+1
We are going to show that similar algorithms to Example 2.24 work to for some nilpotent
algebras, for instance nilpotent rings and groups.

Example 2.25. We saw in Example 2.16, that in a commutative ring, the commutator of two
congruences is given by the product I ·J of the corresponding ideals. Therefore a commutative
ring R is k-step nilpotent, if and only if Rk+1 = 0, or in other words, if and only if the identity
x1 · x2 · · · xk+1 ≈ 0 holds.

25
 Because of this, a polynomial in a nilpotent ring R is always equivalent to a sum of
monomials of total degree less than k. This in turn implies that every k + 1-ary 0-absorbing
polynomial of R is constant. Thus, in order to check if a polynomial p(x1 , . . . , xn ) is equivalent
to the constant 0 function, we only need
to evaluate it at all tuples with at most k-many non-0
entries. This can be done in time O( nk · |A|k ) = O(nk ). Thus PolEQV(R) is in P.

It is further known (by Burris, Lawrence ’93) that for non-nilpotent rings R, PolEQV(R)
is coNP-complete (and therefore not in P, unless P = NP). Therefore nilpotent rings are
exactly those rings, in which checking identities is computationally easy.

Example 2.26. By Proposition 2.12 a group (G, ·, e,−1 ) is n-nilpotent, if and only if the
identity [x1 , [x2 , . . . [xn , xn+1 ] · · · ] ≈ e holds, with [x, y] = x−1 y −1 xy. A similar, but more
technical argument than for rings shows that in n-nilpotent groups all 0-absorbing polynomials
of arity bigger than n are constant. Thus also for nilpotent groups the above algorithm shows
that PolEQV(G) is in P.

So both k-nilpotent groups and k-nilpotent rings have the property that 0-absorbing
polynomials of arity > k are constant. Maltsev algebras with this special property are called
k-supernilpotent.3 From the above examples one might jump to the conclusion that all k-
nilpotent Maltsev algebras have this property, but this is false! Every supernilpotent Maltsev
algebra is also nilpotent; but the opposite is not true:

Example 2.27. Let A = (Z9 , +, 0, −, (fn (x1 , . . . , xn ))n∈N ), where fn (x1 , . . . , xn ) = 3 · x1 ·

x2 · · · xn for every n. This algebra is 2-step nilpotent but not k-supernilpotent, for any k.

Example 2.28. Let A = (Z2 × Z3 , +, (0, 0), −, f (x)), where f is the unary operation defined
by (
(1, 0) if u = 0
f ((l, u)) =
(0, 0) else.
This algebra is 2-step nilpotent but not k-supernilpotent, for any k.

You may try to verify Example 2.27 as an exercise.

So what makes a nilpotent algebra? By the following result, one can regard the operations
of a k-nilpotent algebras as a k − 1-nilpotent algebra ’acting’ on an affine algebra.

Proposition 2.29 ( [3]). Let A be a k-nilpotent algebra with a Maltsev term. Then there
exists a (k − 1) nilpotent algebra U and an affine algebra L of the same signature, such that
A = L × U , and every basic operation of A is of the form

f A ((l1 , u1 ), . . . , (ln , un )) = (f L (l1 , . . . , ln ) + fˆ(u1 , . . . , un ), f U (u1 , . . . , un )),

where fˆ: U n → L.

Proof idea. You may try to prove the result for algebras A containing Abelian group opera-
tions +, 0, −. Let ζ be the center of A. Then set U = A/ζ, and construct L as an extension
of ([0]ζ , +, 0, −).
3
In general supernilpotent algebras are defined in a different way, but for Maltsev algebras those two
definitions coincide.

26
 We saw that in Abelian algebras x·y = m(x, 0, y) is a commutative group operation. More
generally one can prove that in nilpotent algebras x · y = m(x, 0, y) is a loop multiplication.
This follows from the following lemma:

Lemma 2.30. Let A be a nilpotent algebra with a Maltsev term m. Then x 7→ m(x, a, b) is
a bijection for all constants a, b ∈ A.

Proof. The lemma follows from Exercise 2.14!

Proposition 2.29 and Lemma 2.30 give us a really good idea how the polynomials of
nilpotent Maltsev algebras look like. But nevertheless many questions about them are still
unanswered.

Question 2.31. For which nilpotent A is the equivalence problem solvable in polynomial
time?

By Lemma 2.30, we can reduce this always to the problem, of deciding whether a polyno-
mial is equivalent to the constant 0 function. As we saw, there is a polynomial time algorithm
for this problem in supernilpotent algebras. Also for 2-nilpotent algebras the problem is known
to be in P. However, assuming the exponential time hypothesis (an open conjecture in com-
puter science) Idziak et al. constructed very recently (2020) some examples that are not in
P.

Another computational question concerns the subpower membership problem:

Question 2.32. The subpower membership problem of A is the computational problem where
the input consists of tuples b̄, ā1 , . . . , ān ∈ Ak , and the question is if b̄ is generated by ā1 , . . . , ān
in Ak . Is the subpower membership problem in P for finite nilpotent Maltsev algebras A?

This question is also only verified for the supernilpotent case (by results of Peter Mayr);
for general Maltsev algebras we only know that the problem is in NP.

At last we mention an open question that is connected to the next chapter of this lecture:

Question 2.33. Let A be a finite nilpotent algebra with Maltsev term. Is A finitely based ?
So is there a finite set of identities E, such that HSP(A) = Mod(E)?

This is also true for supernilpotent algebras (by results in [3]), but unknown in general.

27
2.6 Exercises
Exercise 2.1. Recall from UA1 the proof that a variety V is congruence permutable if and
only if it has a Maltsev term.

Exercise 2.2. (Without using Theorem 2.9) show that

1. a semilattice (L, ∧) is Abelian if and only if |L| = 1.
2. a group (G, ·, e,−1 ) is Abelian if and only if x−1 y −1 xy ≈ e.
3. a ring (R, +, 0, −, ·) is Abelian if and only if x · y ≈ 0.
(*) What does Abelianness mean in your favorite variety? (E.g.: Show that x · y ≈ y · x is
not sufficient for loops, quasigroups, monoids, semigroups...)

Exercise 2.3.
• Show that Definition 2.6 is equivalent to satisfying the term condition (2.1) for all
polynomial operations of A.
• Show that it is however not sufficient for Abelianness to satisfy (2.1) only for basic
operations of A. (Hint: groups)

Exercise 2.4. Complete the missing proof steps in Theorem 2.9: In the proof of (1)→(2)
why is (A, +, 0, −) a commutative group? And why are the scalar multiplications distributive
with respect to +?

Exercise 2.5. Let A be a set and 0 ∈ A. An operation f : An → A is called 0-absorbing, if

f (0, x2 , . . . , xn ) ≈ f (x1 , 0, x3 , . . . , xn ) ≈ · · · ≈ f (x1 , x2 , x3 , . . . , xn−1 , 0) ≈ 0. Show that, if A
is Abelian, all of its 0-absorbing polynomials operations (of arity n ≥ 2) must be constant.
Compare this with Exercise 2.2, and the proof steps of Theorem 2.9.

Exercise 2.6. Alternatively, try to prove (3)→(2) in Theorem 2.9 with x + y = m(x, 0, y)
and −x = m(0, x, 0). Use that m is central with respect to itself. (You can find the solution
as Theorem 7.34 in [2])

Exercise 2.7. Show that (Q, +) is Abelian, but has no Maltsev polynomial. (Hint: Show
that + preserves the order ≤ on Q and that Malcev operations do not preserve linear orders).
Observe that
Pk every polynomial operation f (x1 , . . . , xk ) of (Q, +) is equal to some affine com-
bination i=1 ni xi + c with ni ∈ Z. Why is this not a counterexample to Corollary 2.10?

Exercise 2.8.
• Show that, if V is a variety with Maltsev term, then also the subclass Vab containing all
Abelian algebras in V forms a variety.
• Let E be a set of identities such that V = Mod(E). Try to find a ’nice’ extension of E
that defines Vab (hint: m is central)
• (*) What could prevent Vab from being a variety for general varieties V?

Exercise 2.9. Let A be a 4-element set, and 0 ∈ A. There are two ways of defining a
commutative group operation on A; Let +1 be such that (A, +1 ) ∼ = Z4 , and +2 be such that
∼
(A, +2 ) = Z2 × Z2 . Show that (A, +1 , +2 ) is not Abelian (Hint: this can be done in one line,
using the results of Section 2.2).

28
Exercise 2.10. Recall the definition of a loop (L, ·, /, \, 0) (see also Bergman [2], page 5).
Show that a loop is Abelian if and only if · is an Abelian group operation.
Exercise 2.11. We saw in UA 1 that for every group G, the commutator subgroup [G, G]
is the smallest normal subgroup such that G/[G, G] is Abelian. Can you generalize this
statement to arbitrary algebras?
Exercise 2.12. Prove Observation 2.13.
Exercise 2.13. Prove Example 2.16.
Hint: Use that polynomials in rings can be written as sums of monomials.
Exercise 2.14. Let A be an algebra with Maltsev polynomial m(x, y, z) and let α, β ∈
Con(A), such that α centralizes β. Let a, b ∈ A such that a α b. Then prove that [a]β and
[b]β have the same size.
Hint: show that the map x 7→ m(x, a, b) is a bijection from [a]β to [b]β .
Exercise 2.15. Show that C(α, β; δ) in Definition 2.11 is equivalent to

t(x̄, ū) δ t(x̄, v̄) ⇒ t(ȳ, ū) δ t(ȳ, v̄)

for all terms t ∈ Clo(A) and all tuples x̄αȳ and ūβv̄.
Exercise 2.16. Look up the definition of the lower central series and upper central series of
a group. How would you generalize the two definitions to arbitrary algebras?
Exercise 2.17. Let V be a variety with Maltsev term. Then prove that all of its 2-nilpotent
members, i.e. all of the algebras satisfying [[1, 1], 1] = 0 form a subvariety.
Exercise 2.18.
1. Let Zp be the cyclic group of prime order p. How does the congruence lattice of Zp × Zp
look like? Show in particular that it is not distributive.
2. Derive that no non-trivial group variety is congruence distributive.
3. After reading the proof of Theorem 2.22: Which congruences of Zp × Zp correspond to
the congruences η1 , η2 , ∆?
Exercise 2.19. Recall from UA1 the proof of the Maltsev chain lemma:
• Let A be an algebra and let X ⊆ A2 . Then CgA (X), the congruence generated by
the pairs in X, is equal to the equivalence relation generated by {(p(x), p(y)) : p unary
polynomial of A}.
• If A has additionally a Maltsev polynomial and let X ⊆ A2 , then CgA (X) is equal to
{(p(x1 , . . . , xn ), p(y1 , . . . , yn )) : p polynomial of A and (xi , yi ) ∈ X for all i}. (This can
be found as Theorem 4.65 in [2].)
• Derive that ∆ in the proof of Theorem 2.22 is a congruence.
Exercise 2.20. Let W be a variety with Maltsev term. Show that
1. If two subvarieties V1 and V2 of W are congruence distributive, then so is V1 ∨ V2
2. If W is locally finite, then there is a largest congruence distributive subvariety.

29
Chapter 3

Finitely based algebras

An equational basis (or short, just basis) of a variety V is a set of identities E, such that
V = Mod(E). We say that E is an equational basis of an algebra A if E is a basis of HSP(A).
A variety (or algebra) is called finitely based if it has a finite basis.
Many familiar varieties, such as the variety of groups, rings, lattices, or Boolean algebras
are finitely based, since they are defined by finitely many identities. An example of a non-
finitely based variety is the variety of vector spaces (V, +, 0, −, (q)q∈Q ) over Q. It is also defined
by identities, but requires infinitely many (to describe the distributivity and composition of
the infinitely many scalar multiplications q ∈ Q). For this reason we generally exclude varieties
of infinite type when discussing finite basis results.
For varieties that are given as the HSP closure of an algebra A (or a class of algebras)
it is however in general not clear, if they are finitely based or not. If A is a finite algebra
(so A has finite universe and finite type), it can be completely specified by a finite amount
of information. So one might expect that also its equational theory is generated by finitely
many identities - but this is not true in general!
The first counterexample was a 7-element algebra with a binary operation found by Lyndon
in 1954. The smallest non-finitely based algebra is a 3-element algebra with a binary operation
constructed by Murskiı̆ in 1965. We are going to discuss a non-finitely based 4-element algebra
with a commutative (but not associative) binary operation later in this section.
On the side of positive results, it is known since the 70ies that every finite group and every
finite ring is finitely based. Unfortunately this does not generalize to Maltsev algebras (by
a result of Bryant ’82, there is even a group with an additional constant, that is not finitely
based). Baker showed in 1977 that if A generates a congruence distributive variety, A is
finitely based. We are going to discuss this in Section 3.1 and prove a result of McKenzie
that was a stepping stone to it.
In general there is little hope for a total classification of finitely based algebras: McKenzie
showed in 1996 that there is no algorithm that decides whether a finite algebra is finitely
based or not.

But why should we care about finitely based varieties in the first place? Having a finite
basis is a desirable property for a variety V, since satisfaction of the identities in the basis
provides a ’nice’ test condition to check if an arbitrary algebra belongs to V.

Example 3.1. Let S3 the symmetric group on a 3-element set. Then G ∈ HSP(S3 ) if and
only if:

30
 1. G is a quotient group of a subgroup of a power of S3 .
2. G has a normal subgroup N such that N is an elementary abelian 3-group and G/N is
an elementary abelian 2-group.
3. G is a group satisfying the identities x6 ≈ e, [x2 , y 2 ] ≈ e and [x, y]3 ≈ e.
The first characterization, while true, offers little information. The second characterization
is more informative, and perhaps the most useful to a group theorist. However it is not an
efficient condition to test, as it does not specify how to find the normal subgroup N . The
third characterization shows that S3 is finitely based; and testing if a finite G satisfies the
identities can be done in polynomial time (in the size of G and its operation tables).

In fact being finitely based is equivalent to having a ’testing condition’ that is definable
in first-order logic:

Observation 3.2. A variety V is finitely based if and only if it has an axiomatization by a

first-order sentence.

Proof. If V has a finite equational basis E then the logical conjunction of the identities in E
clearly is a first-order sentence, which defines V.
So for the opposite direction, assume that ϕ is a first-order sentence such that V consist
of all models of ϕ. For contradiction assume that V is not finitely based. So for every finite
subset E ⊆ Id(V), E ∪ {¬ϕ} has a model. By the compactness theorem of first-order logic,
also Id(V) ∪ {¬ϕ} has a model, which is a contradiction.

Before discussing the non-finitely based example, we prove a theorem of Birkhoff, which
allows us to ’approximate’ finite bases for finite A in a certain sense. Let us denote by Idn (A)
the subset of all identities of Id(A) that only contain variables from {x1 , . . . , xn }. Birkhoff’s
theorem then states as follows:

Theorem 3.3 (Birkhoff ’35). Let A be a finite algebra, and let n ∈ N. Then there exists a
finite subset E ⊆ Idn (A) such that E |= Idn (A).

So in other words, the variety generated by Idn (A) is always finitely based for finite A.
Note that this implies that A is finitely based, if and only if there is some natural number n
such that Idn (A) is an equational basis of A.

Proof of Theorem 3.3. Let T(x1 , . . . , xn ) be the totally free algebra of the same type as A,
generated by variables x1 , . . . , xn . Further let F = FA (x1 , . . . , xn ) be the free algebra in
HSP(A), generated by n-many elements.
By definition, F is isomorphic to T(x1 , . . . , xn )/ Idn (A). On the other hand we know from
Universal Algebra 1 (see also Exercise 4.34.3 in [2]) that F is finite (as it can be considered
n
as a subalgebra of AA ). Therefore Idn (A) has only finitely many equivalence classes.
We fix a set Q = {q1 , . . . , qk } of terms of T(x1 , . . . , xn ) that represent the equivalence
classes of Idn (A). Then we define E as the set of all the identities in Idn (A) that are of one
of the following forms:

xi ≈ xj
x i ≈ ql
f (ql1 , . . . , qlm ) ≈ ql

31
where f is in the type of A and 1 ≤ i, j ≤ n and 1 ≤ l, l1 , . . . , lm ≤ k. Since Q is finite, and
the type of A is finite, also E is finite.
We claim that E |= p ≈ q if and only if (p ≈ q) ∈ Idn (A). The left to right implication
holds by definition of E. For the opposite direction, assume that (p ≈ q) ∈ Idn (A). We
then prove that E |= p ≈ q. Note that it is enough to prove this for q ∈ Q, as every term is
equivalent to a unique q ∈ Q modulo Idn (A).
We prove the statement by induction on the size of p. If p = xi , then (p ≈ q) ∈ E
by definition. For an induction step, let p = f (pi1 , . . . , pim ). Then, for each pik there is a
qik ∈ Q, such that pik ≈ qik ∈ Idn (A). By the induction hypothesis E |= pik ≈ qik . By
its definition, E contains the identity f (qi1 , . . . , qim ) ≈ q. All together, this implies that
E |= f (p1 , . . . , pm ) ≈ q, which is what we wanted to prove.

Example 3.4 (Park ’80). The algebra A = (A, ·) with A = {0, 1, 2, u} and the following
operation table is not finitely based.

· 0 1 2 u
0 0 1 u u
1 1 1 2 u
2 u 2 2 u
u u u u u
Proof. Note that · is commutative, but not associative. When we write products without
brackets, we compute the multiplications left to right, so x · y · z is a shorthand for (x · y) · z.
We can describe the multiplication table of this algebra nicely via a directed graph with
vertices A \ {u} as depicted in Figure 3.1, by setting x · y = y · x = y if (x, y) is an edge of
the graph, and x · y = u else.
For an arbitrary integer n ≥ 2 we define the two n-ary terms

s(x1 , . . . , xn ) ≈ x1 · x2 · · · xn−1 · xn · x1 · · · xn
t(x1 , . . . , xn ) ≈ x2 · · · xn−1 · xn · x1 · · · xn · x1

We are going to show that A |= s ≈ t, but Idn−1 (A) ̸|= s ≈ t. Therefore there is no n
such that the (n − 1)-ary identities form a basis of A, and so A cannot be finitely based.
It is straightforward to see that A |= s ≈ t, by a case distinction: If ai = u for some i, then
s(a1 , . . . , an ) = t(a1 , . . . , an ) = u. The subalgebras ({0, 1}, ·), and ({1, 2}, ·) are semilattices,
so restricted to those values the identity also clearly holds. The only remaining case is when
both 0 and 2 appear among the input to s and t. Then, both of s(a1 , . . . , an ) and t(a1 , . . . , an )
are of the form c1 c2 · · · 2 · · · 0 · · · c2n . As we evaluate this expression, multiplying from left to
right, the result must be in {2, u} once we reach 2, and remain there. When we reach 0 the
result must be u. Thus s(a1 , . . . , an ) = t(a1 , . . . , an ) = u.
We proceed by constructing an algebra B that satisfies Idn−1 (A), but not s ≈ t. We define
B to be the algebra given by the graph in Figure 3.1, so its universe is {0, 1, . . . , n − 1} ∪ {u},
and the multiplication is x · y = y · x = y if x = y or (y = x + 1 mod n) and x · y = u
otherwise.
It is easy to see that

sB (0, 1, 2, . . . , n − 1) = n − 1 ̸= 0 = tB (0, 1, 2, . . . , n − 1),

32
 0

n−1 1

4 2

3
0 1 2 1 2 3 n−1

A as graph B as graph C as graph

Figure 3.1: The algebras in the proof of Example 3.4.

showing that B ̸|= s ≈ t.

So it is only left to show that B is a model of Idn−1 (A). Assume otherwise. Thus
there is an identity (p ≈ q) ∈ Idn−1 (A), and b1 , . . . , bn−1 ∈ B, such that pB (b1 , . . . , bn−1 ) ̸=
q B (b1 , . . . , bn−1 ). By a counting argument, there is an element of {0, 1, . . . , n − 1} that is not
among b1 , . . . , bn−1 . By the symmetry of B we can assume without loss of generality that
0∈ / {b1 , . . . , bn−1 }.
Let C = B \ {0}. Then C is a subuniverse of B. The corresponding subalgebra C can be
described by the graph in Figure 3.1. It follows from the above that C ̸|= p ≈ q. But C is in
HSP(A), which can be seen by defining the elements c̄i ∈ An−3 by

c̄1 = (0, 0, . . . , 0, 0, 0)
c̄2 = (0, 0, . . . , 0, 0, 1)
c̄3 = (0, 0, . . . , 0, 1, 2)
c̄4 = (0, 0, . . . , 1, 2, 2)
..
.
c̄n−1 = (2, 2, . . . , 2, 2, 2)

Then D = {c̄1 , . . . , c̄n−1 } ∪ {ȳ ∈ An−3 : u ∈ {y1 , . . . , yn−3 }} forms a subuniverse of An−3 .
The map that sends each c̄i to i and all other elements to u is a homomorphisms from D to
C, thus C ∈ HSP(A). This is a contradiction to C ̸|= p ≈ q.
We conclude that B is a model of Idn−1 (A), but B ̸|= s ≈ t, and therefore B ̸∈ HSP(A).
Hence A is not finitely based.

3.1 Park’s conjecture and McKenzies DPC theorem

As already mentioned, it is not likely that there will ever be a complete characterization of
all finitely based algebras. However we can still try to look for sufficient criteria that work

33
in many situations. A promising candidate for such a condition is residual finiteness:

Definition 3.5. A variety V is residually finite, if it contains (up to isomorphism) only finitely
many subdirectly irreducible algebras, which are all finite.

Recall from Universal Algebra 1 that an algebra is subdirectly irreducible, if it has a

non-trivial congruence that is contained in all other non-trivial congruences. We denote the
subdirectly irreducible algebras in V by VSI . We saw in Universal Algebra 1 that every algebra
A ∈ V can be written as a subdirect product of elements from VSI .
So if V is residually finite, the subdirectly irreducible elements VSI give us a description
of V by a finite amount of information. Park conjectured in his thesis that this can be used
to show the existence of a finite equational basis.

Conjecture 3.6 (Park’s conjecture ’75). Let A be a finite algebra, such that HSP(A) is
residually finite. Then A is finitely based.

Until now no counterexample to Park’s conjecture was found 1 and it is verified for algebras
A that additionally satisfy one of the following conditions:

1. HSP(A) is congruence distributive (Baker ’77),

2. HSP(A) is congruence modular (McKenzie ’87),
3. HSP(A) has a difference term (Kearnes, Szendrei, Willard ’15).

Without specifying what a difference term is, we remark that congruence modular varieties
always have a difference term. So (3) is the strongest known result up to date. Note also that
varieties with a Maltsev term are congruence modular, so by (2) Park’s conjecture holds for
all algebras A with a Maltsev term.
We are going to prove a result of McKenzie, which states that Park’s conjecture is true
for algebras with definable principal congruences (DPC). This result is not as strong as the
three results above, but nicely illustrates the core idea of the proofs.

Definition 3.7. A variety V has definable principal congruences (DPC) if there is a first-order
formula ϕ(u, v, x, y) such that for every A ∈ V and all a, b, c, d ∈ A:

(c, d) ∈ CgA (a, b) ⇔ A |= ϕ(c, d, a, b).

We then also say that ϕ defines principal congruences on V.

Having DPC is a relatively strong assumption on a variety. Here are a few examples and
non-examples:

Example 3.8.
1. The variety of commutative rings with a unit has DPC. For this recall that congruences
in rings A correspond to ideals; so (c, d) ∈ CgA (a, b) if and only if c − d lies in the
principle ideal generated by a − b. Thus ϕ(c, d, a, b) := ∃x(c − d = x · (a − b)) is
equivalent to (c, d) ∈ CgA (a, b).
1
You can win a price of 50 Euro from Ross Willard if you find one ;)

34
 2. For any positive integer n the variety An of Abelian groups of exponent n has DPC. In
this case (c, d) ∈ CgA (a, b) if and only if c − d lies in the cyclic subgroup generated by
a − b. Thus the formula

ϕn (c, d, a, b) := (c = d) ∨ (c − d = a − b) ∨ (c − d = 2 · (a − b)) ∨ · · · ∨ (c − d = n · (a − b))

is equivalent to (c, d) ∈ CgA (a, b).

3. On the other hand, the variety of all Abelian groups A does not have DPC.
Note that in any Abelian group A ∈ A we have (c, d) ∈ CgA (a, b) if and only if there
is an n such that ψn (c, d, a, b) := ϕn (c, d, a, b) ∨ ϕn (d, c, a, b) holds. But any individual
such formula is not strong enough to define principal congruences (for instance in Z,
ψn (2(n + 1), 0, 2, 0) does not hold, although 2(n + 1) is in the subgroup generated by 2).
Now for contradiction, assume that there is some formula ψ(c, d, a, b) that defines prin-
cipal congruences on A. Let c, d, a, b be some new constant symbols. By the above
paragraph, every finite subset of ψ(c, d, a, b) ∪ {¬ψn (c, d, a, b) : n ∈ N} is satisfiable
in an Abelian group extended by constant symbols c, d, a, b. By the compactness the-
orem of first-order logic, also ψ(c, d, a, b) ∪ {¬ψn (c, d, a, b) : n ∈ N} has a model. So
there is an Abelian group A with elements c, d, a, b ∈ A that satisfy ψ(c, d, a, b), but
/ CgA (a, b)
¬ψn (c, d, a, b) for every n ∈ N. But this implies that ψ(c, d, a, b) and (c, d) ∈
- contradiction!
4. The variety of distributive lattices has DPC (Exercise 3.5).
5. The variety of semilattices has DPC (Exercise 3.6).
6. If a variety has DPC, also all of its subvarieties have DPC (by the same formula).

Interestingly the formulas in Example 3.8 (1) and (2) do not contain universal quantifiers
∀ or negations ¬. Therefore they are preserved under homomorphisms. In fact it can be
proven that, whenever there is is a formula ϕ that defines principal congruences, then there
is also an equivalent formula ψ with the following properties:

1. If h : A → B is a homomorphism, then A |= ψ(c, d, a, b) implies B |= ψ(h(c), h(d), h(a), h(b)).

2. For every algebra A: A |= (ψ(u, v, x, x) → u = v).

Let us call a 4-ary formula ϕ nice 2 3 if it has the two above properties.

Lemma 3.9. Let V be a variety and suppose that ϕ(u, v, x, y) defines principal congruences
on V. Then, there is a nice formula ψ(u, v, x, y) such that V |= ϕ(u, v, x, y) ↔ ψ(u, v, x, y).

Proof idea. This lemma can be proven by a compactness argument, similar to the one in
Example 3.8 (3). We only give a short proof sketch here, and refer to Lemma 5.31. and 5.32.
in [2] for the interested readers.
The Maltsev chain lemma (see also Exercise 2.19) states that, for every algebra A ∈ V
and c, d, a, b ∈ A such that (c, d) ∈ Cg(a, b), there is a chain of elements c = z0 , z1 , . . . , zn = d,
and unary polynomials f0 , . . . , fn−1 , such that {zi , zi+1 } = {fi (a), fi (b)}. Every individual
2
In Bergman’s book [2] this is called a ’congruence formula’, which in my opinion is a misleading notation,
since not every nice formula defines congruences.
3
Update: Actually the name ’congruence formula’ makes some sense considering the properties shown in
Exercise 3.12, sorry about the confusion!

35
such chain can be described by a nice formula ψc,d,a,b (c, d, a, b). Now a compactness argument
similar to the one in Example 3.8 (3), shows that ϕ(u, v, x, y) needs to be equivalent to a finite
disjunction of formulas ψc,d,a,b modulo Id(V). Such a disjunction is also a nice formula.

On an arbitrary algebra, a nice formula ψ does not need to define principal congruences.
But we can describe the algebras, in which it does, by another first-order sentence:

Lemma 3.10. Suppose that ψ(u, v, x, y) is a nice formula (in a finite language). Then there
is a first-order formula αψ (x, y), such that A |= αψ (a, b) if and only if θa,b = {(c, d) ∈ A2 :
ψ(c, d, a, b)} is equal to Cg(a, b).

Proof. Let’s consider the following formulas:

1. ∀u : ψ(u, u, x, y)
2. ∀u, v : ψ(u, v, x, y) → ψ(v, u, x, y)
3. ∀u, v, w : ψ(u, v, x, y) ∧ ψ(v, w, x, y) → ψ(u, w, x, y)
4. for every n-ary function symbol f : ∀ū, v̄ ni=1 ψ(ui , vi , x, y) → ψ(f (ū), f (v̄), x, y)
V

5. ψ(x, y, x, y),
and let αψ (x, y) be the conjunction of all of them. If A |= αψ (a, b) then θa,b is an equivalence
relation by (1)-(3). By (4) it preserves all operation of A and is therefore also a congruence
of A. By (5) θa,b contains (a, b), and thus Cg(a, b) ⊆ θa,b .
To see the opposite inclusion, assume that (c, d) ∈ θa,b . Let B = A/ Cg(a, b) and h : A →
B be the quotient map. Since ψ is nice, it is preserved under homomorphisms, so B |=
ψ(h(c), h(d), h(a), h(b)). But h(a) = h(b) implies that h(c) = h(d) (because ψ is nice) and
therefore (c, d) ∈ Cg(a, b).

Theorem 3.11. Let V be a variety of finite type, and assume that V has DPC, and VSI is
(up to isomorphism) a finite set of finite algebras. Then V is finitely based.

Proof. Let {C1 , . . . Cn } be an enumeration of the elements of VSI . For every Ci there is a
first-order sentence γi such that A |= γi if and only if A is isomorphic to Ci (see also Exercise
3.7). So γ = γ1 ∨ · · · ∨ γn holds in A if and only if A is isomorphic to an element of VSI .
By Lemma 3.9 there is a nice formula ψ(u, v, x, y) defining principal congruences in V.
Then let α be the sentence ∀x, y αψ (x, y), where αψ is as in Lemma 3.10. An algebra satisfies
α, if and only if ψ defines principal congruences on it. Therefore every element of V satisfies
α.
Next let β be the sentence ∃u ̸= v∀x ̸= y(ψ(u, v, x, y)). If an algebra A satisfies α and β,
this implies that there exists u ̸= v ∈ A such that (u, v) ∈ CgA (x, y), for all pairs of distinct
x, y. In other words, CgA (u, v) is contained in all other non-trivial congruences of A, so A is
subdirectly irreducible.
By the above observations, all algebras in V satisfy the formula α ∧ (β ↔ γ). So Id(V) |=
α∧(β ↔ γ). By the compactness theorem of first order logic, there is a finite subset E ⊂ Id(V),
such that E |= α ∧ (β ↔ γ).
We claim that E is a finite basis of V. Clearly every element of V is in Mod(E). For the
opposite direction it is sufficient to show that the subdirectly irreducible elements of Mod(E)
are in VSI . But this follows from the fact that E |= α ∧ (β ↔ γ), so every subdirectly
irreducible algebra in Mod(E) needs to satisfy γ.

36
 Note that the proof of Theorem 3.11 is not constructive. So although Theorem 3.11 states
that some varieties are finitely bounded it gives us no method to find an explicit equational
basis.
Example 3.12. Let R be a finite commutative ring with a unit satisfying xn ≈ x. We saw
in Example 3.8 (1) that HSP(R) has definable principal congruences. On the other hand, we
know from Bergman’s book (see Theorem 3.28 in [2]) that the only subdirectly irreducible
rings satisfying xn ≈ x are the finite fields of size d such that d − 1 divides n − 1. There are
only finitely many such fields, so HSP(R) is finitely based by Theorem 3.11.
In the next section, we give a slight generalization of Theorem 3.11, and study the con-
gruence distributive case.

3.2 Congruence distributive varieties

In this section, we prove a result by Baker (1977), which states that every finitely generated
congruence distributive variety V = HSP(A) is finitely based. We are going to follow a more
recent proof by Baker and Wang (2002) that uses a similar argument as Theorem 3.11. We
are first going to show that V is residually finite, which follows from a special case of Jónsson’s
Lemma. To prove Jónsson’s Lemma, let us first recall the following fact from UA1:
Observation 3.13. Let A1 , . . . , An be finite algebras, and let B ∈ HSP(A1 , . . . , An ) be an
algebra with finitely many generators. Then B is finite.
Proof. Note that the variety HSP(A1 , . . . , An ) is already generated by a single finite algebra
(e.g. A = A1 ×· · ·×An ). Since B has a finite set of generators b1 , . . . , bk , it is a homomorphic
image of the free algebra FA (x1 , . . . , xk ); from UA1 we know however that FA (x1 , . . . , xk ) is
finite, hence also B is finite.

A self-contained proof of Observation 3.13 can also be found in Theorem 3.49 of [2].
Varieties, in which finitely generated algebras are finite are called locally finite. So, Observa-
tion 3.13 states that all finitely generated algebras are locally finite. Note however that the
converse is not true (Exercise 3.9).
Lemma 3.14 (Jónsson’s Lemma ’67). Let A1 , . . . , An , B be finite algebra such that
1. HSP(A1 , . . . , An ) is congruence distributive
2. B ∈ HSP(A1 , . . . , An )
3. B is subdirectly irreducible.
Then B ∈ H S(A1 , . . . , An )
Proof. Since B ∈ HSP(A1 , . . . , An ), without
Q loss of generality, B = C/α for some congruence
α ∈ Con(C), and a subalgebra C ≤ i∈I Di with Di ∈ {A1 , . . . , An } for every i ∈ I.
Without loss of generality we can assume that C is finite - otherwise we take a finite set
X ⊆ C, such that X contains elements of each α-block, and take C′ = SgC (X) instead of C.
By Observation 3.13, C′ is finite. Since it contains elements from all α-classes, B = C/α ∼ =
C′ /(α ↾C ′ ).
Note that B is subdirectly irreducible, if and only if α ∈ Con(A) is ∧-irreducible (i.e. it
cannot be written as the meet of two strictly bigger congruence). Let πi : C → Di be the

37
 V V
i-th projection, and ηi = ker(πi ). Then i∈I ηi = 0C , and thus α = α ∨ i∈I ηi . By the
congruence distributivity ^ ^
α=α∨ ηi = (α ∨ ηi ),
i∈I i∈I

and since α is ∧-irreducible, there must be a j ∈ I with α ∨ ηj = α, i.e. ηj ≤ α. Thus, by the

second isomorphism theorem:

B = C/α ∼
= (C/ηj )/(α/ηj ) ∼
= πj (C)/(α/ηj ) ∈ H S(Dj ),

which finishes the proof.

We remark that, for infinite algebras, also a generalized version of Lemma 3.14 holds that
constructs B via so called ultraproducts (see Section 5.2. in [2]; we are not going to discuss it
in this lecture). Note that Lemma 3.14 in particular implies that |B| is bounded by maxi |Ai |.
Thus HSP(A1 , . . . , An ) only contains finitely many finite subdirectly irreducible algebras.
In this case, surprisingly, there are also no infinite subdirectly irreducible algebras by a
result of Quackenbush (1972) (see e.g. Section 5.1 of [2]; we are not giving a proof here). As
a direct consequence of Lemma 3.14 and Quackenbush’s results we get:

Corollary 3.15. Let A be finite and V = HSP(A) be congruence distributive. Then V is

residually finite.

Together with Theorem 3.11, this already implies that A is finitely based, if HSP(A) is
congruence distributive and has DPC. This is for example true if A is a distributive lattice
(see Exercise 3.5). In general, however, congruence distributive varieties (and even varieties
of lattices) do not need to have DPC. However, we will see that they satisfy the following
generalization:

Definition 3.16. A variety V has definable principle subcongruences (DPSC), if there are
nice formulas ρ and ϕ such that for all B ∈ V, and all a, b ∈ B with a ̸= b, there are c, d ∈ B
with c ̸= d such that B |= ρ(c, d, a, b) and B |= αϕ (c, d).

DPSC is a bit mysterious; it says that, for every a ̸= b, there is a principal congruence
Cg(c, d) that is contained in Cg(a, b) that is defined by ϕ, and we can get from (a, b) to (c, d)
by ρ. Note that DPC implies DPSC by taking ρ = ϕ and c = a and d = b. Then the following
generalization of Theorem 3.11 holds:

Theorem 3.17. Let V be a variety with DPSC, such that VSI can be described by a first-order
formula. Then V is finitely based.

Proof. We leave the proof as an exercise (Exercise 3.10).

We can use Theorem 3.17 to prove Baker’s result:

Observation 3.18. Let (D,V ∧, ∨) be a complete distributive lattice, and α ∈ D be ∧-

irreducible. If we define β := {γ : γ ̸≤ α}, then
1. β ̸≤ α (i.e. β is the minimal element that is not smaller than α)
2. β is ∨-irreducible

38
Proof. Note that, for every γ ∈ D, γ ̸≤ α is equivalent to α ∨ γ > α. Thus we get
^ ^
α ∨ β = α ∨ ( {γ : γ ̸≤ ηm }) = {α ∨ γ : γ ̸≤ α}) > α,

where the last inequality follows from α being ∧-irreducible. Thus β ̸≤ α.

To see (2), note that by (1) β is the smallest element that is not smaller than α. Thus,for
all β1 , β2 < β, it follows that β1 , β2 ≤ α, and hence β1 ∨ β2 ≤ α. Thus β cannot be written
as the join of two properly smaller elements.

Theorem 3.19. Let A be a finite algebra such that V = HSP(A) is congruence distributive.
Then V is finitely based.

Proof. By Corollary 3.15, V is residually finite. So to check that the conditions of Theorem
3.17 are satisfies, it is only left to show that V has DPSC. Note that, since VSI ⊆ H S(A),
there is an integer n ∈ N that bounds the size of algebras in VSI .
In a variety generated by a finite algebra A, the free algebra FA (x1 , . . . , xk ) generated byk
many variables is also finite. Thus, for every k there is a nice formula ψk that defines principal
congruences in FA (x1 , . . . , xk ). As a consequence ψk also defines principal congruences in all
algebras in V with k or less generators. We claim that ρ = ψn and ϕ = ψn+2 witness that V
has DPSC.
Q B ∈ V, and a, b ∈ B elements with a ̸= b. We can write B as a subdirect product
So let
B ≤sd i∈I Si with Si ∈ VSI . Let πi : B → Si denote the projection of B onto Si . Since
a ̸= b, there is an index m, such that πm (a) ̸= πm (b). Without loss of generality let us pick
an m with this property, such that |Sm | is maximal.
We further pick a finite set X ⊂ B, such that X contains a, b and exactly one pre-image
for every element in Sm . Then |X| = |Sm | ≤ n. The subalgebra D = SgB (X) thus has at
most n generators. Since Sm is subdirectly irreducible, the congruence ηm = ker(πm |D ) is
∧-irreducible. V
We then define the congruence δ = {γ : γ ̸≤ ηm } in Con(D). By Observation 3.18,
also δ ̸≤ ηm is ∨-irreducible.
W (As every congruence), we can write δ as a join of principal
congruences δ = {Cg(e, f ) : (e, f ) ∈ δ}. But since δ is ∨-irreducible, there must be a
pair (c, d) such that δ = CgD (c, d). We claim that c ̸= d satisfy B |= ψn (c, d, a, b) and
B |= αψn+2 (c, d).
For the first part, note that D |= ψn (c, d, a, b) holds, since D has at most n generators,
and thus ψn defines principal congruences. Since ψn is a nice formula (and thus preserved
under the natural embedding B ≤ D), also B |= ψn (c, d, a, b).
To see that B |= αψn+2 (c, d), we need to prove that, for any pair (r, s) ∈ CgB (c, d) also
B |= ψn+2 (r, s, c, d) holds. Note that B is in general not generated by n + 2 or less elements.
But this is true for the subalgebra C = Sg(X ∪ {r, s}). Hence it is enough to show that
(r, s) ∈ CgC (c, d); then, by the properties of ψn+2 we get C |= ψn+2 (r, s, c, d), and (by
niceness) B |= ψn+2 (r, s, c, d).
For this, observe that (πi (r), πi (s)) ∈ Cgπi (C) (πi (c), πi (d)) for all i ∈ I:
• If πi (c) = πi (d), then CgB (π(c), π(d)) ⊆ ker πi and thus πi (a) = πi (b). In particular
this implies (πi (r), πi (s)) ∈ Cgπi (C) (πi (c), πi (d)).
• If πi (c) ̸= πi (d), then δ ̸≤ ηi (note that now we are talking about congruences of D). By
definition of δ, this can however only happen, if ηi ≤ ηm . Thus there exists a surjective
homomorphism from D/ηi ≤ Si to D/ηm = Sm , and thus |Si | ≥ |D/ηi | ≥ |Sm |. But,

39
 since |Sm | is maximal, we get that D/ηi must actually be equal to Si (and isomorphic
to Sm ). Since C contains D, we get that πi (C) = Si = πi (B). Thus (r, s) ∈ CgB (c, d)
implies (π(r), π(s)) ∈ Cgπi (B) (π(c), π(d)) = Cgπi (C) (π(c), π(d)).
It is not hard to see (compare with UA1) that πi−1 (Cgπi (C)) (π(c), π(d))) = CgC (c, d) ∨
−1 πi (C)
V πi |Ci ). By the above, (r, s) ∈ π (Cg
(ker (π(c), π(d))) for every i ∈ I. Furthermore
i∈I (ker πi |Ci ) = 0C ; together, with the congruence distributivity of V, this implies (r, s) ∈
CgC (c, d), which is what we wanted to prove.

3.3 Exercises
Exercise 3.1. (*) Try to prove the statements in Example 3.1 (showing (3)→(1) or (2)→(1)
is quite challenging... So don’t worry, if you don’t manage to prove it).
Exercise 3.2. Let A and A′ be two algebras in finite type with Clo(A) = Clo(A′ ). Show
that then A is finitely based if and only if A′ is finitely based. Is this still true if we don’t
assume finite type?
Exercise 3.3. Try to prove the following (using the compactness theorem): If V is finitely
based, every basis of V contains a finite subset that is already a basis.
Exercise 3.4. For any directed graph G = (V, E), we can define a binary algebra A =
(V ∪ {u}, ·) as in Example 3.4. Does HSP(A) then contain the algebras corresponding to
• (induced) subgraphs of G?
• powers of G?
• homomorphic images of G?
(This and other versions of ’graph algebras’ are often used to construct interesting examples
in UA - see https://en.wikipedia.org/wiki/Graph_algebra)
Exercise 3.5. Let L be a distributive lattice. Prove that (c, d) ∈ CgL (a, b) if and only if

c ∧ (a ∧ b) = d ∧ (a ∧ b) and c ∨ (a ∨ b) = d ∨ (a ∨ b).

Thus the variety of distributive lattice has DPC.

Exercise 3.6. Prove that the variety of semilattices has DPC.
Exercise 3.7. In the proof of Theorem 3.11 we use that, for every finite algebra C there is a
first-order formula γ such that B |= γ if and only if B is isomorphic to C. Take a moment to
think why this is true (Hint: up to isomorphism C is determined by having exactly |C|-many
distinct elements, and its operation tables).
Exercise 3.8. Let A be a finite nilpotent algebra with Maltsev term. Show that HSP(A) is
residually finite, if and only if A is Abelian (use Theorem 2.21).
Exercise 3.9. Find a variety that is locally finite, but not finitely generated.
Exercise 3.10. Try to prove Theorem 3.17, by generalizing Theorem 3.11. Does it make a
difference that VSI is not finite, but only definable by a single formula γ? Which formulas
can be used instead of the α and β in the proof of Theorem 3.11?

40
Exercise 3.11 (Perkins ’68). Let V be the variety of semigroups satisfying the identities
xyzw ≈ xzyw and yxk y ≈ xyxk−2 yx for all k = 2, 3, . . .. Show that V is not finitely based.

Hint: Use that in semigroups E ⊢ s ≈ t if and only if there is a sequence of identities

Mi si Ni ≈ Mi ti Ni for i = 1, . . . , n such that
1. Mi , Ni are (possibly empty) products of variables
2. Either si ≈ ti or ti ≈ si is equal to some substitution (θl, θr), for a (l, r) ∈ E
3. M1 s1 N1 = s
4. Mn tn Nn = t
5. for each i = 1, . . . , n − 1: Mi si Ni = Mi+1 ti+1 Ni+1 .

Exercise 3.12. Assume that ψ(x, y, u, v) is a nice formula (i.e. it is preserved by homomor-
phisms and ψ(x, y, u, u) implies x = y). Show that for an algebra A and a, b, c, d ∈ A:

A |= ψ(c, d, a, b) ⇒ (c, d) ∈ CgA (a, b),

but that the opposite implication does not need to hold.

41
Chapter 4

CSPs and Maltsev conditions

4.1 Constraint satisfaction problems (CSP)

Constraint satisfaction problems (short CSPs) are a broad class of computational problems
that have many theoretical and real-life applications. Because of this CSPs are an impor-
tant research topic in computer science (in particular in artificial intelligence and operations
research).
But CSPs also had a major impact on universal algebra in the last two decades, and
lead to many new results in the study of Maltsev conditions. In this section we define CSPs
over a fixed relational structure, illustrate them by some basic examples, and discuss how the
Pol − Inv Galois-connection can be used in studying the complexity of CSPs.
Definition 4.1. A relational structure A = (A; R1 , . . . , Rt ) consists of a set A and a family
of relations Ri ⊆ Aki on it. We are only going to study finite relational structures, so A will
always have a finite domain A, and finitely many relations R1 , . . . , Rt .
A primitive positive sentence (or pp-sentence) over A is a first order sentence that can be
constructed using the relations of A, equality =, conjunctions ∧ and existential quantification
∃ (for example ∃x, y, z R1 (x) ∧ R2 (y, x, x) ∧ R2 (z, z, y)).
Now the constraint satisfaction problem CSP(A) of a relational structure A is defined as:

CSP(A)
Input: A primitive positive sentence ϕ over A.
Question: Is ϕ true in A?

A lot of important computational problems fit this framework:

Example 4.2. 3-COLOR is the computational problem, where the input is a finite graph
(V, E), and the question is if it can be colored by 3 colors (so if there is a map c : V →
{1, 2, 3} such that for every edge (x, y) ∈ E we have c(x) ̸= c(y)). This problem is equal to
CSP(({1, 2, 3}; ̸=)).
To illustrate this consider for example the following graph:

x y

u v

42
 This graph is 3-colorable if and only if the pp-sentence ∃x, y, u, v (x ̸= y) ∧ (x ̸= u) ∧ (y ̸=
v) ∧ (u ̸= v) is satisfied in {1, 2, 3}; here the values of the variables x, y, u, v correspond to
the colors of the vertices; the constraints (x ̸= y), (x ̸= u), . . . describe the condition that two
connected vertices have different colors.

Example 4.3. In 3-SAT the input is a Boolean formula ϕ, given as conjunction of 3-clauses
(for example (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x2 ∨ ¬x4 ∨ x1 ) ∧ (x1 ∨ x3 ∨ x3 )). The question then is if ϕ is
satisfiable in {0, 1}.
Note that every 3-clause can be modelled by a ternary relation on {0, 1} (for example
x1 ∨ ¬x2 ∨ x3 is equivalent to (x1 , x2 , x3 ) ∈ {0, 1}3 \ {(0, 1, 0)}). Therefore 3-SAT is equivalent
to CSP(({0, 1}; R000 , R001 , R011 , R111 )), where Rijk = {0, 1}3 \ {(i, j, k)}.

Example 4.4. Let p be a fixed prime. 3-LIN-p is defined as the problem whose input is a
system of linear equations over Zp , such that each equation contains at most 3 variables. The
question is: Does this system have a solution or not?
3-LIN-p can be modelled by CSP(Zp ; (Rā )ā∈Z4p ), where Rā is a ternary relation defined by
Rā (x, y, z) ⇔ a1 x + a2 y + a3 z = a4 , for every ā = (a1 , a2 , a3 , a4 ).

We remark that there are many related problems (finding explicit solutions to some input,
counting the number of solutions, finding ’approximations’ to solutions, infinite domain CSP,
promise CSPs, etc.) that the CSP community is studying. But we are only going to focus on
’classical’ CSPs here.
Then the question is: What is the computational complexity of CSP(A) for a given
A? We are primarily interested in two complexity classes:
• P: problems that can be solved in polynomial time (with respect to the input size). This
includes 3-LIN-p in Example 4.4, since any system of linear equations can be solved by
Gaussian elimination in polynomial time. Problems in P are usually considered to be
computationally ’easy’.
• NP: problems, for which solutions can be verified in polynomial time. 3-COLOR in
Example 4.2 is in NP, since for every map c : V → {1, 2, 3} we can check in polynomial
time, if it indeed is a 3-coloring of the graph.
Actually for every finite relational structure A, CSP(A) ∈ NP, since it only takes polyno-
mial time to check, if an assignment of values ot the variables is a solution. Now P ⊆ NP, and
it is widely believed that this is a proper inclusion. So a major goal in studying CSPs is (or
was) to classify which of them are in P (and therefore ’easy’), and which are not (assuming
that P ̸= NP).
There is a natural way of comparing the complexity of two problems. We say that a
problem S reduces to a problem Q in polynomial time (and write S ≤p Q), if there is a
polynomial time algorithm that transforms an input I of S in polynomial time to an input
IQ of Q, such that I is a YES-instance of S if and only if IQ is a YES-instance of Q.
Finally, a problem Q is called NP-complete, if Q ∈ NP, and S ≤p Q holds for every other
problem S ∈ NP. So NP-complete problems are, in some sense, the ’hardest’ problem in NP.
1

1
The definitions of P, NP and NP-completeness can be made more precise using Turing machines, as most
of you probably know from some introduction to theoretical computer science / complexity theory. But for
our purposes this is not necessary.

43
 3-SAT and 3-COLOR are well-known examples of NP-complete problems. Starting from
the beginning of CSP research it was observed that all studied examples of CSPs are either
in P (like 3-LIN-p) or NP-complete (like 3-SAT):
• In 1978 Schaefer gave a full classification of structure A with |A| = 2 and showed that
CSP(A) is either in P or NP-complete.
• In 1990 Hell and Nešetřil showed that for all undirected graphs A, CSP(A) is either in
P or NP-complete.
These observations lead to the conjecture of Feder and Vardi (in 1993) that CSP(A) is
always either in P or NP-complete.
But what does universal algebra have to do with all this? In 1998 Jeavons observed that
the clone of polymorphisms of A, Pol(A) actually determines the complexity of CSP(A). This
lead to conjectures about algebraic conditions on Pol(A) that separate the problems in P or
NP-complete (around 2000), followed by many partial results on CSPs and many new results
in universal algebra (also by Libor and members of our group). Ultimately two proofs of the
conjecture were given by Bulatov [7] and Zhuk [6] in 2017.

In the following we discuss the very basic of this ’universal algebraic approach’ to CSPs.
Observation 4.5. Let A = (A; R1 , . . . , Rn ) and B = (A; S1 , . . . , Sk ) be two structures on
the same set A, and assume that every relation of B is pp-definable from A. So every Si
can be defined using relation of A, conjunctions and existential quantifiers. Then CSP(B) ≤p
CSP(A).
Proof. To see this it is enough to see that every instance of CSP(B) can be turned into an
equivalent instance of CSP(A) by substituting every constraint Si by its definition.

Example 4.6. In the structure ({0, 1}; R000 , R001 , R011 , R111 ) in Example 4.3 we can pp-
define the unary relation C0 = {0} by the formula C0 (x) :⇔ R111 (x, x, x); also XOR =
{(0, 1), (1, 0)} has a pp-definition by XOR(x, y) :⇔ R000 (x, y, y) ∧ R111 (x, y, y), or alterna-
tively XOR(x, y) :⇔ ∃a, b : R000 (x, y, a)∧R111 (x, y, b)∧C0 (a)∧C1 (b). In fact, it can be shown
that every relation on the two element set has a pp-definition (maybe you already know this
by some logic or CS lecture).
Observation 4.5 allows to compare CSPs, and was already used by Schaefer to prove
his result on 2-element CSPs. But this is not very deep in itself. As it turns out, the
reductions from Observation 4.5 have an algebraic counterpart. Let recall the definition of
polymorphisms from Universal Algebra 1:
Definition 4.7. A function f : An → A preserves a relation R ⊆ Ak , if for all tuples
r̄1 , . . . , r̄n ∈ R, also f (r̄1 , . . . , r̄n ) ∈ R. Here f (r̄1 , . . . , r̄n ) is computed row-wise, so:
       
r11 r21 rn1 f (r11 , r21 , . . . , rn1 )
r12  r22  rn2   f (r12 , r22 , . . . , rn2 ) 
 ..  ,  ..  , . . . ,  ..  ∈ R ⇒  ∈R
       
..
 .   .   .   . 
r1k r2k rnk f (r1k , r2k , . . . , rnk )
An operation f : An → A is called a polymorphism of A, if it preserves all the relations of
A. The set of all polymorphisms forms a clone, which is denoted by Pol(A).

44
 The relations that are preserved under some set of operations F are also called invariant
relations Inv(F). As discussed in Universal Algebra 1, Pol and Inv forms a Galois connection
between operations and relations on a set A. The Galois-closed subsets of operations are the
(polymorphism) clones. We are going to prove that the Galois-closure on the relational side
corresponds exactly to the pp-definable relations:

Proposition 4.8. Let A = (A; R1 , . . . , Rt ) be a finite structure, and S ⊆ Ak . Then S is

preserved by Pol(A) if and only if S is pp-definable in A.

Proof. It is easy to see that pp-definable relations of A are preserved by Pol(A).

For the opposite direction assume that S is invariant under Pol(A). Let S = {ā1 , . . . āl } ⊆
Ak so that ā1 , . . . āl are the column vectors of the following matrix:
 
a11 a21 · · · al1
a12 a22 · · · al2 
 
 .. .. .. 
 . . . 
a1k a2k · · · alk
Without loss of generality we can assume that this matrix has no duplicate rows (if
for instance the first and second row are equal, then S(x1 , x2 , x3 , . . . , xk ) is equivalent to
S ′ (x1 , x3 , . . . , xk ) ∧ x1 = x2 , for an invariant relation S ′ ).
Next, we extend this matrix in a way, such that the rows enumerate all tuples in Al :
 
a11 a21 · · · al1
 a12 a22 · · · al2 
 
 .. .. .. 
 . . . 
 
 a1k a2k · · · alk 
 
 .. .. .. 
 . . . 
a1m a2m · · · alm
with m = |A|l . Let then ā+ + + +
1 , . . . , āl the resulting column vectors and Q = {f (ā1 , . . . , āl ) : f ∈
Pol(A)}. We claim that Q has a pp-definition in A. If we can prove this claim, then also S is
pp-definable in in A, since S is the projection of Q to the first k coordinates; in other words
S(x1 , . . . , xk ) is equivalent to ∃xk+1 , . . . , xm Q(x1 , . . . , xk , xk+1 , . . . , xm ).
To prove the claim, note first that whenever we have a tuple b̄ ∈ Am , there is a unique
map f : Al → A with f (ā+ +
1 , . . . , āl ) = b̄. This follows from the fact that the rows of the
above matrix enumerate Al . In particular, the elements of Q exactly correspond to the l-ary
polymorphisms of A.
Let ϕ(x1 , . . . , xm ) be the conjunction of all atomic formulas that hold for all tuples ā+ i .
(For instance, if R1 (ai1 , ai3 , ai1 ) holds for every i = 1, . . . , l, then R1 (x1 , x3 , x1 ) is part of the
conjunction ϕ.)
We are going to show that ϕ is a pp-definition of Q. It is easy to see that every tu-
ple in Q satisfies ϕ. For the opposite direction, assume b̄ satisfies ϕ. Since the rows of
ā+ + l l +
1 , . . . , āl enumerate A , there is a unique map f : A → A, such that f (ā1 , . . . , āl ) = b̄.
+

By definition of ϕ, f preserves all relations of A. So f is a polymorphism of A and therefore

b̄ = f (ā+ +
1 , . . . , āl ) ∈ Q.

Proposition 4.8 together with Observation 4.5 now directly implies:

45
Corollary 4.9. Let A and B be finite structures such that Pol(A) ⊆ Pol(B). Then B is
pp-definable in A, and therefore CSP(B) reduces to CSP(A).

So structures with small polymorphism clones have computationally hard CSPs. As an

immediate consequence we get the following corollary:

Corollary 4.10. Let A be a relational structure such that |A| ≥ 2, and Pol(A) consists only
of projections. Then CSP(A) is NP-complete.

Proof. For every other relational structure B with the same domain A, we have that Pol(A) ⊆
Pol(B). By Proposition 4.8, B is pp-definable in A, and therefore CSP(B) reduces to CSP(A).
Since there is a B with NP-complete CSP, also CSP(A) needs to be NP-complete.

More generally we can ask: How small does the polymorphism clone of A need to be, such
that CSP(A) is NP-complete? Is the only possible reason that Pol(A) is the projection clone?
The answer to this question is NO: In the example of 3-COLOR, Pol({1, 2, 3}, ̸=) does not
only consist of projections, since all the permutations of {1, 2, 3} are unary polymorphisms of
({1, 2, 3}, ̸=).
Next time we are going to discuss, which other algebraic conditions imply NP-completeness,
and lead to the algebraic dichotomy conjecture.

4.2 Clone and minion homomorphisms

We saw in the last section, that CSP(B) reduces to CSP(A) if Pol(A) ⊆ Pol(B). This allowed
us to compare the complexity of CSPs on the same set. There are some more general re-
ductions between CSPs on (possibly) different sets, that correspond to special maps between
Pol(A) and Pol(B), namely clone and and minion homomorphisms. We introduce clone and
and minion homomorphisms in this section.

Recall from UA1 that a clone A is a set of operations on a set A, such that
• A contains all projections πin : An → A
defined by πin (x1 , . . . , xn ) = xi , for all 1 ≤ i ≤ n
• A is closed under composition. So if g ∈ A is n-ary, f1 , . . . , fn ∈ A , then also
g ◦ (f1 , . . . , fn ) ∈ A , where g ◦ (f1 , . . . , fn ) is defined by

g ◦ (f1 , . . . , fn )(x1 , . . . , xm ) = g(f1 (x1 , . . . , xm ), . . . , fn (x1 , . . . , xm )).

For every algebra A, the set of its term operation Clo(A) forms a clone. The polymor-
phisms Pol(A) of a relational structure A also naturally form a clone.
Clone homomorphisms are defined as follows:

Definition 4.11. Let A , B be clones. A map ξ : A → B is called a clone homomorphism if

1. ξ(f ) has the same arity as f , for every f ∈ A ,
2. ξ(πin ) = πin for all projections 2

2
Here we are lazy with notation, and do not distinguish between projections on different sets.

46
 3. ξ preserves compositions:

ξ(g ◦ (f1 , . . . , fn )) = ξ(g) ◦ (ξ(f1 ), . . . , ξ(fn )).

Let us write A ≤ B if there is a clone homomorphism ξ : A → B, and A ∼ B if A ≤ B ≤

A.

Note that a clone homomorphism is a map from the operations in A to the operations in
B; this definition does not mention the universes of A or B at all. So clone homomorphisms
should not be confused with homomorphisms between algebras.

Observation 4.12. By definition, clone homomorphisms preserve arbitrary compositions of

functions in A . Let for instance f, g ∈ A and h(x, y) = f (g(x, y, x), x), which is equivalent
to h = f ◦ (g ◦ (π12 , π22 , π12 ), π12 ). If ξ : A → B is a clone homomorphism, then ξ(h) =
ξ(f ) ◦ (ξ(g) ◦ (π12 , π22 , π12 ), π12 ); or in other words ξ(h)(x, y) = ξ(f )(ξ(g)(x, y, x), x) in B.

Observation 4.13. Clone homomorphisms preserve identities. For example, let ξ : A → B

be a clone homomorphism and assume that A has a Maltsev operation. So there is an m ∈ A ,
such that x ≈ m(x, y, y) ≈ m(y, y, x) for all x, y ∈ A. Since ξ is a clone homomorphism, also
ξ(m)(x, y, y) ≈ ξ(m)(y, y, x) ≈ x for all x, y ∈ B. So if A has a Maltsev operation, then also
B has one.

By Observation 4.13, clone homomorphisms are exactly those maps between clones that
preserve identities. Therefore A ≤ B holds if and only if all the identities that hold in A hold
also in B. Note also, that we use ’identities’ here in a different way than for algebras, since
clones do not have a fixed similarity type. (So we say A satisfies x ≈ m(x, y, y) ≈ m(y, y, x)
if there is a m ∈ A such that for all x, y ∈ A: x = m(x, y, y) = m(y, y, x)). If A = Clo(A) is
the term clone of some algebra, these ’identities’ are also called Maltsev conditions on A (for
instance it is a Maltsev condition on A to have a Maltsev term) 3 .
Modulo the equivalence ∼, the relation ≤ is a partial order. In fact, it is even a lattice
order, which is called the interpretability lattice. The minimal element in this lattice is the
equivalence class given by clone of projections on a two element set (see Exercise 4.11). We
write Proj for this particular clone.
There are some natural examples of clone homomorphisms:

Example 4.14.
1. If A ⊆ B, then the inclusion map ξ(f ) = f is a clone homomorphism. We then write
B ∈ E(A ).
2. Let A be an algebra, and A = Clo(A) its term clone. Let B ≤ A, and B = Clo(B).
Then the map ξ : A → B which maps t ∈ A to its restriction t|B ∈ B is a clone
homomorphism. In this case we write B ∈ S(A ).
3. Let A be an algebra, A = Clo(A) and B = Clo(An ) for some n. Then the map
n
ξ : tA → tA is a clone homomorphism. In this case we write B ∈ P(A ).
4. Let A be an algebra, and B be a homomorphic image of A. Then the map ξ : tA → tB
is a clone homomorphism from A = Clo(A) to B = Clo(B). In this case we write
B ∈ H(A ).
3
Unfortunately mathematicians are sometimes a bit uncreative in naming things

47
 Take a moment to think why the maps in Example 4.14 are indeed clone homomorphisms.
The clone homomorphisms described in 2,3,4 correspond to closing algebras under HSP. This
is not a coincidence! In fact, every clone homomorphism can be constructed as a composition
of the clone homomorphisms described in Example 4.14, by the following version of Birkhoff’s
theorem:

Theorem 4.15 (Birkhoff’s HSP theorem for clones). Let A , B be two clones. Then the
following are equivalent:
1. A ≤ B
2. B ∈ EHSP(A )

Proof. We already saw that (2) implies (1) in Example 4.14.

For the opposite direction, assume that ξ : A → B is a clone homomorphism. Note that
B is an extension of ξ(A ). So without loss of generality we can assume that B = ξ(A ); we
are then going to prove that B ∈ HSP(A ).
For this, let A be an algebra such that A = Clo(A); we can find such an A, by simply
fixing an enumeration f1 , f2 , . . . of all elements of A and setting A = (A; f1 , f2 , . . .). We
further define the algebra B = (B; ξ(f1 ), ξ(f2 ), . . .), its term clone is equal to B. We saw
in Observation 4.13 that clone homomorphisms preserve identities. Therefore B satisfies the
same identities as A. By Birkhoff’s theorem B ∈ HSP(A); and therefore B ∈ HSP(A ).

How is this relevant to the study of finite CSPs? Corollary 4.9 states that Pol(B) ∈
E(Pol(A)) implies that B is pp-definable in A, and therefore CSP(B) ≤ CSP(A). More
generally it is possible to show that Pol(B) ∈ EHSP(Pol(A)), if and only if there is a so-called
pp-interpretation of B in A, which again implies that CSP(B) reduces to CSP(A) 4 . We
summarize:

Proposition 4.16. Let A, B be finite structures with Pol(B) ≤ Pol(A). Then CSP(A) reduces
to CSP(B) in polynomial time.

In particular, it follows that

• CSP(A) is NP-complete if Pol(A) ≤ Proj
• the complexity of CSP(A) only depends on the identities holding in Pol(A).
We already saw an Example of this principle in Exercise 4.3. The statement there
can in fact be generalized to the following: If Pol(A) satisfies the identities g(x, g(y, z)) ≈
g(g(x, y), z), g(x, y) ≈ g(y, x) and g(x, x) ≈ x, then CSP(A) ∈ P-
We give another example: Let A be a relational structure, such that there is a constant
polymorphism f ∈ Pol(A). Note that f is constant if and only if it satisfies f (x) ≈ f (y). Let
c be the image of f . Note that every non-empty relation in A contains the tuple (c, c, . . . , c).
This implies that every instance of CSP(A), which does not contain empty relations, has
(c, c, . . . , c) as a solution. Therefore CSP(A) ∈ P.
Identities that are satisfied by the projections are called trivial, since they hold in every
clone (every clone contains the projections). Both, the semilattice identities and the identities
f (x) ≈ f (y) are not satisfied by projections. We therefore call them non-trivial.
4
think of pp-interpretations as pp-definitions boosted by HSP. We are not defining pp-interpretations here
and refer to [8] for the interested reader

48
 So all CSPs such that Pol(A) satisfies only trivial identities are NP-complete. And one
might conjecture that non-trivial identities implied that CSP(A) is in P . However we need
to be careful about this, since actually some other natural reductions do not preserve all
identities (see Exercise 4.6, 4.7, 4.8).
There is an even more general concept, called a minion homomorphism, that preserves
the complexity of CPSs. Minion homomorphisms are those maps that preserve identities of
height 1. That is, identities of two expressions that contain exactly one operation symbol on
each side.

Example 4.17.
• t(x, y) ≈ s(x, y, x) is a height 1 identity.
• t(t(x, y), z) ≈ t(x, t(y, z)) is not of height 1.
• x ≈ m(x, y, y) ≈ m(y, y, x) is not of height 1 (because x contains no operation symbol).
• m(x, x, x) ≈ m(x, y, y) ≈ m(y, y, x) is of height 1.

Definition 4.18. A map ξ : A → B is called a minion homomorphism if

• it preserves arities
• for all operation f ∈ A , and projections πin1 , . . . , πinm :

ξ(f ◦ (πin1 , . . . , πinm )) = ξ(f ) ◦ (πin1 , . . . , πinm )

We write A ≤h1 B if there is a minion homomorphism from A to B.

So minion homomorphisms are a weakening of clone homomorphisms, in which only h1

identities need to be preserved. Note that because of this, the image of a minion homomor-
phism does not need to be a clone. Without a proof we state the following result:

Theorem 4.19. Let B and A be finite structures, and assume there is a minion homomor-
phism from Pol(B) to Pol(A). Then CSP(A) reduces to CSP(B).

So the complexity of CSP(A) depends only on the identities of height 1 that hold in
Pol(A). If there is a minion homomorphism Pol(A) → Proj, then CSP(A) is NP-complete.
And, as Bulatov and Zhuk showed, in the other case CSP(A) is in P.
Next time we are going to give a characterization by Taylor of the non-trivial h1 identities
that hold, if Pol(A) ≤h1 Proj.

4.3 Taylor operations

A clone A is called idempotent if all t ∈ A satisfy t(x, x, . . . , x) ≈ x. In the last section we
discussed how clone homomorphism, and more general, minion homomorphisms correspond
to typical reductions between CSPs. Using such reductions it can be shown that it is enough
to study CSPs with idempotent polymorphism clone.

Lemma 4.20 (without proof). Let A be a finite structure. Then there exists another finite
structure A′ , such that Pol(A) ≤h1 Pol(A′ ) ≤h1 Pol(A), and Pol(A′ ) is idempotent.

49
 So by Lemma 4.20, every CSP is equivalent to the CSP of a structure with idempo-
tent polymorphism clone. This, together with the reductions from last section, lead to the
followings algebraic version of the CSP dichotomy conjecture / now theorem:

Theorem 4.21 (algebraic dichotomy conjecture from ∼2000; proved in [6], [7]). Let A be a
finite structure such that Pol(A) is idempotent. Then either
1. Pol(A) ≤ Proj and CSP(A) is NP-complete, or
2. Pol(A) ̸≤ Proj and CSP(A) is in P.

As we know Pol(A) ≤ Proj implies that CSP(A) is NP-complete. Thus, the really hard
part in proving the conjecture was to show the second case: How can Pol(A) ̸≤ Proj be used
to find a polynomial time algorithm for CSP(A)?
We already saw some examples of how non-trivial identities (semi-lattice operations and
constant operations) can be used to obtain algorithms for the corresponding CSP. So an
important question was: can we characterize all clones in Case 2 of Theorem 4.21 by some
concrete identities? The surprising answer is yes; a first such result was obtained by Walter
Taylor (already long before the study of CSPs).

Definition 4.22. Let t be an idempotent operation (of some arity n). We then call t a Taylor
operation, if it satisfies (n many) h1 identities of the form:

t(x, ∗, ∗, . . . , ∗) ≈ t(y, ∗, ∗, . . . , ∗)
t(∗, x, ∗, . . . , ∗) ≈ t(∗, y, ∗, . . . , ∗)
..
.
t(∗, ∗, ∗, . . . , x) ≈ t(∗, ∗, ∗, . . . , y)

Here, all positions marked by ∗ stand for arbitrary variables.

Example 4.23. 1. Every Maltsev operation m is a Taylor operation, since it is idempotent

and satisfies the identities

m(x, x, y) ≈ m(y, x, x)
m(y, x, x) ≈ m(y, y, y)
m(y, x, x) ≈ m(x, x, y)

2. A (ternary) majority operation m satisfies the identities m(y, x, x) ≈ m(x, y, x) ≈

m(x, x, y) ≈ x, and is therefore also a Taylor operation.
3. Every operation c satisfy c(x1 , x2 , . . . , xn ) ≈ c(x2 , x3 , . . . , xn , x1 ) is Taylor. Such c is
called an n-ary cyclic operation.
4. A 6-ary Siggers operation s satisfies the identity s(x, y, x, z, y, z) ≈ s(y, x, z, x, z, y) and
is therefore also Taylor.

Note that, whenever a clone has a Taylor term, this can be witnessed by identities in
variables x and y alone (since otherwise we can substitute the variables appearing at the
∗-positions by x ans y’s). By the following theorem, a clone is in Case 2 of Theorem 4.21 if
and only if it has a Taylor operation:

50
Theorem 4.24 (Walter Taylor ’77). Let A be an idempotent clone. Then the following are
equivalent:
1. A ̸≤ Proj,
2. A ̸≤h1 Proj,
3. There is a Taylor operation t ∈ A .

Note that Taylor’s theorem even holds if the universe of the clone is not finite. We are
going to prove it in the remaining part of this section.

(2)→(1) holds, since every clone homomorphism is also a minion homomorphism. For
(3)→(2) note that, if there was a minion homomorphism ξ : A → Proj then it would map
the Taylor operation t to a projection ξ(t)(x1 , . . . , xn ) = xi . Since t is Taylor it satisfies an
identity t(∗, . . . , x, . . . , ∗) ≈ t(∗, . . . , y, . . . , ∗), where x and y are on the i-th position. Since
ξ is a minion homomorphism, it preserve this identity, and thus x = ξ(t)(∗, . . . , x, . . . , ∗) ≈
ξ(t)(∗, . . . , y, . . . , ∗) = y, which is a contradiction!

In order to prove (1)→(2)→(3), we need to do some more work, and use the assumption
that A is idempotent (Theorem 4.24 does not hold for non-idempotent clones, see Exercise
4.9).
We define minors, which help us to discuss identities of height 1:

Definition 4.25. Let g an n-ary operation, and α : [n] → [k] be a map. Then the minor g α
is defined as the k-ary operation g α (x1 , . . . , xk ) = g(xα(1) , xα(2) , . . . , xα(n) ). For example, if
α : [3] → [4] such that α(1) = α(2) = 1, and α(3) = 4, then g α (x1 , x2 , x3 , x4 ) = g(x1 , x1 , x4 ).

Observation 4.26. 1. Condition 2 in Definition 4.18 is equivalent to the statement that

for all g ∈ A and all suitable maps α: ξ(g α ) = (ξ(g))α . So minion homomorphisms are
maps that preserve arities of functions and minors.
2. If g is n-ary, α : [n] → [m] and β : [m] → [k], then (g α )β = g β◦α
3. The identities of height 1 are exactly the identities of the form f α ≈ g β .
4. In particular, an n-ary idempotent operation t is Taylor, if for every i = 1, . . . , n there
are maps α, β : [n] → [2] such that tα = tβ and α(i) ̸= β(i).

Another construction that often appears when working with idempotent clones or algebras
is the following:

Definition 4.27. Let f : An → A and g : Am → A. Then we define the ”star product”

f ∗ g : Anm → A by

f ∗ g(x1 , . . . , xnm ) = f (g(x1 , . . . , xm ), g(xm+1 , . . . , x2m ), . . . , g(x(n−1)m+1 , . . . , xnm )).

In idempotent clones we can use the the star product to encode multiple operations as
the minors of a bigger one, by the following lemma:

Lemma 4.28. Let T be a finite set of idempotent operations of A. Then there is a t ∈ Clo(T )
such that for every f ∈ T , there is a map α with f = tα .

51
Proof. If T = {f }, the lemma is clearly true with t = f .
For a 2-element set T = {f, g}, we define t = f ∗ g. Since f and g are idempotent:

f (g(x1 , x1 . . . , x1 ), g(x2 , . . . , x2 ), . . . , g(xn . . . , xn )) = f (x1 , x2 , . . . , xn ). (4.1)

f (g(x1 , x2 . . . , xm ), g(x1 , . . . , xm ), . . . , g(x1 . . . , xm )) = g(x1 , x2 , . . . , xm ). (4.2)

Clearly both expressions on the left side are minors of t. For a general finite set T =
{f1 , . . . , fn }, the term t = f1 ∗ (f2 ∗ (f3 ∗ · · · fn )) has the desired property. This can be
shown by induction on n, and the same argument as for |n| = 2.

Using the same construction, we can prove that minion homomorphism from an idempo-
tent clone to the projections need to preserve the star product.

Lemma 4.29. Let A be idempotent, and let ξ : A → Proj be a minion homomorphism. Then
ξ(f ∗ g) = ξ(f ) ∗ ξ(g), for all f, g ∈ A .

Proof. Since ξ maps A to the projection clone, there are projections πin , πjm , πkmn , such
that ξ(f ) = πin , ξ(g) = πjm and ξ(f ∗ g) = πknm . By definition of the star product we have
πin ∗πjm (x1 , x2 , . . . , xnm ) = πin (xj , xm+j , . . . , x(n−1)m+j ) = x(i−1)m+j . So we need to show that
k = (i − 1)m + j. We use the fact, that we can obtain f and g as minors of t = f ∗ g, as in
the proof of Lemma 4.28.
First, let α : [nm] → [n] be defined by α(x) = ⌈x/m⌉. This corresponds to the minor
in (4.1). Then ξ(f ∗ g)α = ξ((f ∗ g)α ) = ξ(f ) = πin . On the other hand ξ(f ∗ g)α = πα(k) n ,

so ⌈k/m⌉ = i. Next, let β : [nm] → [m] be defined by β(x) = x mod m if x mod m ̸= 0

and m else. Then ξ(f ∗ g)β = ξ((f ∗ g)β ) = ξ(g) = πjm . But, on the other hand ξ(f ∗ g)β =
m , so k must be equal to j modulo m. Both these observations together imply that
πβ(k)
k = (i − 1)m + j.

We are now ready to finish the proof of Taylor’s theorem:

Proof of Theorem 4.24. We first show (1)→(2). So let ξ : A → Proj be a minion homo-
morphism. We want to show that ξ is a clone homomorphism, or in other words, that for
f, g1 , . . . , gn ∈ A :
ξ(f ◦ (g1 , . . . , gn )) = ξ(f ) ◦ (ξ(g1 ), . . . , ξ(gn )).
By Lemma 4.28 there is a g ∈ A , such that every gi is equal to a minor g αi = gi . So

(f ◦ (g1 , . . . , gn )(x1 , . . . , xm ) = f (g(xα1 (1) , . . . , xα1 (k) ), . . . , g(xαn (1) , . . . , xαn (k) )),

where k denotes the arity of g. We can further write this as a minor (f ∗ g)α , where α : [nk] →
[m] is defined by α((i − 1)k + j) = αi (j). So f ◦ (g1 , . . . , gn ) = (f ∗ g)α . Since ξ is a minion
homomorphism
ξ((f ∗ g)α ) = ξ((f ∗ g))α .
By Lemma 4.29 we have

ξ((f ∗ g))α = (ξ(f ) ∗ ξ(g))α = ξ(f ) ◦ (ξ(g)α1 , . . . , ξ(g)αn )

Since ξ is a minion homomorphism, this is equal to

ξ(f ) ◦ (ξ(g α1 ), . . . ξ(g αn )) = ξ(f ) ◦ (ξ(g1 ), . . . ξ(gn )),

52
therefore ξ is a clone homomorphism.

We next show (2) → (3) by an indirect proof. So assume that the clone A does not have
a Taylor operation; we are going to prove that there is a minion homomorphism from A to
Proj, in 3 steps.

Claim 1: For every fixed t ∈ A there is a map ξ from the minors of t to Proj such that
ξ(tα ) = ξ(t)α .
We know that t is not Taylor. So, by Observation 4.26 (4), there is an index i, such that
for all maps α, β either α(i) = β(i) or tα ̸= tβ . So, in some sense the index ’separates’ the
minors of t (Note that i is not necessarily unique). We define the map by ξ(tα ) = πα(i) k

(for α : [n] → [k]). This map is well-defined since whenever tα = tβ , then α(i) = β(i),
and therefore ξ(tα ) = ξ(tβ ) = πα(i)
k . Moreover it satisfies ξ(tα ) = π k n α
α(i) = (πi ) = ξ(t) .
α

Claim 2: For every finite set T ⊆ A , there is a map from T to Proj that preserves minors.
By Lemma 4.29 for every finite subset T ⊆ A , there is an operation t ∈ A such that
all operations in T are minors of t. Now Claim 2 follows by applying Claim 1 to t.

Claim 3: There is a minion homomorphism ξ : A → Proj

This follows from a compactness argument; we create a first-order theory Σ, that for-
mally describes minion homomorphisms from A to Proj. The language of Σ consists of
constant symbols πin for all 1 ≤ i ≤ n and ξ(t) for every t ∈ A . And Σ consist of the
sentences

• πim ̸= πjn for all indices i ̸= j or m ̸= n

• for all t ∈ A of arity n we add the sentence ξ(t) = π1n ∨ ξ(t) = π2n ∨ · · · ∨ ξ(t) = πnn .
• for all t, s ∈ A such that s = tα we add the sentences ξ(t) = π1n → ξ(s) = πα(1) k ,
n k n k
ξ(t) = π2 → ξ(s) = πα(2) , . . . ξ(t) = πn → ξ(s) = πα(n) .

Now clearly, if Σ has a model, then t 7→ ξ(t) is a minion homomorphism. By Claim 2,

every finite subset of Σ has a model. But, by the compactness theorem of first-order
logic, also Σ has a model, which concludes the proof.

Having a Taylor operation t is still a very general condition, since we don’t know anything
about the arity of t, or the specific form. But it can be show that for idempotent clone A on
a finite set A, the following are equivalent:

• A has a Taylor term

• A has a 6-ary Siggers operation s(x, y, x, z, y, z) ≈ s(y, x, z, x, z, y)
• A has a 4-ary Siggers operation s(a, r, e, a) ≈ s(r, a, r, e)
• A has a WNU (weak near unanimity) operation, i.e. an operation satisfying w(y, x, . . . , x) ≈
w(x, y, x, . . . , x) ≈ · · · ≈ w(x, x, . . . , y).
• A has a cyclic operation c(x1 , . . . , xp ) ≈ c(x2 , . . . , xp , x1 ), for every prime p > |A|

53
 Many of these results can be proved nicely using the theory of absorption developed by
Libor Barto and Marcin Kozik. (Due to lack of time) we are however only going to sketch
an elementary proof of the existence of the 6-ary Siggers term t(xyxzyz) ≈ t(yxzxzy) in the
next section.
Surprisingly, even if we drop the finiteness condition, there is a uniform characterization
of idempotent Taylor clones by the existence of so called Olšák terms:

t(xyy, yxx) ≈ t(yxy, xyx) ≈ t(yyx, xxy)

This result was proved by Mirek Olšák in 2016.

4.4 Siggers operations

In order to prove the existence of Siggers terms in finite idempotent Taylor algebras, it is
enough to prove the following statement about graphs:

Proposition 4.30 (Loop lemma). Let A be an idempotent algebra on a finite set A with
Clo(A) ̸≤ Proj, and let E ∈ Inv(A) be an invariant relation, such that (A; E) is an undirected
graph that contains a triangle/3-clique K3 . Then E contains a loop (i.e. an edge (a, a) ∈ E).

Several similar statements (also generally referred to as loop lemmas), were shown for
different assumptions on the edge relation E and algebra A. Proposition 4.30 then implies
the existence of Siggers terms:

Corollary 4.31. Every finite idempotent A with Clo(A) ̸≤ Proj has a 6-ary Siggers term
s(xyxzyz) ≈ s(yxzxzy).

Proof. Let F = FA (x, y, z) be the free algebra in HSP(A) generated by 3 variables. Note
that F is also finite, idempotent and Clo(F) ̸≤ Proj (since it has some Taylor term). Then,
consider the subalgebra
           
x y x z y z
E = SgF2 , , , , , ≤ F2 .
y x z x z y
Note that E is an undirected graph on F that contains the triangle {x, y, z}. By Propo-
sition 4.30, E contains a loop. The elements of E are of the form t(xyxzyz)


t(yxzxzy)
; thus there is a
6-ary term s and such that s(xyxzyz) = s(yxzxzy). In other words, s is a Siggers term of
A.

So, it only remains to prove Proposition 4.30. In order to do so, we first mention some
properties of the triangle K3 = ({0, 1, 2}, ̸=) and its powers:

Lemma 4.32.
1. Pol(K3 , {0}, {1}, {2}) = Proj, i.e. the only idempotent polymorphisms of K3 are the
projections
2. Pol(Kk3 , ({c})c∈K k ) ≤ Proj, for every power k ≥ 1
3

3. Every edge Kk3 is in exactly one triangle. But, by introducing any additional edge to Kk3 ,
we lose this property.

54
 4. If G is a homomorphic image of Kk3 , such that every edge is in at most one triangle,
then G ∼= Km
3 for some 1 ≤ m ≤ k.

We leave the proof of Lemma 4.32 for later/as an exercise, and move on to prove the loop
lemma:

Proof of Proposition 4.30. For contradiction, assume that there is an idempotent Taylor al-
gebra A on a finite set A with an invariant graph relation E containing a triangle, but not a
loop. Without loss of generality, let us pick A minimal. Then:

Claim 1 For every subuniverse B < A, (B, E|B ) does not contain any triangle.
This is clearly the case, otherwise the Taylor algebra B, together with the graph (B, E|B )
would contradict the minimality of A.

Claim 2 Every x ∈ A is part of a triangle.

If this is not the case, then B = {x ∈ A | ∃y, z E(x, y) ∧ E(y, z) ∧ E(x, z)} is a proper
nonempty subuniverse of A (note that B is pp-definable from E). Also, (B, E|E ) con-
tains a triangle, contradicting Claim 1.

Claim 3 Every edge of (A; E) is part of at most one triangle.

To show this, we define the binary relation R(x, y) := ∃t, zE(x, t) ∧ E(x, z) ∧ E(t, z) ∧
E(t, y) ∧ E(z, y), which describes two points being connected by a ’diamond’ graph:

x y

Note that, by Claim 1, R is reflexive. For every n ∈ N, let us define Rn = {(x, y) ∈

A2 | ∃c0 , c1 , . . . , cn : a = c0 ∧ R(c0 , c1 ) ∧ · · · ∧ R(cn−1 , cn ) ∧ cn = b}. Note that Rn is
pp-definable in R. Since A is finite, the transitive closure R̄ of R is equal to some Rn ,
and thus also pp-definable in R. In other words, R̄ is a congruence of A. Note Claim 3
holds, if and only if R̄ is the identity.
Let us assume, for contradiction that R̄ is not the identity. Then A/R̄, together with
the edge relation E/R̄ is also a graph that is invariant under the Taylor algebra A/R̄.
If this graph does not contain a loop, then it contradicts to the minimality of |A|.
So let us assume that E/R̄ contains a loop. This means that there are a, b ∈ A, such
that E(a, b) ∧ R̄(a, b).Let us take such a, b such that Rn (a, b) for minimal n.
If n = 1, then this means that the (A; E) contains a copy of the complete graph K4 :

a b
•

55
 Since A is idempotent, {a} is a subalgebra. Therefore also B = x ∈ A : E(x, a) is a
proper subalgebra of A. But B contains a triangle, which contradicts to Claim 1.
More general, if n = 2k + 1 is odd, then let c the element such that Rk+1 (a, c) ∧ Rk (c, b).
Then, we define B = {x ∈ A : ∃yRk (c, y) ∧ E(y, x)}. This B does not contain c itself
(otherwise n would not be minimal). So B is a proper, minimal subalgebra of A. On
the other hand, B contains the triangle (consisting of a and two neighbors t1 , z1 ) -
contradiction!

t1 • • • •

a • • c • b
z1 • • • •

• •

c • • B
• •

Figure 4.1: The construction of B for n = 5.

If n = 2k, we can define a subalgebra B using a similar trick; we illustrate the construc-
tion for n = 4, and leave the proof details to the reader.

t1 • c •

a • • • b
z1 • d •

c •

•c • B
•
d

Figure 4.2: The construction of B for n = 4.

Claim 4 A has a subuniverse B such that (B; E|B ) is isomorphic to Kk3 for some k ∈ N.

We construct B inductively, by constructing a sequence of subsets B0 ⊆ B1 ⊆ B2 · · · ⊆

B, such that every (Bi ; E) is isomorphic to a power of K3 .
We set B0 to be equal to a triangle. And, for an induction step, assume we already
know Bi , such that (Bi , E) is isomorphic to Kk3i . If Bi is closed under A, we set B = Bi
and are done.
Otherwise,there is a term f ∈ Clo(A), and elements b1 , . . . , bn ∈ Bi with f (b1 , . . . , bn ) ∈
/
n
Bi . We set Bi+1 = f (Bi ). By the idempotence of f , Bi ⊆ Bi+1 . Since f preserves the

56
 edge relation E, also f (E n ) ⊆ E. In particular, in (Bi+1 , f (E|nB )), no edge is contained
k
in more than one triangle. By Lemma 4.32 (4), (Bi+1 , f (E|nB )) is isomorphic to K3i+1
for some ki+1 . By Lemma 4.32 (3), the restriction of E to Bi+1 must be equal to f (E n )
(otherwise an edge would be in more than one triangle). This finishes the induction
step i → i + 1. Since A is finite, there is some index j, such that B = Bj is closed under
Clo(A).

Claim 5 Clo(A) ≤ Proj.

Note that for the subuniverse B from Claim 4, (B, E|B ) contains a triangle,. Thus,
by Claim 1, it must be already equal to (A; E). So (A, E) ∼ = Kk3 and Clo(A) is a
k
subset of the idempotent polymorphisms of K3 . By Lemma 4.32 (2), there is a clone
homomorphism to Proj.

Claim 5 contradicts to our assumption that Clo(A) is Taylor - contradiction.

For completeness, we next prove the properties of K3 discussed in Lemma 4.32:

Proof of Lemma 4.32.

1. Exercise 4.14
2. Exercise 4.15
3. Note that a pair a = (a1 , . . . , ak ), b = (b1 , . . . , bk ) forms an edge in Kk3 if and only if
ai ̸= bi for all i = 1, . . . , k. Thus there is a unique way to complete an edge to a triangle;
namely by the vertex (c1 , . . . , ck ) with |{ai , bi , ci }| = 3 for all i.
Moreover, for every pair a, b that does not have an edge, there are at least two vertices
c, c′ that are neighbors of both a and b. Thus, if we add the edge (a, b) to Kk3 , we obtain
two triangles sharing the edge (a, b).
4. G = (V ; E) is a homomorphic image of Kk3 , so there is a surjective map ϕ : K3k → V ,
such that (x, y) ∈ E if and only if there is an edge (a, b) in Kk3 with ϕ(a) = x and
ϕ(b) = y. If ϕ is injective, we are done.
Let otherwise i be an index, such that there are a ̸= b with ai ̸= bi and ϕ(a) = ϕ(b).
We then prove that ϕ does not depend on i at all, i.e. ker π{1,...,k}\{i} ⊆ ker ϕ.
Wlog i = 1, so a1 ̸= b1 . Let c1 be such that |{a1 , b1 , c1 }| = 3. Let t, t′ such that
ti = t′i ̸= ai and t1 = b1 , t′1 = c1 . Then clearly E(t, x) and E(t′ , x). Note that t has no
edge with b, thus t and b have a common neighbor s = (a1 , s2 , . . . , sk ). This s is further
also a neighbor of t′ .
Then ϕ(a) = ϕ(b), implies that both ϕ(a), ϕ(t), ϕ(s) and ϕ(a), ϕ(t′ ), ϕ(s) are triangles;
since they share an edge, this can only happen if ϕ(t) = ϕ(t′ ). (By symmetry, the same
holds also for neighbors t, t′ of b, that agree everywhere except on the first coordinate.)
Now, take any pair z, z ′ with z1 ̸= z1′ and zi = zi′ else. Note that {z1 , z1′ } ∩ {a1 , b1 } =
̸ ∅.
Without loss of generality z1 = a1 . Then, one can find a common neighbor t of z, z ′
and a. But then, similar as in the first step, one can show ϕ(t) = ϕ(t′ ) (for some t′
with a different first coordinate that t) implies ϕ(z) = ϕ(z ′ ), which is what we wanted
to prove.

57
 If we set I = {1 ≤ i ≤ n | ∃a, b : ai ̸= bi , ϕ(a) = ϕ(b)}, then ker ϕ = ker π{1,...,k}\I , i.e. ϕ
is the projection of Kk3 to the coordinates {1, . . . , k} \ I.

4.5 Exercises
Exercise 4.1. We claimed that for every n ≥ 2 there is structure A with |A| = n and a
NP-complete CSP(A). For n = 2, 3 we saw this in Example 4.3 and 4.2. For general n > 3
prove it as follows:
• Show that 3-COLOR reduces to n-COLOR (the problem coloring a graph with n colors).
• Thus n-COLOR is NP-complete.
• Give a description of n-COLOR as CSP of a structure on the set {1, 2, . . . , n}.
Exercise 4.2. We say in Example 4.4 that solving systems of linear equations over Zp can
be modeled as a CSP. Prove that for every finite algebra A (so finite universe and finite type)
there is a structure A, such that solving systems of polynomial equations over A is equivalent
to CSP(A). (Hint: use the function graphs of the basic operations as relations of A).
Exercise 4.3. Let A be finite and ∅ = ̸ R ⊆ A2 be a binary relation, and assume that R is
preserved by a semilattice operation.
1. Show that, if R is subdirect, every primitive positive sentence
∃x1 , . . . , xn R(xi1 , xj1 ) ∧ · · · ∧ R(xik , xjk ) is true (and hence CSP(A; R) ∈ P).
2. Show that (1) is not true if R is not subdirect.
3. Try to prove for general such R that CSP(A; R) ∈ P.
Exercise 4.4. Have a look at Section 1 and 2 of [8] if you want more background / examples
of CSPs.
Exercise 4.5. What do you think: Does Proposition 4.8 also hold for structures A
• with finite domain A, but infinitely many relations?
• with infinite domain A, but finitely many relations?
Exercise 4.6. Let A, A′ be two relational structures of the same type (Example: two graphs).
We say that they are homomorphically equivalent, if there are homomorphisms h : A → A′
and h′ : A′ → A (here a homomorphism is a map that preserves all relations). Show that then
CSP(A) = CSP(A′ ).
Exercise 4.7. Let A = ({0, 1}; ≤), and A′ = ({0}; ≤).
• Show that A and A′ are homomorphically equivalent.
• Show that Pol(A′ ) contains a Maltsev polymorphism, but Pol(A) does not. Therefore
there is no clone homomorphism ξ : Pol(A′ ) → Pol(A)
Exercise 4.8. There is however a minion homomorphism in the example from Exercise 4.7
(and in general for homomorphically equivalent structures): Let h : A → A′ and h′ : A′ → A
be the two homomorphisms. Then show that ξ : Pol(A) → Pol(A′ ), which is defined by
ξ(f )(x1 , . . . , xn ) = hf (h′ (x1 ), . . . , h′ (xn )) is a minion homomorphism.

58
Exercise 4.9. An operation f is called essentially injective, if f (x1 , . . . , xn ) = g(xi1 , . . . , xik ),
for an injective g. The essentially injective operations on N form a clone A .
• Show that this clone contains no Taylor term.
• However show that there are f, u ∈ A such that f (x, y) = u ◦ f (y, x). Conclude that
A ̸≤ Proj.
• (*) try to find a system of non-trivial height 1 identities in A .
Exercise 4.10. In the proof of (1)→(2) of Theorem 4.24, we only checked that ξ preserves
compositions. Complete the proof that ξ is actually a clone homomorphism.
Exercise 4.11. Let ProjA be the clone of the projections on a set A. Note that we defined
Proj = Proj{0,1} .
• Show that ProjA ∼ Proj for every |A| > 1. Conclude that the equivalence class of Proj
is the smallest element of the interpretability lattice.
• What is the problem with ProjA for |A| = 1? Prove that its equivalence class under ∼
is the maximum of the interpretability lattice.
Exercise 4.12. Prove that the following are equivalent for finite idempotent algebras A:
• Clo(A) contains an n-ary cyclic term t(x1 , x2 , . . . , xn ) ≈ t(x2 , x3 , . . . , x1 )
• Every n-ary invariant relation R ≤ An , which is invariant under cyclic shifts (i.e.
(a1 , a2 , . . . , an ) ∈ R ⇒ (a2 , a3 , . . . , an , a1 ) ∈ R) contains a constant tuple (i.e. ∃a (a, a, . . . , a) ∈
R).
Hint: for the interesting implication, define R to be the subalgebra generated by a tuple and
all its cyclic shifts. Show that there is a term that behaves like a cyclic operations on these
tuples; then compose all such terms in a smart way.
Exercise 4.13. A ternary operation f : A3 → A is called a majority operation if it satisfies

f (y, x, x) ≈ f (x, y, x) ≈ f (x, x, y) ≈ x.

Let R ⊆ An be invariant under a majority operation. Show that then ā = (a1 , . . . , an ) ∈ R if

and only if (ai , aj ) ∈ pri,j R for every pair of coordinates 1 ≤ i, j ≤ n (here pri,j R denotes the
projection of R to the coordinates i and j).
Exercise 4.14. We show that the idempotent polymorphisms of K3 = ({0, 1, 2}, ̸=) are the
projections on {0, 1, 2}:
1. Show that all such polymorphisms of arity at most 3 are projections
2. For an n-ary poylmorphism f and 1 ≤ i ≤ n, let us define the minors fi (x, y) =
f (x, . . . , x, y, x, . . . , x), where the only y is on the i-th position. Prove that either
fi (x, y) = x or fi (x, y) = y, and there is at most one i, with fi (x, y) = y
3. Show that not all minors fi (x, y) can be equal to x.
4. Show that, if fi (x, y) = y, then f = πin .
Exercise 4.15. Show that, for every k ≥ 3, the clone of idempotent polymorphisms of Kk3 ,
i.e. Pol(Kk3 , ({c})c∈K3 ) has a clone homomorphism to Proj. (Hint: show that x ∼ y iff x1 = y1
is a congruence; either by directly checking it, or finding a pp-definition in (Kk3 , ({c})c∈K3 )).

59
Bibliography

[1] Jaroslav Ježek. Universal Algebra http://ka.karlin.mff.cuni.cz/jezek/ua.pdf

Script, 2008

[2] Clifford Bergman. Universal algebra: Fundamentals and selected topics. Chapman and
Hall/CRC, 2011. (Book available in our library)

[3] Ralph Freese, Ralph McKenzie. Commutator theory for congruence modular varieties.
CUP Archive, 1987.

[4] Andrew Moorhead. Supernilpotent algebras are nilpotent. Preprint on

https://arxiv.org/abs/1906.09163 2019.

[5] Pawel Idziak, Jacek Krzaczkowski. Satisfiability in multi-valued circuits. Proceedings of

the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. 2018.

[6] Dmitriy Zhuk. A proof of CSP dichotomy conjecture. 58th Annual Symposium on Foun-
dations of Computer Science (FOCS). 2017.

[7] Bulatov, Andrei A. A dichotomy theorem for nonuniform CSPs. 58th Annual Symposium
on Foundations of Computer Science (FOCS). 2017.

[8] Libor Barto, Andrei Krokhin, Ross Willard. Polymorphisms, and how to use them. https:
//drops.dagstuhl.de/opus/volltexte/2017/6959/pdf/DFU-Vol7-15301-1.pdf

[9] Donald Knuth, Peter Bendix Simple word problems in universal algebras. Automation of
Reasoning: 2: Classical Papers on Computational Logic 1967–1970, pp 342–376, 1983.

Thanks
Thanks to Libor Barto, Martin Boroš, Anna Gajdova, Juraj Hartmann, Štěpán Hudeček,
Zuzana Procházková, Svilen Popov, Lucien Šima, Žaneta Semanišinová, Ester Sgallová, Yifan
Zhang for pointing out mistakes and typos in earlier versions.

60