EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 6, No. 3, 2013, 335-339 ISSN 1307-5543 – www.ejpam.com Finiteness Conditions for Unions of Two Semigroups and Ranks of B(G, n) Melis Minisker Mustafa Kemal University, Faculty of Education, Antakya-Hatay Abstract. In this paper we try to find the finiteness conditions for union of two finite semigroups with a specially defined binary equation. Moreover we find the ranks of the semigroup B(G, n). 2010 Mathematics Subject Classifications: 20M05 Key Words and Phrases: finiteness conditions, ranks, union 1. Introduction Finiteness conditions of semigroups (the properties of semigroups which all finite semi- groups have) have been considered for certain classes of semigroup constructions. (for exam- ples see [1, 2]). In this paper periodicity, residual finiteness and solvability of word problem of union of two finite semigroups are determined. Let S and T be two finite semigroups with empty intersection. We define a binary equation on S ∪ T as follows: If s1 ∈ S and s2 ∈ S then s1.s2 is considered as the same operation defined on S. If t1 ∈ T and t2 ∈ T then t1.t2 is considered as the same operation defined on T . If s ∈ S and t ∈ T then st = ts = t. In [3] it is shown that any finitely presented semigroup S is embedded into an inefficient semigroup, namely, the semigroup S∪SLn where SLn is the free semilattice of rank n. Let S be a finite semigroup. A subset U of S is called independent if, for every u in U , the element u does not belong to the semigroup < U \{u}> generated by the remaining elements of U (see [4]). In [5] Howie and Ribeiro introduced r1(S), r2(S), r3(S), r4(S) and r5(S) defined as follows: • r1(S) = max{k : every subset U of S of cardinality k is independent} • r2(S) = min{k : there exists a subset U of S of cardinality k which generates S} Email addresses: melisminisker@hotmail.com http://www.ejpam.com 335 c© 2013 EJPAM All rights reserved. M. Minisker / Eur. J. Pure Appl. Math, 6 (2013), 335-339 336 • r3(S) = max{k : there exists a subset U of S of cardinality k which is independent and which generates S} • r4(S) = max{k : there exists a subset U of S of cardinality k which is independent} • r5(S) = min{k : every subset U of S of cardinality k generates S} Generally in [5], r1(S) is small rank, r2(S) is lower rank, r3(S) is intermediate rank, r4(S) is upper rank and r5(S) is large rank. In [5] r5(Cn), r5(Tn) and r5(B(G, n)) are given. Here Cn is the cyclic group of order n, Tn is the full transformation semigroup and B(G, n) is a Brandt semigroup. In [5] it is also shown that all five ranks of the aperiodic Brandt semigroup Bn are different. In this paper we examine r1(B(G, n)), r2(B(G, n)), r3(B(G, n)) and r4(B(G, n)). 2. Periodicity Recall that a semigroup S is periodic if, for each s ∈ S the monogenic semigroup generated by s is finite, or equivalently there exists positive integers m and n (depending on S) such that sm = sn. Theorem 1. Let S and T be finite semigroups. Then S and T are periodic if and only if S ∪ T is periodic. Proof. (⇒) Let S and T be periodic. Let x ∈ S ∪ T . Then x ∈ S or x ∈ T . If x ∈ S, since S is periodic there exists ∃m, n ∈ N such that xm = xn. If x ∈ T , since T is periodic there exists ∃k, l ∈ N such that xk = x l . So S ∪ T is periodic. (⇐) Let S ∪ T be periodic. Let x ∈ S. Since S ⊆ S ∪ T we have x ∈ S ∪ T . Since S ∪ T is periodic there exists ∃k1, k2 ∈ N such that xk1 = xk2 . We obtain S is periodic. Let y ∈ T . Since T ⊆ S ∪ T we have y ∈ S ∪ T . Since S ∪ T is periodic there exists ∃k3, k4 ∈ N such that yk3 = yk4 . Thus T is also periodic. 3. Residual Finiteness We call a semigroup residually finite if, for each pair s 6= t ∈ S there exists a homomor- phism φ from S onto a finite semigroup such that φ(s) 6= φ(t), or equivalently, there exists a congruance ρ with finite index (that is ρ has finitely many equivalence classes) such that (s, t) /∈ ρ. (Residual finiteness of completely (0)-simple semigroups, which are Rees matrix semigroups M[G; I , J , P] over groups was investigated in [2].) Theorem 2. S ∪ T is residually finite if and only if S and T are residually finite. Proof. (⇒) Assume that S∪T is residually finite. Since S and T are subsemigroups of S∪T then S and T are residually finite. (⇐) Assume that S and T are residually finite semigroups. We will show that S∪T is residually finite. Let s1, s2 ∈ S∪T and s1 6= s2. Since S is residually finite there is a finite semigroup K and an onto homomorphism φ : S→ K such that φ(s1) 6= φ(s2). Let Ψ : S ∪ T → K ∪ {0}. If x ∈ S M. Minisker / Eur. J. Pure Appl. Math, 6 (2013), 335-339 337 let Ψ(x) = φ(x) and if x ∈ T let Ψ(x) = 0. Then Ψ(s1) = φ(s1) 6= φ(s2) = Ψ(s2). If s1, s2 ∈ S then Ψ(s1s2) = φ(s1s2) = φ(s1).φ(s2). If t1, t2 ∈ T then Ψ(t1 t2) = 0 = ψ(t1).ψ(t2) = 0.0. If s ∈ S and t ∈ T then Ψ(st) = Ψ(t) = 0=Ψ(s)Ψ(t). So Ψ is an onto homomorphism. Let t1, t2 ∈ S ∪ T and t1 6= t2. Since T is residually finite there is a finite semigroup L and an onto homomorphism θ : T → L such that θ(t1) 6= θ(t2). We define α : S ∪ T → L ∪ {1} as follows. If x ∈ S let α(x) = 1 and if x ∈ T let α(x) = θ(x). It is clear that α(t1) = θ(t1) 6= θ(t2) = α(t2). If s1, s2 ∈ S then α(s1s2) = α(s1).α(s2) = 1.1 = 1. If t1, t2 ∈ T then α(t1 t2) = θ(t1 t2) = θ(t1).θ(t2). If s ∈ S and t ∈ T then α(st) = α(t) = θ(t) = α(s).α(t) = 1.θ(t). So α is an onto homomorphism. Let s, t ∈ S ∪ T and s 6= t. We define µ : S ∪ T → R2 = {a, b}. Here R2 = {a, b} is the right zero semigroup with 2 elements and ab = b, ba = a. If s ∈ S let µ(s) = a and if t ∈ T let µ(t) = b. We have µ(s) = a 6= µ(t) = b. If s1, s2 ∈ S then µ(s1s2) = a = µ(s1).µ(s2) = a.a = a. If t1, t2 ∈ T then µ(t1 t2) = b = µ(t1).µ(t2) = b.b = b. If s ∈ S and t ∈ T then µ(st) = µ(t) = b = µ(s)µ(t) = a.b = b. Thus µ is an onto homomorphism. 4. Solvable Word Problem A semigroup S is said to have a solvable word problem with respect to a generating set A if there exists a algorithm which, for any two words u, v ∈ A+, decides whether the relation u = v holds in S or not. It is a well-known fact that, for a finitely generated semigroup S, the solvability of the word problem does not depend on the choice of the finite generating set for S. Thus we say that a semigroup S has a solvable word problem with respect to any finite generating set. Theorem 3. S∪T has solvable word problem if and only if S and T have solvable word problem. Proof. (⇒) Let S ∪ T have solvable word problem. Since S and T are finitely generated, let Y1 be generating set of S and Y2 be generating set of T . Then Y1 ∪ Y2 is a generating set for S ∪ T . Let w1, w2 ∈ Y+1 . Since w1, w2 ∈ Y+1 ⊆ (Y1 ∪ Y2)+ and since S ∪ T has solvable word problem there exists an algorithm which decides whether w1 = w2 holds in S∪ T . Since w1, w2 ∈ Y+1 and Y1 is a generating set for S, the algorithm decides whether w1 = w2 holds in S. So S has a solvable word problem. Similarly it is shown that T has a solvable word problem. (⇐) Assume that S and T have solvable word problem. Let X be a finite generating set for S ∪ T . Then X1 = X ∩ S and X2 = X ∩ T are generating sets for S and T . The set Z = {x1 x2 = x2, x2 x1 = x2 | x1 ∈ X1, x2 ∈ X2} is finite. For w1, w2 ∈ X+, if we apply some necessary relations from Z we obtain w1, w2 ∈ X+ such that w1 = w′1 and w2 = w′2 holds in T . w′i ∈ X+1 (i = 1,2) or w′i ∈ X+2 (i = 1, 2). If w′1 and w′2 are not elements of the same free semigroup X+i (i = 1, 2) then w′1 = w′2 does not hold in S∪T . If w′1 and w′2 are in the same free semigroup X+i (i = 1,2) there exists an algorithm which decides whether the relation w′1 = w′2 holds in S or T . Because S and T have solvable word problem. So S ∪ T has solvable word problem. M. Minisker / Eur. J. Pure Appl. Math, 6 (2013), 335-339 338 5. Ranks of B(G, n) The semigroup B(G, n) = {1, 2, . . . , n} × G × {1, 2, . . . , n} ∪ {0} is the Brandt semigroup. The binary operation on B(G, n) is defined as follows (i, a, j).(k, b, l) = (i, ab, l) if j = k 0 if j 6= k 0.(i, a, j) = (i, a, j).0= 0.0= 0 In [5] r5(B(G, n)) is given. Now we define other ranks of B(G, n). Lemma 1. Let B(G, n) be the Brandt semigroup. Let A be the minimum generating set of G. Then r1(B(G, n)) = 1, r2(B(G, n)) = 2n.|A| and r3(B(G, n)) = 2n.|A|. Proof. Let A be the minimum generating set of G. We show the set B = {(1, a, j), (i, a, 1)|a ∈ A, 1≤ i ≤ n, 1≤ j ≤ n} is the minimum generating set for B(G, n). For (i, g, j) ∈ B(G, n) we have (i, g, j) = (i, a1, 1).(1, a2, 1).(1, a3, 1) . . . (1, am, j), (ai ∈ A, i = 1, 2, . . . m). So B is a generating set for B(G, n). Let C be a generating set for B(G, n). Since (i, a, 1) = (i, a, 1).(1, 1,1)(a ∈ A) and (1,1, j) = (1, 1,1).(1, 1, j). So we have B ⊆ C . Thus B is the minimum generating set for B(G, n). We have r2(B(G, n)) = 2n.|A|. Let D be a generating set for B(G, n) and assume that D is independent. Since D is a generating set and B is the minimum generating set then B ⊆ D. Let (i′, g, j′) ∈ D B. Let g = a′1a′2 . . . a′l(a ′ i ∈ A). Then (i′, g, j′) = (i′, a′1, 1).(1, a′2, 1)(1, a′3, 1) . . . (1, a′l , j′). This contradicts with the assumption of D to be independent. So B is the unique independent generating subset of B(G, n). Thus r3(B(G, n)) = 2n.|A|. Let (i, g, j) ∈ B(G, n). If i = j then (i, g, j).(i, g, j) = (i, g2, j) 6= (i, g, j) unless g2 = g. If i 6= j then (i, g, j).(i, g, j) = 0. So B(G, n) is not a band. Since r2(B(G, n)) 6=| B(G, n) | then B(G, n) is not royal. (see [5]) So r1(B(G, n)) = 1. In the following theorem we determine r4(B(G, n)). Theorem 4. Let B(G, n) be a Brandt semigroup. Let r4(G) = k. Then r4(B(G, n)) = k+ 1. Proof. Let U be the maximum independent subset of G. Since r4(G) = k then | U |= k. We will show that U ′ = {(1, u, 1)|u ∈ U}∪{0} is the maximum independent subset of B(G, n). Let (1, u, 1) = (1, u1, 1).(1, u2, 1)(u1, u2 ∈ U). Then u= u1.u2. Since U is independent then u= u1 or u = u2. We obtain U ′ is independent. Let U ′′ ⊆ B(G, n) be another independent set. We have U ′ ∪ (S\U ′) = S = B(G, n). Let s ∈ S\U ′. Let s = (i, g, j)(1≤ i ≤ n, g ∈ G\U , 1≤ j ≤ n). Since g ∈ G\U then g = g1.g2(g1, g2 ∈ G, g1 6= g, g2 6= g). We have (i, g, j) = (i, g1, j).( j, g2, j) and U ′′ = ((U ′∪{0})∩U ′′)∪ (U ′′∩ (S\U ′)). Since the elements of S\(U ′∪{0}) can be written REFERENCES 339 as a product of two elements. So U ′′ ∩ (S\(U ′ ∪ {0}) = ;. Then U ′′ = (U ′ ∪ {0})∩ U ′′. So U ′′ ⊆ (U ′ ∪ {0}). We obtain U ′ ∪ {0} is the maximum independent set. So r4(B(G, n)) = k+ 1. The studies on finiteness conditions of semigroups and ranks of semigroups may be ex- panded to different classes of semigroups as future work. References [1] H. Ayık. Presentations and Efficiency of Semigroups. PhD thesis, 1998. [2] H. Ayık. On Finiteness Conditions for Rees Matrix Semigroups. Czechoslovak Mathemati- cal Journal, 55, 2005. [3] H. Ayık, M. Minisker, and B. Vatansever. Minimal Presentations and Embedding Into Inefficient Semigroups. Algebra Colloquium, 12:59–65, 2005. [4] E. Giraldes and J.M. Howie. Semigroups of High Rank. Proceedings of the Edinburgh Mathematical Society, 28:13–34, 1985. [5] J.M. Howie and M.I.M. Ribeiro. Rank Properties of Semigroups II: the small rank and the large rank. Southeast Asian Bulletin of Mathematics, 24:231–237, 2000.