Basic notions of (constructive) semigroups with apartness

Abstract

We examine basic notions of special subsets and orders in the context of semigroups with apartness and prove constructive analogues of some classical theorems relating such subsets and orders.

1 Introduction

Errett Bishop-style constructive mathematics (BISH) forms the framework for our work. BISH originated in 1967 with the publication of the book [1] in which a large part of modern analysis with constructive background was developed. There has been a steady stream of publications contributing to Bishop’s programme since 1967, see [6, 9, 24]. A 10-year long systematic research of computable topology, using apartness as the fundamental notion, resulted in the first book [10] on topology within BISH framework. Modern algebra, as is noticed in [7], “contrary to Bishop’s expectations, also proved amenable to natural, thoroughgoing, constructive treatment”. Constructive algebra is more complicated than classical in various ways. For example, an algebraic structure as a rule does not carry a decidable equality relation; there is (sometime) awkward abundance of all kinds of substructures.

Throughout this paper our basic structure will be semigroup with apartness. Following [24, Vol. II], “The study of algebraic structures in an intuitionistic setting was undertaken by Heyting [14]. Heyting considered structures equipped with an apartness relation in full generality”. Since then several authors have worked in this area, for more details see, for example, [18, 24]. There is no doubt about deep connections of constructive mathematics with computer science, see, for example, [7]. In [17] it is shown that constructive algebraic structures with apartness can be applied in computer science (especially in computer programming) as well. Within BISH the history of constructive semigroups with an inequality began recently. For example, in proving a constructive version of the Spectral Mapping Theorem, Bridges and Havea [8] have used such constructive semigroups. Isomorphism Theorems for semigroup with apartness have been proved in [11].

The main objective of this paper is to outline some of the basic concepts of semigroups with apartness, such as special subsets on the one side, and orders on the other side. Constructive analogues of classical theorems about their mutual connections will be proved too. Our work is based on applications of ideas and notions coming from [5, 10]. Presented results are partly inspired by some classical ones which are overviewed in Sect. 2. Special subsets of a set or a semigroup with apartness, as well as coquasiorders defined on such structures are subject of Sect. 3. Positive coquasiorders, i.e., coquasiorders with some special properties in connection with multiplication, are constructed and studied in Sect. 4. Some special positive coquasiorders are treated too.

More background on constructive mathematics can be found in [1, 3, 6, 9, 10, 24]. The standard reference for constructive algebra is [18]. For classical semigroup theory see [19, 20, 22].

Our semantical models will be Kripke models with constant domains [24]. A Kripke model with constant domain is a Kripke model $\mathscr {K}\equiv (K, \le , \Vdash , D)$ such that $D(k)=D$ for all $k\in K$. If x is not a free variable of P, we have

$$\begin{aligned} \Vdash \forall _x\, (P\vee R(x))\, \rightarrow \ (P\vee \forall _x\,R(x)). \end{aligned}$$

2 Classical case

As we pointed above, results of this paper are partly inspired by the ones coming from classical semigroup theory. Classical results in question are given in this section.

Various approaches have been developed over the years to construct frameworks for understanding the structure of semigroups. Introductional and basic study of semigroups (of any kind) includes a description of special subsets, special elements, ideals, Green’s relations, homomorphisms, congruences. For the purpose of this work, we are going to list some of them. A number of subsets of a semigroup enjoy special properties relative to the multiplication. A subset T of a semigroup S is:

• completely isolated if $ab\in T$ implies $a\in T$ or $b\in T,$

• isolated if $a^2\in T$ implies $a\in T,$

• convex if $ab\in T$ implies both $a, b\in T,$

for any $a,b\in S$. A subset T is a subsemigroup if for any $a,b\in T$, we have $ab\in T$. A subsemigroup I of S is an ideal if $as,sa\in I$ for any $a\in I$ and $s\in S$. A subsemigroup T of S which is convex as a subset is called a convex subsemigroup. In an analogous way we define a completely isolated subsemigroup (ideal) or isolated subsemigroup (ideal) of S. Such subsemigroups are used for definitions of certain kind of congruences, whose classes are among them as well. Of great importance is their role in describing the structure of transformation semigroups. We refer the reader to [12, 22] for more details in definitions, properties and applications of such kind of subsemigroups.

Describing a semigroup and its structure may be a formidable task. There are many different techniques developed for that purpose. Semilattice decomposition of semigroups is one of the methods with general applications. For more information on semilattice decomposition of semigroups see [19, 20]. It is shown in [20] that this method leads to the study of completely isolated and isolated ideals and convex subsemigroups.

Now we are going to meet quasiorders, reflexive and transitive binary relations. In (general) semigroup theory their role is especially emphasized in studying the semilattice decomposition of semigroups. Quasiorders are distinguished according to the behavior of their related elements to multiplication. Thus, the starting point is a quasiorder $\rho$ defined on S and called positive, that is, $(a,ab), (a,ba)\in \rho$, for any $a,b\in S$. Further, a positive quasiorder $\rho$ is with cm-property if $(a,c), (b,c)\in \rho$ implies $(ab,c)\in \rho$, for any $a,b,c\in S$. A quasiorder $\rho$ is linear if $(a,b)\in \rho$ or $(b,a)\in \rho$. As usual, $a\rho = \{x\in S \,:\, (a,x)\in \rho \}$, and $\rho a = \{x\in S \,:\, (x,a)\in \rho \}$ are the left and the right $\rho$-class of the element a respectively. Recall that the division relation | on a semigroup S, defined by

$$\begin{aligned} a|b \ \Longleftrightarrow \ (\exists x,y\in S^1) \ b=xay, \end{aligned}$$

for $a,b\in S$, is the smallest positive quasi-order defined on S. Positive quasi-orders have been introduced in [21]. In [23] their link to semilattice decompositions of semigroups has been established. Finally, close connections between positive quasiorders and subsemigroups defined above have been given in [4]. Here we mention some of these results:

• $\rho$ is a positive quasiorder iff $a\rho$ is an ideal iff $\rho a$ is a convex subset of S iff $(ab)\rho \subseteq a\rho \cap b\rho$ iff $\rho a\cup \rho b\subseteq \rho (ab)$;

• $\rho$ is a positive quasiorder with cm-property iff $\rho a$ is a convex subsemigroup iff $(ab)\rho = a\rho \cap b\rho$;

• $\rho$ is a linear positive quasiorder with cm-property iff $a\rho$ is a completely isolated ideal.

In order to end this section, we can say that, from semigroup theory point of view, the interrelations between the following notions are of interest:

• semilattice decomposition of semigroups,

• completely isolated and convex subsemigroups and/or ideals,

• positive quasiorders.

3 Semigroups with apartness

We begin this section by introducing the constructive framework within which our further considerations lie. Following [2] and [15], to define a set S we have to give a property that enables us to construct members of S and to describe the equality between elements of S. We will consider a set S as endowed with a prescribed equivalence relation $\backsimeq$, called the equality of S. Furthermore, we will be interested only in properties P(x) which are extensional in the sense that for all $x_1,x_2\in S$ with $x_1\backsimeq x_2$, $P(x_1)$ and $P(x_2)$ are equivalent. Let $(S,\backsimeq )$ be a nonempty set (i.e., we can construct an element of S). Contrary to classical background, the notion of equality is a matter of convention except that it must be an equivalence relation. The notion of equality of different sets is not defined. The only way in which elements of two different sets can be regarded as equal is by requiring them to be subsets of a third set. For this reason, operations of union and intersection are defined only for sets which are given as subsets of a given set. There is another problem more to be faced with when we consider families of sets that are closed under a suitable operation of complementation. Following [3] “we do not wish to define complementation in the terms of negation; but on the other hand, this seems to be the only method avaliable. The way out of this awkward position is to have a very flexible notion based on the concept of a set with apartness” , the second most important relation in constructive mathematics, [24, p. 384]. Its basic properties are given below.

• (Ap1) ;

• (Ap2) ;

• (Ap3) .

is a set with apartness. If , then x and y are different, or distinct. Roughly speaking, $a\backsimeq b$ means that we have a proof that a equals b while means that we have a proof that a and b are different. Therefore, the negation of $a\backsimeq b$ does not necessarily implies that and vice versa: given a and b, we may have neither a proof that a and b are equal nor a proof that a and b are different. In general, more computational information is required to distinguish elements of a set S, then to show that elements are equal.

An apartness is tight if

• (Ap4)

Apartness (tight one) appears in [15]. The term “pre apartness” for an apartness relation is used in [24]. By extensionality we have

A set with apartness is the starting point for our further considerations, and it will be simply denoted by S. We give a connection between two elementary relations: “to be a subset” (in all sorts of mathematics) and “apartness”, the important one in the constructive case. In doing so we follow [5, 10]. Let $\rhd$ be a relation between an element $x\in S$ and a subset Y defined by

Let Y be a subset of S. The subset

$$\begin{aligned} {\sim } Y \, = \, \{x \in S\, : \, x \rhd Y\} \end{aligned}$$

of S called the complement of Y in S. A subset Y of a set S is detachable in S, or, in short, is a d-subset in S if

$$\begin{aligned} \forall _{ x\in S} \, (x \in Y \vee x \rhd Y ), \end{aligned}$$

i.e., if

$$\begin{aligned} \forall _{ x\in S} \, (x \in Y \vee x \in {\sim } Y). \end{aligned}$$

In what follows d-subsets will be one of the main objects of investigation.

The Cartesian product of two sets with apartness and is the set of all ordered pairs $(s,t)\in S\times T$ with $s\in S$ and $t\in T$, together with the equality and the apartness given by

Let be a set with apartness. A subset of $S\times S$ is called a (binary) relation on S. For any nonempty subset $\tau \subseteq S\times S$ (i.e., for any relation $\tau$ defined on the set S) and any $(a,b)\in S\times S$ we have, by the definition given above,

Among relations defined on S we consider only those which are related to apartness in the following way:

($Q_1$):

.

We call such a relation $\tau$ consistent. A relation $\tau$ is cotransitive if

($Q_2$):

$x \,\tau \,z \ \Rightarrow \ \forall _{y\in S}\,(x\, \tau \,y\ \vee \ y\, \tau \,z)$.

A consistent and cotransitive relation defined on S is called a coquasiorder.

Example 1

Let $S = \{a,b,c,d,e\}$ be a set with diagonal

$$\begin{aligned} \triangle _S = \{ (a,a), (b,b), (c,c), (d,d) , (e,e)\} \end{aligned}$$

as the equality relation. If we denote by $K=\triangle _S \cup \{(a,b),(b,a)\}$, then we can define an apartness on S to be $(S\times S) \setminus K$. Thus, is a set with apartness. The relation $\alpha \subseteq S \times S$, defined by

$$\begin{aligned} \alpha = \{(c,a),(c,b),(d,a),(d,b),(d,c),(e,a),(e,b),(e,c), (e,d)\}, \end{aligned}$$

is a coquasiorder on S.

By the definition, a binary relation $\tau$ on a set S is a subset of $S\times S$. But, to describe the relation, we have to determine which ordered pairs belong to $\tau$, i.e., we have to determine $a\tau$ and $\tau a$, the left and the right $\tau$-class of each element a from S. That is the way to connect (in CLASS and in BISH as well) a relation defined on a given set with certain subsets of the set. Starting from a d-subset T of S, we are able to construct coquasiorders as follows.

Lemma 1

Let T be a d-subset of a set with apartness S. Then

• (i) the relation $\tau$ on S, defined by

  $$\begin{aligned} (a,b)\in \tau \ \Leftrightarrow \ a \rhd T\,\wedge \, b \in T, \end{aligned}$$

  is a coquasiorder on S;

• (ii) the relation $\sigma$ on S, defined by

  $$\begin{aligned} (a,b)\in \sigma \ \Leftrightarrow \ a \in T\,\wedge \, b \rhd T, \end{aligned}$$

  is a coquasiorder on S.

Proof

• (i) Let $(a,b)\in \tau$ and let $x\in S$. So, $a \rhd T$ and $b\in T$ and, as T is a d-subset of S, we have $x\in T$ or for any $t\in T$. If then it follows $(x,b)\in \tau$, or, for $x\in T,$ we have that $(a,x)\in \tau$, and cotransitivity of $\tau$ is proved. By the definition of $\tau$ consistency follows immediately. Thus, $\tau$ is a coquasiorder on S.

• (ii) Proof is similar to (i).

$\square$

Conversely, starting from a given coquasiorder $\tau$, we have d-subsets of S:

Lemma 2

Let $\tau$ be a coquasiorder on a set S. Then $a\tau$ (respectively $\tau a$) is a d-subset of S, such that

$$\begin{aligned} a\rhd a\tau \quad \ (\text {respectively} \ \ a\rhd \tau a), \end{aligned}$$

for any $a\in S$. Moreover, the following implication

$$\begin{aligned} (a,b)\in \tau \quad \Rightarrow \quad a\tau \cup \tau b = S \end{aligned}$$

is true for all $a,b\in S$.

Proof

Let $x\in S$ and $y\in a\tau$. Then, by cotransitivity of $\tau$, we have $(a,x)\in \tau$ or $(x,y)\in \tau$. So, $x\in a\tau$ or, by $(Q_1)$, . Thus, $a\tau$ is a d-subset of S, and, again by $(Q_1)$, we have $a\rhd a\tau$. In a similar manner we can prove that $\tau a$ is a d-subset of S such that $a\rhd \tau a$.

Let $a,b\in S$ such that $(a,b)\in \tau$ and let $x\in S$. This means, by $(Q_2)$, that $(a,x)\in \tau$ or $(x,b)\in \tau$, i.e., $x\in \tau a$ or $x\in \tau b$, or, equivalently, $x\in a\tau \cup \tau b$. Therefore, $S\subseteq a\tau \cup \tau b$, which implies equality. $\square$

Now, we define the notion of a semigroup in a constructive way. In doing so, we follow [13, 24]. A tuple is a semigroup with apartness with as a set with apartness, $\cdot$ a binary operation on S which is associative

• (A) $\forall _{a,b,c \in S} \ [(a\cdot b)\cdot c \backsimeq a\cdot (b\cdot c)]$,

and strongly extensional

• (S) .

As usual, we are going to write ab instead of $a\cdot b$. Until the end of this paper we will consider only semigroups with apartness, calling them, in short, semigroups.

Let be a set with apartness. A function $f:A\longrightarrow A$ is strongly extensional or, for short, an se-function if implies for all $a,b\in A$.

Theorem 1

Let be a set with apartness. If S is the set of all se-functions from A to A, and $\circ$ stands for composition of functions, then with

$$\begin{aligned} f\backsimeq g \ \Longleftrightarrow \ \forall _{x\in A} \, (f(x)\backsimeq g(x)), \end{aligned}$$

and

is a semigroup with apartness.

Proof

By [18, Theorem I.2.2] is a set with apartness.

Let $f, g\in S$ and suppose that for some $x,y\in A$. Then, by the definition of the composition, , and, as f is an se-mapping, we have . Finally, as g is an se-mapping as well, we have . Thus, $f\circ g$ is an se-mapping and $f\circ g\in S$. As in the classical case, composition of functions is associative, [1], so $(S,\circ )$ is a semigroup.

Let $f,g,h,w\in S$ and . Then, by the definition of apartness in S, there is an element $x\in A$ such that , i.e., . Now we have

which, further, implies (because f is an se-mapping) or (by the definition of the apartness relation on S). Thus that is, composition $\circ$ is an se-operation and is a semigroup with apartness. $\square$

The apartness from the previous theorem does not have to be tight as is shown in [11]. For a concrete example of a semigroup with apartness, observe that one can define the following multiplication on the set S from Example 1.

Let and be semigroups with apartness. A homomorphism $\varphi :S\longrightarrow T$ is an se-homomorphism if it is an se-mapping, i.e.,

An se-homomorphism $\varphi$ an se-embedding if $\varphi$ is one-one, i.e.,

Corollary 1

Every semigroup with apartness se-embeds into the semigroup of all strongly extensional self-maps on a set.

Proof

Let be a semigroup with apartness. The semigroup S embeds into the monoid with apartness with equality $\backsimeq _1$ which consists of all pairs in $\backsimeq$ and the pair (1, 1), and with apartness which consists of all pairs in and the pairs (a, 1), (1, a) for each $a\in S$.

Let $f_a$ be a left translation of $S^1$, i.e., $f_a(x) = a\cdot x$, for all $x\in S^1$. Then $f_a$ is an se-function. Indeed, is equivalent to . The strong extensionality of multiplication implies .

Denote by T the set of all se-functions from $S^1$ to $S^1$. As in CLASS, define a mapping $\varphi :S^1\longrightarrow T$ letting

$$\begin{aligned} \varphi (a) = f_a, \end{aligned}$$

for each $a\in S^1$. It is routine to verify that

$$\begin{aligned} \varphi (ab) = f_{ab} = f_a\circ f_b = \varphi (a)\varphi (b), \end{aligned}$$

as well as

Thus, $\varphi$ is an se-homomorphism. Also, $\varphi (a)\backsimeq _T \varphi (b)$ iff $ax \backsimeq _1 bx$ for all $x\in S^1$, and, for $x=1$, we have $a\backsimeq _1 b$. Therefore, $\varphi$ is an embedding. $\square$

We are going to encounter d-subsets or d-subsemigroups which have some of the properties mentioned in Sect. 2. For example, a detachable convex subsemigroup of S is called shortly a d-convex subsemigroup of S. Similarly, there are d-convex, d-isolated, d-completely isolated subsets (subsemigroups) of S. We present some results concerning connections of those subsets (subsemigroups) and their complements.

Lemma 3

If T is a d-convex subset of a semigroup with apartness S, then ${\sim }T$ is either empty or an ideal of S.

Proof

Let $a\in {\sim }T$ and $x\in S$. Because of the detachability of T, we have $ax\rhd T$ or $ax\in T$. If $ax\rhd T$, then $ax\in {\sim }T$. If $ax\in T$, then, as T is convex, we have $a\in T$, which is impossible. Similarly, one can prove that $xa\in {\sim }T$. So, ${\sim }T$ is an ideal of S. $\square$

Lemma 4

• (i) If F is a d-convex subsemigroup of a semigroup with apartness S, then ${\sim } F$ is a completely isolated ideal of S.

• (ii) If I is a d-completely isolated ideal of a semigroup with apartness S, then ${\sim } I$ is a convex subsemigroup of S.

Proof

• (i) By Lemma 3, ${\sim } F$ is an ideal of S. Let $xy\in {\sim } F$, i.e., $xy \rhd F$. Then, by detachability of F, we have and , for any $f\in F$. If $x \in F$ and $y \in F$, then, by the assumption, $xy \in F$ which is in contradiction with $xy \rhd F$. So, we have $x \rhd F$ or $y \rhd F$, i.e., $x\in {\sim } F$ or $y\in {\sim } F$. Therefore ${\sim } F$ is a completely isolated.

• (ii) Let $a,b\in {\sim } I$, i.e., $a\rhd I$ and $b\rhd I$. Since I is a d-subset, we have $ab\rhd I$ or $ab\in I$. If $ab\in I$, then, by the assumption, $a\in I$ or $b\in I$, which is impossible. Thus $ab\rhd I$ and ${\sim } I$ is a subsemigroup of S. Let $xy\in {\sim } I$, i.e., $xy\rhd I$. Since I is a d-subset, we have $x\rhd I$ or $x\in I$. If $x\in I$, then, as I is an ideal, we have $xy\in I$, which is impossible. Thus $x\rhd I$, and $x\in {\sim } I$. Similarly we can prove that $y\in {\sim } I$. So ${\sim } I$ is convex. $\square$

4 Positive coquasiorders

Let $\tau$ be a coquasiorder defined on a semigroup S with apartness. Following classical results as much as possible we can start with the following definition. A coquasiorder $\tau$ on a semigroup S is positive if or any $a,b\in S$,

$$\begin{aligned} (a,ab)\rhd \tau \wedge (a,ba)\rhd \tau , \end{aligned}$$

The following lemmas show how some d-subsets give rise to positive coquasiorders.

Lemma 5

Let K be a d-convex subset of a semigroup S. The relation $\tau$ defined by

$$\begin{aligned} (a,b)\in \tau \Longleftrightarrow a \rhd K \wedge b \in K \end{aligned}$$

is a positive coquasiorder on S.

Proof

By Lemma 1, $\tau$ is a coquasiorder on S. Let (x, y) be any element of $\tau$. Using $(Q_2)$, we have $(x,a)\in \tau \,\vee \,(a,ab)\in \tau \,\vee \,(ab,y)\in \tau$, for any $a,b\in S$. If $(a,ab)\in \tau$, then, by the definition of $\tau$, we have $a\rhd K$ and $ab\in K$, and, as K is a convex subset, we have $a\in K$ and $b\in K$, which is impossible. So, we have

$$\begin{aligned} (x,a)\in \tau \,\vee \,(ab,y)\in \tau . \end{aligned}$$

By the definition of $\tau$ we have

i.e., . Thus, we have proved that $(a,ab)\rhd \tau$ for any $a,b\in S$. The proof of $(a,ba)\rhd \tau$ is similar. Therefore, $\tau$ is a positive coquasiorder on S. $\square$

Lemma 6

Let J be a d-ideal of S such that $J \subset S$. The relation $\tau$ on S defined by

$$\begin{aligned} (a,b)\in \tau \Longleftrightarrow a \in J \wedge b \rhd J \end{aligned}$$

is a positive coquasiorder relation on S.

Proof

By Lemma 1, $\tau$ is a coquasiorder on S. Let (x, y) be any element of $\tau$. Using $(Q_2)$, we have

$$\begin{aligned} (x,a)\in \tau \,\vee \,(a,ab)\in \tau \,\vee \,(ab,y)\in \tau , \end{aligned}$$

for any $a,b\in S$. If $(a,ab)\in \tau$, then, by the definition of $\tau$, we have $a\in J$ and $ab\rhd J$, which, as J is an ideal, further implies $ab\in J$, a contradiction. The rest of the proof is similar to arguments in the proof of Lemma 5. $\square$

Conversely, positive coquasiorders give rise to some special subsets and subsemigroups. Here is the main result of this section.

Theorem 2

The following conditions for a coquasiorder $\tau$ on a semigroup S are equivalent:

• (i) $\tau$ is positive;

• (ii) $\forall _{a,b \in S}\ \ (a \tau \cup b \tau \subseteq (ab)\tau )$;

• (iii) $\forall _{a,b \in S}\ \ (\tau (ab)\subseteq \tau a \cap \tau b)$;

• (iv) $a\tau$ is a d-convex subset of S and $a \rhd a\tau$ for every $a \in S$;

• (v) $\tau a$ is a d-ideal of S and $a \rhd \tau a$ for every $a \in S$.

Proof

(i) $\Rightarrow$ (iii) Since $\tau$ is a coquasiorder, for all $a,b,x\in S$ such that $x \in \tau (ab)$, i.e., $(x,ab)\in \tau$, we have in view of $(Q_2)$

$$\begin{aligned} ((x,a)\in \tau \vee (a,ab)\in \tau )\wedge ((x,b)\in \tau \vee (b,ab)\in \tau ). \end{aligned}$$

But $\tau$ is positive, so that we have $(x,a)\in \tau \wedge (x,b)\in \tau$, i.e., $x\in \tau a \cap \tau b$.

(iii) $\Rightarrow$ (iv) By Lemma 2, $a\tau$ is a d-subset of S such that $a\rhd a\tau$ for any $a\in S$. Since

$$\begin{aligned} xy \in a \tau&\Leftrightarrow (a,xy)\in \tau \\&\Leftrightarrow a\in \tau (xy) \subseteq \tau x \cap \tau y\\&\Rightarrow a \in \tau x \wedge a \in \tau y\\&\Leftrightarrow x \in a \tau \wedge y \in a \tau , \end{aligned}$$

we see that $a\tau$ is a convex subset for any $a\in S$.

(iv) $\Rightarrow$ (i) Let (x, y) be any element of the coquasiorder $\tau$. Then

$$\begin{aligned} (x,a)\in \tau \vee (a,ab)\in \tau \vee (ab,y)\in \tau , \end{aligned}$$

for any $a,b\in S$. Let $(a,ab)\in \tau$, i.e., $ab\in a\tau$. Then, by (iv), $a\in a\tau$ (and $b\in a\tau$), which is impossible. Now, by $(Q_1)$, we have or , i.e., . Thus $(a,ab)\rhd \tau$ for any $a,b\in S$. The fact that $(a,ba)\rhd \tau$ can be proved similarly.

(i) $\Rightarrow$ (v) By Lemma 2, $\tau a$ is a d-subset of S such that $a\rhd \tau a$ for any $a\in S$. Let $a,x\in S$ be such that $x\in \tau a$, i.e., $(x,a)\in \tau$. By $(Q_2)$, we have

$$\begin{aligned} (x,xs)\in \tau \vee (xs,a)\in \tau , \end{aligned}$$

for any $s\in S$. But, as $\tau$ is positive, we have only $(xs,a)\in \tau$, i.e $xs\in \tau a$. In the same way one can prove that $sx\in \tau a$. Thus, $\tau a$ is an ideal of S for any $a\in S$.

(v) $\Rightarrow$ (i) Let (x, y) be any element of $\tau$ and $a,b \in S$. Then

$$\begin{aligned} (x,a)\in \tau \vee (a,ab)\in \tau \vee (ab,y)\in \tau . \end{aligned}$$

If $a\in \tau (ab)$, then, by (v), $ab\in \tau (ab)$, which is, by (v) again, impossible. Now, by $(Q_1)$, we have or , i.e., . Thus $(a,ab)\rhd \tau$ for any $a,b\in S$. The fact that $(a,ba)\rhd \tau$ can be proved similarly.

(v) $\Rightarrow$ (ii) Using $(Q_2)$ and positivity of $\tau$, we have

$$\begin{aligned} x \in a \tau \cup b \tau&\Leftrightarrow x \in a \tau \vee x \in b \tau \\&\Leftrightarrow (a,x)\in \tau \vee (b,x)\in \tau \\&\Rightarrow ((a,ab)\in \tau \vee (ab,x)\in \tau ) \vee ((b,ab)\in \tau \vee (ab,x)\in \tau )\\&\Rightarrow (ab,x)\in \tau \\&\Leftrightarrow x \in (ab)\tau . \end{aligned}$$

(ii) $\Rightarrow$ (v) By Lemma 2, $\tau a$ is a d-subset of S and $a\rhd \tau a$ for any $a\in S$. Now let $x\in \tau a$ and $s\in S$. Then, by $(Q_2)$, we have $(x,xs)\in \tau$ or $(xs,a)\in \tau$. If $(x,xs)\in \tau$, then $xs\in x\tau \subseteq x\tau \cup s\tau \subseteq (xs)\tau$, which is, by Lemma 2, impossible. Thus $(xs,a)\in \tau$. As $(sx,a)\in \tau$ can be proved similarly, we have proved that $\tau a$ is a d-ideal of S. $\square$

A coquasiorder $\tau$ defined on semigroup S has like common multiple property, or, in short, lcm-property if, for all $a,b,c\in S$,

$$\begin{aligned} (ab,c) \in \tau \Rightarrow (a,c)\in \tau \vee (b,c)\in \tau . \end{aligned}$$

Theorem 3

Let $\tau$ be a positive coquasiorder on a semigroup S. The following conditions are equivalent:

• (i) $\tau$ has the lcm-property;

• (ii) $\forall _{a,b\in S}\ ((ab)\tau = a \tau \cup b \tau )$;

• (iii) $\tau a$ is a d-completely isolated ideal of S such that $a\rhd \tau a$ for any $a\in S$.

Proof

(i) $\Rightarrow$ (ii) By Theorem 2, $a\tau \cup b\tau \subseteq (ab)\tau$ for all $a,b\in S$. To prove the converse inclusion, take $x\in (ab)\tau$. Then we have

(ii) $\Rightarrow$ (iii) By Theorem 2, $\tau a$ is a d-ideal of S such that $a\rhd \tau a$, for any $a\in S$. Let $x,y\in S$ be such that $xy \in \tau a$. Then $a \in (xy)\tau = x \tau \cup y \tau$ by (ii). Thus, $a \in x \tau$ or $a \in y \tau$. So, $x \in \tau a$ or $y \in \tau a$ and $\tau a$ is a completely isolated ideal of S for any $a\in S$.

(iii) $\Rightarrow$ (i) Let $a,b,c\in S$ be such that $(ab,c)\in \tau$. Then $ab \in \tau c$ and, since $\tau c$ is completely isolated, $a \in \tau c$ or $b\in \tau c$, which means that $(a,c)\in \tau$ or $(b,c)\in \tau$. $\square$

A coquasiorder $\tau$ defined on a semigroup S has common multiple property, or, in short, cm-property if, for all $a,b,c\in S$,

$$\begin{aligned} (a,c)\rhd \tau \wedge (b,c)\rhd \tau \Rightarrow (ab,c)\rhd \tau . \end{aligned}$$

Corollary 2

A positive coquasiorder with the lcm-property has the cm-property.

Proof

Let $\tau$ be positive coquasiorder with the lcm-property on a semigroup S and let $a,b,c,x,y\in S$ be such that $(a,c),(b,c)\rhd \tau$ and $(x,y)\in \tau$. Then we have

Hence $(ab,c)\rhd \tau$. $\square$

A coquasiorder $\tau$ defined on a semigroup S is linear if, for any $a,b\in S$,

$$\begin{aligned} (a,b)\rhd \tau \vee (b,a)\rhd \tau . \end{aligned}$$

Theorem 4

Let $\tau$ be a positive coquasiorder on a semigroup S. The following conditions are equivalent:

• (i) $\forall _{a,b \in S}\ \ ((ab,a)\rhd \tau \vee (ab,b)\rhd \tau )$;

• (ii) $\forall _{a,b \in S}\ \ (\tau (ab) = \tau a \cap \tau b)$;

• (iii) $a \tau$ is a d-convex subsemigroup of S such that $a\rhd a\tau$ for any $a\in S$;

• (iv) $\tau$ is linear.

Proof

(i) $\Rightarrow$ (ii) Using (i) and $(Q_2)$, we have, for $a,b,x\in S,$

$$\begin{aligned} x \in \tau a \cap \tau b&\Leftrightarrow (x,a)\in \tau \wedge (x,b)\in \tau \\&\Rightarrow ((x,ab)\in \tau \vee (ab,a)\in \tau )\wedge ((x,ab)\in \tau \vee (ab,b)\in \tau )\\&\Rightarrow (x,ab)\in \tau \\&\Leftrightarrow x \in \tau (ab). \end{aligned}$$

The opposite inclusion follows from Theorem 2.

(ii) $\Rightarrow$ (iii) By Theorem 2, $a\tau$ is a d-convex subset such that $a\rhd a\tau$ for any $a\in S$. Let $x,y\in a \tau$. Then $a \in \tau x \cap \tau y= \tau (xy)$ by (ii) whence $xy \in a \tau$. Thus, $a\tau$ is a subsemigroup, i.e., it is a d-convex subsemigroup of S for any $a\in S$.

(iii) $\Rightarrow$ (i) Let $(x,y)\in \tau$. Then, by $(Q_2)$ and $(Q_1)$, we have that, for any $a,b\in S$,

If $(ab,a)\in \tau$, i.e., $a\in (ab)\tau$, then, by (iii), we have or $b\in (ab)\tau$. If $b\in (ab)\tau$, then, by (iii) again, we have $ab\in (ab)\tau$, which is impossible. Thus . Thus,

Therefore, $(ab,a)\rhd \tau$ or $(ab,b)\rhd \tau$, for any $a,b\in S$.

(i) $\Rightarrow$ (iv) Assume that $(ab,a)\rhd \tau$ for any $a,b\in S$. Let $(x,y)\in \tau$. Then, by $(Q_2)$, we have

$$\begin{aligned} (x,ab)\in \tau \vee (ab,a)\in \tau \vee (a,y)\in \tau , \end{aligned}$$

which, by (i), gives $(x,ab)\in \tau \vee (a,y)\in \tau$ for any $a,b\in S$. If $(x,ab)\in \tau$, i.e., if $ab\in x\tau$, then, by Theorem 2, $a\in x\tau$ and $b\in x\tau$. Thus, we have

Therefore, $(b,a)\rhd \tau$. In a similar manner we can deduce $(a,b)\rhd \tau$ from $(ab,b)\rhd \tau$.

(iv) $\Rightarrow$ (i) This follows immediately. $\square$

Example 2

The coquasiorder $\alpha$ defined on a semigroup S considered in Example 1 is, as it can easily be verified, linear. But it is not positive because we have $(e,ea)=(e,d)\in \alpha$. From $(ac,c)=(d,c)\in \alpha$ it follows that neither (a, c) nor (c, c) belong to $\alpha$, so $\alpha$ does not have the lmc-property too. Finally, $(b,c)\rhd \alpha$ and $(c,c)\rhd \alpha$ imply $(bc,c)=(d,c)\in \alpha$, whence $\alpha$ does not have the cm-property.

Example 3

Let S be the 3-element semilattice given by

Let the equality on S be the diagonal $\triangle _S = \{ (a,a), (b,b), (c,c)\}$. We can define an apartness on S to be $(S\times S) \setminus \triangle _S$. Thus, is a semigroup with apartness. A relation $\beta \subseteq S \times S$, defined by

$$\begin{aligned} \beta = \{(a,b), (c,a),(c,b)\}, \end{aligned}$$

is a coquasiorder on S. Moreover, it can be easily check that $\beta$ is a positive and linear coquasiorder. But, on the other side, from $(ab,a)=(c,a)\in \beta$ neither (a, a) nor (b, a) is in $\beta$, so $\beta$ does not have the lcm-property. From $(a,a)\rhd \beta$ and $(b,a)\rhd \beta$ we have $(ab,a)=(c,a)\in \beta$, and $\beta$ does not have the cm-property as well.

Comparing the obtained results with parallel ones in the classical background, one can see that most of the similarities have been obtained in the beginning, with characterizations of positive coquasiorderes (Theorem 2). Differences appear when a coquasiorder has cm-property. Then, there are two definitions: the lmc-property, which is similar to the classical case (Theorem 3) and the cm-property which is more in the constructive “fashion” and follows the classical counterpart closely. Nevertheless, the last definition is stronger (Corollary 2). Coquasiorders which are linear need not have the lmc- nor the cm-property (see Theorem 4), which their classical counterparts have.

5 Concluding remarks

Green’s relations are fundamental tools in the classical structure theory of semigroups. Their definitions involve existential quantification. Recall, for example, that two elements a and b of a semigroup S are $\mathcal R$-related iff there exist $u, v\in S^1$ such that $au= b$ and $bv= a$. On the other hand, by [3], “contructive existence is much more restrictive then the ideal existence of classical mathematics. The only way to show that an object exists is to give a finite routine for finding it, whereas in classical mathematics other methods can be used.” This means that we are in trouble at the very start of our investigation of the structure of semigroups with apartness. Our further work will be focused on finding constructive counterparts of Green’s relations.

Another special trouble for constructive algebraist can be the axiom

$$\begin{aligned} (P\vee \forall _x\,R(x)) \, \rightarrow \, \forall _x\, (P\vee R(x)). \end{aligned}$$

We are forced to use formulas with disjunctions, which, of course, means that our semantical models have to be Kripke models with constant domains.

Why study semigroup with apartness? One can give an answer similar to the one given in [16], and completely compatible with the one taken from [6]: “...doing constructive mathematics” (here semigroups) “is interesting (it can be fun!) and challenging...”.