TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

arXiv:1708.09681v1 [math.GR] 31 Aug 2017

J. ALMEIDA AND O. KLÍMA
Abstract. A new scheme for proving pseudoidentities from a given
set Σ of pseudoidentities, which is clearly sound, is also shown to be
complete in many instances, such as when Σ defines a locally finite
variety, a pseudovariety of groups, more generally, of completely simple
semigroups, or of commutative monoids. Many further examples when
the scheme is complete are given when Σ defines a pseudovariety V which
is σ-reducible for the equation x = y, provided Σ is enough to prove a
basis of identities for the variety of σ-algebras generated by V. This
gives ample evidence in support of the conjecture that the proof scheme
is complete in general.

1. Introduction
Pseudovarieties are classes of finite algebras closed under taking homomorphic images, subalgebras and finite direct products. They have been
studied mostly in the context of finite semigroup theory due to the connections with automata and formal languages. In the framework of Eilenberg’s
correspondence [26], determining whether a regular language enjoys a suitable property of a certain kind is converted to the membership problem of
its syntactic semigroup in the corresponding pseudovariety of semigroups.
On the other hand, pseudovarieties are in many respects like the varieties
of classical Universal Algebra, admitting relatively free algebras, albeit in
general not finite, but rather profinite, and thus being defined by formal
equations, where pseudoidentities play the role of identities [2]. While there
is a natural proof scheme for identities that is sound and complete, which
is sometimes referred as the completeness theorem for equational logic, the
situation in the theory of pseudovarieties is not so simple.
Indeed, the first author has shown that there is no complete finite deduction system that is sufficient to prove a given pseudoidentity from a set of
hypotheses (or basis) assuming that all models of the basis are also models of
the pseudoidentity [2, Section 3.8]. Some sort of topological closure operator
seems to be required. While such an operator was also proposed by the first
author (see [2, Section 3.8]), it is very hard to handle and only one instance
of its application has been found so far [12].
The main contribution of this paper is a new approach which consists
in starting with all evaluation consequences of the basis, and completing
them in the same term; then, transfinitely alternating transitive closure and
topological closure. This proof scheme is clearly sound and, by definition,
it is suitable for transfinite induction proofs. We show that it is complete
2010 Mathematics Subject Classification. Primary 20M07. Secondary 20M05, 03F03.
Key words and phrases. pseudoidentity, syntactical proof, semigroup, profinite monoid,
completeness, reducible pseudovariety, implicit signature.
1

2

J. ALMEIDA AND O. KLÍMA

in many familiar instances of concrete bases: whenever they define locally
finite varieties (in their algebraic language), pseudovarieties of groups or,
more generally, of completely simple semigroups, or pseudovarieties of commutative monoids. For the proof of some of these results, we need to show
that concrete pseudoidentities that valid in a pseudovariety with a given basis are provable from the basis. The main technique in proving such results
is invoking excluded structures.
We also show that the proof scheme is complete when the pseudovariety
defined by the basis Σ is σ-reducible with respect to the equation x = y,
where σ is an implicit signature such that the variety of σ-algebras generated
by the pseudovariety defined by Σ admits a basis whose elements can be
obtained from Σ by our proof scheme. Combining with several reducibility
results that can be found in the literature, an exercise that by no means we
carry out exhaustively, this provides ample evidence in favor of the conjecture
that our proof scheme is complete in general.
2. Preliminaries
We recall quickly in this section some basic notions from general algebra,
which also serves to fix some notation. The reader is referred to [19] for
basic notions on Universal Algebra and to [2, 5, 36] for an introduction to
pseudovarieties and profinite structures.
By an algebraic type τ we mean a set of operation symbols, each of which
has an associated finite arity. We assume from hereon that τ is finite. An
algebra of type τ or a τ -algebra is a nonempty set endowed with an interpretation of each operation symbol of the type in question as an operation of the
corresponding arity. In general, we fix an algebraic type and consider only
algebras of that type. The (symbols of) operations of the type are sometimes
called the basic operations.
By a topological algebra we mean an algebra endowed with a topology such
that the interpretations of the basic operations are continuous functions.
Such an algebra is compact if so is its topology. We endow finite algebras
with the discrete topology. A topological algebra S is residually C for a
class C of algebras if distinct points in S may be separated by continuous
homomorphisms into members of C.
Given a family (Si )i∈I of topological algebras, where the index set is directed, and for each pair (i, j) of indices with i ≥ j, a continuous homomorphism ϕi,j : Si → Sj such that ϕi,i is the identity mapping on Si and, for
i ≥ j ≥ k, ϕj,k ◦ ϕi,j = ϕi,k , we may consider the inverse limit limi∈I Si ,
←−
Q
which may be described as the subset of the product i∈I Si consisting of all
families (si )i∈I such that each si ∈ Si and, for i ≥ j, ϕi,j (si ) = sj . In case
each Si is compact and the functions ϕi,j are onto, limi∈I Si is nonempty
←−
Q
and a closed subalgebra of i∈I Si .
Recall that a pseudovariety is a (nonempty) class of finite algebras of a
given type that is closed under taking homomorphic images, subalgebras
and finite direct products. Let U be a pseudovariety. A pro-U algebra is an
inverse limit of algebras from U. In other words, a pro-U algebra is a compact
algebra that is residually U. A profinite algebra is a pro-U algebra for the
class U of all finite algebras of the given type. In case a profinite algebra S is

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

3

finitely generated as a topological algebra, meaning that a finitely generated
subalgebra is dense, since the signature is assumed to be finite, there are,
up to isomorphism, only countably many finite homomorphic images of S.
Hence, S embeds in a countable product of finite algebras, which implies that
its topology is metrizable; in particular, the topology of S is characterized
by the convergence of sequences.
Given an arbitrary algebra S, one may consider all homomorphisms S →
F onto algebras from a set of representatives of isomorphism classes of algebras from a given pseudovariety U. These homomorphisms form a directed
set and so we may consider the inverse limit limS→F F , which is called the
←−
pro-U completion of S and is denoted ŜU . Note that the natural mapping
S → ŜU is injective if and only if S is residually U. In case U consists of
all finite algebras of the given type, we drop the index U and talk about the
profinite completion of S.
By an alphabet we simply mean a finite set. Alphabets will appear as free
generating sets of various structures.
By a term (of a given algebraic type) we mean a formal expression in
a fixed alphabet constructed using the basic operations according to their
arities. In other words, it is an element of the free algebra in the (Birkhoff)
variety of all algebras of the given type.
A pro-U algebra S is said to be freely generated by A if it comes endowed
with a function ι : A → S such that, for every function ϕ : A → T into a
pro-U algebra T , there is a unique continuous homomorphism ϕ̂ : S → T
such that the following diagram commutes:
ι /
S✤
❄❄
❄❄
✤
ϕ̂
❄
ϕ ❄❄ ✤
 

A❄

T

Such a structure S is unique up to isomorphism of topological algebras and
can be easily shown to be precisely the inverse limit of all A-generated members of U. It is denoted ΩA U. If n = |A|, then we may sometimes write Ωn U
instead of ΩA U as it is easy to see that, up to isomorphism of topological
algebras, ΩA U only depends on the cardinality of the set A and not on the
set itself. The subalgebra of ΩA U generated by ι(A) is denoted ΩA U; it is the
algebra in the variety generated by U that is freely generated by the alphabet
[
A. Note that ΩA U may also be obtained as the profinite completion Ω
A U.
An element of ΩA U is sometimes called a U-pseudoword; those that lie
in ΩA U are said to be finite whereas the remaining U-pseudowords are said
to be infinite. Every pseudoword w ∈ ΩA U has a natural interpretation as
an operation of arity |A| on a pro-U algebra T : |A|-tuples of elements of T
may be identified with functions ϕ : A → T and so the interpretation of w
becomes a function wT : T A → T ; the image wT (ϕ) is defined to be ϕ̂(w),
where ϕ̂ is given by the above commutative diagram. Viewed as operations,
pseudowords are sometimes called implicit operations because their natural
interpretations commute with continuous homomorphisms between pro-U
algebras.

4

J. ALMEIDA AND O. KLÍMA

By a U-pseudoidentity we mean a formal equality u = v with u, v ∈ ΩA U
for some alphabet A. A pseudoidentity u = v holds in an algebra T ∈ U
if uT = vT . For a set Σ of U-pseudoidentities the class JΣKU consists of all
algebras T ∈ U in which all pseudoidentities from Σ hold. When the ambient
pseudovariety U is understood from the context, we may also write JΣK. This
defines a pseudovariety contained in U, that is, a subpseudovariety of U, and
Reiterman’s theorem [35] states that every subpseudovariety of U is of this
form.
By an implicit signature (over U) we mean a set σ of U-pseudowords
including those of the form o(a1 , . . . , an ) ∈ ΩA U, where A = {a1 , . . . , an } is
an n-letter alphabet and n is the arity of the basic operation o. By the above,
every pro-U algebra has a natural structure of σ-algebra. In particular, this
is the case for the algebras from U which, as σ-algebras, generate a variety of
σ-algebras denoted Uσ . It is also the case of ΩA U; the σ-subalgebra generated
by ι(A) is denoted ΩσA U and it is easily shown to be the algebra of the variety
Uσ freely generated by A.
Two pseudovarieties that have received a lot of attention are the pseudovariety S, of all finite semigroups, and M, of all finite monoids. For an element
s of a finite semigroup S, there is a unique power sn (n ≥ 1) of s which is
an idempotent and is denoted sω . The element s2n−1 is then also denoted
sω−1 . In terms of the discrete topology, sω is the limit of the sequence (sn! )n
while sω−1 is the limit of the sequence (sn!−1 )n . It follows that if, instead
of taking S finite we take S to be profinite, the sequences in question still
converge and the notation for the limits is retained.
Consider the semiring N of all natural numbers (including zero) and the
ring Z of integers, both under the usual addition and multiplication. These
may be viewed as algebras of type consisting of two binary operation symbols,
of addition and multiplication. Since both underlying additive monoids are
monogenic, so are there finite homomorphic images. Note also that a finite
monogenic additive monoid M carries a natural structure of semiring via
the natural additive homomorphism N → M . Moreover, in case M is a
group, such a homomorphism factors through the embedding N → Z as a
ring homomorphism Z → M . It follows that the profinite completion of each
of N and Z as additive structures carries a multiplication which makes it
isomorphic (as topological algebra) with the semiring N̂, respectively with
the ring Ẑ.
Let G and Gp denote, respectively, the pseudovarieties of all finite groups
and of all finite p-groups. The above allows to describe the structure of
the monoid Ω1 M and of the groups Ω1 G and Ω1 Gp . Indeed we know that
Ω1 M and Ω1 G are respectively the inverse limits of the finite monogenic
monoids and of the finite cyclic groups, which we know that, as additive
algebras, carry multiplicative structures which make them isomorphic to N̂
and Ẑ, respectively. The isomorphisms N̂ → Ω1 M and Ẑ → Ω1 G are easy
to describe: if the free generator is denoted x, they send each natural n in
N or in Z to xn , respectively in Ω1 M and in Ω1 G. For this reason, we also
denote, for each α in N̂ or in Ẑ the image in Ω1 M or in Ω1 G, respectively, by
xα . Thus the usual laws of exponents hold and (xα )β = xαβ can be viewed
as a composition of implicit operations.

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

5

Similarly, Ω1 Gp may be identified with the completion ẐGp = limn Z/pn Z,
←−
which is frequently denoted Zp . Moreover, thanks to the Chinese Remainder
Q
Theorem, it is easy to see that Ẑ ≃ p Zp , where the index p runs over all
primes. The structure of the ring Zp is quite transparent: it is an integral
domain and every ideal is both principal and closed. It follows that the
principal ideals of the ring Ẑ are the closed ideals, which in turn are the
finitely generated ideals. In particular, every subset of Z has a greatest
common divisor, which is a generator of the closed ideal generated by the
given set.
Since each of the (semi)rings N and Z is residually finite, and the later
is even residually Gp , there are natural embeddings N → N̂, Z → Ẑ, and
Z → Zp , which we view as inclusion mappings. It is easy to see that the
invertible elements of Zp are those that are not divisible by p. Hence, the
invertible elements of Ẑ are those that are not divisible by any prime p.
The semiring N̂ has two idempotents, namely 0 and ω = lim n!. The
maximal additive group Hω containing ω is a closed ideal of N̂ which is
generated by ω + 1. The natural continuous homomorphism π : N̂ → Ẑ,
mapping 1 to 1, also maps ω+1 to 1 and therefore restricts to an isomorphism
Hω → Ẑ. Thus, Ẑ may be identified with Hω , which we do from hereon; it
is a retract of N̂ under the mapping α 7→ ω + α. Also note that N̂ is the
disjoint union of N with Ẑ.

3. A proof scheme
Let U be a pseudovariety of a certain finite type of algebras involving only
finitary operations. Let Σ be a set of pseudoidentities u = v with u and v elements of the free pro-U algebra over some arbitrary finite alphabet. We seek
a complete proof scheme for pseudoidentities valid in the pseudovariety JΣK,
that is, a deduction system that is capable of deducing from Σ exactly the
pseudoidentities valid in JΣK.
By transfinite recursion, we define, for each ordinal α, a set Σα of pseudoidentities over A as follows:
• Σ0 consists of all pairs of the form

t(ϕ(u), w1 , . . . , wn ), t(ϕ(v), w1 , . . . , wn )
such that either u = v or v = u is a pseudoidentity from Σ, say with
u, v ∈ ΩB U, ϕ : ΩB U → ΩA U is a continuous homomorphism, t is a
term (in the algebraic language of U), and wi ∈ ΩA U (i = 1, . . . , n);
• Σ2α+1 is the transitive closure of the binary relation Σ2α ;
• Σ2α+2 is the topological closure of the relation Σ2α+1 in the space
ΩA U × ΩA U;
S
• if α is a limit ordinal, then Σα = β<α Σβ .
Note that, if Σα+2 = Σα , then Σα is both transitive and topologically closed,
so that Σβ = Σα for every ordinal β with β ≥ α. Such a condition must hold
S
for α at most ω1 , the least uncountable ordinal. Hence, the union Σ̃ = α Σα
defines a transitive closed binary relation on ΩA U.

6

J. ALMEIDA AND O. KLÍMA

Consider a binary relation θ on ΩA U. We say that θ is stable if (u, v) ∈ θ
implies

t(u, w1 , . . . , wn ), t(v, w1 , . . . , wn ) ∈ θ
for every term t and w1 , . . . , wn ∈ ΩA U. We also say that θ is fully invariant
if, for every continuous endomorphism ϕ of ΩA U and (u, v) ∈ θ, we have
(ϕ(u), ϕ(v)) ∈ θ. A stable equivalence relation is also called a congruence.
The following result establishes the soundness of the above proof scheme.
Proposition 3.1. The relation Σ̃ is a fully invariant closed congruence
on ΩA U. For every (u, v) ∈ Σ̃, the pseudoidentity u = v is valid in JΣK.
Proof. Note that Σ0 is a reflexive and symmetric binary relation on ΩA U,
whence so are all Σα as well as Σ̃. We prove by transfinite induction on α that
each Σα is a stable fully invariant binary relation on ΩA U whose elements,
viewed as pseudoidentities, are valid in the pseudovariety JΣK.
For α = 0, the claimed properties are immediate from the definition of Σ0 .
Assuming the claim holds for all α < β, then it clearly also holds for Σβ
in case β is a limit ordinal. Otherwise, β is a successor ordinal, and we
distinguish the cases where β is odd or even.
In case β is odd, that is, it is of the form β = 2γ + 1, Σβ is the transitive
closure of Σ2γ which, by the induction hypothesis, is a stable fully invariant
binary relation on ΩA U whose elements define pseudoidentities valid in the
pseudovariety JΣK. The elements of Σβ are pairs (u0 , un ) such that there
exist u1 , . . . , un−1 with each (ui , ui+1 ) ∈ Σ2γ (i = 0, . . . , n − 1). In particular, each pseudoidentity ui = ui+1 is valid in JΣK, whence so is u0 = un .
If t is a term and w1 , . . . , wm are elements from ΩA U then, by the
 induction hypothesis, each pair t(ui , w1 , . . . , wm ), t(ui+1 , w1 , . . . ,wm ) belongs
to Σ2γ , and so the pair t(u0 , w1 , . . . , wm ), t(un , w1 , . . . , wm ) also belongs
to Σβ . Finally, if ϕ is a continuous endomorphism of ΩA U, by the induction
hypothesis each of the pairs (ϕ(ui ), ϕ(ui+1 )) belongs to Σ2γ , which entails
that (ϕ(u0 ), ϕ(un )) belongs to Σβ .
Consider next the case where β = 2γ + 2, that is, a nonzero and non-limit
even ordinal. Then, since ΩA U is a metric space, every element from Σβ
is the limit (u, v) of a sequence (un , vn )n of elements from Σ2γ+1 . By the
induction hypothesis, as a pseudoidentity, every element of the sequence
is valid in JΣK, whence so is u = v since, under an evaluation of the elements of A in a finite algebra, the sequences (un )n and (vn )n eventually
stabilize, precisely at the values of u and v, respectively. Since Σ2γ+1 is
assumed to be stable, for a term t and w1, . . . , wm ∈ ΩA U, the sequence of
pairs t(un , w1 , . . . , wm ), t(vn , w1 , . . . , wm ) n consists of elements of Σ2γ+1 ,

whence its limit t(u, w1 , . . . , wm ), t(v, w1 , . . . , wm ) belongs to Σβ = Σ2γ+1 .
Finally, if ϕ is a continuous endomorphism of ΩA U, then the elements of the
sequence (ϕ(un ), ϕ(vn ))n belong to Σ2γ+1 and, therefore, its limit (ϕ(u), ϕ(v))
belongs to Σβ . This completes the transfinite induction.
In view of the already established initial claim, we know that Σ̃ is a reflexive symmetric stable fully invariant binary relation consisting of pairs (u, v)
such that the pseudoidentity u = v is valid in JΣK. To complete the proof,
it remains to recall that we already observed that Σ̃ is a closed transitive
binary relation.


TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

7

We call the elements of Σ̃ the pseudoidentities provable from Σ. A proof
consists in a transfinite sequence of steps in which in step 0 we invoke pseudoidentities from Σ, suitably evaluated in ΩA U, in which both sides are
plugged in the same place of an arbitrary term, and in later steps we either
use transitivity of equality or take limits, in the latter two cases from already
proved steps, or simply collect together all pseudoidentities in previous steps.
In the last step in the proof we should have a set of pseudoidentities containing the one to be proved.
An alternative but equivalent, in the sense of capturing the same proved
pseudoidentities, definition of proof would be to take a transfinite sequence
of pseudoidentities in which in each step we allow one of the pseudoidentities
of the above step 0, we take u = w if there are two previous steps of the form
u = v and v = w, or we take u = v provided there is a sequence of earlier
steps (un = vn )n with u = lim un and v = lim vn . The latter steps are called
limiting steps. The last step in such a proof should be the pseudoidentity to
be proved.
If such a proof only involves a finite number of non-limiting steps and no
limiting steps, then we say the proof is algebraic. Note that such a proof
exists precisely for the pseudoidentities of Σ1 .
Several examples of proofs in the above general sense can be found in
the literature. In fact, all proofs that a pseudovariety defined by certain
pseudoidentities satisfies a given pseudoidentity that we have been able to
find in the literature seem to be expressible in this form. This suggests the
following general conjecture which amounts to completeness of our proof
scheme.
Conjecture 3.2. A U-pseudoidentity u = v is provable from a set Σ of
U-pseudoidentities whenever JΣK satisfies u = v.
The above statement is to be interpreted as a logical clause depending on
three parameters: U, Σ, and u = v, where the latter two determine the first
one. Since we have been unable to establish the conjecture in full generality,
particular instances of the conjecture, where one of the parameters is fixed
may be of interest as they provide evidence towards the conjecture. If a
parameter is fixed then those that are not determined by it are interpreted
as being universally quantified.
We say that a set Σ of U-pseudoidentities is h-strong (within U, or for U)
if the statement in the conjecture holds for the given fixed choice of Σ and
an arbitrary choice of the U-pseudoidentity u = v. In case Σ = {u = v}
consists of a single pseudoidentity, we also say that u = v is h-strong if so
is Σ.
A U-pseudoidentity u = v is said to be t-strong (within U, or for U) if the
statement in the conjecture holds for the given fixed choice of u = v and an
arbitrary choice of Σ.1
The conjecture also involves an ambient pseudovariety U with respect to
which pseudoidentities are taken. We say that the pseudovariety U is strong if
1The letters h and t in “h/t-strong” are meant to refer to whether the pseudoidentities
appear as hypotheses or thesis in the proofs.

8

J. ALMEIDA AND O. KLÍMA

the statement in the conjecture holds that is it holds for every set Σ∪{u = v}
of U-pseudoidentities.
Taking into account the results of [2, Section 3.8], showing that Σ is hstrong is equivalent to showing that Σ̃ is a profinite congruence in the sense
of [36, Page 139], that is, for every finite alphabet A, that Σ̃ is a closed
congruence on ΩA U such that the quotient topological algebra ΩA U/Σ̃ is
a profinite algebra. A further equivalent formulation of this property is
that, given any two distinct Σ̃-classes, there is a clopen union of Σ̃-classes
separating them. The difficulty in establishing this property in general is
to obtain Σ̃-saturation of such clopen sets. In case all congruence classes
are determined by a single class, as in the group case, this program is much
easier to achieve (cf. Section 8).
We are able to prove the conjecture in several cases of interest. The remainder of the paper is concerned with gathering evidence for the conjecture.
4. A transfer result
The purpose of this section is to show that it is possible to extend the
validity of the conjecture within a certain ambient pseudovariety V to a larger
pseudovariety U provided that V is defined within U by a basis satisfying the
conjecture. We first note that the converse is also true without the additional
assumption on a basis of V.
Proposition 4.1. Let U be a pseudovariety and let V be a subpseudovariety
of U. Suppose that the set Γ of U-pseudoidentities defines a subpseudovariety
of V and Γ is h-strong within U. Then the set Γ′ = {π(u) = π(v) : (u =
v) ∈ Γ} is h-strong within V, where π stands for the natural continuous
homomorphism ΩA U → ΩA V.2
Proof. Let u, v ∈ ΩA U be such that the V-pseudoidentity π(u) = π(v) holds
in the pseudovariety JΓ′ KV = JΓKU. Then, the U-pseudoidentity u = v holds
in the pseudovariety JΓKU . Since we assume that Γ is h-strong within U, it
follows that there is a proof of the pseudoidentity u = v from Γ. Projecting
by π into ΩA V all steps in such a proof, we obtain a proof of π(u) = π(v)
from Γ′ ; more precisely, one may easily prove by induction on the ordinal α

that (π × π)(Γα ) ⊆ Γ′α . Hence, Γ′ is h-strong within V.
Going in the opposite direction is more interesting, but requires an additional assumption.
Proposition 4.2. Let U be a pseudovariety and let V be a subpseudovariety
of U. Suppose that V admits a basis Σ of U-pseudoidentities that is h-strong
within U and consists of t-strong pseudoidentities. Let Γ be a set of Upseudoidentities such that JΓKU ⊆ V. If the set Γ′ = {π(u) = π(v) : (u =
v) ∈ Γ} is h-strong within V, where π is as above, then the set Γ is h-strong
within U.
2Here, we should write π instead of π, since all finite sets of variables may need to
A
be considered. Nevertheless, since the set A will usually be clear from the context, most
often we abuse notation by writing simply π independently of the generating set A.

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

9

Proof. Let u = v be a U-pseudoidentity valid in the pseudovariety JΓKU .
This means that the V-pseudoidentity π(u) = π(v) holds in JΓ′ KV as JΓKU ⊆
V = JΣKU. Since Γ′ is h-strong within V, π(u) = π(v) is provable from Γ′ .
We need to show that u = v is also provable from Γ. We first claim that
there are u′ and v ′ such that u′ = v ′ is provable from Γ, π(u′ ) = π(u), and
π(v ′ ) = π(v). Before proving the claim, we show how it allows us to conclude
the proof of the proposition. Since Σ is h-strong within U, it follows that Σ
proves u′ = u and v ′ = v. On the other hand, since the pseudovariety JΓK
is contained in V, it satisfies all pseudoidentities from Σ and, as these are
assumed to be t-strong, they are provable from Γ. Hence, Γ proves u′ = u,
v ′ = v and, assuming the claim, also u′ = v ′ , which entails that Γ proves
u = v. Thus, it remains to establish the claim.
Consider the sets Γ′α defined in Section 3. The proof will be complete once
we establish the above claim that every pseudoidentity in Γ′α is of the form
π(w) = π(z) for some pseudoidentity w = z provable from Γ. To prove the
claim, we proceed by transfinite induction on α.
In case α = 0, we have a pseudoidentity of the form


(1)
t ϕ(π(w)), π(s1 ), . . . , π(sn ) = t ϕ(π(z)), π(s1 ), . . . , π(sn ) ,
where t is a term, w = z is a pseudoidentity from Γ, say over the set
of variables B, ϕ : ΩB V → ΩA V is a continuous homomorphism, and
s1 , . . . , sn ∈ ΩA U. By the universal property of relatively free profinite algebras, there is a continuous homomorphism ψ : ΩB U → ΩA U such that the
following diagram commutes:
ΩB U

ψ

/ ΩA U

πB



ΩB V

πA
ϕ


/ ΩA V

It follows that the pseudoidentity (1) is obtained from
t(ψ(w), s1 , . . . , sn ) = t(ψ(z), s1 , . . . , sn )
by applying π to each member, which completes the basic step α = 0 of the
induction.
Suppose next that α = 2β+1 and that the pseudoidentities wi = wi+1 (i =
′
∈
0, . . . , k − 1) belong to Γ′2β . By induction hypothesis, there exist wi′′ , wi+1
′′
′
′
ΩA U such that the pseudoidentity wi = wi+1 is provable from Γ, π(wi ) =
′′ ) = w
′
′′
wi , and π(wi+1
i+1 . In particular, we have π(wi ) = wi = π(wi ) for
i = 1, . . . , k − 1, and so each pseudoidentity wi′ = wi′′ is also provable from Γ.
Hence, w0 = wk is provable from Γ.
For the case α = 2β+2, consider a sequence (wn = zn )n of U-pseudoidentities such that each π(wn ) = π(zn ) belongs to Γ′2β+1 and suppose that
(π(wn ) = π(zn ))n converges to π(w) = π(z). By compactness and continuity
of π, we may as well assume that (wn = zn )n converges to w = z. Since each
pseudoidentity wn = zn is provable from Γ by induction hypothesis, w = z is
also provable from Γ.
Since the case of limit ordinals is trivial, the transfinite induction is complete and the claim is established.


10

J. ALMEIDA AND O. KLÍMA

With essentially the same arguments, one may replace the t-strongness
hypothesis by provability of Σ from Γ, which yields the following corollary.
Corollary 4.3. Let U be a pseudovariety and let V be a subpseudovariety
of U. Suppose that V admits a basis of U-pseudoidentities Σ that is h-strong
within U and that V is strong. Then every set of U-pseudoidentities from
which Σ is provable is h-strong within U.

5. Locally finite sets of identities
Recall that a variety is locally finite if all its finitely generated algebras
are finite. We also say that a set Σ of identities is locally finite if it defines
a locally finite variety.
Theorem 5.1. Every locally finite set of identities is h-strong.
Proof. Consider a set Σ of identities that is locally finite. Let A be a finite
set and let π : ΩA U → ΩA JΣK be the natural continuous homomorphism.
For each of the finitely many elements s of ΩA JΣK choose an element f (s)
of ΩA U such that π(f (s)) = s. Let f˜ = f ◦ π and note that, since π is
continuous, so is f˜.
For u ∈ ΩA U, consider the identity u = f˜(u). Since π(u) = π ◦ f ◦ π(u) =
π(f˜(u)), it is valid in the pseudovariety JΣK. As the basis Σ is locally finite,
it is also valid in the variety [Σ]. By the completeness theorem for equational
logic, it follows that the identity u = f˜(u) is algebraically provable from Σ.
Finally, consider an arbitrary pseudoidentity u = v with u, v ∈ ΩA U and
suppose that it is valid in JΣK, that is, π(u) = π(v). Let (un )n and (vn )n be
sequences in ΩA U converging respectively to u and v. Since π is continuous
and ΩA JΣK is a discrete space, we may as well assume that the sequences
(π(un ))n and (π(vn ))n are constant. It follows that each of the identities un =
vn is valid in JΣK, whence the equality f˜(un ) = f˜(vn ) holds. By the preceding
paragraph, we deduce that the identities un = f˜(un ) = vn are algebraically
provable from Σ. Hence, the pseudoidentity u = v is, sidewise, the limit of
the sequence (un = vn )n of algebraically provable pseudoidentities, which
shows that u = v is provable from Σ, thereby establishing that Σ is hstrong.

For a locally finite set of identities, we may take any basis of a variety
generated by a single finite algebra. A classical example of locally finite
identity for semigroups which is not of this type is x2 = x (see, for instance,
[29]).
Along the same lines of the proof of Theorem 5.1, we may prove the
following result.
Theorem 5.2. Every locally finite set of identities defines a strong pseudovariety.
Proof. Let V be the pseudovariety defined by a locally finite set Σ of identities
and let V be the variety defined by Σ. Let Γ be a set of V-(pseudo)identities
and let u, v ∈ ΩA V = ΩA V be such that the identity u = v is valid in JΓK.
Since V is generated by V, whence also [Γ] is generated by JΓK, it follows

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

11

that the variety [Γ] also satisfies the identity u = v. By the completeness
theorem for equational logic, we deduce that u = v is provable from Γ. 
Combining Theorem 5.1 and 5.2 with Corollary 4.3, we obtain the following result.
Corollary 5.3. Every set of pseudoidentities which proves a locally finite
set of identities is h-strong.

It would be nice to replace the provability assumption in Corollary 5.3
by the hypothesis that the given set of pseudoidentity is locally finite. This
would follow from Corollary 4.3 if we could show that every identity is tstrong, which is a particular case of the conjecture which have not established
in general.
6. T-strongness
The main proposition of this section gathers the statement of t-strongness
of several pseudoidentities. Some of these results play a role in the application of Proposition 4.2 in later sections.
We start with a simple lemma which is used in several points in the sequel.
Lemma 6.1. If xα = xβ is a nontrivial one-variable M-pseudoidentity, then
it proves the pseudoidentity xα = xα+ω .
Proof. Suppose first that β is either infinite or finite and greater than α. In
this case, we can write the given pseudoidentity in the form xα = xα xβ−α
which proves algebraically xα = xα x(β−α)n! for every positive integer n.
Taking the limit as n goes to infinite, we deduce that xα = xβ proves xα =
xα x(β−α)ω = xα+ω .
If the initial assumption on β fails, then it holds when we interchange the
roles of α and β. By the above, we deduce that, in that case, xα = xβ proves
xβ = xβ+ω and, therefore, also xα = xβ = xβ xω = xα xω = xα+ω .

The following finite semigroups play a role below:
• Sl2 stands for the two-element semilattice;
• for positive integers m and n, let B(m, n) denote the rectangular
band m × n, consisting of the pairs (i, j) with 1 ≤ i ≤ m and 1 ≤
j ≤ n, where multiplication is described by (i, j)(k, ℓ) = (i, ℓ);
• for positive integers m and n, let Cm,n = ha : am = am+n i be the
monogenic semigroup with m+n−1 elements and maximal subgroup
with n elements;
• for a positive integer n, let Cn be the cyclic group of order n;
• B2 is the five-element aperiodic Brandt semigroup, which is given by
the presentation
ha, b; aba = a, bab = b, a2 = b2 = 0i
as a semigroup with zero;
• N is the semigroup with zero given by the presentation
ha, b; a2 = b2 = ba = 0i;
• T is the semigroup with zero given by the presentation
he, a; e2 = e, ea = a, ae = 0i.

12

J. ALMEIDA AND O. KLÍMA

We say that two sets of U-pseudoidentities are equivalent if every pseudoidentity from each of them is provable from the other set. Another simple
result that is useful below is the following lemma.
Lemma 6.2. Let Γ be a set of pseudoidentities and suppose that Γ is equivalent to a single pseudoidentity ε. If each pseudoidentity in Γ is t-strong,
then so is ε.
Proof. Let Σ be a set of pseudoidentities and suppose that JΣK satisfies ε.
From the equivalence hypothesis, it follows that JΣK satisfies each pseudoidentity γ from Γ. Since γ is t-strong, we deduce that Σ proves γ. By the
equivalence hypothesis again, we conclude that Σ proves ε.

We are now ready for the announced proposition.
Proposition 6.3. Each of the following pseudoidentities is t-strong:
(i) xω = 1;
(ii) xω+1 = x;
(iii) xω+1 = xω ;
(iv) (xω y)ω xω = (xω y)ω ;
(v) (xω y)ω = (yxω)ω ;
ω
(vi) (xy)ω x(xy)ω = (xy)ω ;
(vii) (xy)ω x(xy)ω = (xy)ω ;
(viii) ((xy)ω x)ω = (xy)ω ;
(ix) (xy)ω = (yx)ω ;
(x) (xy)ω x = (xy)ω ;
(xi) xω y = yxω ;
(xii) (xy)ω x = x.
Proof. For simplicity, we may refer to one of (i)–(xii) as meaning either a
part of the proposition or the pseudoidentity in it; which is the case should
be clear from the context.
Let Σ be a set of pseudoidentities. Except in the case of (xii), where we
should take S-pseudoidentities to get a pseudoidentity that is not equivalent
to xω = 1, we assume that the elements of Σ are M-pseudoidentities. For
each of the pseudoidentities ε in the statement of the proposition, we assume
that the pseudovariety JΣK satisfies ε and show that Σ proves ε.
(i) Since all finite semigroups satisfying Σ are groups, in particular Sl2
fails some pseudoidentity u = v from Σ, which means that there is some
variable that occurs in one of the sides but not in the other. Substituting xω
for that variable and 1 for all others, we conclude that xω = 1 is algebraically
provable from Σ.
1 fails (ii), it must fail some pseudoidentity u = v
(ii) Since the monoid C2,1
from Σ under some suitable evaluation. If such an evaluation gives the values
0 and 1 for u and v, then u and v do not involve the same variables, so that,
substituting xω for one variable and 1 for all others, one gets xω = 1, from
which (ii) follows. Otherwise, one of the sides, say u, is evaluated to a and
the other to either 0 or 1. Substituting 1 for all variables in u that are not
evaluated to a and x for every other variable, we obtain a pseudoidentity of
the form x = xα , with α ∈ N̂ \ {1}. By Lemma 6.1, each such pseudoidentity
proves (ii).

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

13

(iii) Each of the cyclic groups of prime order fails the pseudoidentity (iii).
For a pseudoword w and a variable x, let wx be the pseudoword that is
obtained from w by substituting 1 for every variable except x. Since the
cyclic group Cp satisfies a pseudoidentity u = v if and only if, for every
variable x, it satisfies the pseudoidentity ux = vx , it follows that, if Cp
fails Σ, then there is αp ∈ N̂ \ N = Ẑ such that p does not divide αp and Σ
proves xαp = xω .
Let α be a greatest common divisor of the αp , which is a limit of a sequence
of linear combinations of the αp . Since each prime p does not divide αp , it
cannot divide α. Hence, α is invertible P
in the ring Ẑ and there exists β ∈ Ẑ
n
γ
ω
such that αβ = ω + 1. Now, if γ =
i=1 γi αpi , then Σ proves x = x
by raising both sides of each pseudoidentity xαpi = xω to the γi power and
multiplying the results side by side. The pseudoidentity xα = xω is therefore
a limit of pseudoidentities provable from Σ, and whence it is provable from Σ.
Finally, raising both sides of xα = xω to the β power, we deduce that the
pseudoidentity (iii) is provable from Σ.
(iv) As it is easy to see, and well known, B(1, 2)1 fails a pseudoidentity
u = v if and only if, from right to left, the order of first occurrences of
variables in u and v is not the same. In particular, the monoid B(1, 2)1
fails (iv) and, therefore, it fails some pseudoidentity from Σ. Hence, there
is a substitution that sends all variables but two to 1 that yields from some
pseudoidentity in Σ a two-variable pseudoidentity of the form ux = vy, where
x and y are distinct variables, or a nontrivial pseudoidentity u = 1 or 1 = u.
In the latter case, by substituting all the variables by xω , we conclude that
Σ proves xω = 1 and, hence, every pseudoidentity in which both sides are
products of ω powers, as is the case of (iv). Thus, it remains to consider the
former case. Applying the substitution x 7→ xω and y 7→ xω y and raising
both sides to the ω power, we conclude that Σ proves the pseudoidentity (iv).
(v) Noting that the sets of pseudoidentities {(xω y)ω xω = (xω y)ω , xω (yxω )ω =
(yxω )ω } and {(xω y)ω = (yxω )ω } are equivalent, in view of (iv) and its dual,
it suffices to apply Lemma 6.2.
(vi) The evaluation of x to a and y to b shows that the monoid B21 fails the
pseudoidentity (vi). Hence, there is some pseudoidentity u = v from Σ and
an evaluation of the variables in B21 which yields different values for u and v.
A variable being assigned the value 1 corresponds to deleting that variable.
For all other values in B21 , since B2 is generated by {a, b} as a semigroup,
we may first substitute the variable by a word in the variables x and y and
then evaluate x to a and y to b. Thus, under the assumption that B21 fails
u = v, we conclude that there is a pseudoidentity u′ = v ′ in x and y that
can be proved from Σ and which fails in B21 under the evaluation x 7→ a and
y 7→ b. Under such an evaluation, not both sides are evaluated to 0. If one of
the sides is 1 then, substituting x for y, we get a pseudoidentity of the form
xα = 1, which proves xω = 1 and, therefore, also the pseudoidentity (vi).
Otherwise, one of the sides of the pseudoidentity u′ = v ′ , say u′ , must be a
factor of (xy)ω while v ′ either admits x2 or y 2 as a factor or does not start
or end with the same letter as u′ . By multiplying both sides of u′ = v ′ by
suitable factors of (xy)ω , we may prove from u′ = v ′ a pseudoidentity u′′ = v ′′
of the form (xy)ω = w where w is a pseudoword that admits at least one of

14

J. ALMEIDA AND O. KLÍMA

the words x2 and y 2 as a factor, starts with x and ends with y. Substituting
(xy)ω x for x and y(xy)ω for y, we obtain from u′′ = v ′′ a pseudoidentity of
the form
(2)

(xy)ω = (xy)α x(xy)β w

or of the form
(3)

(xy)ω = (xy)α y(xy)β w,

where α and β are infinite exponents and w is some pseudoword. From the
pseudoidentity (2), we may prove, algebraically,
n!
n!
(xy)ω = (xy)α x · (xy)ω · (xy)β w = · · · = (xy)α x (xy)ω (xy)β w
and so, taking limits, also
ω
ω
(xy)ω = (xy)α x (xy)ω (xy)β w
ω
which entails (xy)ω = (xy)α x(xy)ω . Similarly, from
ω−1
(xy)α · (xy)ω · x(xy)ω ,
(xy)ω = (xy)α x(xy)ω
concentrating on the rightmost factor, we may deduce the desired pseudoidentity (vi). If we start from the pseudoidentity (3) instead
of (2), we
ω
reach similarly the pseudoidentity (xy)ω = (xy)ω y(xy)ω . Interchanging
ω
x and y, we obtain (yx)ω = (yx)ω x(yx)ω . Multiplying both sides on the
left by x and on the right by y(xy)ω−1 , and rearranging the right hand side
(using equalities valid in M) yields the pseudoidentity (vi).
(vii) First note that (vii) proves (vi) by simply raising both sides to
the ω power; it also proves (iii) by substituting y by x and using equalities that are valid in M. Conversely, from (vi), using (iii), we deduce that
ω
ω+1
= (xy)ω y(xy)ω = (xy)ω . It remains
(xy)ω x(xy)ω = (xy)ω x(xy)ω
to apply Lemma 6.2 and the above.
(viii) The
x 7→ xω transforms (viii) into the pseudoidentity
ω substitution
ω
ω
ω
ω
(x y) x
= (xy) . Since (xω y)ω xω is an idempotent, this shows that
(viii) proves (iv). Similarly, upon multiplication of both sides of (viii) on the
right by (xy)ω , we conclude that (viii) proves (vi). In view of the above and
Lemma 6.2, it remains to establish that, together, the pseudoidentities (iv)
and (vi) prove(viii). Indeed, the substitution
x 7→ (xy)ω x, y 7→ (xy)ω in (iv)
ω
ω
ω
ω
ω
. Combining the latter pseudoidentity
gives (xy) x = (xy) x(xy)
with (vi), by transitivity we obtain (viii).
(ix) Note first that (ix) proves the pseudoidentities
(xy)ω = (yx)ω = y(xy)ω−1 · (xy)ω · (xy)ω x.
n!
n!
Hence, (ix) proves (xy)ω = y(xy)ω−1 · (xy)ω · (xy)ω x ; by taking limω
ω
and, therefore, (ix)
its, we get (xy)ω = y(xy)ω−1 · (xy)ω · (xy)ω x
proves (viii). Since (ix) is its own left right dual,
(ix)
also proves the
ω
ω
= (yx)ω . Conversely,
dual of (viii), namely the pseudoidentity x(yx)
from (viii) and its dual, we may prove
ω
ω
(xy)ω = y(xy)ω = (yx)ω y = (yx)ω .
Taking into account previous parts of the proposition, it suffices to invoke
Lemma 6.2.

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

15

(x) Substituting y by x in the pseudoidentity (x) yields (iii) while, raising
both sides to the ω power we obtain (viii). Once again, in view of Lemma 6.2,
it suffices to show that, together, (iii) and (viii) also prove (x) which can be
done as in proof of (vii):
ω
ω
(xy)ω = (xy)ω x = (xy)ω x (xy)ω x = (xy)ω (xy)ω x = (xy)ω x.
(xi) Raising both sides of (xi) to the ω power, we obtain (v) and so Σ
proves (v). On the other hand, the monoid T 1 and its left right dual fails the
pseudoidentity (xi). Hence, each of them fails some pseudoidentity from Σ.
Let us consider first the fact that T 1 fails some pseudoidentity from Σ.
As in earlier arguments, we deduce that Σ proves either the pseudoidentity
x = xω+1 or a two-variable pseudoidentity of the form xω y = w, where w is a
pseudoword that admits yx as a factor. If y occurs more than once in w then,
substituting x by 1, we get a nontrivial pseudoidentity y = y α , which entails
x = xω+1 by Lemma 6.1. Hence, Σ proves either x = xω+1 or xω y = xω yxω .
Working instead with the dual of the monoid T 1 , we deduce dually that Σ
proves either x = xω+1 or yxω = xω yxω .
Suppose first that Σ proves x = xω+1 . Since Σ also proves (v), it proves
the following pseudoidentities:
xω y = (xω y)ω+1 = xω (yxω )ω y = xω (xω y)ω y = (xω y)ω y = (yxω )ω y.
Dually, Σ proves yxω = y(xω y)ω and so also (xi). Thus, we may assume
that Σ does not prove x = xω+1 . From the above, it follows that Σ proves
xω y = xω yxω = yxω , as required.
(xii) Substituting y by x in (xii), we obtain the pseudoidentity (ii). On
the other hand, since Sl2 fails (xii), it also fails some pseudoidentity from Σ,
and so there is some variable z that occurs only on one side of that pseudoidentity. Substituting xω yxω for z and xω for every other variable, we
conclude that Σ proves a pseudoidentity of the form (xω yxω )α = xω and
so also the special case where α = ω, which may be written in the form
(xω y)ω xω = xω . Substituting xy for y, multiplying both sides on the right
by x, and using additionally the pseudoidentity xω+1 = x, we obtain the
required pseudoidentity (xii).

The choice of the monoids and semigroups considered in the proof of
Proposition 6.3 was guided by several results in the literature, even though
such results are not explicitly used in the proof. For a pseudoidentity ε, we
essentially take a complete set of excluded monoids, that is, a set of finite
monoids such that a pseudovariety V satisfies ε if and only if contains none of
the monoids from the set. Such sets can be found in the literature for several
pseudoidentities. See [2] for further details. It should be noted that the proof
of Proposition 6.3 in fact implies that the sets in question are complete sets
of excluded monoids.
7. H-strongness: the role of reducibility
In this section, we consider a method that allows us to give a class of
examples of h-strong sets of pseudoidentities. In all of them, the key property
of the pseudovariety V = JΣK is that every pseudoidentity u = v valid in V is
the limit of a sequence of identities in a suitable implicit signature σ which

16

J. ALMEIDA AND O. KLÍMA

are also valid in V. In this case we say that the pseudovariety V is σ-reducible
for the equation x = y.
In terms of formal proofs, the above property reduces the conjecture for Σ
to proving from Σ the σ-identities which are valid in V. If, additionally,
one knows a basis Σ′ of identities for the variety Vσ , all that is needed is to
show that Σ′ is provable from Σ. In summary, we have the following simple
observation which provides a method of proof that underlies all the examples
in the remainder of the section.
Proposition 7.1. Let σ be an implicit signature and let Σ be a set of Upseudoidentities defining a σ-reducible pseudovariety V for the equation x =
y. If the variety Vσ admits a basis whose identities are provable from Σ, then
Σ is h-strong.

We apply below Proposition 7.1 to the usual bases of pseudoidentities of
several extensively studied pseudovarieties of semigroups. Before doing so,
it is worth explaining why we use the above terminology introduced in [13]
that has been widely adopted in the literature. This connection needs to
be clarified in order to justify invoking several published results that are
required in our application of Proposition 7.1.
As above, fix an ambient pseudovariety U. We also consider a subpseudovariety V of U. By a system of equations we mean a set S whose elements
u = v are formal equalities (that is, pairs) of terms in the algebraic signature
of U. Let X be the set of variables that occur in S, a set which, for simplicity,
we assume to be finite. We are interested in V-solutions of S on a fixed but
arbitrary finite set of generators A, which consist of a mapping assigning to
each variable x ∈ X an element ϕ(x) of ΩA U whose natural extension ϕ̂ to
terms is such that V satisfies each pseudoidentity ϕ̂(u) = ϕ̂(v) with u = v
a member from S. Such systems are often constrained by assigning to each
variable x ∈ X a clopen subset Kx of ΩA U. The V-solution ϕ is said to
satisfy the constraints if ϕ(x) ∈ Kx for every x ∈ X.
The key property of the pseudovariety V introduced in [13] is the following.
Let σ be an implicit signature, each of whose elements belongs to some
ΩB U, where B is a finite set. We say that V is σ-reducible for S if, for
every choice of constraints for X, if there is a V-solution of S satisfying the
constraints, then there is such a solution taking its values in ΩσA U, which
we call a (V, σ)-solution. Since the clopen sets form a basis of the topology
of ΩA U, one immediately recognizes the following result which is nothing
but a topological reformulation of the definition of reducibility. For that
purpose, we view solutions of the system S as elements of the product space
(ΩA U)X .
Proposition 7.2. The pseudovariety V is σ-reducible for the system of equations S over the set of variables X if and only if the set of (V, σ)-solutions
is dense in the set of all V-solutions.

In particular, the terminology adopted at the beginning of the section is
consistent with that from [13].

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

17

The property of σ-reducibility of a pseudovariety V was conceived as part
of a strong form of decidability called σ-tameness. The remaining requirements for σ-tameness are computability assumptions, namely: the pseudovariety V is assumed to be recursively enumerable, the signature σ also
recursively enumerable and to consist of operations that are computable in
elements of V, and the word problem in ΩσA V is supposed to be decidable.
The computability assumptions on the pseudovariety V and the implicit signatures considered in all our examples are immediately verified.
It should be pointed that the word problem in ΩσA V is equivalent to the
variety Vσ to admit a recursive basis of identities. Besides σ-reducibility
for the identity x = y, it is the knowledge of such a basis that underlies all
our applications of Proposition 7.1. Thus, our results rely more properly on
σ-tameness of V rather than just σ-reducibility for the identity x = y.
We are now ready to present our concrete examples of evidence for the
conjecture obtained as applications of Proposition 7.1. In the following, the
ambient pseudovariety U will be either the pseudovariety S of all finite semigroups or the pseudovariety M of all finite monoids. The implicit signatures
involved are often either κ = {_·_, _ω−1 } or {_·_, _ω } the latter of which,
by abuse of notation, we also denote ω.
7.1. Some simple examples. Our first example is given by the pseudoidentity xω+1 = xω , which defines the pseudovariety A of all finite aperiodic
monoids. In view of Schützenberger’s characterization of star-free languages
[37], this is a very important pseudovariety.
Theorem 7.3. For U = M, the pseudoidentity xω+1 = xω is h-strong.
Proof. The first key ingredient here is that the pseudovariety A is ω-reducible
for the equation x = y. This is proved in [10, Corollary 3.2] based on
Henckell’s algorithm for the computation of A-pointlike sets of finite monoids
[27, 28].
The second key ingredient is a basis of identities for the variety Aω obtained by McCammond [31, 9]. It consists of the following identities:
(xy)z = x(yz), x1 = 1x = x
(xω )ω = (xr )ω = xω xω = xω (r ≥ 2)
(xy)ω x = x(yx)ω
xω x = xxω = xω
Except for the identities in the last line, which are immediately provable
from xω+1 = xω , all the other identities are valid in all finite monoids and so
they require no proof in our proof setup within the ambient pseudovariety M.
Applying Proposition 7.1, we conclude that the pseudoidentity xω+1 = xω is
h-strong.

Our next example is the usual basis of the pseudovariety R of all finite
R-trivial monoids.
Theorem 7.4. For U = M, the pseudoidentity (xy)ω x = (xy)ω is h-strong.
Proof. The ω-reducibility of R for the equation x = y was first proved in [7].
In fact, the same holds for arbitrary systems of ω-equations [8]. The following

18

J. ALMEIDA AND O. KLÍMA

basis of identities for the variety Rω was obtained in [17]:
(xr )ω = (xω )ω = xω (r ≥ 2)
(xy)z = x(yz), x1 = 1x = x
(xy)ω = (xy)ω x = (xy)ω xω = x(yx)ω .
Of all the above identities the only one that is not obviously provable from
(xy)ω x = (xy)ω is (xy)ω xω = (xy)ω . Yet, iterating the hypothesis, one gets
(xy)ω xn! = (xy)ω , whence also (xy)ω xω = (xy)ω by taking limits.

While the two previous examples could be reformulated in the language
of semigroups, as the pseudovariety of semigroups generated in each case has
no additional monoids, for the next one the monoids in the pseudovariety
constitute a much smaller class. Indeed, we now consider the pseudovariety LSl of all finite semigroups which are locally semilattices, that is, the
pseudovariety defined by the set in the following result.
Theorem 7.5. For U = S, the set of pseudoidentities
Σ = {xω yxω zxω = xω zxω yxω , xω yxω yxω = xω yxω }
is h-strong.
Proof. The ω-reducibility of LSl for the equation x = y was first proved
in [24], where graph systems of equations are also considered.3 The following
basis of identities for the variety LSl may be found in [21]:
(xr )ω = xω xω = xω x = xω (r ≥ 2)
(xy)z = x(yz), (xy)ω x = x(yx)ω
xω yxω zxω = xω zxω yxω , xω yxω yxω = xω yxω
(xy ω z)ω = (xy ω z)2 .
Of all the above identities, the only one that requires a proof from Σ is the
last one. We first note that the second pseudoidentity from Σ immediately
infers (xy ω z)3 = (xy ω z)2 , which entails (xy ω z)n+1 = (xy ω z)n for every
n ≥ 2, whence also (xy ω z)n! = (xy ω z)2 . Taking limits, we may further
prove (xy ω z)ω = (xy ω z)2 . In view of Proposition 7.1, this concludes the
proof of the theorem.

7.2. Monoids in which regular elements are idempotents. The next
example is given by two simple bases of pseudoidentities for the pseudovariety DA of all finite semigroups whose regular D-classes are aperiodic subsemigroups, a property which is equivalent to all regular elements being
idempotents.
Theorem 7.6. For U = M, the sets of pseudoidentities
Σ = {xω+1 = xω , (xy)ω (yx)ω (xy)ω = (xy)ω }
Γ = {((xy)ω x)2 = (xy)ω x}
3Later, reducibility of LSl was extended to arbitrary systems of κ-equations [22]. In

view of the well-known decomposition LSl = Sl ∗ D (see, for instance, [2, Section 10.8]), a
generalization in a different direction has been obtained in [23] where, in particular, it is
proved that if V is κ-reducible for the equation x = y, then so is V ∗ D. This was later
extended to the case of graph systems of equations in [25].

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

19

are h-strong.
Proof. The ω-reducibility of DA for the equation x = y has been proved
in [10]. The following basis of identities for DAω has been recently obtained [11]:
(xr )ω = (xω )ω = xω (r ≥ 2);
(xy)ω x = x(yx)ω ;
(xy)z = x(yz), x1 = 1x = x
uω vuω = uω ,
where u, v ∈ ΩB U for an arbitrary finite alphabet B and every variable that
occurs in v also occurs in u. Only the family of identities in the last line
requires a proof since the others are valid in every finite monoid.
We start by showing that Σ proves Γ. We may prove algebraically:
(xy)ω = (xy)ω (yx)ω (xy)ω = (xy)ω (yx)ω+1 (xy)ω
= (xy)ω y · (xy)ω · x(xy)ω = · · · = ((xy)ω y)n! (xy)ω (x(xy)ω )n! .
Taking limits, we get
(xy)ω = ((xy)ω y)ω (xy)ω (x(xy)ω )ω

(4)

which, upon multiplication of both sides on the right by x(xy)ω x, yields
((xy)ω x)2 = ((xy)ω y)ω (xy)ω (x(xy)ω )ω+1 x
= ((xy)ω y)ω (xy)ω (x(xy)ω )ω x = (xy)ω x.
(4)

Conversely, we may algebraically prove Σ from Γ as follows. First, substituting x for y in the pseudoidentity ((xy)ω x)2 = (xy)ω x and multiplying
both sides by xω−1 , we obtain
xω+1 = xω−1 ((xx)ω x)2 = xω−1 (xx)ω x = xω .
Also, multiplying both sides of the pseudoidentity from Γ on the right by
y(xy)ω−1 yields
(xy)ω x(xy)ω = (xy)ω .

(5)
Next, we obtain

(xy)ω = (xy)ω−1 xy(xy)ω = (xy)ω−1 x(yx)ω y = (xy)ω−1 x(yx)ω y(yx)ω y
(5)

= (xy)ω (yx)ω y = (xy)ω y(xy)ω ,
and so
(xy)ω y(xy)ω = (xy)ω ,

(6)
which entails

(xy)ω = (xy)ω y(xy)ω = (xy)ω y(xy)ω x(xy)ω
(6)

(5)

ω

ω+1

= (xy) (yx)

(xy)ω = (xy)ω (yx)ω (xy)ω .

From hereon, we are thus allowed to use Σ ∪ Γ as hypothesis in our proofs
and we assume them without further mention. Recall that our objective is
to prove that every ω-identity of the last form uω vuω = uω under the above
assumptions on u and v. Since u and v may expressed as limits of sequences

20

J. ALMEIDA AND O. KLÍMA

of words with constant content, we may as well assume that both u and v
are words.
To simplify the notation we let e = uω . We claim that the following
statements hold:
(i) if ewe = e may be proved, then ew2 e = e may also be proved;
(ii) if eve = e = ewe may be proved, then evwe = e may also be proved;
(iii) the pseudoidentity (xyz)ω y(xyz)ω = (xyz)ω is provable.
To establish (i), assume that we have proved ewe = e. Then we may also
prove ew = ewew = · · · = (ew)n and, taking limits, ew = (ew)ω = (ew)ω−1 .
Similarly, we can prove we = (we)ω . This yields the following equalities:
e = ewe = (ew)ω e = (ew)ω (we)ω (ew)ω e = ewweewe = ew2 e.
For (ii), suppose we have proved eve = e = ewe. Then, in view of (i), we
may prove
e = ee = eweeve = e · wev · e = e · wev · wev · e = evwe.
To prove (iii), observe first that, from (5) and (6) we deduce that the pseudoidentities
(yzx)ω = (yzx)ω yz(yzx)ω = (yzx)ω y(yzx)ω = (yzx)ω x(yzx)ω
are provable, so that, by (ii), so are (yzx)ω = (yzx)ω yx(yzx)ω and
(xyz)ω = (xyz)ω+1 = x(yzx)ω yz = x(yzx)ω yzyx(yzx)ω yz
= (xyz)ω+1 y(xyz)ω+1 = (xyz)ω y(xyz)ω .
Let v = v1 · · · vn , where the vi are letters. By (iii) since every letter appearing
in v also appears in u, we may prove evi e = e (i = 1, . . . , n). Applying (ii)
n − 1 times, we deduce that we may also prove eve = e, as required.

7.3. J -trivial monoids. The next example consists of the two bases commonly used to describe the pseudovariety J of all finite J -trivial semigroups.
Theorem 7.7. For U = M, the sets of pseudoidentities
Σ = {xω+1 = xω , (xy)ω = (yx)ω } and Γ = {(xy)ω x = (xy)ω = y(xy)ω }
are h-strong.
Proof. It is not difficult to show that J is ω-reducible for the equation x = y.
In fact, J is ω-reducible for all finite systems of equations, and even of κequations [4, Theorem 12.3]. On the other hand, the following basis of
identities for the variety Jω is given in [2, Section 8.2]:
(xy)z = x(yz), x1 = 1x = x, (xω )ω = xω
xω x = xxω = xω
(xy)ω = (yx)ω = (xω y ω )ω .
The identities in the first line are valid in all finite monoids and, therefore
require no proof. In view of Proposition 7.1, to finish the proof it suffices to
show that the remaining identities are provable from both Σ and Γ.
In the case of Σ, only the identity (xy)ω = (xω y ω )ω needs to be considered.
The following describes a proof from Σ. First, we do an algebraic proof:
(7)

(xy)ω = (xy)ω+1 = x(yx)ω y = x(xy)ω y = · · · = xm (xy)ω y m .

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

21

Hence, we may also prove from Σ
(xy)ω = (yx)ω = y m (yx)ω xm = y m (xy)ω xm ,
which, combined with (7), yields
(xy)ω = xm y m (xy)ω xm y m

(8)

Iterating (8), we get an algebraic proof of (xy)ω = (xm y m )m (xy)ω (xm y m )m .
Letting m = n! and taking limits, we obtain that Σ proves
(xy)ω = (xω y ω )ω (xy)ω (xω y ω )ω .

(9)

Similarly, we may prove algebraically
(xω y ω )ω = xω y ω (xω y ω )ω = xxω y ω (xω y ω )ω = x(xω y ω )ω
and so also
(xω y ω )ω = xy(xω y ω )ω = · · · = (xy)n! (xω y ω )ω .
Taking limits, we get (xω y ω )ω = (xy)ω (xω y ω )ω . Combining with (9) and
taking into account that (xω y ω )ω is idempotent, we finally complete the
proof of (xy)ω = (xω y ω )ω from Σ.
For Γ, we first note that, substituting x for y in (xy)ω x = (xy)ω , yields
ω+1
x
= xω . Hence, it suffices to show that the pseudoidentity (xy)ω = (yx)ω
is provable from Γ, which can be established algebraically:
(xy)ω = y(xy)ω = (yx)ω y = (yx)ω . 
Note that, in the proof of Theorem 7.7, we alternated several times topological and transitive closure. More precisely, we actually proved that Σ̃ =
Σ4 . We do not know whether Σ̃ = Σ3 but show below that Σ̃ 6= Σ2 .
We start with an auxiliary lemma involving equidivisibility. We say that a
semigroup S is equidivisible if any two factorizations of the same element admit a common refinement [32]. We say that a pseudovariety (of semigroups
or monoids) V is equidivisible if, for each finite set A, the semigroup ΩA V
is equidivisible. The equidivisible pseudovarieties of semigroups have been
characterized in [6]. The characterization of equidivisible pseudovarieties of
monoids can be derived from it by noting that, for a pseudovariety V of
monoids, ΩA V = (ΩA W)1 , where W is the pseudovariety of semigroups generated by V, which amounts to a simple exercise, together with the obvious
observation that a semigroup S is equidivisible if and only if so is the monoid
S 1 . In particular, M is equidivisible.
The following lemma can surely be generalized but is already sufficient for
our purposes.
Lemma 7.8. Let w ∈ A∗ and u, v ∈ ΩA M be such that wω is a factor of uv.
Then, wω is a factor of at least one of the factors u and v.
Proof. By equidivisibility, from the two factorizations uv = xwω y (for some
x, y ∈ ΩA M), we know that there is a common refinement. Hence, if wω is a
factor of neither u nor v, then there is a factorization wω = zt with u = xz
and v = ty. We reach a contradiction by showing that wω must be a factor
of at least one of z and t.
First note that at least one of z and t is a not a finite word for, otherwise,
so would be wω . By symmetry, we may as well assume that z is not a finite

22

J. ALMEIDA AND O. KLÍMA

word. We claim that wn is a prefix of z for every n ≥ 1 and, therefore, so is
wω , thereby reaching the desired contradiction. To prove the claim, consider
the monoid Mk consisting of all words of A∗ of length at most k = |wn |
where the product is defined by r · s = rs if |rs| ≤ k, while r · s is taken to be
the prefix of rs of length k otherwise. Consider also the unique continuous
homomorphism ϕk : ΩA M → Mk which maps each letter a from A to a as an
element of Mk . Note that ϕk maps each word of length at most k to itself
and every other finite word to its prefix of length k. It follows that ϕk (s) is
a prefix of s for every pseudoword s ∈ ΩA M.
Since z is not a finite word, there is a sequence of words (zm )m converging
to z with |zm | ≥ k for every m. Then, from the equalities ϕk (z) = ϕk (zt) =
ϕk (wω ) = wn , we deduce that wn is a prefix of z, as was claimed.

Proposition 7.9. For U = M and Σ = {xω+1 = xω , (xy)ω = (yx)ω }, we
have Σ̃ 6= Σ2 .
Proof. For the purpose of the present proof, we take A = {x, y}.
We have shown in the proof of Theorem 7.7 that the ω-identity
(10)

(xω y ω )ω = (xy)ω

belongs to Σ3 . We prove that it does belong to Σ2 . For that purpose, we
claim that, if the pseudoidentity w = (xy)ω is in Σ2 , then (xy)ω is a factor
of w. Since not even the word xyx is a factor of (xω y ω )ω (cf. [16, Lemma 8.2]),
we conclude that the pseudoidentity (10) cannot belong to Σ2 .
The hypothesis of the claim implies the existence of a sequence of pseudoidentities (wn = vn )n in Σ1 which converges to w = (xy)ω . Now, by
taking subsequences, we may as well assume that either the sequence (vn )n
consists only of finite words or only of infinite pseudowords. In the first case,
the only Σ1 -pseudoidentity of the form u = vn is the trivial pseudoidentity
vn = vn . Since the pseudoidentity (10) is not trivial over M, the first case is
excluded. In the second case, we note that (xy)ω is a factor of vn for every
sufficiently large n. Indeed, the language (xy)∗ has an open closure in ΩA M
[2, Theorem 3.6.1], which consists of all powers of xy.
Thus, to establish our claim, it suffices to show that, if the pseudoidentity
u = v belongs to Σ1 and the pseudoword (xy)ω is a factor of v then it is
also a factor of u. Since Σ1 is the transitive closure of Σ0 , by a straightforward induction argument it suffices to treat the case where u = v belongs
to Σ0 . Hence, there are a nonempty word t, pseudowords w1 , . . . , wn , a
pseudoidentity u′ = v ′ such that either it or v ′ = u′ belongs to Σ, and
a continuous endomorphism ϕ of ΩA M such that u = t(ϕ(u′ ), w1 , . . . , wn )
and v = t(ϕ(v ′ ), w1 , . . . , wn ). Note that, since u′ and v ′ are J -equivalent,
so are ϕ(u′ ) and ϕ(v ′ ), which means that these two pseudowords have the
same factors. Without loss of generality, we may assume that, writing
t = t(x0 , x1 , . . . , xn ), all the letters xi (i = 1, . . . , n) appear at least once
in t. By Lemma 7.8, we deduce from the assumption that (xy)ω is a factor
of v that it must also be a factor of either ϕ(v ′ ) or one of the wi . Hence,
(xy)ω is a factor of either ϕ(u′ ) or one of the wi and, therefore, also of u. 

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

23

8. The group case
Let G be the pseudovariety of all finite groups. As far as subpseudovarieties
of G are concerned, whether we view groups in the natural signatures for
semigroups, monoids, or groups is irrelevant, since the identity element is
the only idempotent xω and inversion is also captured by the semigroup
pseudoword xω−1 . However, for the purpose of this section, we prefer to deal
with the group signature, consisting of a binary multiplication, a constant
symbol 1, for the identity element, and the unary operation of inversion.
Note that for u, v ∈ ΩA G, each of the pseudoidentities u = v and u−1 v = 1
is provable from the other. Hence, in the language of groups, it suffices to
deal with pseudoidentities of the form w = 1.
For a set Υ of group pseudowords, consider the pseudovariety
HΥ = Ju = 1 : u ∈ ΥK.
Denote by NΥ the subgroup of ΩA G generated by all conjugates of elements
of the form ϕ(u) with B a finite alphabet, u ∈ Υ∩ΩB G, and ϕ : ΩB G → ΩA G
a continuous homomorphism.
Theorem 8.1. Let Υ be a set of group pseudowords. Then, for every w ∈
ΩA G, the pseudovariety HΥ satisfies the pseudoidentity w = 1 if and only if
w belongs to the closure of NΥ in ΩA G.
Proof. Suppose that w ∈ NΥ , say w = lim wn for a sequence (wn )n of elements of NΥ . Now, for each u ∈ Υ ∩ ΩB G and each continuous homomorphism ϕ : ΩB G → ΩA G, the pseudoidentity ϕ(u) = 1 is valid in HΥ , whence
so is gϕ(u)g−1 = 1 for every g ∈ ΩA G. Hence, each pseudoidentity wn = 1
is also valid in HΥ , which entails that so is w = 1.
Conversely, suppose that w ∈ ΩA G is such that HΥ satisfies the pseudoidentity w = 1 but, arguing by contradiction, w does not belong to NΥ .
Since ΩA G is a profinite group, for each v ∈ NΥ there is a clopen normal
subgroup Kv of ΩA G such that
As NΥ is compact, weTmay exS wKv 6= vKv . S
tract a finite covering from v∈NΥ vKv , say ni=1 vi Kvi . Let K = ni=1 Kvi ,
which is a clopen normal subgroup of ΩA G. Finally, let L = NΥ K, which
is again a clopen normal subgroup of ΩA G. Clearly, L contains NΥ and we
claim that it does not contain w. Indeed, if w ∈ L, then there is v ∈ NΥ such
that w ∈ vK. Since the open sets vi Kvi cover NΥ , we deduce that there is
i ∈ {1, . . . , n} such that v ∈ vi Kvi . Hence, we have
w ∈ vK ⊆ vi Kvi K ⊆ vi Kvi ,
which contradicts the choice of Kvi .
Let G be the quotient group ΩA G/L, which is a finite group. Since L
contains NΥ , by the first part of the proof we infer that G ∈ HΥ . Hence, by
hypothesis, G satisfies the pseudoidentity w = 1 which, for the evaluation of
each letter a ∈ A by the coset aL, yields w ∈ L, in contradiction with the

choice of L. It follows that w must belong to NΥ .
Corollary 8.2. The pseudovariety G is strong.
The same method may be applied to show that the pseudovariety of all
finite rings (not necessarily with identity element) is strong.

24

J. ALMEIDA AND O. KLÍMA

Theorem 8.3. For U = M, the pseudoidentity xω = 1 is h-strong.
Proof. The key result upon which the proof is based is the κ-reducibility of
G = Jxω = 1K for the equation x = y. More generally, based on a celebrated
theorem of Ash [18], which contains all the essential hard work, it has been
observed in [13, Theorem 4.9] that G is κ-reducible for all finite graph systems
of equations.4 In view of Proposition 7.1, it remains to show that every κidentity valid in G may be proved from xω = 1 in the sense of Section 3. In
fact, we show that it may be algebraically proved.
The essential observation is that the κ-identity
(xy)ω−1 = y ω−1 xω−1

(11)

may be algebraically proved from xω = 1. Indeed here is a description of
such a proof:
(xy)ω−1 = y ω (xy)ω−1 xω = y ω−1 y(xy)ω−1 xxω−1
= y ω−1 (yx)ω xω−1 = y ω−1 xω−1 .
Note also that (xω−1 )ω−1 = xω+1 = x, where the latter equality is provable
from xω = 1. Applying repeatedly the identity (11), every κ-term may
be rewritten in the form xε11 · · · xεnn , where each xi is a variable and each
exponent εi is either 1 or ω − 1. We say that a κ-term of this type is in
standard form; a κ-identity whose sides are in standard form is also said to be
in standard form. Thus, in the presence of the pseudoidentity xω = 1, every
κ-identity valid in G is algebraically provably equivalent to a κ-identity u = v
in standard form that is also valid in G. Since the free group is residually
finite, u = v may be viewed as a group identity (by removing the ω’s from
the exponents) that is satisfied by all groups, which means that, by applying
the reduction rules aa−1 → 1 and a−1 a → 1 a finite number of times, both
sides may be transformed to the same reduced group word. Since, in the
context of finite monoids, both rules follow from the pseudoidentity xω = 1,
we conclude that u = v is algebraically provable from xω = 1.

Although the next result is superseded by Corollary 9.4, it seems worthwhile to include it at this stage.
Corollary 8.4. For U = M, every set Σ of pseudoidentities defining a group
pseudovariety is h-strong.
Proof. It suffices to apply Proposition 4.2 taking into account Theorem 8.3,
Corollary 8.2, and Proposition 6.3(i).

4By a graph system of equations we mean the system associated with a finite directed
y
graph which, for each edge x −
→ z in the graph, includes the equation xy = z. Now, for G,
every solution of the equation y1 = y2 is a solution of the graph system determined by the

graph x

y1

z and, conversely, every solution of the graph system involves a solution

y2

of the equation y1 = y2 .

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

25

9. The completely simple semigroup case
Let CS be the pseudovariety of all finite completely simple semigroups.
It is defined, for instance, by the pseudoidentity (xy)ω x = x. By a wellknown theorem of Rees, completely simple semigroups are precisely those
that admit a Rees matrix representation M(I, G, Λ, P ), where I and Λ are
sets, G is a group, and P : Λ × I → G is a function (the sandwich matrix,
the image P (λ, i) being usually denoted pλ,i ); as a set, it is the Cartesian
product I × G × Λ, and multiplication is given by the formula
(i, g, λ)(j, h, µ) = (i, gpλ,j h, µ).
Assuming that 1 is a common element of I and Λ, the sandwich matrix may
be supposed to be normalized in the sense that p1,i = pλ,1 = 1 for all i ∈ I
and λ ∈ Λ.
The purpose of this section is to establish that CS is strong. The key
ingredient is the following characterization of the congruences on a Rees
matrix semigroup which may be extracted from [20, Theorem 10.48].
Theorem 9.1. Let S = M(I, G, Λ, P ) be a Rees matrix semigroup and let
ρ be a congruence on S. Consider the relations
ρ1 = {(i, j) ∈ I × I : (i, 1, 1) ρ (j, 1, 1)}
ρ2 = {(λ, µ) ∈ Λ × Λ : (1, 1, λ) ρ (1, 1, µ)}
Nρ = {g ∈ G : (1, g, 1) ρ (1, 1, 1)}.
Then ρ1 (respectively ρ2 ) is an equivalence relation on the set I (resp. Λ)
and N is a normal subgroup of G such that
(12)

(i, j) ∈ ρ1 =⇒ pλ,i Nρ = pλ,j Nρ

(13)

(λ, µ) ∈ ρ2 =⇒ pλ,i Nρ = pµ,i Nρ .

Conversely, for every triple τ = (ρ1 , ρ2 , Nρ ), where ρ1 (resp. ρ2 ) is an equivalence relation on the set I (resp. Λ) and Nρ is a normal subgroup of G,
satisfying properties (12) and (13), the relation


ρτ = (i, g, λ), (j, h, µ) ∈ S × S : i ρ1 j, λ ρ2 µ, gNρ = hNρ
is a congruence on S and every congruence on S is of this form.
We may now proceed as in the proof of Theorem 8.1 to obtain our next
result. For a set Σ of CS-pseudoidentities, consider the closed congruence
ρ = Σ̃ generated by the pairs of the form (ϕ(u), ϕ(v)) with u = v in Σ,
u, v ∈ ΩB CS, and ϕ : ΩB CS → ΩA CS a continuous homomorphism.
Theorem 9.2. The pseudovariety CS is strong.
Proof. Suppose that u, v ∈ ΩA CS are such that the pseudoidentity u = v is
valid in JΣK. We claim that u = v is provable from Σ, which amounts to the
condition u ρ v.
Arguing by contradiction, suppose that (u, v) ∈
/ ρ. By [1], there is an
isomorphism ψ : ΩA CS → S = M(A, ΩX G, A, P ) where, choosing an element
a0 from A and letting A′ = (A \ {a0 })2 be the Cartesian square, we have
X = A ∪ A′ , pa0 ,b = pb,a0 = 1, and pa,b = (a, b) for each (a, b) ∈ A′ . Note

26

J. ALMEIDA AND O. KLÍMA

that the letter a0 plays the role of 1 in the normalization of the sandwich
matrix.
Consider the normal subgroup Nρ and the equivalence relations ρ1 and
ρ2 as defined in Theorem 9.1. Note that Nρ is a closed normal subgroup
of ΩX G.
Let ψ(u) = (a, g, b) and ψ(v) = (c, h, d). Since we are assuming that
(u, v) ∈
/ ρ, at least one of the following conditions must hold:
(a, c) ∈
/ ρ1 , (b, d) ∈
/ ρ2 , gNρ 6= hNρ .
In case one of the first two conditions holds, the mapping from S onto the
rectangular band T = A/ρ1 × A/ρ2 that maps each triple (x, w, y) ∈ S
to (x/ρ1 , y/ρ2 ) is a continuous homomorphism onto a semigroup from CS
that distinguishes u and v. Moreover, its kernel congruence is contained in ρ,
which implies that T ∈ JΣK, contradicting the assumption that JΣK satisfies
u = v. Hence, we may assume that (a, c) ∈ ρ1 and (b, d) ∈ ρ2 , so that gω−1 h
does not belong to Nρ . As in the proof of Theorem 8.1, we deduce that there
is a clopen normal subgroup K of ΩX G such that Nρ ⊆ K and g ω−1 h ∈
/ K.
Since K contains Nρ , the triple (ρ1 , ρ2 , K) still satisfies the analogues of
conditions (12) and (13). Hence, by Theorem 9.1, it defines a congruence ρ̄
on S. Since K has finite index in ΩX G, the congruence ρ̄ has finite index
in S. The reader may easily verify that, since ρ is a closed congruence
on S and K is a closed subgroup of ΩX G, the congruence ρ̄ is still closed,
whence the natural mapping S → S/ρ̄ is a continuous homomorphism. As ρ̄
contains ρ, the quotient semigroup S/ρ̄ satisfies Σ but, by construction, fails
the pseudoidentity u = v. This completes the proof.

We proceed with some observations on the variety CS of completely simple
semigroups, consisting of algebras with a binary multiplication and unary “inversion” _−1 satisfying the following identities, where u0 abbreviates uu−1 :
(14)

(xy)z = x(yz), x−1 x = x0 , x0 x = x, (x−1 )−1 = x

(15)

(xyx)0 = x0 .

The identities (14) define the variety of completely regular semigroups [34].
In the presence of them, it is well known that the identity (15) is equivalent
to
(16)

(xy)0 x = x.

Note that, when the inversion operation _−1 is interpreted as _ω−1 in a finite
semigroup, _0 becomes _ω and the first two identities in (14) are verified
while the last two identities in (14) are valid in every completely regular
finite semigroup.
Theorem 9.3. For U = S, each of the sets of pseudoidentities
Σ = {(xyx)ω = xω , xω+1 = x} and Γ = {(xy)ω x = x}
is h-strong.
Proof. As implied by the entry for CS in [13, Table 2], the methods of [3]
show that the pseudovariety CS is κ-reducible for graph systems of equations.
In fact, in [3] vertices were allowed to be constrained by the clopen subset

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

27

{1} ⊆ (ΩA S)1 , which forces the corresponding variable to be evaluated by 1.
It follows that CS is κ-reducible for the equation x = y
Consider next the variety CSκ . Since free completely simple semigroups
are residually finite [33, Proposition 2.5], in view of the above remarks a
basis of identities for CSκ is given by
(xy)z = x(yz), xω−1 x = xxω−1 , xxω−1 x = x, (xω−1 )ω−1 = x
xyx(xyx)ω−1 = xxω−1 .
All the identities in the first line are obviously provable from Σ. On the
other hand, substituting x for y gives a proof of xω+1 = x from Γ and we
already observed that in the presence of the identities in the above first line,
the identities (xyx)ω = xω and (xy)ω x = x are provable from each other.
Thus, the result follows from Proposition 7.1.

Combining Theorems 9.2 and 9.3 with Proposition 6.3(xii), and applying
Proposition 4.2, we obtain the following result.
Corollary 9.4. For U = S, every set Σ of pseudoidentities such that JΣK ⊆
CS is h-strong.

Taking into account the κ-reducibility for the equation x = y of the pseudovariety CR = Jxω+1 = xK, of all finite completely regular semigroups,
(cf. [15]) and the residual finiteness of free completely regular semigroups
(viewed as algebras in the signature {_._, _−1 }), the following theorem
can be proved in the same way as Theorem 9.3.
Theorem 9.5. For U = S, the pseudoidentity xω+1 = x is h-strong.
10. The commutative case
Our next example is the usual basis of the pseudovariety Com of all finite
commutative monoids.
Theorem 10.1. For U = M, the identity xy = yx is h-strong.
Proof. Although [38] deals with the notion of hyperdecidability, which is
weaker than σ-reducibility provided the implicit signature σ has suitable
algorithmic properties (cf. [13, 14]), it is observed in [13] that the same
methods show that Com is κ-reducible, in particular for the equation x = y.
We claim that the following is a basis of identities for the variety Comκ , as
usual, we write xω for the product xω−1 x:
xω−1 xω = xω−1 , (xω−1 )ω−1 = xω+1
(xy)z = x(yz), x1 = 1x = x
xy = yx
(xy)ω−1 = xω−1 y ω−1 .
Indeed all such identities are clearly valid in Com. On the other hand,
using the above identities, one may reduce every κ-term to one of the form
u = xε11 · · · xεnn , where each exponent εi is either 1 or ω − 1. Moreover,
we may rearrange the factors so that the powers with the same base are
not separated by other powers. On the other hand, powers with the same
base can collected together to powers of one of the forms xn or xω−1 xn ,

28

J. ALMEIDA AND O. KLÍMA

where n is a nonnegative integer, or (xω−1 )n , where n ≥ 2. For convenience,
we write xω−1 xn as xω−1+n and (xω−1 )n as x(ω−1)n . In this form, we say
that we have a κ-term in completely reduced form. Consider two κ-terms
in completely reduced form u = aε11 · · · aεnn and v = aδ11 · · · aδnn over the
alphabet {a1 , . . . , an } and assume that the identity u = v is valid in Com.
Then, substituting 1 for every variable but one, we obtain an identity valid
in Com of the form xε = xδ with ε and δ exponents of one of the forms n,
ω − 1 + n or (ω − 1)n. By considering a suitable monogenic finite semigroup,
one immediately verifies that ε = δ. This proves the claim.
To conclude the proof, it remains to observe that the last identity in the
above basis is provable from xy = yx. Indeed, each identity (xy)n!−1 =
xn!−1 y n!−1 can be easily proved and the result follows by taking limits. 
We next show that the pseudoidentity xy = yx also defines a strong
pseudovariety.
Theorem 10.2. The pseudovariety Com is strong.
Proof. First of all, we recall that elements of the free profinite monoid ΩA Com
over the set A = {a1 , . . . , an } can be written in the form aε11 · · · aεnn , where
ε1 , . . . , εn ∈ N̂. Each pseudoidentity aε11 · · · aεnn = aδ11 · · · aδnn is provably
equivalent to the set of pseudoidentities {aε11 = aδ11 , . . . , aεnn = aδnn }. Therefore, we may assume that all pseudoidentities which are under consideration
are over a single variable.
Recall that Ω1 Com and Ω1 M are both isomorphic to N̂ via the mapping
ε 7→ xε and that Ẑ = N̂ \ N is isomorphic to Ω1 G. For the purpose of
simplification of notation, we identify isomorphic structures, so, for example,
we denote by π the continuous homomorphisms π : Ω1 Com → Ω1 G given by
the rule π(xε ) = xω+ε , which is formally a projection πG : Ω1 M → Ω1 G after
the identification Ω1 Com = Ω1 M. In this way, the group Ω1 G can be viewed
as a retract of the monoid Ω1 Com.
Let Σ be a set of pseudoidentities in the variable x and xε = xδ be a
nontrivial pseudoidentity satisfied by JΣK. We need to show that xε = xδ
belongs to Σ̃.
By the finite index i(Σ) of Σ is meant the minimal natural number n such
that (xn = xµ ) ∈ Σ where µ 6= n. If such n ∈ N does not exist, we say that
Σ has infinite index.
If n is the index of Σ, then in a nontrivial pseudoidentity (xn = xµ ) ∈ Σ
we have µ infinite or n < µ ∈ N. In both cases, in view of Lemma 6.1
the pseudoidentity xn = xω+n is provable from Σ. On the other hand,
1
belongs to JΣK, whence it satisfies xε = xδ .
the monogenic monoid Cn,1
Hence, both ε and δ are infinite or greater than or equal to i(Σ) = n. From
Lemma 6.1, it follows that xε = xω+ε and xδ = xω+δ are provable from Σ.
Therefore, xε = xδ is provable from Σ if and only if so is xω+ε = xω+δ . On
1 belongs to JΣK
the other hand, if Σ has infinite index, then the monoid Cn,1
for every n ∈ N and we see that ε, δ 6∈ N. Altogether, we can deal just with
the case ε, δ ∈ Ẑ.
Before finishing the proof, we make one technical observation. Let ρ be
the restriction of the relation Σ̃ to the set {xλ : λ ∈ Ẑ} and τ denote the

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

29

] on Ω1 G. We claim that these relations are equal, under our
relation π(Σ)
identification of underlying sets with Ẑ. Since Ẑ is a closed ideal in N̂ and Σ̃
is a closed congruence on N̂ = Ω1 Com, the relation ρ is a closed congruence
on Ẑ. We have π(Σ) ⊆ Σ0 , because each pseudoidentity xω+λ = xω+µ
is provable from xλ = xµ . Hence, π(Σ) ⊆ Σ̃, where π(Σ) is a relation
]
on Ẑ. Therefore, π(Σ) ⊆ ρ and the transitive-topological closure τ = π(Σ)
is also a subset of the closed congruence ρ. The reverse inclusion ρ ⊆ τ
will be proved if we establish (by the induction), for each α, the inclusion
Σα |Ẑ×Ẑ ⊆ (π(Σ))α .
Let α = 0 and (xλ , xµ ) ∈ Σ0 , where λ, µ ∈ Ẑ. Taking into account commutativity, we may assume that xλ = xa+bk , xµ = xa+bℓ , where a, b, k, ℓ ∈ N̂
and (xk = xℓ ) ∈ Σ. Then, (xω+k = xω+ℓ ) ∈ π(Σ) and we have (xa+b(ω+k) =
xa+b(ω+ℓ) ) ∈ (π(Σ))0 . Since λ, µ ∈ Ẑ, we see that a + b(ω + k) = a + bk + ω =
λ + ω = λ and, similarly, a + b(ω + ℓ) = µ, which yields Σ0 |Ẑ×Ẑ ⊆ (π(Σ))0 .
Now assume that Σ2γ |Ẑ×Ẑ ⊆ (π(Σ))2γ and let (xλ = xµ ) ∈ Σ2γ+1 , where
λ, µ ∈ Ẑ. Then there is a finite sequence λ = λ0 , λ1 , . . . , λm = µ ∈ N̂
such that (xλi−1 = xλi ) ∈ Σ2γ , for each i = 1, . . . , m. Since Σ2γ is stable
under multiplication, we deduce that (xλi +ω = xλi+1 +ω ) ∈ Σ2γ |Ẑ×Ẑ . By the
induction assumption, these pairs also belong to (π(Σ))2γ and since λ+ω = λ
and µ + ω = µ, we obtain (xλ = xµ ) ∈ (π(Σ))2γ+1 .
Let Σ2γ+1 |Ẑ×Ẑ ⊆ (π(Σ))2γ+1 and assume that (xλ = xµ ) ∈ Σ2γ+2 , where
λ, µ ∈ Ẑ. Then, there is an infinite sequence of pseudoidentities from Σ2γ+1
converging to xλ = xµ . Multiplying the pseudoidentities in the sequence by
xω and using the fact that Σ2γ+1 is a congruence, we obtain the sequence
of pseudoidentities from Σ2γ+1 |Ẑ×Ẑ with the limit xλ = xµ . Now, using the
induction hypothesis we obtain, that (xλ = xµ ) ∈ (π(Σ))2γ+2 .
To accomplish the proof of the claim by transfinite induction we need to
consider a limit ordinal α, but the inclusion follows immediately from the
inclusions for smaller ordinals.
Now, we are ready to finish the proof of the theorem. We assumed that JΣK
satisfies the pseudoidentity xε = xδ , where ε, δ ∈ Ẑ. We need to show that
(xε = xδ ) ∈ Σ̃, or equivalently written (ε, δ) ∈ ρ. Assume on the contrary
that (ε, δ) 6∈ ρ. We have proved the equality of two closed congruences ρ and
τ . So, we can consider the monoid Ẑ/ρ = Ẑ/τ , which is a profinite monoid,
because it is a quotient of Ω1 G by the relation τ = Γ̃ for Γ = π(Σ) and
G is strong by Corollary 8.2. Thus, there is a continuous homomorphism
f : Ẑ → G onto a finite (cyclic) group G ∈ Jπ(Σ)KG ⊆ JΣK, such that
f (ε) 6= f (δ). Now, we can consider the composition of f with π and we
obtain the continuous homomorphism g : Ω1 Com → G, g(xλ ) = f (λ + ω),
such that g(xε ) 6= g(xδ ). This is a contradiction because the group G ∈ JΣK
must satisfy the pseudoidentity xε = xδ . Therefore, we have (xε = xδ ) ∈ Σ̃
and the proof is finished.


To complete the program already followed in Sections 8 and 9, we establish
missing strongness property for the pseudoidentity xy = yx. It was not

30

J. ALMEIDA AND O. KLÍMA

established earlier, namely as part of Proposition 6.3, because our argument
depends on Corollary 8.4.
Proposition 10.3. The pseudoidentity of monoids xy = yx is t-strong.
Proof. Let Σ be a set of M-pseudoidentities such that all monoids in JΣK are
commutative. We need to show that Σ proves xy = yx.
In the terminology introduced at the end of Section 6, by a theorem of
Margolis and Pin [30], a complete set of excluded monoids for the pseudoidentity xy = yx is given by all non-Abelian groups together with N 1 ,
B(1, 2)1 , and B(2, 1)1 . Hence, each such monoid fails some pseudoidentity
from Σ. Actually, since xy = yx entails xω y = yxω and the latter pseudoidentity is t-strong by Proposition 6.3(xi), we already know that Σ proves
xω y = yxω .
On the other hand, as N 1 fails some pseudoidentity u = v from Σ, either
Σ proves xω = 1 or N 1 fails a two-variable pseudoidentity provable from Σ
by evaluating x as a and y as b. Taking into account that the only nonzero
product involving at least two factors using either a, b, or both is ab, we
deduce that Σ proves either x = xω+1 or a nontrivial pseudoidentity of the
form xy = w. If w is not yx, then one may substitute one of the variables
by 1 to get a nontrivial pseudoidentity of the from x = xα , which again
entails x = xω+1 by Lemma 6.1. Hence, Σ deduces either x = xω+1 or
xy = yx, which means that we may as well assume that Σ proves the former
pseudoidentity. Thus, Σ proves the pseudoidentities
(17)
(18)

xω+1 = x
xω y = yxω ,

which are known to define the join Sl ∨ G, that is, the pseudovariety of all
finite monoids that are semilattices of groups [2, Exercise 9.1.4]. Since it
is not so easy to deduce pseudoidentities from Σ from the knowledge that
non-Abelian groups fail some pseudoidentity in Σ, we proceed instead to
reduce our problem to the group case and apply Corollary 8.4 to draw the
conclusion that Σ proves xy = yx.
First, we exhibit other provable consequences of Σ. Since we deal with the
pseudoidentity xy = yx, we work over the alphabet A = {x, y} only, even
though more general pseudoidentities may be handled similarly. In fact we
list some useful pseudoidentities that are provable from (17) and (18).
We have (xy)ω = xω (xy)ω y ω = y ω (xy)ω xω , where we used (17) first and
(18) in the second step. Then we get y ω (xy)ω xω = y ω−1 (yx)ω+1 xω−1 =
y ω−1 yxxω−1 = y ω xω = xω y ω , where the first and third equality hold in ΩA M
and the second and fourth equality follow respectively from (17) and (18).
Now, for each word w ∈ A∗ containing both variables x and y, if we use
the pseudoidentities (xy)ω = xω y ω and (18) repeatedly, we may prove wω =
xω y ω . Hence, from (17) and (18) we may prove wω xω y ω = xω y ω for every
pseudoword w over the alphabet {x, y}.
Recall that Σ̃ is a relation on ΩA M. Let Γ = Σ ∪ {xω = 1} and consider
Γ̃ on the same monoid ΩA M. Then JΓK = JΣK ∩ G. Applying Corollary 8.4
we obtain that (xy = yx) ∈ Γ̃. We claim, for any pseudoidentity u = v,
that (u = v) ∈ Γ̃ implies (uxω y ω = vxω y ω ) ∈ Σ̃. This gives the proof of the

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

31

statement because the pseudoidentities xy = xyxω y ω and yx = yxxω y ω are
provable from (17) and (18).
The claim will be proved if we show, for every ordinal α, the following
implication:
(u = v) ∈ Γα =⇒ (uxω y ω = vxω y ω ) ∈ Σ̃ .
Let α = 0 and (u = v) ∈ Γ0 . If we use in the proof of u = v a
pseudoidentity from Σ, then (u = v) ∈ Σ0 and therefore also (uxω y ω =
vxω y ω ) ∈ Σ0 . So, we may assume, without loss of generality, that u =
t(ϕ(xω ), w1 , . . . , wn ), v = t(ϕ(1), w1 , . . . , wn ), where ϕ : Ω1 M → ΩA M is a
continuous homomorphism, t is a word and wi ∈ ΩA M (i = 1, . . . , n). Using (18) and the fact that (ϕ(x))ω xω y ω = xω y ω is Σ-provable, we get that
(uxω y ω = vxω y ω ) ∈ Σ̃.
The other steps of the induction proof are easy to see as Σ̃ is a closed
congruence.

As in Sections 8 and 9, we may now apply Proposition 4.2 to obtain the
following result.
Corollary 10.4. For U = M, every set Σ of pseudoidentities defining a
pseudovariety of commutative monoids is h-strong.

11. Conclusion
We have introduced a natural and sound proof scheme for pseudoidentities.
We have given ample evidence for the conjecture that our proof scheme
is complete. There is a nice connection with the much studied notions of
reducibility and tameness. In fact, in all our examples built on reducible
pseudovarieties, we have shown that Σn = Σ̃ for some integer n. But, in
Proposition 7.9, we also established that n = 2 is not enough. It is expectable
that in general there may be no n ≥ 1 such that Σn = Σ̃, or perhaps even
Σω 6= Σ̃, but we have found no example in which that is the case.
We have not tried to treat exhaustively all cases of pseudovarieties which
are known to be tame. Those that we have considered are perhaps those
that appear more frequently in the literature. Of course, since we believe
in our conjecture, more such results would only be adding evidence to our
claim that we have identified a completely general phenomenon.
It is the knowledge of congruences on suitable relatively profinite monoids
or semigroups that allowed us to prove that the pseudovarieties G, CS, and
Com are strong. Much is also known about the congruences on ΩA CR but
we have not taken the natural path of trying to prove that the pseudovariety
CR is strong.
Acknowledgments
The first author acknowledges partial funding by CMUP (UID/MAT/
00144/2013) which is funded by FCT (Portugal) with national (MATT’S)
and European structural funds (FEDER) under the partnership agreement
PT2020. The second author was supported by Grant 15-02862S of the Grant
Agency of the Czech Republic.

32

J. ALMEIDA AND O. KLÍMA

References
1. J. Almeida, On finite simple semigroups, Proc. Edinburgh Math. Soc. 34 (1991), 205–
215.
2.
, Finite semigroups and universal algebra, World Scientific, Singapore, 1995,
English translation.
, On hyperdecidable pseudovarieties of simple semigroups, Int. J. Algebra Com3.
put. 10 (2000), 261–284.
4.
, Finite semigroups: an introduction to a unified theory of pseudovarieties,
Semigroups, Algorithms, Automata and Languages (Singapore) (G. M. S. Gomes,
J.-E. Pin, and P. V. Silva, eds.), World Scientific, 2002, pp. 3–64.
, Profinite semigroups and applications, Structural theory of automata, semi5.
groups and universal algebra (New York) (V. B. Kudryavtsev and I. G. Rosenberg,
eds.), Springer, 2005, pp. 1–45.
6. J. Almeida and A. Costa, Equidivisible pseudovarieties of semigroups, Publ. Math.
Debrecen 90 (2017), 435–453.
7. J. Almeida, J. C. Costa, and M. Zeitoun, Tameness of pseudovariety joins involving
R, Monatsh. Math. 146 (2005), 89–111.
8.
, Complete reducibility of systems of equations with respect to R, Portugal.
Math. 64 (2007), 445–508.
9.
, McCammond’s normal forms for free aperiodic semigroups revisited, LMS J.
Comput. Math. 18 (2015), 130–147.
, Reducibility of pointlike problems, Semigroup Forum 94 (2017), 325–335.
10.
11. J. Almeida and M. Kufleitner, Pro-DA closures of regular languages, In preparation.
12. J. Almeida and M. H. Shahzamanian, The finite basis and finite rank properties for
pseudovarieties of semigroups, Tech. report, Univ. of Porto, 2016, arXiv:1611.08089.
13. J. Almeida and B. Steinberg, On the decidability of iterated semidirect products and
applications to complexity, Proc. London Math. Soc. 80 (2000), 50–74.
14.
, Syntactic and global semigroup theory, a synthesis approach, Algorithmic
Problems in Groups and Semigroups (J. C. Birget, S. W. Margolis, J. Meakin, and
M. V. Sapir, eds.), Birkhäuser, 2000, pp. 1–23.
15. J. Almeida and P. G. Trotter, The pseudoidentity problem and reducibility for completely regular semigroups, Bull. Austral. Math. Soc. 63 (2001), 407–433.
16. J. Almeida and M. V. Volkov, Subword complexity of profinite words and subgroups of
free profinite semigroups, Int. J. Algebra Comput. 16 (2006), 221–258.
17. J. Almeida and M. Zeitoun, An automata-theoretic approach to the word problem for
ω-terms over R, Theor. Comp. Sci. 370 (2007), 131–169.
18. C. J. Ash, Inevitable graphs: a proof of the type II conjecture and some related decision
procedures, Int. J. Algebra Comput. 1 (1991), 127–146.
19. S. Burris and H. P. Sankappanavar, A course in universal algebra, Grad. Texts in
Math., no. 78, Springer, Berlin, 1981.
20. A. H. Clifford and G. B. Preston, The algebraic theory of semigroups, vol. II, Amer.
Math. Soc., Providence, R.I., 1967.
21. J. C. Costa and C. Nogueira, On bases of identities for the ω-variety generated by
locally testable semigroups., Theor. Comp. Sci. 401 (2008), no. 1-3, 206–216.
22.
, Complete reducibility of the pseudovariety LSl, Int. J. Algebra Comput. 19
(2009), no. 2, 247–282.
23. J. C. Costa, C. Nogueira, and M. L. Teixeira, Pointlike reducibility of pseudovarieties
of the form V ∗ D, Int. J. Algebra Comput. 26 (2016), 203–216.
24. J. C. Costa and M. L. Teixeira, Tameness of the pseudovariety LSl, Int. J. Algebra
Comput. 14 (2004), 627–654.
25. J. C. Costa, M. L. Teixeira, and C. Nogueira, On κ-reducibility of pseudovarieties of
the form V ∗ D, Int. J. Algebra Comput. 27 (2017), 23–40.
26. S. Eilenberg, Automata, languages and machines, vol. B, Academic Press, New York,
1976.
27. K. Henckell, Pointlike sets: the finest aperiodic cover of a finite semigroup, J. Pure
Appl. Algebra 55 (1988), 85–126.

TOWARDS A PSEUDOEQUATIONAL PROOF THEORY

33

28. K. Henckell, J. Rhodes, and B. Steinberg, Aperiodic pointlikes and beyond, Int. J.
Algebra Comput. 20 (2010), 287–305.
29. J. M. Howie, An introduction to semigroup theory, Academic Press, London, 1976.
30. S. W. Margolis and J.-E. Pin, Minimal noncommutative varieties and power varieties,
Pacific J. Math. 111 (1984), 125–135.
31. J. McCammond, Normal forms for free aperiodic semigroups, Int. J. Algebra Comput.
11 (2001), 581–625.
32. J. D. McKnight, Jr. and A. J. Storey, Equidivisible semigroups, J. Algebra 12 (1969),
24–48.
33. F. J. Pastijn and P. G. Trotter, Residual finiteness in completely regular semigroup
varieties, Semigroup Forum 37 (1988), 127–147.
34. M. Petrich and N. Reilly, Completely regular semigroups, Canadian Math. Soc. Series
of Monographs and Advanced Texts, vol. 23, Wiley-Interscience, New York, 1999.
35. J. Reiterman, The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1982),
1–10.
36. J. Rhodes and B. Steinberg, The q-theory of finite semigroups, Springer Monographs
in Mathematics, Springer, 2009.
37. M. P. Schützenberger, On finite monoids having only trivial subgroups, Inform. and
Control 8 (1965), 190–194.
38. B. Steinberg, On pointlike sets and joins of pseudovarieties, Int. J. Algebra Comput.
8 (1998), 203–231.
CMUP, Dep. Matemática, Faculdade de Ciências, Universidade do Porto,
Rua do Campo Alegre 687, 4169-007 Porto, Portugal
E-mail address: jalmeida@fc.up.pt
Dept. of Mathematics and Statistics, Masaryk University, Kotlářská 2,
611 37 Brno, Czech Republic
E-mail address: klima@math.muni.cz

