0
$\begingroup$

Does there exist an isomorphism between the semigroups $S(4)$ and ‎‎‎‎‎‎$\mathbf Z_{256‎‎‎‎‎‎‎}$.‎

$S(4)$ is the set of all maps from the set $X$ to itself and $X = \{1, 2, 3, 4\}$. $S(4)$ is a semigroup under the composition of mappings and ‎‎‎‎‎$\mathbf Z_{256} = {0, 1, 2, … , 255}$ is the semigroup under multiplication of integers modulo 256.

$\endgroup$
1
  • 2
    $\begingroup$ This might be better received at mathstackexchange but some reformatting is needed. $\endgroup$ Oct 9, 2013 at 16:59

3 Answers 3

4
$\begingroup$

Note that in $\mathbb Z_{256}$ we only have two elements $x$ so that $$x^2=x$$

Indeed, if $x$ is odd, it is invertible, otherwise $x-1$ is invertible $\mod{256}$.

In $S(4)$ there are many functions $f$ so that $f \circ f =f$, for example, all functions with only one element in the image.

So the answer is no.

Second solution The invertible elements in $S(4)$ are the permutations, thus $S(4)$ has $4!=24$ invertible elements. The invertible elements in $\mathbf Z_{256‎‎‎‎‎‎‎}$ are the numbers relatively prime to $256$ (i.e. odd numbers). Thus $\mathbf Z_{256‎‎‎‎‎‎‎}$ has 128 invertible elements.

$\endgroup$
2
$\begingroup$

Another answer, to add to N.S.'s two. In $\mathbb{Z}_{256}$, the element $3$ has order 64. That is, $3^{n}\neq 1$ for all $1\le n<64$, but $3^{64}=1$. In order for an element of $S(4)$ to have an order at all, it must be a bijection (permutation). All permutations of $\{1,2,3,4\}$ have order $1,2,3$, or $4$; much less than 64.

$\endgroup$
1
  • 1
    $\begingroup$ OR: As $f : Im(f) \to Im f$ becomes a bijection, it follows that for every $f \in S(4)$ there exists an $2 \leq m \leq 5$ so that $f^m=f$. As you pointed for $3$ the smallest such number is $65$, not even close... This observation makes finding such a number much easier, because the order doesn't matter anymore, it only matters if it is more than $4$. $\endgroup$
    – N. S.
    Oct 9, 2013 at 19:00
2
$\begingroup$

$\mathbb Z_{256}$ is commutative and $S(4)$ isn't.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .