Math. Log. Quart. 59, No. 6, 407–414 (2013) / DOI 10.1002/malq.201200107

Semigroups with apartness

Sinisˇa Crvenkovic´1, Melanija Mitrovic´2∗, and Daniel Abraham Romano3 1 Department of Mathematics and Informatics, University of Novi Sad, Trg Dositeja Obradovica 4, 21000 Novi

Sad, Serbia 2 Department of Mathematics, University of Nisˇ, Aleksandra Medvedeva 14, 18000 Nisˇ, Serbia 3 Faculty of Education, East Sarajevo University, Svetog Save 24, 76300 Bijeljina, Bosnia and Herzegovina

Received 10 December 2012, revised 11 April 2013, accepted 12 April 2013

Published online 14 November 2013

Key words Set with apartness, semigroup with apartness, coequivalence, cocongruence.

MSC (2010) 03F65, 20M99

Proving a constructive version of the Spectral Mapping Theorem, Bridges and Havea used a constructive semigroup with inequality in [8]. This motivated us to achieve a little progress in that direction. The starting point is the structure (S,=, =, · ) called a semigroup with apartness. Our primary objective is to prove isomorphism theorems for such constructive semigroups. In doing so our main ideas and notions come from [10].

C© 2013 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim 1 Introduction

In this paper, we present a small portion of the theory of semigroups with apartness from a constructive-algebraic point of view. The focus is on Bishop’s approach to constructive mathematics (BISH). Since the appearance of

Bishop’s monograph [2] in 1967, there have been significant developments in Bishop-style analysis and topology; cf., e.g., [4, 8, 9, 10, 23]. But, as is remarked in [7], “contrary to Bishop’s expectations, modern algebra also proved amenable to natural, thoroughgoing, constructive treatment”—cf. the well-known constructive algebra book [20].

In [24], Troelstra and van Dalen say that “[t]he study of algebraic structures in an intuitionistic setting was undertaken by Heyting, [15]. Heyting considered structures equipped with an apartness relation in full generality”.

Since then several authors have worked in this area; cf., e.g., [20, 23, 24]. There is no doubt about the deep connections of constructive analysis with computer science: cf., e.g., [7]. In [19] it is shown that constructive algebraic structures with apartness also can be applied in computer science (especially in computer programming).

In universal algebra within CLASS (i.e., classical mathematics), the formulation of homomorphic images (together with subalgebras and direct products) is one of the principal tools used to manipulate algebras. In the study of homomorphic images of an algebra a lot of help comes from the notion of a quotient algebra, which captures all homomorphic images, at least up to isomorphism. On the other hand, homomorphism is the concept which goes hand in hand with congruences. Thus concepts of congruence, quotient algebra and homomorphism are closely related. Knowing that the congruence θ on an algebra A is the kernel of the quotient map from A onto A/θ , we can treat congruence relations on A as kernels of homomorphisms with A as the domain. The relationship between quotients, homomorphisms and congruences is described by the celebrated isomorphism theorems, which are a general and important foundational part of universal algebra; cf. [11].

The main goal of this paper is to give isomorphism theorems for semigroups with apartness. As in [4, 8], “every effort will be made to follow classical development along the lines suggested by familiar classical theories or in altogether new directions.”

Semigroup theory is also a young part of CLASS. As a separate branch of algebra with its own objects, formulations of problems, and methods of investigations, semigroup theory was formed more than 60 years ago.

Historically, it can be viewed as an algebraic abstraction of the properties of the composition of transformations on a set. Later sources, besides of those coming from the theory of groups and the theory of rings, include an abstraction of certain ideas arising in connection with topological or linear spaces. More about the history of ∗ e-mail: meli@masfak.ni.ac.rs

C© 2013 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim 408 S. Crvenkovic´, M. Mitrovic´, and D. A. Romano: Semigroups with apartness algebraic theory of semigroups can be found in [17]. 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 [6], used such semigroups.

Within BISH isomorphism theorems for groups and rings with tight apartness are presented in [23, 24]. Beside the fact that “a considerable part of the traditional notions and techniques is salvaged”, new concept must be introduced as well. Thus, as a “positive ‘dual’ of” a subgroup the notion of antisubgroup appears in groups with tight apartness. A similar job within rings with tight apartness is done by the notion of anti-ideal.

As we have already pointed out, our primary objective is to prove isomorphism theorems for semigroups with apartness. Our work is based on applications of ideas and notions coming from [6, 10]. The paper is organized in the following way. A set with apartness together with an equivalence and its ‘dual’ coequivalence (Theorem 2.3) is the subject of § 2. The main result of this section is Theorem 2.5, an apartness version of the Isomorphism

Theorem for Sets. Semigroups with apartness are studied in Section 3. This section begins with Example 3.1, which justify the study of such structures. The main results are given in Theorem 3.3 and Theorem 3.4 which are apartness isomorphism theorems for semigroups with apartness.

For undefined notions and notation, cf. [20, 23, 24]. Other general references for constructive mathematics are [2, 4, 8, 9, 10]. For the classical case, cf. [1, 11, 18, 21]. 2 Sets with apartness

In the constructive order theory the notion of cotransitivity, i.e., the property that for every pair of related elements any other element is related to one of the original elements in the same order as the original pair is a constructive counterpart to classical transitivity. Irreflexive and cotransitive relations are the building blocks of constructive order theory. With a primitive notion of ‘set with apartness’, our intention is to connect all relations defined on such a set. This is done by requiring them to be a part (subset) of an apartness. Such relations are clearly irreflexive; if, in addition, they are cotransitive, then they are called coquasiorders. More about coquasiorders can be found in, e.g., [13, 22]. The main subjects of this section are those symmetric coquasiorders called coequivalences, and the equivalences which can be associated to them.