Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

164 M. Jackson

is ﬁnitely based, then Σ can be chosen to be ﬁnite, and we get a ﬁnite basis for S

(this is also

discussed in [15]). Now if S is not ﬁnitely based, then Σ must be inﬁnite and no ﬁnite subset

of Id(S) is suﬃcient to derive all of Σ. As Σ is also satisﬁed by S

,andId(S

) ⊆ Id(S), it

follows that S

also has no ﬁnite basis of identities. 2

2.6 Corollary The ﬁnite basis problem for ﬁnite semigroups (monoids) is polynomially

equivalent to its restriction to the class of ﬁnite syntactic semigroups (monoids).

Proof The monoid version of this result follows immediately from Lemma 2.4.

Now let S be a ﬁnite semigroup. By Lemma 2.5, S is ﬁnitely based if and only if S

is ﬁnitely based. By Lemma 2.2, S

generates a variety equal to one generated by a single

syntactic semigroup (that can be constructed in polynomial time from S

). 2

3 A language theoretic approach

The ﬁnite basis problem for monoids has a natural analogue in terms of varieties of regular

languages. Analogous statements will hold for semigroups as well.

3.1 Deﬁnition For K a class of regular languages, let V

∗

(K)denotethe∗-variety of lan-

guages generated by K and let V

∗

(K) denote the subclass of V

∗

(K) consisting of those

languages which are in alphabets of at most n letters. We say that a ∗-variety of languages

is ﬁnitely ∗-veriﬁable for K languages if there exists an n ∈ N such that for all languages

W ∈ K,

W ∈V

⇐⇒ V

∗

(W ) ⊆V.

If K is the class of all regular languages, then we say that a ∗-variety is ﬁnitely ∗-veriﬁable

instead of ﬁnitely ∗-veriﬁable by K-languages.

The connection between the ﬁnite ∗-veriﬁcation property for ∗-varieties of languages and

the ﬁnite basis problem for monoids arises through the Eilenberg correspondence and the

following result essentially due to M. Sapir.

3.2 Lemma (M. Sapir [14]) Let V be a subvariety of a ﬁnitely generated variety of semi-

groups (monoids).ThenV is non-ﬁnitely based if and only if for each n ∈ N there are ﬁnite

semigroups (monoids, respectively) S

∈Vsuch that S

satisﬁes all n-variable identities

of V but not all identities of V. Equivalently, S

∈Vbut all n-generated subsemigroups

(submonoids) of S

are contained in V.

Proof We ﬁrst discuss the semigroup case. The statement above diﬀers from the main

result of [14] only in that it allows for the possibility that V is not generated by any ﬁnite

semigroup. All arguments in [14] except for Proposition 1 depend only on the local ﬁniteness

of V. Proposition 1 however, is itself an extract from a more general result from [12] that

concerns any locally ﬁnite variety in which all groups are ﬁnitely based. As Sapir notes in [12],

this is true of any ﬁnitely generated semigroup variety (by [10]) and hence in any subvariety

of such a variety. Therefore Sapir’s proof in fact extends to the semigroup part of the lemma

we have stated above.

Now we investigate the monoid case which again follows without signiﬁcant change from

Sapir’s result for semigroups. As is discussed in [15], a monoid is non-ﬁnitely based (in the

The ﬁnite basis problem 165

type 2, 0) if and only if it is non-ﬁnitely based as a semigroup (in the type 2). Let V



denote

the semigroup variety generated by the members of V considered as semigroups, and say that

V (whence V



) is not ﬁnitely based. Using the semigroup version of the lemma, there are ﬁnite

semigroups S

such that S

is not contained in V



, while all n-generated subsemigroups of

are contained in V



. Now consider S

, also not in V



and therefore not in V (as a monoid).

As semigroups, the n-generated submonoids of S

are either n-generated subsemigroups of S

(that happen to be monoids) or are of the form of an n-generated subsemigroup of S

with

adjoined identity element. In either case, Lemma 1.1 shows that the n-generated submonoids

lie in V.Thuswehave,foralln ∈ N, a ﬁnite monoid not in V but whose n-generated

submonoids are in V. 2

This result guarantees that for ﬁnite semigroups and monoids, the third condition of

Lemma 1.2 can be replaced by its restriction to ﬁnite algebras. The corresponding result for

general algebras appears to be an interesting open problem; see [4, 5].

3.3 Lemma If S is a ﬁnite monoid with no ﬁnite basis of identities then for each n ∈ N there

is a regular language W

such that every n-generated submonoid of Syn

) is contained

in V(S) but Syn

) ∈ V(S).

Proof By Lemma 3.2, for each n ∈ N there is a ﬁnite monoid S

such that every n-generated

submonoid of S

is contained in V(S) but S

∈ V(S).

Let us ﬁx some arbitrary n ∈ N. For each element s ∈ S

,letS

n,s

denote the semigroup

/∼

{s}

.NoweachS

n,s

is a quotient of S

and therefore satisﬁes all identities satisﬁed by S

However V(S) is generated by {S

n,s

: s ∈ S} (see Section 1.1) and therefore there must be an

identity of S that fails on S

n,s

for some s ∈ S

. Therefore we have a ﬁnite syntactic monoid

of a regular language, W

say, that satisﬁes all identities of S

(and therefore all n-variable

identities of S) but not all identities of S. Equivalently (see Lemma 1.2), we have shown that

there is a regular language W

such that every n-generated submonoid of Syn

) lies in

the monoid variety of S while Syn

)doesnot. 2

The extension of Lemma 3.3 to semigroups is obvious and we omit the details.

3.4 Theorem Let S be a ﬁnite monoid and V

denote the ∗-variety of languages whose syn-

tactic monoids are ﬁnite and contained in V(S).ThenS is ﬁnitely based if and only if V

ﬁnitely ∗-veriﬁable.

Proof Let S be a ﬁnite monoid with a ﬁnite basis of identities Σ in n variables and let V

denote the ∗-variety of regular languages whose syntactic monoids are in V

ﬁn

(S). Obviously if

W ∈V

then V

∗

(W ) ⊆V, while if W is a language not in V then the Eilenberg correspondence

guarantees that Sym

(W ) |= Σ. Hence there is an n-variable identity u ≈ v that fails on

Sym

(W ). Evidently, there is an n-generated submonoid T of Sym

(W )onwhichu ≈ v

fails. By examining the syntactic quotients of T with respect to the singleton subsets of T

(as in the proof of Lemma 3.3), it follows that there is t ∈ T such that u ≈ v fails on T/∼

{t}

also n-generated. Let A = {a

,...,a

} be a set of free generators for a free monoid A

∗

and

let φ : A

∗

→ T be a surjective homomorphism. Then T/∼

{t}

is the syntactic monoid of

the regular language W

:= φ

−1

(t/∼

{t}

)inthen-letter alphabet A, whence it follows that

∈V

∗

(W ) \V. This shows that there is an n ∈ N such that for regular languages W ,

W ∈V

=⇒V

∗

(W ) ⊆V,thatis,V is ﬁnitely ∗-veriﬁable.

166 M. Jackson

Now assume that S is non-ﬁnitely based. By Lemma 3.3, for all n ∈ N there are regular

languages W

such that Sym

) ∈ V(S) but such that every n-variable identity satisﬁed

by S is satisﬁed by Sym

). Now if U ∈V

∗

)thenSym

(U)isn-generated and

satisﬁes all identities of Syn

) and in particular, all n-letter identities of S.Elementary

arguments then show that Sym

(U) ∈ V(S). Hence U ∈Vso V

∗

) is a subclass of V,

while W

is not in V. Because n ∈ N is arbitrary, V is not ﬁnitely ∗-veriﬁable. 2

Again, trivial variations of this theorem give the corresponding result for semigroup vari-

eties and +-varieties of languages.

It is interesting to note that the main proof in [14] shows that if S is a ﬁnite inher-

ently non-ﬁnitely based monoid (or semigroup), then the corresponding ∗-variety of lan-

guages is not ﬁnitely ∗-veriﬁable for singleton languages. For example, the monoid B

given

in the introduction is known to be (isomorphic to) the syntactic monoid of the language

{ab}

∗

(in the alphabet {a, b}) and is also known to be inherently non-ﬁnitely based [13].

Hence V

∗

({ab}

∗

) is not ﬁnitely ∗-veriﬁable for singleton languages. In fact from [11] and the

proof of Theorem 3.4, we have {ba

...a

n−1

...a

} ∈V

∗

({ab}

∗

) for any n ∈ N, but

∗

({ba

...a

n−1

...a

}) ∈V

∗

({ab}

∗

Let the ﬁnite ∗-veriﬁcation problem for regular expressions denote the following decision

problem: given a regular expression, decide if the corresponding language generates a ﬁnitely

∗-verifable ∗-variety. The ﬁnite +-veriﬁcation problem is deﬁned analogously.

3.5 Corollary The ﬁnite basis problem for ﬁnite semigroups (monoids) is decidable if and

only if the ﬁnite +-veriﬁcation (∗-veriﬁcation, respectively) problem for regular expressions

is decidable.

Proof We discuss the monoid case; the semigroup case is almost identical. The standard

proofs of the equivalence of the class of languages recognisable by ﬁnite state automata and

languages corresponding to regular expressions are constructive. That is, with each ﬁnite

automata, we can eﬀectively associate a regular expression corresponding to the language

recognised by the machine and vice versa. Likewise, with a syntactic monoid Syn

(W )ofa

language W we may construct an automata recognising W (by representing Syn

(W )asa

monoid of transformations), and conversely with each automata, we may eﬀectively construct

a minimal automata recognising the same language and then construct the syntactic monoid

of this language as the transition monoid of the automata. Therefore we can eﬀectively

associate a syntactic monoid S with a regular expression for a language recognised by S and

vice versa.

The result now follows by combining Theorem 3.4 and its semigroup variant with Corol-

lary 2.6. 2

We note that the translation from syntactic semigroups or monoids to regular expressions

is polynomial time, however the reverse may not be true. It is a well known PSPACE-complete

problem to determine if a regular expression r over {0, 1} represents the same language as

{0, 1}

∗

; see [7]. The syntactic monoid of {0, 1}

∗

(as a regular language in the alphabet {0, 1})

is trivial, however if r represents a non-empty language W distinct from {0, 1}

∗

, then the

syntactic monoid of W is non-trivial and so Syn

(W ) generates a non-trivial variety. Thus

if P=PSPACE, there can be no polynomial time method for constructing, from a regular

expression r for a language W , a monoid generating the same variety as Syn

(W ).

The ﬁnite basis problem 167

References

[1] J. Almeida, Finite Semigroups and Universal Algebra, Series in Algebra 3, World Scien-

tiﬁc Publishing, Singapore, 1994.

[2] G. Birkhoﬀ, On the structure of abstract algebras, Proc. Camb. Philos. Soc. 31 (1935),

433–454.

[3] S. Burris and H. Sankappanavar, A Course in Universal Algebra, Graduate Texts in

Mathematics 78, Springer Verlag, New York, 1980.

[4] R. Cacioppo, Finite bases for varieties and pseudovarieties, Algebra Universalis 25

(1988), 263–280.

[5] R. Cacioppo, Nonﬁnitely based pseudovarieties and inherently nonﬁnitely based varieties,

Semigroup Forum 47 (1993), 223–226.

[6] S. Eilenberg, Automata, Languages and Machines Vol. B, Pure and Applied Mathemat-

ics, Academic Press, New York, 1976.

[7] M. Garey and D. Johnson, Computers and Intractability: A Guide to the theory of

NP-Completeness, W. H. Freeman, New York, 1979.

[8] R. McKenzie, Tarski’s ﬁnite basis problem is undecidable, Internat. J. Algebra Comput.

6 (1996), 49–104.

[9] I. I. Mel’nik, On varieties and lattices of varieties of semigroups, in: Studies in algebra

No. 2 (V. V. Vagner, ed.), Izdat. Saratov. Univ., Saratov (1970), 47–57 (in Russian).

[10] S. Oates and M. B. Powell, Identical relations in ﬁnite groups, J. Algebra 1 (1964),

11–39.

[11] P. Perkins, Bases for equational theories of semigroups, J. Algebra 11 (1969), 298–314.

[12] M. V. Sapir, Problems of Burnside type and the ﬁnite basis property in varieties of

semigroups, Math. USSR Izv. 30 (2) (1988), 295–314.

[13] M. V. Sapir, Inherently nonﬁnitely based ﬁnite semigroups, Math. USSR-Sb. 61 (1)

(1988), 155–166.

[14] M. Sapir, Sur la propi´et´e de base ﬁnie pour les pseudovari´et´es de semigroupes ﬁnis, C.

R. Acad. Sci. Paris (S´er. I) 306 (1988), 795–797 (in English and French).

[15] M. V. Volkov, The ﬁnite basis problem for ﬁnite semigroups Sci. Math. Jpn. 53 (2001),

171–199.

Endoprimal algebras

Kalle KAARLI

∗

Institute of Pure Mathematics

University of Tartu

50090 Tartu

Estonia

L´aszl´oM

ARKI

†‡

A. R´enyi Institute of Mathematics

Hungarian Academy of Sciences

H-1364 Budapest, Pf. 127

Hungary

Abstract

This survey is an overview of investigations into endoprimal algebras: their general

properties and connections with endoduality, as well as descriptions of endoprimal objects

in various kinds of algebras.

1 Early development

An algebra is called primal if every ﬁnitary function deﬁned on it is a term function. The most

common primal algebra is the 2-element Boolean algebra. Primal algebras were introduced

when studying categorical properties of the variety of Boolean algebras. Subsequently, several

generalisations have been investigated: algebras in which the term functions are exactly the

functions that preserve some derived structure (see e.g. [17]). Following this line, an algebra

is called endoprimal if its term functions are precisely those functions which permute with

all endomorphisms. It is convenient to call the latter functions endofunctions of the given

algebra. Thus, an algebra is endoprimal if and only if its endofunctions are term functions.

Endoprimal algebras made their ﬁrst appearance, however, in a diﬀerent way: in the

course of investigations into duality theory. Without using this name, B. A. Davey [2] proved

in 1976 that every ﬁnite chain is endoprimal as a Heyting algebra. In 1985 B. A. Davey and

H. Werner [8] proved that the Heyting algebra 2

⊕ 1 is also endoprimal, and this paper marks

the appearance of the name ‘endoprimal’. (Here and in the sequel A ⊕1 is the ordered set A

∗

The ﬁrst author thanks the Estonian Science Foundation grant no. 5368 for support.

†

The second author’s research was partially supported by the Hungarian National Foundation for Scientiﬁc

Research grants T34530 and T43034.

‡

Both authors thank the Estonian and the Hungarian Academies of Sciences for making possible mutual

visits through their exchange agreement.

169

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 169–180.

170 K. Kaarli and L. M´arki

with new greatest element 1.) In a note published in 1990, A. A. L. Sangalli [22] rephrased the

deﬁnition of endoprimality by using clones, and gave three examples for endoprimal algebras:

primal algebras, sets of cardinality diﬀerent from 2, and (arbitrary) free algebras on inﬁnite

sets.

The next result appeared in 1993, when L. M´arki and R. P¨oschel [20] proved that a

distributive lattice is endoprimal if and only if it is not relatively complemented. This result

seemed to be the end of the story, since it showed that endoprimal algebras do not share any

of the ‘nice’ properties of (quasi)primal algebras; hence one could not expect much of their

investigation. Contrary to this expectation, [20] has become the starting point of further

research, and the impetus for this came from B. A. Davey.

2 General theory and links with endoduality

In the paper [3] written in 1994, B. A. Davey showed that the occurrence of endoprimal alge-

bras in duality theory is not an accident: every endodualisable ﬁnite algebra (i.e., every ﬁnite

algebra which admits a particular kind of natural duality) is endoprimal. Then B. A. Davey,

M.Haviar,andH.A.Priestley[4]explainedhowtheargumentsusedbyL.M´arki and

R. P¨oschel lift to a duality-theoretic setting and yield that the class of endoprimal distribu-

tive lattices coincides with that of endodualisable distributive lattices. Finally, in 1997,

B. A. Davey and J. Pitkethly [7] managed to carry over the argumentation to a wide range

of quasi-varieties generated by a single algebra.

Let us now take a closer look at the connection between endoprimality and endodualis-

ability. Without deﬁning the latter notion, we brieﬂy explain why endoprimality of a ﬁnite

algebra is an easy consequence of its endodualisability. All details can be found in the mono-

graph [1]. Suppose we are given a ﬁnite algebra M.OnM , the underlying set of M,a

new structure M

∼

is introduced. This structure may involve ﬁnitary (partial) functions on

M and ﬁnitary relations on M. For building up the duality it is essential to assume that

∼

is equipped with the discrete topology but this is not important for our considerations.

The functions and relations involved are assumed to be algebraic, that is, the functions are

homomorphisms from B

to M where B is a subalgebra of M and relations are subalgebras

of some M

where n is a natural number. In particular, it makes sense to consider the case

∼

= M;EndM.

One of the main questions of duality theory is: which structures M

∼

dualise M?TheFirst

Duality Theorem (see [1]) asserts that if this happens then the morphisms of M

∼

to M

∼

are

precisely the n-ary term functions of M.IfM

∼

= M;EndM dualises M then we say that

M is endodualisable. Since clearly in this case the morphisms from M

∼

to M

∼

are the n-ary

endofunctions of M, it becomes obvious that endodualisable algebras are endoprimal.

Note that the ﬁniteness of M is essential for the theory of natural dualities. Methods of

duality theory can therefore be directly used only for constructing ﬁnite endoprimal algebras.

Fortunately, there is a way to go beyond ﬁniteness as the next theorem shows.

2.1 Theorem [7, Theorem 1.2] Let M be an endoprimal algebra and A ∈ ISP(M).IfA has

a retract isomorphic to M then A is endoprimal.

It is worth emphasizing that duality theory is good for providing examples of endoprimal

algebras but has very rarely been used for proving that a given algebra is not endoprimal.

Endoprimal algebras 171

Results of the latter kind can be obtained using the following basic theorem.

2.2 Theorem [1, Proposition 2.2.3] Let M be a ﬁnite algebra and A = ISP(M).ThenM is

endoprimal if and only if End M yields duality on all ﬁnitely generated free algebras of A.

In most cases, however, non-endoprimality is proved by the explicit construction of an

endofunction which is not a term function. A model argument is that used in [20]: a relatively

complemented distributive lattice is not endoprimal because the ternary function f (x, y, z)=

u,whereu is the complement of y in the interval [x∧y, y∨z], permutes with all endomorphisms

but is not a term function, since it does not preserve the order.

It was noticed already in [7] that there are ﬁnite endoprimal algebras which are not

endodualisable; e.g., 2

⊕ 1 regarded as a bounded semilattice is endoprimal but not endo-

dualisable. Thus certainly, even in the case of ﬁnite algebras, duality theory is not suﬃcient for

characterising endoprimal algebras. The problem has arisen of how far actually endoprimality

is from endodualisability. Perhaps the main result in this direction is the criterion given by

M. Haviar and H. A. Priestley.

2.3 Theorem [13, Theorem 6] Assume that a ﬁnite algebra D is dualised by the structure

∼

which beside End D involves ﬁnitary algebraic relations s

,...,s

.LetF be a ﬁnitely

generated free algebra in D = ISP(D). If the algebras s

,...,s

are retracts in F and D is

a retract in a ﬁnite endoprimal algebra M,thenM is endodualisable.

One can apply the theorem to prove that in the classes of distributive lattices, double

Stone algebras, median algebras, and ﬁnite abelian groups endoprimal algebras are endo-

dualisable. However, which median algebras are endoprimal seems to be an open question.

It is well known that the term functions of a ﬁnite algebra M can be characterised as

the functions which preserve all subalgebras of the ﬁnite powers of M. Hence, in view of the

standard Galois connection between clones and relational clones the endoprimality of a ﬁnite

algebra M means, in fact, that End M (viewed as the set of all graphs of endomorphisms of

M) generates the relational clone of all subalgebras of ﬁnite powers of M or, in the language

of [6], that this set clone entails all ﬁnitary algebraic relations on M. By a well-known result

in clone theory (cf. [19]), the latter is equivalent to the requirement that every algebraic

relation on M can be obtained from graphs of endomorphisms using certain well-deﬁned

natural constructs like projections, relational product, etc. The other entailment comes from

duality theory. Our limited space does not allow us to give a strict deﬁnition of this notion; it

serves to reduce the size of the set of algebraic relations on M used for providing duality, so

that if the structure M

∼

= M; R dualises M and a relation r ∈ R is duality entailed by R\r,

then the structure M; R \r dualises M, too. In particular, if R contains all endomorphisms

of M and we are able to show that End M duality entails every element of R \ End M then

M is endodualisable. A list of constructs which allow us to get from a given set of relations R

every relation r duality entailed by R was ﬁrst presented in [5]. This list is smaller than that

for clone entailment: in particular, it does not include relational product. This shows once

again that endoprimality is a consequence of endodualisability but not vice versa. A detailed

analysis of the diﬀerence between the two entailments on the example of Kleene algebras was

givenbyB.A.Davey,M.Haviar,andH.A.Priestley[6].

The next step makes use of an idea coming from the study of aﬃne completeness. Re-

call that an algebra is called aﬃne complete if all its congruence compatible functions (i.e.,

172 K. Kaarli and L. M´arki

functions which preserve all congruences of the algebra) are polynomials. Suppose we want

to prove that an algebra A is aﬃne complete. We take a congruence compatible function

f on A and try to prove that it is a polynomial function. A is often given as a subdirect

product of some smaller algebras A

, i ∈ I. Then, since f is compatible with all projection

kernels, it decomposes into a system of coordinate functions f =(f

)

i∈I

. Trying to handle

an endofunction f in a similar way, we face the problem that f need not in general be com-

patible with all congruence kernels. Still the argument goes through if all subdirect factors

are isomorphic to subalgebras of A, and hence the projection kernels are kernels of endo-

morphisms of A. This observation is the underlying idea of the paper [18] by K. Kaarli and

H. A. Priestley. One of the main results of the paper shows that if an algebra has a ‘good’

subdirect decomposition then its endofunctions are determined by what they induce on the

largest subdirect factor.

2.4 Theorem [18, Corollary 2.4] Let A be a subdirect product of the algebras A

, i ∈ I,and

assume that there is an algebra M satisfying the following conditions:

(SD1) every A

is a subalgebra of M;

(SD2) A has a subalgebra isomorphic to M;

(SD3) some of the A

is isomorphic to M.

Then for every endofunction f of A there exists an endofunction g of M such that f

= g|

for every i ∈ I.

In fact, these conditions (SD1)–(SD3) are satisﬁed in several cases where the endopri-

mality problem has been succesfully solved. As a corollary one immediately gets that, under

these conditions, endoprimality of M yields that of A, a fact that actually follows also from

Theorem 2.1. The usefulness of Theorem 2.4 becomes more obvious if we apply it in the case

when the algebra has a majority term. Recall that a majority function is a ternary function

f satisfying the identities

f(x, x, y)=f(x, y, x)=f (y,x,x)=x

and a majority term for an algebra A is a ternary term which induces a majority function

in A. The median function (x ∨y) ∧ (y ∨ z) ∧(z ∨x) is a majority term for all algebras with

lattice reduct.

The next theorem follows from Theorem 2.4 and the well-known Baker-Pixley Lemma

which essentially asserts, in particular, that a function deﬁned on a ﬁnite algebra M with a

majority term is a term function if and only if it preserves all subalgebras of M

.Wedenote

by S

(M) the algebra whose underlying set is the set of all subalgebras of M

and whose

fundamental operations are the relational product ◦, taking the converse ˘, intersection ∩,and

two nullary operations: one corresponding to the diagonal ∆

and another corresponding to

the whole square M

2.5 Theorem [18, Proposition 3.3] Assume that the assumptions of Theorem 2.4 are fulﬁlled,

M is ﬁnite and has a majority term. If S

(M) is generated by all graphs of homomorphisms

→ A

and all 2-fold coordinate projections A

, i, j ∈ I,thenA is endoprimal.

Applications of this theorem are given in the next section.

Endoprimal algebras 173

3 Enriched distributive lattices

In this section we survey the results on endoprimality of algebras having a distributive lattice

reduct.

We start with the observation that the result of L. M´arki and R. P¨oschel [20] on distribu-

tive lattices follows easily from Theorem 2.5. Indeed, it is well known that a distributive

lattice is relatively complemented if and only if it cannot be mapped homomorphically onto

the 3-element chain. Now, if a distributive lattice L is not relatively complemented, it has

a subdirect decomposition with all factors isomorphic to the 2-element chain 2 and at least

one 2-fold coordinate projection isomorphic to the 3-element chain. Clearly then S

(2)is

generated by 2-fold coordinate projections of L, hence L is endoprimal.

Using similar, only slightly more complicated arguments, one can derive from Theorem 2.5

the description of endoprimal non-Boolean Stone algebras, originally obtained by B. A. Davey

and J. G. Pitkethly [7], and this was done by K. Kaarli and H. A. Priestley in [18]. Formally

the result presented in [18] is stronger because in [7] it was required that 4 is a retract,

not only a homomorphic image, but it is easy to see that in the present situations these

requirements are equivalent. Recall that a Stone algebra is a bounded distributive lattice

with an extra unary operation

∗

such that the following identities are satisﬁed:

(x ∧ y)

∗

= x

∗

∨ y

∗

, (x ∨ y)

∗

= x

∗

∧ y

∗

, 0

∗

=1, 1

∗

=0, (3.1)

x ∧ x

∗

=0,x

∗

∨ (x

∗

)

∗

=1. (3.2)

3.1 Theorem [18, Theorem 5.1] A non-Boolean Stone algebra is endoprimal if and only if

it has the 4-element Stone chain as a homomorphic image.

Note that all Boolean algebras are endoprimal by Theorem 2.1 as is, in fact, every algebra

in the variety generated by a (ﬁnite) primal algebra. Also note that, as pointed out by

B. A. Davey and J. G.Pitkethly [7], the endoprimality criterion for non-Boolean Stone algebras

can be given in internal terms. Given a Stone algebra S,anelementx ∈ S is called dense if

∗

= 0. The set of all dense elements of S is denoted by d(S). It is easy to see that d(S)isa

sublattice of S. Now, it is known that the lattice d(S) is relatively complemented if and only

if 4 is not a homomorphic image of S. Hence, a non-Boolean Stone algebra S is endoprimal

if and only if d(S) is not relatively complemented.

M. Haviar and H. A. Priestley [12] described ﬁnite endoprimal double Stone algebras

(hence, by Theorem 2.2, also ﬁnite endodualisable double Stone algebras). It is pretty clear

that one should be able to derive the same results from Theorem 2.5. Recall that a double

Stone algebra is a bounded distributive lattice L with two extra unary operations,

∗

and

, such that the reducts L;

∗

 and L;

 are a Stone algebra and a dual Stone algebra,

respectively. A double Stone algebra is called regular if it satisﬁes the condition x∨x

∗

≥ y∧y

The core of a double Stone algebra A is its subset K(A)={x ∈ A | x

∗

=0,x

=1}. Recall

that every n-element chain has a unique structure of a double Stone algebra; the latter will

be denoted by n.

3.2 Theorem [12, Theorems 6.1–6.3]

(1) A ﬁnite non-regular double Stone algebra with non-empty core is endoprimal if and only

if it has 5 as a retract.

174 K. Kaarli and L. M´arki

(2) A ﬁnite non-regular double Stone algebra with empty core is endoprimal if and only if

it has 5 × 2

as a retract.

(3) A ﬁnite regular non-Boolean double Stone algebra is endoprimal if and only if it has

3 × 2

as a retract.

In [6], B. A. Davey, M. Haviar, and H. A. Priestley study endodualisability and endopri-

mality of Kleene algebras. Recall that a Kleene algebra is a bounded distributive lattice with

an extra unary operation

∗

such that beside (3.1) the identities

∗

)

∗

= x, (x ∧x

∗

) ∨ (x ∨ x

∗

)=x ∨ x

∗

are satisﬁed. It turns out that from the point of view of endoprimality Kleene algebras are

much worse than Stone algebras, a fact strikingly diﬀerent from the situation in the case of

aﬃne completeness (cf. [17]). In view of [18] the reason is the following. The variety of all

Kleene algebras is generated by the 3-element Kleene chain 3 but there are Kleene algebras

in which 3 is not a subalgebra. Therefore Theorem 2.5 does not apply to all Kleene algebras.

It may apply, however, in quasivarieties generated by an appropriate Kleene algebra diﬀerent

from 3, but there are too many quasivarieties of this kind. Actually the Kleene algebras

containing 3 as a subalgebra are not endoprimal. Indeed, if 3 is a subalgebra of a Kleene

algebra K then K contains an element a such that a

∗

= a. Then it is easy to see that the

constant function with value a is an endofunction but not a term function of K.

The paper [6] focuses mainly on the quasivariety L generated by the 4-element Kleene

chain 4; its results on endoprimality were improved by K. Kaarli and H. A. Priestley [18].

3.3 Theorem [6, Theorem 5.2], [18, Theorem 6.1] A non-Boolean Kleene algebra A ∈Lis

endoprimal if it has the 1-generated free Kleene algebra and the 6-element Kleene chain as

homomorphic images. If A is ﬁnite then this condition is also suﬃcient.

We conclude the section with Heyting algebras. Recall that a Heyting algebra can be

deﬁned as a bounded distributive lattice with an extra binary operation → such that the

following identities are satisﬁed:

x → x =1, (x → y) ∧ y = y, x ∧ (x → y)=x ∧ y,

x → (y ∧ z)=(x → y) ∧ (x → z), (x ∨ y) → z =(x → z) ∧ (y → z).

The standard example of a Heyting algebra is a Boolean algebra with x → y = x



∨ y.

As we have mentioned already, Heyting algebras provided the ﬁrst nontrivial examples for

endoprimal algebras. It is easy to see that every chain has a unique structure of a Heyting

algebra. As we did above in case of Kleene, Stone and double Stone algebras, we shall denote

the n-element Heyting chain simply by n. The following theorem is due to B. A. Davey and

J. G. Pitkethly [7].

3.4 Theorem [7, Theorems 4.1 and 4.2] If M is a ﬁnite Heyting chain or the Heyting algebra

⊕ 1 then all algebras of the variety generated by M are endoprimal.

We see that beside the varieties generated by a primal algebra there are other ones with

the property that all their members are endoprimal. It might be an interesting problem to

try to describe all varieties with this property, at least under the restrictions that they are

ﬁnitely generated and admit a majority term.