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.
$\begingroup$
$\endgroup$
9
-
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 SteinbergAug 14, 2018 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$– MikasaAug 14, 2018 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$– MikasaAug 14, 2018 at 10:53
-
3$\begingroup$ Computationally, group isomorphism is already not so easy. I would guess semigroup isomorphism is more difficult. $\endgroup$– Benjamin SteinbergAug 14, 2018 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 GrochowAug 29, 2018 at 12:19
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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.