Module Code MAT00050M MMath and MSc Examinations 2020/21 Department: Mathematics Title of Exam: Semigroup Theory Time Allowed: You have 24 hours from the release of this exam to upload your solutions. Allocation of Marks: Each question carries 25 marks. The marking scheme shown on each question is indicative only. Instructions for Candidates: Answer all questions. It is important to show your work and reasoning in order to demonstrate your knowledge and understanding. In your solutions, you may use anything covered during the course, without reproving it. Queries: If you believe that there is an error on this exam paper, then please use the “Queries” link below the exam on Moodle. This will be available for the first hour after the release of this exam. After that, if a question is unclear, then answer it as best you can and note the assumptions you’ve made to allow you to proceed. Submission: Please write clearly and submit a single copy of your solution to each question. Any handwritten work in your electronic submission must be legible. Black ink is recommended for written answers. View your submission before uploading. Number each page of your solutions consecutively. Write the exam title, your candidate number, and the page number at the top of each page. Upload your solutions to the “Exam submission” link below the exam on Moodle (preferably as a single PDF file). If you are unable to do this, then email them to maths-submit@york.ac.uk. Page 1 (of 4) MAT00050M A Note on Academic Integrity We are treating this online examination as a time-limited open assessment, and you are therefore permitted to refer to written and online materials to aid you in your answers. However, you must ensure that the work you submit is entirely your own, and for 28 hours after the exam is released, you must not: communicate with departmental staff on the topic of the assessment (except by means of the query procedure detailed overleaf), communicate with other students on the topic of this assessment, seek assistance on this assessment from the academic and/or disability support services, such as the Writing and Language Skills Centre, Maths Skills Centre and/or Disability Services (unless you have been recommended an exam support worker in a Student Support Plan), seek advice or contribution from any third party, including proofreaders, friends, or family members. We expect, and trust, that all our students will seek to maintain the integrity of the assessment, and of their awards, through ensuring that these instructions are strictly followed. Failure to adhere to these requirements will be considered a breach of the Academic Misconduct regulations, where the offences of plagiarism, breach/cheating, collusion and commissioning are relevant — see Section AM.1.2.1 of the Guide to Assessment (note that this supersedes Section 7.3). Page 2 (of 4) MAT00050M 1 (of 4). Consider the transformation semigroup TX with X = {1, 2, 3, 4, 5}. (a) Show that the set T = {( 1 2 3 4 5 1 1 3 5 5 ) , ( 1 2 3 4 5 3 3 5 1 1 ) , ( 1 2 3 4 5 5 5 1 3 3 )} forms a subgroup of TX . [8] (b) Find the maximal subgroup M of TX containing T and list its elements. [9] (c) To which well-known group is T isomorphic To which well-known group is M isomorphic Write down explicit isomorphisms. [8] 2 (of 4). Consider the monogenic semigroup 〈a〉, where a has index n and period r. (a) Describe all the principal ideals of 〈a〉. [7] (b) Prove that all ideals of 〈a〉 are principal. [6] (c) Let I be any ideal of 〈a〉. Prove that 〈a〉/I is monogenic, and describe all the possible values the index and period of its generator can take. [6] (d) Determine the values of n and r for which all congruences of 〈a〉 are Rees congruences. [6] Page 3 (of 4) Turn over MAT00050M 3 (of 4). Consider the semigroup (R2×2, ·) of all 2-by-2 matrices with real entries under multiplication, and let S = {( 1 0 0 0 ) , ( 0 1 0 0 ) , ( 0 0 1 0 ) , ( 0 0 0 1 ) , ( 0 0 0 0 )} . (a) Prove that S forms a subsemigroup of R2×2. [5] (b) Determine the relations L,R,H and D on S and draw the egg-box diagrams of all D-classes of S. [10] (c) Deduce that S is completely 0-simple. [3] (d) Give a Rees matrix semigroup isomorphic to S, making use of the proof of Rees’s theorem. [7] 4 (of 4). Let S, T be inverse semigroups, and denote the inverse of s by s′. (a) Prove that if : S → T is a semigroup morphism, then for any s ∈ S, we have s′ = (s )′. [6] (b) Deduce that if ρ is a congruence on S, then for any s, t ∈ S, we have s ρ t implies s′ ρ t′. [6] (c) Let ρ be any congruence on S. Prove that ρ H if and only if for all idempotents e, f of S, whenever e ρ f we have e = f . [8] (d) Give an example of a nontrivial inverse semigroup which has no nontrivial congruences ρ satisfying ρ H. [5] Page 4 (of 4) End of examination. SOLUTIONS: MAT00050M 1. (a) Put α = ( 1 2 3 4 5 1 1 3 5 5 ) , β = ( 1 2 3 4 5 3 3 5 1 1 ) , γ = ( 1 2 3 4 5 5 5 1 3 3 ) . One can check by computation that α is as an identity element in T , and βγ = γβ = α, furthermore β2 = γ, γ2 = β. So T is closed under multiplica- tion, and every element has an inverse with respect to α, (β 1 = γ, γ 1 = β). 8 Marks (b) We know by the maximal subgroup theorem that M is the (common)H-class of elements of T . The kernel partition of elements of T is {{1, 2}, {3}, {4, 5}}, and the image is {1, 3, 5}. The elements ofM are all the maps with this kernel and image, so M = T ∪ {( 1 2 3 4 5 1 1 5 3 3 ) , ( 1 2 3 4 5 5 5 3 1 1 ) , ( 1 2 3 4 5 3 3 1 5 5 )} . 9 Marks (c) We have T ～= Z3 as that is the only group of order 3 up to isomorphism. An isomorphism is : T → Z3, α 7→ 0, β 7→ 1, γ 7→ 2. The group M is isomorphic to S3 via ψ : M → S3,( 1 2 3 4 5 1 1 3 5 5 ) ψ = ( 1 2 3 1 2 3 ) , ( 1 2 3 4 5 1 1 5 3 3 ) ψ = ( 1 2 3 1 3 2 ) , ( 1 2 3 4 5 3 3 1 5 5 ) ψ = ( 1 2 3 2 1 3 ) , ( 1 2 3 4 5 3 3 5 1 1 ) ψ = ( 1 2 3 2 3 1 ) ,( 1 2 3 4 5 5 5 1 3 3 ) ψ = ( 1 2 3 3 1 2 ) , ( 1 2 3 4 5 5 5 3 1 1 ) ψ = ( 1 2 3 3 2 1 ) . 8 Marks Total: 25 Marks 2. (a) Put S = 〈a〉. Let k ∈ N, then we have b ∈ S1akS1 if and only if b = axakay = ak+x+y for some x, y ∈ N0 (where a0 = 1), that is, if and only if b = al for some l ≥ k. We claim that am ∈ S1akS1 m ≥ n or m ≥ k. Recall that elements of S are uniquely of the form am with 1 ≤ m ≤ n+r 1. If m < n, then for any l ∈ N, am = al implies m = l, therefore if m < n, m < k, then we have am /∈ S1akS1 as am does not arise as al for any l ≥ k. 5 SOLUTIONS: MAT00050M However, if m ≥ n, then am = am+kr, and as m + kr ≥ k, we have am = am+kr ∈ S1akS1 by the first paragraph. If m ≥ k then of course we also have am ∈ S1akS1 by the first paragraph. This proves our claim. So S1akS1 = {am : min(k, n) ≤ m ≤ n + r 1}. If k ≤ n, then this is just the set {ak, ak+1, . . . , an+r 1}, if k > n then this is (independently of k) {an, an+1, . . . , an+r 1}. 7 Marks (b) Let I be any ideal, and let ak ∈ I (where 1 ≤ k ≤ n + r 1) be such that k is minimal. We will prove that I = S1akS1. We of course have S1akS1 I , so in particular k is the minimal exponent in S1akS1 as well, thus k ≤ n by part (a). But then S1akS1 = {ak, ak+1, . . . , an+r 1} by part (a) and I {ak, ak+1, . . . , an+r 1} by the minimality of k, which proves the claim. 6 Marks (c) From parts (a) and (b), we have I = {ak, ak+1, . . . , an+r 1} for some 1 ≤ k ≤ n. Recall that S/I ～= S I ∪ {0} = {a, . . . , ak 1, 0}, where 0 is a zero element, and we have am = 0 for any m ≥ k. It is clear that a generates S/I , the index of a is k, and the period of a is 1. 6 Marks (d) By exercise 3/6, we have that the image of any surjective morphism : 〈a〉 → T is a monogenic semigroup generated by b = a , and its index can be any n′ ∈ N with n′ ≤ n and its period any r′ ∈ N with r′ | r. By the homomorphism theorem, the congruences of 〈a〉 are exactly the kernels of such maps , and thus we need to find for which n and r are these kernels all Rees congruences. If ker = ρI for some ideal I , then 〈b〉 = T ～= 〈a〉/ ker = 〈a〉/ρI and so by part (c) we must have r′ = 1. This happens for all surjective mor- phisms : 〈a〉 → T if and only if the only possibility for r′ ∈ N with r′ | r is r′ = 1, that is if r = 1. 6 Marks Total: 25 Marks 3. (a) We need to prove that S is closed under taking products. The zero matrix is the zero element of R2×2, so any product involving it will be contained in S. We therefore only need to check the products of the other four matrices. This can be done brute force but also follows from the following observation: the product of two matrices each containing at most one nonzero entry will also contain at most one nonzero entry, the product of the respective entries. 5 Marks 6 SOLUTIONS: MAT00050M (b) We begin by calculating the left and right principal ideals: S1 ( 1 0 0 0 ) = S1 ( 0 0 1 0 ) = {( 1 0 0 0 ) , ( 0 0 1 0 )} , S1 ( 0 1 0 0 ) = S1 ( 0 0 0 1 ) = {( 0 1 0 0 ) , ( 0 0 0 1 )} ,( 1 0 0 0 ) S1 = ( 0 1 0 0 ) S1 = {( 1 0 0 0 ) , ( 0 1 0 0 )} ,( 0 0 1 0 ) S1 = ( 0 0 0 1 ) S1 = {( 0 0 1 0 ) , ( 0 0 0 1 )} , S1 ( 0 0 0 0 ) = ( 0 0 0 0 ) S1 = {( 0 0 0 0 )} . This tells us that there are two D-classes with the respective egg-box dia- grams: ( 1 0 0 0 ) ( 0 1 0 0 ) ( 0 0 1 0 ) ( 0 0 0 1 ) ( 0 0 0 0 ) 10 Marks (c) Since S is finite, D = J , so we have a single nonzero J -class, which makes S 0-simple. Again, as S is finite, it is completely 0-simple. 3 Marks (d) To obtain a Rees matrix semigroup isomoprhic to S, we follow the proof of Rees’s theorem. We begin by finding an idempotent in the non-zero D-class, say e = ( 1 0 0 0 ) . The corresponding H-class is G = {e}. As the egg-box is two-by-two, we have I = Λ = {1, 2}, furthermore q1 = r1 = ( 1 0 0 0 ) , q2 = ( 0 1 0 0 ) , r2 = ( 0 0 1 0 ) . Then (denoting the zero matrix by 0), we have p11 = q1r1 = e, p12 = q1r2 = 0, p21 = q2r1 = 0, p22 = q2r2 = e. So P = ( e 0 0 e ) , and S ～=M0(G; I,Λ;P ). 7 Marks 7 SOLUTIONS: MAT00050M Total: 25 Marks 4. (a) Note that (s )(s′ )(s ) = (ss′s) = s , and similarly (s′ )(s )(s′ ) = (s′ss′) = s′ , so s′ is a (generalized) inverse of s in T . Since T is an inverse semigroup, the inverse of every element is unique, so (s )′ = s′ . 6 Marks (b) Consider the homomorphism : S → S/ρ guaranteed by the homomorphism theorem. Then S/ρ is an inverse semigroup. Proof1: S/ρ is regular by Exercise 9/2. We show that its idempotents also commute, thus it is inverse. First assume s ∈ E(S/ρ), that is, s = (s )2 = s2 . Put es = s(s2)′s ∈ S. Note that (s(s2)′s)2 = s(s2)′s2(s2)′s = s(s2)′s, thus es ∈ E(S). Furthermore es = (s(s 2)′s) = s2 (s2)′ s2 = (s2(s2)′s2) = s2 = s . So for any s, t ∈ S with s , t ∈ E(S/ρ), we have that es, et ∈ E(S) thus eset = etes as S is inverse, and so s t = es et = (eset) = (etes) = t s by the previous, proving that the idempotents of S/ρ commute indeed. As S/ρ is an inverse semigroup, and we can apply part (a) to . Then s = [s]ρ = [tρ] = t , so (s′ ) = (s )′ = (t )′ = (t′ ). Therefore [s′]ρ = [t′]ρ, that is s′ ρ t′. 6 Marks (c) First assume ρ H. Then if e ρ f for some e, f ∈ E(S), then e H f and so e = f indeed. Conversely assume ρ is idempotent separating, and assume s ρ t. We need s H t. Recall that this is equivalent to ss′ = tt′, s′s = t′t. As s ρ t, by part (b) we have s′ ρ t′ as well, so ss′ ρ tt′, s′s ρ t′t. As ρ is idem- potent separating, this implies ss′ = tt′, s′s = t′t and thus s H t indeed. 8 Marks (d) The best example is the bicyclic monoid: here H = ι, so clearly every con- gruence contained inH is also ι. 5 Marks Total: 25 Marks 1Maximum points were given even if this proof was missing. 8
