I have two finite semigroups namely $$S_1=\langle a,b: R\rangle,~~~S_2=\langle a,b: T\rangle$$ How can one show they are the same isomorphically? Should I show that the relations in one, implies the others and vice versa? Thanks for your time and your consideration.

  • 2
    $\begingroup$ If you know that they are finite you can compute the multiplication tables and search for isomorphisms. I am not sure how computationally feasible this is. $\endgroup$ – Benjamin Steinberg Aug 14 '18 at 10:11
  • $\begingroup$ @BenjaminSteinberg: That's right. It is a practical method of using the Cayley table of them to find that possible isomorphism. But in this case, elements may exceed and so I am searching for an abstract way counting on theorems and facts. Regards $\endgroup$ – mrs Aug 14 '18 at 10:44
  • $\begingroup$ @BenjaminSteinberg: I could find almost nothing on the web about it. Maybe it is covered inside an old article or new one and so I am not aware of it. $\endgroup$ – mrs Aug 14 '18 at 10:53
  • 3
    $\begingroup$ Computationally, group isomorphism is already not so easy. I would guess semigroup isomorphism is more difficult. $\endgroup$ – Benjamin Steinberg Aug 14 '18 at 11:11
  • 2
    $\begingroup$ @Benjamin Steinberg: semigroup isomorphism from multiplication tables is equivalent to graph isomorphism under polynomial time reductions. Suggests that it is hard in general, but perhaps good graph iso software (nauty, traces, bliss, conauto) could be of use for particular instances. $\endgroup$ – Joshua Grochow Aug 29 '18 at 12:19

If you have a function $f_1 : S_1 \rightarrow S_2$ and can show that $f_1(u) = f_1(v)$ for all $(u, v) \in R$ then you will have shown that $f_1$ is a homomorphism. If you can find such a function $f_1$ and another function $f_2 : S_2 \rightarrow S_1$ such that $f_2(u) = f_2(v)$ for all $(u, v) \in T$ and additionally show that they are either (i) both injective or (ii) both surjective then you will have proved isomorphism.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.