1
$\begingroup$

I'm trying to learn about the Krohn-Rhodes theorem, and I'm struggling to apply it even on incredibly simple semigroups.

Notation

$C_2 = \langle e,x \mid x^2=e \rangle$ is the cyclic group on two elements. $U_3 = \langle S, R, E \mid SR = RR = R, RS = SS = S \rangle$ is the "flip-flop monoid" with three elements "set", "reset", and "do nothing".

Problem

Let $\{0,1\}^{\{0,1\}}$ be the set of functions $f : \{0,1\} \rightarrow \{0,1\}$. There are four such functions: the identity $f_i$, the constant 0 and 1 functions $f_0$ and $f_1$, and the "not" function $f_n$. These four functions form a semigroup (technically a monoid) when endowed with the composition operator $\circ$. This semigroup has one group as a factor, namely $C_2$, which is isomorphic to $f_i, f_n$. What is the smallest Krohn-Rhodes decomposition of this semigroup?

What I've tried

My first instinct was that perhaps $\{0,1\}^{\{0,1\}}$ was a factor of $C_2 \wr U_3$. In this case, we would represent $f_i$ as $(e,e)e$, and perhaps $f_n$ as $(x,x)e$, which gives us $f_n \circ f_n = (x,x)e * (x,x)e = (xx,xx)ee = (e,e)e$ as desired. But then I got stuck trying to implement $f_0 = (-,-)R$ and $f_1 = (-,-)S$. I've also tried $U_3 \wr C_2$ to no avail. Is it something more complicated like $U_3 \wr C_2 \wr U_3$? Any help would be greatly appreciated.

$\endgroup$
2
  • $\begingroup$ @Nobody I don't see how this works; the proposed decomposition doesn't have an identity element, but $\{0,1\}^{\{0,1\}}$ does $\endgroup$
    – Jake
    Aug 26, 2022 at 10:46
  • $\begingroup$ You're right. I'll delete my comment above. $\endgroup$
    – Nobody
    Aug 26, 2022 at 11:09

1 Answer 1

0
$\begingroup$

First, I've found a lot of conflicting notation and convention for the wreath product, and I think I was using poor notation before. The other catch is that the monoid I actually want to use is what is called $U_2$ in the Krohn-Rhodes paper, which consists of a constant 0 function $S$ and the identity function $E$ (keeping consistency with my earlier presentation).

Finally, here I'll be assuming that a group element applied on the right is the "last" thing being applied, so it's the same as the function being applied on the left.

The wreath product I want is $C_2 \wr U_2$. Using notation from here, the mapping from $\{0,1\}^{\{0,1\}}$ are as follows:

  • $f_i$ maps to $E(e,e)$ as expected
  • $f_n$ maps to $E(e,f)$
  • $f_0$ maps to $S(e,e)$
  • $f_1$ maps to $S(e,f)$

Note that the first element in each of the "coordinate pairs" is always $e$, which is what allows $f_0$ and $f_1$ to be absorbing.

The important operations (again, based on the notation from the same source) are:

  • $E(e,f) \cdot E(e,f) = E(e,e)$ (so $f_n^2 = f_i$ as expected)
  • $E(e,f) \cdot S(e,e) = ES(ee, ee) = S(e,e)$ (so $f_0$ is absorbing as expected)
    • In general one can see that, because the first element of each of the coordinate pairs is $e$, any term with an $S$ is right-absorbing
  • $S(e,e) \cdot E(e,f) = SE(ee, ef) = S(e,f)$ (flipping $f_0$ gives $f_1$)
$\endgroup$

You must log in to answer this question.

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