NONDUALIZABLE SEMIGROUPS

DAVID HOBBY

Abstract. A family of semigroups is produced, none of which can be dualized.

One of the fundamental problems in the theory of natural dualities is the dualizability problem, that of deciding which finite algebras are dualizable, generating a quasi-variety which admits a natural duality. This problem has been solved piecemeal for a variety of well-known algebras. Dualizable classes include Boolean Algebras (shown by Stone in [14]), Distributive Lattices (by Priestley in [11] and [12]) and Abelian Groups (by Pontryagin in [9] and [10]). Many more examples are included in [2], the definitive book by Clark and Davey.

In many classes of algebras, the “simplest” algebras are dualizable, while the others are not. But the dualizability problem of determining which algebras in a given class are dualizable seems to be very difficult in general. In a few cases the dualizability problem has been completely solved, with some elements of the class proved dualizable and the others proved nondualizable. The most successful results are for the class of congruence distributive algebras. (Who??) proved in (cite something??) that an algebra in a congruence distributive variety is dualizable if it has an n-ary near-unanimity term for some n. And Davey, Heindorf and McKenzie proved the converse in [6]. Together, these two results solve the dualizability problem for congruence distributive algebras.

Two other classes for which the dualizability problem has been solved are finite Commutative Rings (by Clark, Idziak, Sabourin, Szabó and Willard in [5]) and three-element unary algebras (by Clark, Davey and Pitkethly in [4]). The latter also constitutes a nice example that shows how difficult it can be to separate the dualizable algebras from the nondualizable ones. Indeed, most of those who have studied the problem conjecture that there is no recursive method for solving it in general. (Cite something? McKenzie, et al?)

An area that is presently being worked on is the class of Semigroups. As mentioned above, Abelian Groups are dualizable. And Quackenbush and Szabó proved in [13] that finite nilpotent groups are not dualizable. While the dualizability problem is still not completely solved for Groups, it is even more open for Semigroups in general. Clark and Davey show in [2] that both Rectangular Bands and Meet-Semilattices with one are dualizable. (The last example does use a language with an additional constant. Since the dualizability of an algebra depends on what one chooses its type to be, this result is not directly applicable.) And (Knox?) shows in (?) that certain small commutative semigroups are dualizable. Apart from the work of Quackenbush and Szabó mentioned above, no examples of nondualizable semigroups were known. The role of this paper is to provide a new class of such examples, the first which are not groups.

Date: August, 2000.

1991 Mathematics Subject Classification. Primary 08C05, 08A60; Secondary 18A40, 20M99.

Key words and phrases. Natural duality, dualizability, ghost elements, semigroups.

The new results are in the second section, after a preliminary section devoted to background material and notation. A section of examples and remarks concludes this paper.

1. Preliminaries

We let ℕ denote {0, 1, 2, … }, the set of natural numbers, and we use ℕ^{+} for the set {1, 2, 3, … }. Our notation will be standard for Universal Algebra–either of the books [1] or [8] may be used as a reference.

We will briefly review the specialized concepts and theorems that will be needed. A more detailed exposition may be found in Clark and Davey [2]. Let \underline{M} be a finite algebra. An algebraic relation on \underline{M} is a relation r ⊆ M^{n} which forms a subalgebra of \underline{M}^{n}, for some n ∈ ℕ. An algebraic operation on \underline{M} is a homomorphism g : \underline{M}^{n} → \underline{M}, for some n ∈ ℕ. And an algebraic partial operation on \underline{M} is a homomorphism h : D → \underline{M} such that D is a subalgebra of \underline{M}^{n}, for some n ∈ ℕ^{+}.

We say that a topological structure M ∼ = ⟨M; G, H, R, T ⟩ is an alter ego of \underline{M} if G is a set of algebraic operations, H is a set of algebraic partial operations and R is a set of algebraic relations on \underline{M}, and T is the discrete topology on M. We hope to use some alter ego M ∼ of \underline{M} to represent the algebras in the quasi-variety 𝒜 := 𝕀𝕊ℙ \underline{M} as algebras of continuous homomorphisms.

To see how this works, let M ∼ = ⟨M; G, H, R, T ⟩ be some fixed alter ego of \underline{M}. Given A ∈ 𝒜 , we define its dual, D(A), to be the set 𝒜 (A, \underline{M}), of all homomorphisms from A to \underline{M}, regarded as a substructure of M ∼^{A}. Thus D(A) belongs to the category 𝒳 := 𝕀𝕊_{c}ℙ^{+} M ∼ consisting of all isomorphic copies of topologically closed substructures of non-zero powers of M ∼. Similarly, the dual, E(X), of a structure X ∈ 𝒳 is the set 𝒳 (X, M ∼) regarded as a subalgebra of \underline{M}^{X}. There is a natural evaluation map e_{A} : A → ED(A), given by e_{A}(a)(x) := x(a), for all a ∈ A and each x ∈ D(A). The map e_{A} is an embedding, since A belongs to the quasi-variety 𝕀𝕊ℙ \underline{M}. For each a ∈ A, we say that the map e_{A}(a) is given by evaluation at a and that e_{A}(a) is an evaluation. For any Y ⊆ D(A) and for any a ∈ A, a map α : D(A) → M is given by evaluation at a on Y if α↾_{Y} = e_{A}(a)↾_{Y}. A subset B of A is a support for such a map α : D(A) → M iff for all x, y ∈ D(A) with x↾_{B} = y↾_{B} we have α(x) = α(y).

We say that M ∼ yields a duality on A, or equivalently, that G ∪ H ∪ R yields a duality on A, iff e_{A} is surjective. For in this case e_{A} is an isomorphism from A onto the algebra of all continuous homomorphisms from its dual, D(A), into M ∼. Thus, M ∼ yields a duality on A iff every morphism α : D(A) → M ∼ is an evaluation. We say that the structure M ∼ yields a duality on 𝒜 iff e_{A} is surjective for all A ∈ 𝒜 . If M ∼ yields a duality on 𝒜 , then we also say that M ∼ dualizes \underline{M}. Finally, if there is some alter ego M ∼ of \underline{M} which dualizes \underline{M}, then we say that \underline{M} is dualizable. When no alter ego exists which dualizes it, we of course say that \underline{M} is nondualizable.

For each n ∈ ℕ^{+}, let R_{n} denote the set of n-ary algebraic relations on \underline{M}. Let A ∈ 𝕀𝕊ℙ \underline{M} and let α : D(A) → M. We say that α preserves R_{n} if α preserves every relation in R_{n}. The following lemma was first explicitly proved in [3]. It is also implicit in [2], and proved again in [4].

Lemma 1.1 Let n ∈ ℕ, let A ∈ 𝕀𝕊ℙ \underline{M} and let α : D(A) → M. Then α agrees with an evaluation on each n-element subset of D(A) if and only if α preserves R_{n}.

Proof Assume that α preserves R_{n} and let x_{1}, …, x_{n} ∈ D(A). The relation r := { (x_{1}(b), …, x_{n}(b)) | b ∈ A } belongs to R_{n}, so r is preserved by α. Thus there is an a ∈ A such that α(x_{i}) = x_{i}(a), for all i ∈ {1, …, n}. The other direction is easy.

2. A Condition for Nondualizability

We will use the ghost element method to prove that certain semigroups nondualizable. This method was introduced in [7] and has been used extensively since then. For a good survey of its use, the interested reader is refered to [2].

The basic idea of this method is to use the following lemma to obtain a contradiction. The version given here is taken from [2]. For an algebra A ⩽ \underline{M}^{S} and s ∈ S, we define ρ_{s} : A → \underline{M} to be the restriction to A of the projection onto s.

Lemma 2.1 Let \underline{M} be a finite algebra. Let S be a non-empty set, let A ⩽ \underline{M}^{S} and let α : D(A) → M. Assume that

(i) α has finite support in A, and (ii) α is an evaluation on each finite subset of D(A).

Define g_{α} ∈ M^{S} by g_{α}(s) := α(ρ_{s}), for all s ∈ S. If \underline{M} is dualizable, then g_{α} ∈ A.

Proof Assume that some structure M ∼ = ⟨M; G, H, R, T ⟩ yields a duality on 𝕀𝕊ℙ \underline{M}. It is easy to see that (i), insures that the map α is continuous. By (ii) and Lemma 1.1, we have that the map α preserves R_{n} for all n. So α preserves every relation r ∈ R, and it preserves the graph of each h in G ∪ H. Thus α : D(A) → M ∼ is a morphism. So there is some a ∈ A such that α is given by evaluation at a. For all s ∈ S, we have g_{α}(s) = α(ρ_{s}) = ρ_{s}(a) = a(s). Thus g_{α} = a ∈ A.

This lets us show that a finite algebra \underline{M} is non-dualizable by finding an algebra A and a map α : D(A) → M which satisfies (i) and (ii) of Lemma 2.1, such that g_{α} ∉ A. The element g_{α} is then called a ghost element of A.

We will use the following refinement of the previous lemma for all our ghost element proofs. In it, we take the set S to be ℕ and make a number of other fairly nonrestrictive assumptions. This lemma first appeared in [4]; a proof has been provided for completeness.

Lemma 2.2 Let \underline{M} be a finite algebra. Let g ∈ M^{ℕ}, let A_{0} ⊆ M^{ℕ} and let A ⩽ \underline{M}^{ℕ} with A_{0} ⊆ A. Assume there is some m_{0} ∈ M, a finite subset A_{f} of A_{0}, and a directed order ≼ on A_{0} such that the following hold:

(i) g^{−1}(m_{0}) ⊇ ⋃{a^{−1}(m_{0}) | a ∈ A_{f}} and g^{−1}(m) ⊇ ⋂{a^{−1}(m) | a ∈ A_{f}}, for all m ∈ M\{m_{0}};

(ii) for every homomorphism x : A → \underline{M} such that x↾_{A_{0}} is not constant, we have m_{0} ∈ x(A_{f}) and A_{x} ⊆ x^{−1}(m_{0}), for some upset A_{x} of ⟨A_{0}; ≼⟩.

If \underline{M} is dualizable, then g ∈ A.

Proof Let a_{0} be any fixed element of A_{f}, and define α : D(A) → M by

α(x) = \begin{cases}x(a_{0}) & if m_{0} ∉ x(A_{f}), \\ m_{0} & otherwise. \end{cases}

We will first show that when g_{α} is defined as in Lemma2.1, that it is in fact equal to g. So consider any n ∈ ℕ, and put ρ_{n} in for x. Our first case is where m_{0} ∉ ρ_{n}(A_{f}). Then ρ_{n}↾_{A_{0}} is constant, by (ii). We must show that g(n) = ρ_{n}(a_{0}), for then we will have g(n) = ρ_{n}(a_{0}) = α(ρ_{n}) = g_{α}(n). Letting m = ρ_{n}(a_{0}), we have m ≠ m_{0}. Since ρ_{n}↾_{A_{0}} is constant, ρ_{n}(a) = m for all a ∈ A_{0}. Thus n ∈ a^{−1}(m) for all a ∈ A_{f}, and n ∈ g^{−1}(m) by (i). This gives g(n) = m = ρ_{n}(a_{0}), as required.

Our other case is where m_{0} ∈ ρ_{n}(A_{f}). Then n is in ⋃{a^{−1}(m_{0}) | a ∈ A_{f}}, which is a subset of g^{−1}(m_{0}) by (i). Thus g(n) = m_{0} = α(ρ_{n}) = g_{α}(n). This shows that g = g_{α}.

The set A_{f} is clearly a finite support for α. To see that α is locally an evaluation, let X be a finite subset of D(A). Let X_{nc} denote the set of all x ∈ X such that x↾_{A_{0}} is not constant, and for each x ∈ X_{nc} let A_{x} be as in (ii). Since the order ≼ is directed on A_{0}, the finite intersection ⋂{ A_{x} | x ∈ X_{nc} } is nonempty. Thus there is an element a of A_{0} which is in all those A_{x}. For all x ∈ X\X_{nc}, we have α(x) = x(a_{0}) = x(a). And for all x ∈ X_{nc}, we have α(x) = m_{0} = x(a), because a ∈ A_{x}. This shows that α↾_{X} is given by evaluation at a. It now follows from Lemma 2.1 that g ∈ A if \underline{M} is dualizable.

For various semigroups \underline{M} we will be working with elements of the Cartesian power M^{ℕ} that are almost everywhere constant. It will be convenient to modify some notation from [4] to refer to these sequences. So let k, n_{1}, …, n_{k} ∈ ℕ and let

a, b_{1}, …, b_{k} ∈ M. We define the sequence a\begin{matrix}b_{1} \\ n_{1} \end{matrix}\begin{matrix}... \\ ... \end{matrix}\begin{matrix}b_{k} \\ n_{k} \end{matrix} in M^{ℕ} by

a\begin{matrix}b_{1} \\ n_{1} \end{matrix}\begin{matrix}... \\ ... \end{matrix}\begin{matrix}b_{k} \\ n_{k} \end{matrix}(i) = \begin{cases}b_{j} & if i = n_{j}, for some j ∈ \{1, …, k\}, \\ a & otherwise. \end{cases}

Ghost element arguments in the literature tend to be ad hoc, with new approaches needed for every new class of algebras. It does indeed seem to be hard to prove a nice general result for semigroups by this method as well. The next lemma does the best it can to carve out as large a class of semigroups as possible in which one particular kind of ghost element argument shows nondualizability.

Lemma 2.3 Let \underline{M} be a finite semigroup. Suppose that there are three distinct elements a, b and c of \underline{M} such that the following conditions hold.

(i) For all x ∈ M, a · x = a and b · x = b. (ii) c is an identity for {a, b, c}, that is, a · c = c · a = a, b · c = c · b = b, and

c · c = c. (iii) Any endomorphism of \underline{M} that does not send a and b to the same element is

equal to the identity on {a, b, c}. (iv) Let C be the subalgebra of \underline{M}^{3} generated by the set

\{h ∈ M^{3} | h(j) = b for some j in \{0, 1, 2\}\}. Any homomorphism of C into \underline{M} that sends ⟨a, b, a⟩ to a, ⟨b, b, a⟩ to b and ⟨c, b, a⟩ to c must also send ⟨a, a, b⟩ to a.

Then \underline{M} is not dualizable.

Proof Suppose that \underline{M} is a finite semigroup that satisfies the conditions of the lemma. We will use Lemma 2.2, taking g ∈ M^{ℕ} to be a\begin{matrix}b \\ 0 \end{matrix} (That is, ⟨b, a, a, a, ...⟩). The set A_{0} will be \{a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ j \end{matrix} | j ⩾ 0\}, and we will take A to be the subalgebra of \underline{M}^{ℕ} generated by A_{0} together with {h ∈ M^{ℕ} | h(0) = b and there exists j ⩾ 0 with h(j) = b}. Note that condition (i) implies that g is not in A. We let m_{0} be a, A_{f} be \{a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ 1 \end{matrix}, a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ 2 \end{matrix}\} and define ≼ on A_{0}

by setting a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ i \end{matrix} ≼ a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ j \end{matrix} iff i ⩽ j.

Then g^{−1}(m_{0}) = g^{−1}(a) = ℕ \ {0} ⊇ (ℕ \ {0, 1}) ∪ (ℕ \ {0, 2}) = ⋃{h^{−1}(b) | h ∈ A_{f}}, g^{−1}(b) = {0} = ⋂{h^{−1}(b) | h ∈ A_{f}}, and so on, showing that (i) of Lemma 2.2 is satisfied.

For (ii), let x : A → \underline{M} be such that x↾_{A_{0}} is not constant. So there are m, n ⩾ 1 with x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ m \end{matrix}) ≠ x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ n \end{matrix}). Now consider x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix}). It must be different from at least one of x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ m \end{matrix}) and x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ n \end{matrix}). Without loss of generality, suppose it differs from x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ m \end{matrix}), and consider B = \{a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}d \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix} | d ∈ M\}. We have that B is a subalgebra of A, and that f : \underline{M} → B given by f(d) = a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}d \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix} is an isomorphism.

Then (x↾_{B})∘f is an endomorphism of \underline{M} that takes a and b to different elements, so it is the identity on \{a, b, c\} by (iii). Thus x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}a \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix}) = a, x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix}) = b and

x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}c \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix}) = c.

Now consider x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ k \end{matrix}), where k is a number different from 0, m and n. We will be done if we can show that x(a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ k \end{matrix}) must always be a, for then a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ n \end{matrix} will be the only element of A_{0} that x does not send to a, and A_{x} = \{a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ j \end{matrix} | j ⩾ n + 1\} will be the requisite upset of ≼.

To simplify the remainder of the argument, we will assume that m = 1, n = 2 and k = 3. Observe that {h ∈ A | h(0) = b and h(j) = a for all j ⩾ 4} is a subalgebra of A, and that it is isomorphic to the algebra C of condition (iv) in a natural way, where a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}a \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix}, a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix} and a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}c \\ m \end{matrix}\begin{matrix}b \\ n \end{matrix} correspond to ⟨a, b, a⟩, ⟨b, b, a⟩ and ⟨c, b, a⟩, respectively. So the restriction of x to this subalgebra of A corresponds to a homomorphism of C into \underline{M} that takes ⟨a, b, a⟩ to a, ⟨b, b, a⟩ to b and ⟨c, b, a⟩ to c. By condition (iv), this homomorphism must take ⟨a, a, b⟩ to a. This implies that

x takes a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}b \\ k \end{matrix} = a\begin{matrix}b \\ 0 \end{matrix}\begin{matrix}a \\ m \end{matrix}\begin{matrix}a \\ n \end{matrix}\begin{matrix}b \\ k \end{matrix} to a.

Note that there are some trade-offs between the statements of conditions (iii) and (iv) in the previous lemma. This is governed by the size of the algebra A used in the proof. A similar argument will work for a range of situations. We may take A to be as small as possible, and say that it is generated by {h ∈ {a, b, c}^{ℕ} | h(0) = b and there exists j ⩾ 0 with h(j) = b}. Then condition (iii) would be modified to refer to homomorphisms into \underline{M} from the subalgebra of \underline{M} generated by \{a, b, c\}. Condition (iv) would also be modified by defining C to be the subalgebra generated by {h ∈ {a, b, c}^{3} | h(j) = b for some j in {0, 1, 2}}. We could also take A to be larger than in the lemma, provided that its universe did not contain the ghost element g. Condition (iii) would stay the same, but the subalgebra C used in condition (iv) could be larger. The version of the lemma given has a simple statement, and will suffice for our purposes.

It seems natural to define semigroups by representing them as sets of functions under composition, for this way it is not necessary to check associativity. By the analogue of Cayley’s Theorem, nothing is lost by doing this.

If p ⩾ 2, we define the following functions on {0, 1, 2, ⋯ p}. Let 0, 1, 2, ⋯ p be the constant functions with values 0, 1, 2, ⋯ p respectively. If T is any subset of {2, 3, ⋯ p}, we define the function f_{T} on {0, 1, 2, ⋯ p} by setting f_{T} (n) to be 1 if n = 1 or n ∈ T and to be 0 otherwise. Observe that whenever T and U are subsets of {2, 3, ⋯ p}, that f_{T} ∘ f_{U} = f_{U}, 0 ∘ f_{T} = f_{T} ∘ 0 = 0, and so on. This shows that any set of the form {0, 1, 2, ⋯ p, f_{T} , f_{U}, f_{V} , ⋯ } is closed under composition and forms a semigroup. We will call semigroups produced by this construction 2idempotent derived, since their nonconstant functions are all 2-idempotent, that is idempotent functions into a common two element set. So which 2-idempotent derived semigroups can be shown by Lemma 2.3 to be nondualizable?

Theorem 2.4 Let p ⩾ 2, let n ⩾ 1, and let T_{1}, T_{2}, ...T_{n} be subsets of {2, 3, ⋯ p}. Then if the following conditions are met the semigroup ⟨{0, 1, 2, ⋯ p, f_{T_{1}}, f_{T_{2}}, ⋯ f_{T_{n}}}, ∘⟩ is not dualizable.

(i) For all distinct elements q and r of {0, 1, 2, ⋯ p}, there is a set T_{j} for some j ⩽ n such that f_{T_{j}}(q) ≠ f_{T_{j}}(r).

(ii) There is a set T = T_{j} for some j such that |T | and p − 1 − |T | are not equal, and none of the other sets T_{1}, T_{2}, ⋯ T_{n} are of either of those cardinalities.

Proof Let S = ⟨{0, 1, f_{T_{1}}, f_{T_{2}}, ⋯ f_{T_{n}}}, ∘⟩ satisfy conditions (i) and (ii) of the theorem, and let T be as in condition (ii). We will use Lemma 2.3, with a = 0, b = 1 and c = f_{T}. Checking the conditions of the lemma, we see that (i) is true since the functions a and b are constant. Condition (ii) holds since f_{T} is constant on both 0 and 1.

For (iii), we first show that S is subdirectly irreducible with monolith {0, 1}^{2} ∪Δ. So let distinct q and r in S be given. If q and r are both in {0, 1, 2, ⋯ p}, then (i) gives a T_{j} such that one of f_{T_{j}}(q) and f_{T_{j}}(r) is 0 and the other is 1. This shows that ⟨0, 1⟩ ∈ Cg(⟨q, r⟩). Next suppose that one of the two elements, say q, is in {0, 1, 2, ⋯ p}, while r is some f_{T_{j}}. Then r ∘ 0 = f_{T_{j}}(0) = 0, while q ∘ 0 = q. Thus ⟨q, 0⟩ ∈ Cg(⟨q, r⟩). Similarly, r∘1 = f_{T_{j}}(1) = 1 and q∘1 = q yield ⟨q, 1⟩ ∈ Cg(⟨q, r⟩). Combining, we get ⟨0, 1⟩ ∈ Cg(⟨q, r⟩). Lastly, suppose that q is f_{T_{i}} and r is f_{T_{j}}, for some i and j. Since q ≠ r, there is some s ⩽ p with f_{T_{i}}(s) ≠ f_{T_{j}}(s). That is, f_{T_{i}} ∘ s ≠ f_{T_{j}} ∘ s. So one is 0, the other is 1, and ⟨0, 1⟩ ∈ Cg(⟨q, r⟩). It is easy to verify that {0, 1}^{2} ∪ Δ is a congruence, so it is the monolith of S.

So we have that any endomorphism of S that does not send 0 and 1 to the same place must actually be an automorphism. Such an automorphism would have to permute the elements 0, 1, 2, ⋯ p of S, since they are characterized as the values of y such that y ∘ z = y for all z. Now consider c, which is f_{T} where T is as in (ii). We see that f_{T} ∘x has one value (i.e. 1) for |T |+1 many values of x in {0, 1, 2, ⋯ p}, and another (i.e. 0) for the other p−|T | possible values of x in {0, 1, 2, ⋯ p}. Condition (ii) of the theorem implies that f_{T} is unique in this respect, so it must be fixed by any automorphism. We also have that the two values of the expression f_{T} ∘ x for x ∈ {0, 1, 2, ⋯ p} are fixed–they are 0 and 1. (In case T is ∅ or {2, 3, ⋯ p}, only one of 0 and 1 is obtained this way. The other one can then be found by looking at the values of f_{T_{j}} ∘ x for some other j.) This shows that (iii) of Lemma 2.3 is satisfied.

To see that (iv) holds, let C be the subalgebra of S^{3} and let x : C → S be a homomorphism with x(⟨a, b, a⟩) = a, x(⟨b, b, a⟩) = b and x(⟨c, b, a⟩) = c. Since

\begin{matrix}∘ & 0 & 1 & 2 & 3 & f_{∅} & f_{\{2\}} & f_{\{3\}} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ f_{∅} & 0 & 1 & 0 & 0 & f_{∅} & f_{\{2\}} & f_{\{3\}} \\ f_{\{2\}} & 0 & 1 & 1 & 0 & f_{∅} & f_{\{2\}} & f_{\{3\}} \\ f_{\{3\}} & 0 & 1 & 0 & 1 & f_{∅} & f_{\{2\}} & f_{\{3\}} \end{matrix}

Table 1. Smallest nondualizable semigroup known

⟨c, b, a⟩ = ⟨c, b, a⟩ ∘ ⟨c, a, b⟩, c = c ∘ x(⟨c, a, b⟩). It is clear that x(⟨c, a, b⟩) must be an f_{T_{j}}, so c ∘ x(⟨c, a, b⟩) = x(⟨c, a, b⟩) and c = x(⟨c, a, b⟩). Now ⟨c, a, b⟩ ∘ ⟨a, b, a⟩ = ⟨a, a, b⟩, so c ∘ a = x(⟨a, a, b⟩). That is, a = x(⟨a, a, b⟩), as required.

As with Lemma 2.3, it is possible to modify the statement of this theorem so that it still applies even when conditions (i) and (ii) are not quite met. But it seems that as the conditions are weakened, the proof grows rapidly more complicated! The examples in the next section will make this point clearer.

3. Examples and Remarks

The smallest 2-idempotent derived semigroups do not meet the conditions of Theorem ??. When p = 2, the only possible 2-idempotent functions are f_{{2}} and f_{∅}. Condition (i) fails unless both are included in the semigroup, but (ii) fails if they are.

When p = 3, there are four 2-idempotent functions: f_{∅}, f_{{2}}, f_{{3}}, f_{{2,3}}. Condition (i) holds whenever at least three of them are included, or when just f_{{2}} and f_{{3}} are. But condition (ii) fails for all of these, except when the set of included functions is {f_{∅}, f_{{2}}, f_{{3}}}. (Or when it is {f_{{2}}, f_{{3}}, f_{{2,3}}}, but that yields an isomorphic semigroup.) So the smallest nondualizable semigroup given by the theorem has its operation given by Table 1.

To explicitly demonstrate that there are infinitely many 2-idempotent derived semigroups that are not dualizable, we can generalize the previous example in the following way. For each p ⩾ 3, we let S_{p} be the semigroup obtained by including the 2-idempotent functions f_{∅}, f_{{2}}, f_{{3}}, f_{{4}}, ⋯ f_{{p}}. It is easily verified that all of the S_{p} satisfy conditions (i) and (ii) of Theorem 2.4.

Other semigroups can also be shown to be nondualizable by using Lemma 2.3 directly. The arguments are of course more involved. As a second example, here is the first nondualizable semigroup I discovered. Consider functions on the set {0, 1, 2, 3}, where 0, 1, 2 and 3 are the respective constant functions. We add to these f_{∅} and f_{{3}}, defined as in the first example. And also add two more functions g and h, defined as follows: g(0) = 2, g(1) = 3, g(2) = 2, g(3) = 3 and h(0) = 2, h(1) = 3, h(2) = 2, h(3) = 2. Let K = ⟨{0, 1, 2, 3, f_{{3}}, g, f_{∅}, h}, ∘⟩ be the semigroup formed by these functions.

[figure: 0; 1; 2; 3; f_{{3}}; 0; 1; 2; 3; g; 0; 1; 2; 3; f_{∅}; 0; 1; 2; 3; h]

Figure 1. Functions for the second example

\begin{matrix}∘ & 0 & 1 & 2 & 3 & f_{\{3\}} & g & f_{∅} & h \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ f_{\{3\}} & 0 & 1 & 0 & 1 & f_{\{3\}} & f_{\{3\}} & f_{∅} & f_{∅} \\ g & 2 & 3 & 2 & 3 & g & g & h & h \\ f_{∅} & 0 & 1 & 1 & 1 & f_{\{3\}} & 1 & f_{∅} & 1 \\ h & 2 & 3 & 3 & 3 & g & 3 & h & 3 \end{matrix}

Table 2. The operation of K

The reader easily verifies that the eight functions of K form a semigroup under composition, and that the table of this group is as in Table 2.

Theorem 3.1 The semigroup K given above is not dualizable.

Proof We will use Lemma 2.3, taking a = 0, b = 1 and c = f_{{3}}. Conditions (i) and (ii) are easily verified by looking at the table for K.

To see that condition (iii) holds, we first observe that whenever q and r are distinct elements of K, that ⟨0, 1⟩ ∈ Cg(⟨q, r⟩), unless {q, r} = {1, 3} (This is best done by trying all possible values for the pair ⟨q, r⟩, each time using the table). Now consider any endomorphism x of K that does not send 0 and 1 to the same place. By the above, it must have either Δ or Cg(⟨1, 3⟩) = {1, 3}^{2} ∪ Δ as its kernel. Looking at the patterns in the rows of the table, we see that x must preserve the set {0, 1, 2, 3} (That is, send its elements back into the set). Since the patterns of their rows are sufficiently different, x must also preserve the sets {f_{{3}}, g} and {f_{∅}, h}. We now look at the patterns in the columns of the table, keeping in mind the sets we know are preserved. This gives us that the element f_{∅} must stay fixed under x. For we know that f_{∅} must go to an element of {f_{∅}, h}, and we have f_{{3}} ∘ f_{∅} = f_{∅} ∘ f_{∅}. This implies that x(f_{{3}}) ∘ x(f_{∅}) = x(f_{∅}) ∘ x(f_{∅}), where x(f_{{3}}) ∈ {f_{{3}}, g} and x(f_{∅}) ∈ {f_{∅}, h}. The only solution is where x(f_{∅}) = f_{∅} and x(f_{{3}}) = f_{{3}}. A similar argument shows that x(h) = h as well.

This implies that f_{∅} ∘ h = 1 and h ∘ h = 3 are also fixed under x. Thus x is an automorphism that fixes 1, 3, f_{∅} and h. It is now easy to verify by looking at columns in the table that x must be the identity, which is more than enough to show (iii).

To show (iv), recall that a = 0, b = 1 and c = f_{{3}}. We let C be the subalgebra of K^{3} generated by {l ∈ K^{3} | l(j) = b for some j in {0, 1, 2}}, and let y : C → K send ⟨a, b, a⟩ to a, ⟨b, b, a⟩ to b and ⟨c, b, a⟩ to c. We must show that y(⟨a, a, b⟩ = a.

Since ⟨c, b, a⟩ ∘ ⟨c, a, b⟩ = ⟨c, b, a⟩, we have that c ∘ y(⟨c, a, b⟩) = c. So y(⟨c, a, b⟩) is f_{{3}} or g. Thus ⟨a, a, b⟩ = ⟨c, a, b⟩ ∘ ⟨a, b, a⟩ implies that y(⟨a, a, b⟩) is either f_{{3}} ∘ 0 = 0, or g ∘ 0 = 2. We want to show that the second possibility leads to a contradiction.

So assume that y(⟨a, a, b⟩) = 2. Then ⟨a, c, b⟩ ∘ ⟨a, a, b⟩ = ⟨a, a, b⟩ implies y(⟨a, c, b⟩) ∘ 2 = 2 and y(⟨a, c, b⟩) ∈ {2, g}. And ⟨a, b, c⟩) ∘ ⟨a, b, a⟩ = ⟨a, b, a⟩ implies y(⟨a, b, c⟩) ∘ 0 = 0 and y(⟨a, b, c⟩) ∈ {0, f_{{3}}, f_{∅}}. But ⟨a, c, b⟩ ∘ ⟨a, b, c⟩ = ⟨a, b, b⟩ = ⟨a, b, c⟩ ∘ ⟨a, c, b⟩, so y(⟨a, c, b⟩) and y(⟨a, b, c⟩) must commute. Trying all possible values for them, we see that this is impossible. This contradiction shows that y(⟨a, a, b⟩) = 0 = a, and (iv) is proved.

Note how complex the argument showing condition (iv) was in the above proof. This complexity seems to be necessary, and explains the somewhat inelegant form of condition (iv). It seems difficult to give a simpler version of this condition without weakening it.

References

1. S. Burris and H.P. Sankappanavar, A Course in Universal Algebra, Springer, New York, Heidelberg, Berlin, 1981.

2. D.M. Clark and B.A. Davey, Natural Dualities for the Working Algebraist, Cambridge University Press, Cambridge, 1998.

3. D.M. Clark, B.A. Davey, and J.G. Pitkethly, Binary homomorphisms and natural dualities, preprint.

4. D.M. Clark, B.A. Davey, and J.G. Pitkethly, Dualisability of three-element unary algebras, preprint.

5. D.M. Clark, P. Idziak, L. Sabourin, Cs. Szabó, and R. Willard, Natural dualities for quasivarieties generated by a finite commutative ring, preprint.

6. B.A. Davey, L. Heindorf, and R. McKenzie, Near unanimity: an obstacle to general duality theory, Algebra Universalis 33 (1995), 428–439.

7. B.A. Davey and H. Werner, Dualities and equivalences for varieties of algebras, Contributions to lattice theory (Szeged, 1980), North-Holland, Amsterdam, 1983, 101–275.

8. R.M. McKenzie, G.F. McNulty and W.F. Taylor, Algebras, Lattices, Varieties. Vol. 1, Wadsworth & Brooks/Cole, Monterey, California, 1987.

9. L.S. Pontryagin, Sur les groupes abélian continus, C.R.Acad. Sci. Paris 198 (1934), 238–240.

10. L.S. Pontryagin, The theory of topological commutative groups, Ann. Math. 35 (1934), 361– 388.

11. H.A. Priestley, Representation of distributive lattices by means of ordered Stone spaces, Bull. London Math. Soc. 2 (1970), 186–190.

12. H.A. Priestley, Ordered topological spaces and the representation of distributive lattices, Proc. London Math. Soc. 3 24 (1972) 507–530.

13. R. Quackenbush and Cs. Szabó, Finite nilpotent groups are not dualizable, preprint, 1997.

14. M.H. Stone, The theory of representations for Boolean Algebras, Trans. Amer. Math. Soc. 4 (1936), 37–111.

SUNY, New Paltz, NY 12561, U.S.A.

E-mail address: hobby@mcs.newpaltz.edu