PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 82(96) (2007), 119–128 DOI 102298/PIM0796119C

A THEOREM ON ANTI-ORDERED FACTOR-SEMIGROUPS

Siniša Crvenković and Daniel A. Romano

Abstract. Let K be an anti-ideal of a semigroup (S, =, ≠, ·, θ) with apartness. A construction of the anti-congruence Q(K) and the quasi-antiorder θ, generated by K, are presented. Besides, a construction of the anti-order relation Θ on syntactic semigroup S/Q(K), generated by θ, is given in Bishop’s constructive mathematics.

1. Introduction

1.1. Setting. Setting of our work is Bishop’s constructive mathematics [1,2,4], mathematics developed with Constructive Logic (or Intuitionistic Logic [11]—logic without the Law of Excluded Middle P ∨ ¬P. We have to note that ‘the crazy axiom’ ¬P → (P → Q) is included in Constructive Logic. Precisely, in Constructive Logic the ‘Double Negation Law’ P ↔ ¬¬P does not hold but the following implication P → ¬¬P holds even in Minimal Logic. In Constructive Logic ‘Weak Law of Excluded Middle’ ¬P ∨ ¬¬P does not hold, too. It is interesting, that in Constructive Logic the following deduction principle A ∨ B, A ⊢ B holds, but this is impossible to prove without ‘the crazy axiom’. For elegant examples of nonconstructive proofs see Constructive Mathematics by Douglas Bridges in Stanford Encyclopedia of Philosophy. The constructive (intuitionist) logic is one of the great discoveries in mathematical logic—surprisingly, a complete system of constructive reasoning can be obtained simply by dropping the Law of Excluded Middle from the list of valid logical principles. Bishop’s constructive mathematics is consistent with the classical mathematics.

2000 Mathematics Subject Classification: Primary 03F65; Secondary 06F05, 20M99.

Key words and phrases: Constructive mathematics, semigroup with apartness, anti-order, quasi-antiorder, anti-ordered semigroup.

Supported by Ministry of Science of the Republic of Serbia, Grant 144011 (S. Crvenković)

and by Ministry of Science and Technology of the Republic of Srpska, Bosnia and Herzegovina (D. Romano).

1.2. Set with apartness. Let (X, =, ≠) be a set in the sense of [1], [2], [4] and [11], where “≠” is a binary relation on X which satisfies the following properties:

¬(x ≠ x), x ≠ y → y ≠ x, x ≠ z → x ≠ y ∨ y ≠ z

called apartness (Heyting). The relation ≠ must be extensional by the equality, in the following sense

x ≠ y ∧ y = z → x ≠ z.

Let Y be a subset of X and let x ∈ X. By x ▷◁ Y we denote (∀y ∈ Y)(y ≠ x) and by Y^{C} we denote subset {x ∈ X : x ▷◁ Y } – the strong complement of Y in X [4]. The subset Y of X is strongly extensional [11] in X if and only if y ∈ Y → y ≠ x∨x ∈ Y.

Example 0. (1) Let ℘(X) be the power-set of set X. If, for subsets A, B of X, we define A ≠ B if and only if (∃a ∈ A)¬(a ∈ B) or (∃b ∈ B)¬(b ∈ A), then the relation ≠ is a diversity relation on ℘(X) but it is not an apartness.

(2) [6] The relation ≠ defined on the set Q^{N} by

f ≠ g ↔ (∃k ∈ N)(∃n ∈ N)(m ⩾ n → |f(m) − g(m)| > k^{−1})

is an apartness on Q^{N}. □

Let X be a set with apartness and let α, β be relations on X. The filed product [8–10] of α and β is the relation β ∗ α defined by

β ∗ α = {(x, z) ∈ X × X : (∀y ∈ X)((x, y) ∈ α ∨ (y, z) ∈ β)}.

For n ⩾ 2, let ^{n}α = α ∗ α ∗ ⋯ ∗ α (n factors). Put ^{1}α = α. By c(α) we denote the intersection ⋂_{n∈N}(^{n}α). The relation c(α) is a cotransitive relation on X, by Theorem 0.4 of [9]. It is called cotransitive internal fulfillment of the relation α.

1.3. Semigroup with apartness. Semigroup with apartness was for the first time defined and studied by Heyting. After that, several authors have worked on this important topic as for example Mines et all [4], Troelstra and van Dalen [11], and the second author [8–10]. Let S = (S, =, ≠, ·) be a semigroup with apartness, where the semigroup operation is strongly extensional in the following sense

(∀a, b, x, y ∈ S)((ay ≠ by → a ≠ b) ∧ (xa ≠ xb → a ≠ b)).

A subset T of S is a consistent subset of S if and only if (∀x, y ∈ S)(xy ∈ T → x ∈ T ∧ y ∈ T). A relation q on X is a coequality relation on X [7–10] if and only if

q ⊆ ≠, q^{−1} = q and q ⊆ q ∗ q.

Let q be a coequality relation on semigroup S. We say that q is anti-congruence on S if and only if

(∀a, b, x, y ∈ S)((ax, by) ∈ q → (a, b) ∈ q ∨ (x, y) ∈ q).

Note that (xay, xby) ∈ q implies (a, b) ∈ q for any x, y, a, b ∈ S. If q is anticongruence on semigroup S, then the strong complement q^{C} of q is a congruence on the semigroup S compatible with q in the following sense:

(∀x, y, z ∈ X)((x, y) ∈ q ∧ (y, z) ∈ q^{C} → (x, z) ∈ q).

We can construct the factor-semigroup S/q = {aq : a ∈ S}, where equality, diversity and the internal operation are defined as above:

aq =_{1} bq ↔ (a, b) ▷◁ q, aq ≠_{1} bq ↔ (a, b) ∈ q, aq · bq =_{1} (ab)q.

The mapping π(q) : S → S/q is strongly extensional and surjective homomorphism called natural epimorphism. There is an interesting property about coequality relation on semigroup S with apartness [8, Theorem 5]: Let q be a coequality relation on a semigroup S with apartness. Then the relation q^{+} = {(x, y) ∈ S × S : (∃a, b ∈ S^{1})((axb, ayb) ∈ q)} is an anti-congruence on S and it is a minimal extension of q.

1.4. Motivation and goals of this article. We present some facts concerning factor-semigroup by anti-congruence generated by an anti-ideal in Bishop’s constructive sense. These notions are important in Formal language theory, which is a part of Theoretical Computer Science. For a more complete treatment of syntactic semigroups, in Formal Language Theory, the reader should consult Pin’s papers [5, 6]. Any notion in Bishop’s constructive mathematics has positively defined symmetrical pair, since Law of Excluded Middle does not hold in Constructive logic. Our intention is development of these symmetrical notions and their comparability with the ‘first notions’ in semigroups ordered by an anti-order relation. As the first, semigroup is equipped with diversity relation compatible with the equality, and, the second, the semigroup operation is total, extensional and strongly extensional function from S × S into S. If T is an anti-ordered semigroup [7], K an order anti-ideal of T, a construction of anti-congruence Q(K) generated by K and the factorsemigroup T/Q(K) = {aQ(K) : a ∈ T } are presented. Particulary, it is shown haw to construct anti-order on T/Q(K) by a quasi-antiorder [10], generated by K, so that Q(K) = θ∪θ^{−1}. In the main theorem of this article we give the following result: Let α : R → S be a reverse isotone surjective homomorphism of anti-ordered semigroups and let W be an anti-ideal in S. Then there exist anti-congruences Q(W) and Q(α^{−1}(W)) of S and R, respectively, such that α^{−1}(Q(W)) = Q(α^{−1}(W)), and reverse isotone bijection ψ : S/Q(W) → R/Q(α^{−1}(W)), which is embedding such that π(α^{−1}(W)) = ψ ∘ π(W) ∘ α, where π(α^{−1}(W)) : S → S/Q(α^{−1}(W)) and π(W) : R → R/Q(W) are natural homomorphisms. An application of this result in Formal Language Theory is given.

1.5. References. For undefined notions and notations of Semigroup Theory and of Automata Theory see [3] and papers [5] and [6]. For constructive items we refer to well-known books [1], [2], [4] and [11], and to the second author’s papers [7–10].

2. Preliminaries

We start this section with the following definitions. Let (S, =, ≠, ·) be a semigroup with apartness. For S we say (following Romano’s definition in [7]) that it is an anti-ordered semigroup if S is equipped with anti-order relation Θ such that

Θ ⊆ ≠ (consistency), ≠ ⊆ Θ ∪ Θ^{−1} (linearity), Θ ⊆ Θ ∗ Θ (cotransitivity) and it is compatible with the semigroup operation:

(∀x, y, u ∈ S)(((ux, uy) ∈ Θ → (x, y) ∈ Θ) ∧ ((xu, yu) ∈ Θ → (x, y) ∈ Θ)).

As in [10], we say that the relation θ is a quasi-antiorder on semigroup S if it is consistent, cotransitive and compatible with the semigroup operation. It is easy to verify that if θ is a quasi-antiorder on semigroup S, then the relation q = θ ∪ θ^{−1} is anti-congruence on S.

Note 1. (i) The implication x ⩽ y∧z Θ y → z Θ x is equivalent to the condition ¬(x ⩽ y ∧ x Θ y). Indeed: Suppose that implication x ⩽ y ∧ z Θ y → z Θ x holds and suppose that x ⩽ y and x Θ y. Then, by compatibility of relations, we have x Θ x. This is impossible, because the relation Θ is consistent. So, it should be ¬(x ⩽ y ∧ x Θ y). On the opposite, let the condition ¬(x ⩽ y ∧ x Θ y) holds. If x ⩽ y ∧z Θ y, then, by cotransitivity of Θ, we have z Θ x∨x Θ y. Thus, we conclude z Θ x, because x ⩽ y and x Θ y is impossible. So, the implication x ⩽ y ∧ z Θ y → z Θ x is consequence of the condition ¬(x ⩽ y ∧ x Θ y).

(ii) Also, if relations ⩽ and Θ are compatible, then the implication x Θ y ∧ z ⩽ y → x Θ z holds too. In fact, from x Θ y follows x Θ z or z Θ y. Since z ⩽ y and z Θ y is impossible, we deduce x Θ z.

(iii) Note that the apartness on semigroup S is an antiorder relation on S. □

Note 2. Anti-order relation Θ is a strongly extensional subset of S×S. In fact: Let (a, b) be an arbitrary element of Θ and (x, y) an arbitrary element of S × S. Then, from (a, x) ∈ Θ ∨ (x, y) ∈ Θ ∨ (y, b) ∈ Θ, it follows a ≠ x ∨ (x, y) ∈ Θ ∨ y ≠ b. So, the implication

(a, b) ∈ Θ ∧ (x, y) ∈ S × S → (x, y) ≠ (a, b) ∨ (x, y) ∈ Θ

holds for every a, b, x, y ∈ S. □

Example 1. Let S={a, b, c, d, e} with multiplication defined by the table

· a b c d e
a b b d d d
b b b d d d
c d d c d c
d d d d d d
e d d c d c

The relation α, defined by

α = {(a, c), (a, d), (a, e), (b, a), (b, c), (b, d), (b, e), (c, a),
(c, b), (c, d), (c, e), (d, a), (d, e), (e, a), (e, b), (e, d)},

is an anti-order relation on the semigroup S and the relation

β = {(a, e), (b, e), (c, a), (c, b), (c, d), (c, e), (d, e), (e, a), (e, b), (e, d)}

is a quasi-antiorder relation on the semigroup S. □

Example 2. Let A be a strongly extensional consistent subset of a semigroup (S, =, ≠, ·). Then the relation Θ_{A} ⊆ S ×S, defined by (a, b) ∈ Θ_{A} ↔ a ≠ b∧a ∈ A, is an quasi-antiorder relation on S but it is not an antiorder relation on S.

Indeed: It is clear that Θ_{A} ⊆ ≠. Let a, c be arbitrary elements of S such that a Θ_{A} c and let b be an arbitrary element of S, i.e., let a ≠ c and a ∈ A. From a ≠ c it follows a ≠ b or b ≠ c. If a ≠ b, then a Θ_{A} b. Suppose that b ≠ c and a ∈ A. Then a ≠ b or b ∈ A. If a ∈ A and a ≠ b, we have (a, b) ∈ Θ_{A} again. If b ∈ A and b ≠ c, then b Θ_{A} c. Let xa Θ_{A} xb (x ∈ S), i.e., let xa ≠ xb and xa ∈ A. Thus a ≠ b and a ∈ A. So, a Θ_{A} b. Similarly, we have ax Θ_{A} bx → a Θ_{A} b.

Suppose that ¬(a ∈ A) and ¬(b ∈ A) and a ≠ b. The implication a ≠ b → a Θ_{A} b ∨ bΘ_{A}a does not follow from our assumption. So, the relation Θ_{A} is not an anti-order relation on S. □

Note 3. (1) If {s_{k}}_{k∈J} is a family of quasi-antiorders on a set (X, =, ≠), then ⋃_{k∈J} s_{k} is a quasi-antiorder on X. Indeed: Let {s_{k}}_{k∈J} be a family of quasiantiorders on a set (X, =, ≠) and let (x, z) be an arbitrary elements of X such that (x, z) ∈ ⋃_{k∈J} s_{k}. Then there exists k in J such that (x, z) ∈ s_{k}. Hence, for every y ∈ X we have (x, y) ∈ s_{k} ∨ (y, z) ∈ s_{k}. So, (x, y) ∈ ⋃_{k∈J} s_{k} ∨ (y, z) ⋃_{k∈J} s_{k}. On the other hand, for every k in J, s_{k} ⊆≠. From the previous we obtain ⋃_{k∈J} s_{k}.

(2) Let R(⊆ ≠) be a relation on a set (X, =, ≠). Then for an inhabited family of quasi-antiorders under R there exists the biggest quasi-antiorder relation under R. That relation is exactly the relation c(R) = ⋂_{n∈N}(^{n}R). Note that the proof of this fact is not trivial.

(3) Let (X, =, ≠, α) be an anti-ordered set. Then the family A = {τ : τ is a quasi-antiorder on X} is a complete lattice.

(4) If {α_{k}}_{k∈J} is a family of anti-orders on a set (X, =, ≠), then ⋃_{k∈J} α_{k} is an anti-order of X. In fact, let {α_{k}}_{k∈J} be a family of anti-orders on a set (X, =, ≠). Let x and y be arbitrary elements of X such that x ≠ y. Then

(∀k ∈ J)((x, y) ∈ α_{k} ⊆ ⋃_{k∈J} α_{k} ∨ (y, x) ∈ α_{k} ⊆ ⋃_{k∈J} α_{k}).

Thereffore, the relation ⋃_{k∈J} α_{k} is linear. □

Our first proposition is the following lemma which gives another example of quasi-antiorder relation on semigroup S generated by a strongly extensional subset of S. So, a connection between the family of all strongly extensional subsets of S and the family of all quasy-anatiorders on S is natural.

Lemma 2.0. Let A be a strongly extensional subset of a semigroup (S, =, ≠, ·). Then, the relation Θ_{A} ⊆ S × S, defined by

(a, b) ∈ Θ_{A} ↔ (∃x, y ∈ S^{1})(xby ∈ A ∧ xay ▷◁ A),

is a quasi-antiorder relation on S.

Proof. It is clear that Θ_{A} ⊆ ≠ and that (uav, ubv) ∈ Θ_{A} implies (a, b) ∈ Θ_{A}. Let a, c be elements of S such that a Θ_{A} c and let b be an arbitrary element of S i.e., such that (∃x, y ∈ S^{1})(xcy ∈ A ∧ xay ▷◁ A). Let t be an arbitrary element of S. Then t ≠ xby or xby ∈ A by strongly extensionality of A. If xby ∈ A (and xay ▷◁ A), then a Θ_{A} b. If ¬(xby ∈ A), then xby ▷◁ A. So, b Θ_{A} c. □

In what follows, we have the notion of order substructures. We follow the classical Pin’s definition [5, 6] of order ideal of ordered semigroup. Here we are dealing with anti-ordered semigroup. An anti-ideal of S is a subset K of S such that

(∀x, y)(y ∈ K → y Θ x ∨ x ∈ K).

Example 3. The subset K(a) = {z ∈ S : z Θ a} is an anti-ideal called a principal anti-ideal generated by element a. In fact, let z be an arbitrary element of K(a) and let y be an arbitrary element of S. Then, from z Θ a follows z Θ y or y Θ a. So, the implication z ∈ K(a) → y ∈ K(a) ∨ z Θ y holds. Therefore, the set K(a) is an anti-ideal of S.

If K is an anti-ideal and a an arbitrary element of S, then the sets [a : K] = {x ∈ S : ax ∈ K} and [K : a] = {y ∈ S : ya ∈ K} are anti-deals of S. Indeed: Let y ∈ [a : K], i.e., let ay ∈ K. Then ay Θ ax or ax ∈ K for an arbitrary element x of S. Thus y Θ x or x ∈ [a : K]. So, the set [a : K] is an order anti-ideal of S. For [K : a] the proof is analogous. □

Now, suppose that we have a mapping φ : S → T between two anti-ordered semigroups. First, let us recall some standard notions and notations about mappings: A mapping φ must be strongly extensional, i.e., the following implication (∀x, x′ ∈ S)(φ(x) ≠_{T} φ(x′) → x ≠_{S} x′) holds; φ is an embedding if and only if (∀x, x′ ∈ S)(x ≠_{S} x′ → φ(x) ≠_{T} φ(x′)); φ is a homomorphism of semigroups if (∀x, x′ ∈ S)(φ(x · x′) = φ(x) · φ(x′)) holds. Now, we need a new kind of homomorphism between anti-ordered semigroups. A homomorphism φ : (S, Θ) → (T, Ω) of anti-ordered semigroups is an isotone homomorphism if and only if for every x, y ∈ S, x Θ y implies φ(x)Ωφ(y). If φ(y)Ωφ(x) implies x Θ y we say that homomorphism φ is reverse isotone homomorphism of anti-ordered semigroups.

Lemma 2.1. Let φ : (S, =, ≠, ·, Θ) → (T, =, ≠, ·, Ω) be a reverse isotone homomorphism of anti-ordered semigroups. If W is an anti-ideal of T, then φ^{−1}(W) is an anti-ideal of S.

Proof. Let y ∈ φ^{−1}(W) and let x be an arbitrary element of S. Then φ(y) ∈ W. Thus, φ(y) Ω φ(x) or φ(x) ∈ W. If φ(y) Ω φ(x), then y Θ x because φ is a reverse-isotone homomorphism. If φ(x) ∈ W, then x ∈ φ^{−1}(W). So, φ^{−1}(W) is an anti-ideal of S. □

3. Main results

Let (T, =, ≠, ·) be an anti-ordered semigroup and let K be an anti-ideal of T. We define on T a relation Q(K) by setting

u Q(K) v ↔ (∃x, y ∈ T^{1})((xuy ∈ K ∧ xvy ▷◁ K) ∨ (xvy ∈ K ∧ xuy ▷◁ K)).

Theorem 3.1. The relation Q(K) is an anti-congruence on T.

Proof. If (a, b) ∈ Q(K), then
(∃x, y ∈ S^{1})((xay ∈ K ∧ xby ▷◁ K) ∨ (xby ∈ K ∧ xay ▷◁ K)).

If xay ∈ K ∧ xby ▷◁ K, we have xay ≠ xby and a ≠ b. So, the relation Q(K) is consistent. It is obvious that the relation Q(K) is symmetric. Let a, c be elements of S such that (a, c) ∈ Q(K) and let b be an element of S. Suppose that (∃x, y ∈ S^{1})((xay ∈ K ∧ xcy ▷◁ K). Let u be an element of K. Then, by strongly extensionality of K, we obtain: u Θ xby ∨ xby ∈ K. If u ≠ xby and xay ∈ K, then (a, b) ∈ Q(K). If xby ∈ K and xcy ▷◁ K, then (b, c) ∈ Q(K). Let a, b, c be arbitrary elements of S such that (ac, bc) ∈ Q(K). Suppose that (∃x, y ∈ S^{1}) ((xacy ∈ K ∧ xbcy ▷◁ K). Then (∃x, cy ∈ S^{1})(xa(cy) ∈ K ∧ xb(cy) ▷◁ K). So, (a, b) ∈ Q(K). Similarly, we have (ca, cb) ∈ Q(K) → (a, b) ∈ Q(K). Therefore, the relation Q(K) is an anti-congruence on S i.e., it is coequality relation on S compatible with the operation “·”. □

Note that we are able to construct the quasi-antiorder θ_{K}(⊆ Θ_{T}) on T (see Lemma 2.0) in the following way: a θ_{K} b ↔ (∃u, v ∈ T^{1})(ubv ∈ K ∧ uav ▷◁ K) such that Q(K) = θ_{K} ∪ (θ_{K})^{−1}. The quasi-antiorder θ_{K} on T induces an anti-order Θ_{K} on T/Q(K) by (aQ(K), bQ(K)) ∈ Θ_{K} ↔ a θ_{K} b.

Lemma 3.1. The map π(K) : T → T/Q(K) is a reverse isotone homomorphism of anti-ordered semigroup (T, =, ≠, ·, Θ) onto (T/Q(K), =_{1}, ≠_{1}, ·_{1}, Θ_{K}).

Proof. Since Q(K) is an anti-congruence, the mapping π(K) : T → T/Q(K) is a homomorphism of semigroups.

Suppose that aQ(K) Θ_{K} bQ(K), i.e., suppose that (a, b) ∈ θ_{K}. Then there exist elements u, v ∈ T^{1} such that ubv ∈ K and uav ▷◁ K. Thus, uav Θ ubv or uav ∈ K. Since uav ∈ K, we have a Θ b because the anti-order is compatible with the semigroup operation. So, the mapping π is anti-order reverse isotone homomorphism of semigroups. □

The following theorem is the main result of this article:

Theorem 3.2. Let α : R → S be a reverse isotone surjective homomorphism of anti-ordered semigroups and let W be an anti-ideal in S. Then, there exists an anti-order reverse isotone isomorphism

ψ : (S/Q(W), =_{1}, ≠_{1}, ·_{1}, Θ_{W}) → (R/Q(K), =_{2}, ≠_{2}, ·_{2}, Θ_{K})

such that π(K) = ψ ∘ π(W) ∘ α, where K = α^{−1}(W).

Proof. (1) K = α^{−1}(W) is an anti-ideal of R by lemma 2.1.

(2) Define ψ : bQ(W) ↦ aQ(K) where α(a) = b, a ∈ R, b ∈ S. This correspondence is a mapping since:

(i) Let α(a) = b and α(a′) = b′ such that bQ(W) =_{1} b′Q(W) i.e., such that (b, b′) ▷◁ Q(W), and let (u, v) be an arbitrary element of Q(K). Then (u, a) ∈ Q(K) or (a, a′) ∈ Q(K) or (a′, v) ∈ Q(K), and hence u ≠ a or a′ ≠ v because (a, a′) ∈ Q(K) is impossible. In fact, if (a, a′) ∈ Q(K), then there exist x and y of R1 such that xa′y ∈ K ∧ xay ▷◁ K or xay ∈ K ∧ xa′y ▷◁ K. Since xay ▷◁ K = α^{−1}(W) implies α(x)bα(y) ▷◁ W, we have that the case (a, a′) ∈ Q(K) is impossible. Indeed, let xay ▷◁ α^{−1}(W) and let w be an arbitrary element of W. Thus, w ≠ α(x)bα(y) or xay ∈ α^{−1}(W). So, the implication xay ▷◁ α^{−1}(W) → α(x)bα(y) ▷◁ W has to hold. Therefore, at least we have (a, a′) ▷◁ Q(K), i.e., we have that aQ(K) =_{2} a′Q(K). Hence, ψ is a mapping.

(ii) Let aQ(K), a′Q(K) be elements of R/Q(K) such that aQ(K) Θ_{K}a′Q(K). By definition it means that a θ_{K} a′. Then (∃x, y ∈ R^{1})(xay ▷◁ K ∧ xa′y ∈ K). Suppose that α(a) = b, α(a′) = b′, α(x) = u and α(y) = v (and suppose that (∃x, y ∈ R^{1})((xa′y ∈ α^{−1}(W) ∧ xay ▷◁ α^{−1}(W))). Then, there exists element u = α(x) and v = α(y) ∈ imφ = S such that α(x)α(a′)α(y) ∈ W. Let t be an arbitrary element of W. Then, t ≠ α(xay) or α(x)α(a)α(y) ∈ W. In the second case we should have xay ∈ α^{−1}(W) which is impossible. So, α(x)α(a)α(y) ▷◁ W. Therefore, there exist elements u = α(x) and v = α(y) such that ub′v ∈ K and ubv ▷◁ K. Thus, b θ_{W} b′, and bQ(W) Θ_{W} b′Q(W).

Hence, if aQ(K) ≠_{2} a′Q(K), then bQ(W) ≠_{1} b′Q(W). Finally, the mapping ψ is strongly extensional.

(3) Let bQ(W) and b′Q(W) be arbitrary elements of S/Q(W) such that bQ(W) ≠_{1} b′Q(W). Then (b, b′) ∈ Q(W) and (α(a), α(a′)) ∈ Q(W), where b = α(a) and b′ = α(a′) for some a, a′ ∈ R. Thus, (a, a′) ∈ α^{−1}(Q(W)). Since α^{−1}(Q(W)) = Q(α^{−1}(W)), we have (a, a′) ∈ Q(α^{−1}(W)). So, aQ(α^{−1}(W)) =_{2} a′Q(α^{−1}(W)). Therefore, the mapping ψ is an embedding.

(4) Let aQ(α^{−1}(W)), a′Q(α^{−1}(W)) be elements of R/Q(α^{−1}(W)) such that aQ(α^{−1}(W)) =_{2} a′Q(α^{−1}(W)), i.e., let (a, a′) ▷◁ Q(α^{−1}(W)) = α^{−1}(Q(W)). We have to prove that (α(a), α(a′)) ▷◁ Q(W). Let (u, v) be an arbitrary element of Q(W). Then, (u, α(a)) ∈ Q(W) or (α(a), α(a′)) ∈ Q(W) or (α(a′), v) ∈ Q(W). If (α(a), α(a′)) ∈ Q(W), then we have (a, a′) ∈ α^{−1}(Q(W)) = Q(α^{−1}(W)). So, this case is impossible, because (a, a′) ▷◁ Q(α^{−1}(W)). Therefore, it has to be u ≠ α(a) or α(a′) ≠ v. This means that (α(a), α(a′)) ≠ (u, v) ∈ Q(W). Hence, we have that (a)Q(W) =_{1} (a′)Q(W). So, the mapping ψ is an injective mapping.

(5) Let bQ(W) and b′Q(W) be arbitrary elements of S/Q(W). Then there exist elements a and a′ of R such that ψ : bQ(W) ↦ aQ(K) and ψ : b′Q(W) ↦ a′Q(K). Since α(aa′) = α(a)α(a′) = bb′ we conclude that ψ is a homomorphism of semigroups. From part 2(ii) of this proof, we infer that φ is reverse isotone homomorphism of anti-ordered semigroups.

(6) The equality (K) = ψ ∘ π(W) ∘ α immediately follows from definitions of homomorphisms π(K) : R → R/Q(K), ψ, π(W) : S → S/Q(W) and α. □

Let (S, =, ≠, ·, Θ) and (T, =, ≠, ·, Ω) be anti-ordered semigroups, and let α : S → T be an anti-order reverse isotone surjective homomorphism of semigroups. Following the classical definition, for example as in [5], we say that substructure P of S is recognized by homomorphism α if there exists a substructure Q of T such that P = α^{−1}(Q). Note that this condition implies α(P) = (α ∘ α^{−1})(Q) = Q because the homomorphism α is a surjection. By extension, an anti-ideal W of S is said to be recognized by (T, =, ≠, ·, Ω) if there exists a surjective strongly extensional reverse isotone homomorphism α of anti-ordered semigroups from (S, =, ≠, ·, Θ) onto (T, =, ≠, ·, Ω) that recognizes W.

Corollary 3.1. Let α : R → S be a surjective reverse isotone homomorphism of anti-ordered semigroups and let K be an anti-ideal of R. The homomorphism α recognizes K if and only if there exists reverse isotone homomorphism γ : S → R/Q(K) such that π(K) = γ ∘ α.

Proof. (1) If α recognizes K of semigroup R, then there exist an anti-ideal W of S such that K = α^{−1}(W). By Theorem 3.3, there exists a strongly extensional reverse isotone homomorphism γ : S → R/Q(K) such that π(K) = γ ∘ α.

(2) Since the homomorphism π : R → R/Q(K) recognizes anti-ideal K, then there exists anti-ideal V of R/Q(K) such that K = π^{−1}(V). Suppose that there exists a strongly extensional reverse isotone homomorphism γ : S → R/Q(K) such that π = γ ∘α, then W = γ^{−1}(V) is an anti-ideal of anti-order semigroup S. Hence, we have

α^{−1}(W) = α^{−1}(γ^{−1}(V)) = (γ ∘ α)^{−1}(V) = π^{−1}(V) = K.

Hence, the homomorphism α recognizes the set K. □

Let (R, =, ≠, ·, Θ) be an anti-ordered semigroup and let W_{1} and W_{2} be antiideals of R such that W_{1} ⊆ W_{2}. Then, for quasi-antiorders Θ_{1} and Θ_{2}, and anticongruences Q(W_{1}) and Q(W_{2}) the following hold: (i) Q(W_{1}) ⊆ Q(W_{2}); (ii) θ_{1} ⊆ θ_{2} and θ_{1} ∪ (θ_{1})^{−1} = Q(W_{1}) and θ_{2} ∪ (θ_{2})^{−1} = Q(W_{2}). Besides, anti-order Θ_{2} on R/Q(W_{2}) is defined by (aQ(W_{2}), bQ(W_{2})) ∈ Θ_{2} ↔ (a, b) ∈ θ_{2}. So, the semigroup R/Q(W_{1}) is anti-ordered semigroup and W_{1}/Q(W_{2}) is anti-ideal of the semigroup R/Q(W_{2}). The next assertion is another application of the main theorem:

Corollary 3.2. Let π : R → R/Q(W_{2}) be the natural reverse isotone epimorphism of anti-ordered semigroups and let W_{1} be an anti-ideal in R such that W_{1} ⊆ W_{2}. Then, W_{1}/Q(W_{2}) is an anti-ideal of the semigroup R/Q(W_{2}) and there exists a reverse isotone isomorphism

(R/Q(W_{2}))/Q(W_{1}/Q(W_{2})) ≅ R/π^{−1}(Q(W_{1}/Q(W_{2}))).

References

[1] E. Bishop, Foundations of Constructive Analysis, McGraw-Hill, New York 1967

[2] D. S. Bridges and F. Richman, Varieties of Constructive Mathematics, London Mathematical Society Lecture Notes 97, Cambridge University Press, Cambridge, 1987

[3] J. E. Hopcroft, R. Motwani, R. and J. D. Ullman, Introduction to Automata Theory, Language and Computation; Addison-Wesley, 2001

[4] R. Mines, F. Richman and W. Ruitenburg, A Course of Constructive Algebra, Springer-Verlag, New York, 1988

[5] J. E. Pin A variety theorem without complementation, Russian Mathematics 39 (1995), 80–90 [6] J. E. Pin, Syntactic Semigroups; in: I. G. Rozenberg and A. Salomaa (eds.), Handbook of

Formal Language Theory, Springer-Verlag, New York 1997, 679–746

[7] D. A. Romano, A semivaluation on Heyting fields, Kragujevac J. Math. 20 (1998), 24–40 [8] D. A. Romano, A left compatible coequality relation on semigroup with apartness, Novi Sad

J. Math 29(2) (1999), 221–234 [9] D. A. Romano, Some relations and subsets generated by principal consistent subsets of semi-

group with apartness, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat 13 (2002), 7–25

[10] D. A. Romano, A note on a family of quasi-antiorder on semigroup, Kragujevac J. Math. 27 (2005), 11–18

[11] A. S. Troelstra and D. van Dalen, Constructivism in Mathematics, An Introduction, Volume II, North-Holland, Amsterdam, 1988

Prirodno-matematički fakultet 21000 Novi Sad Serbia

sima@eunet.yu

Prirodno-matematički fakultet 78000 Banja Luka Srpska, Bosnia and Herzegovina

bato49@hotmail.com