# Krohn-Rhodes decomposition for transformations over $\{0,1\}$

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.

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

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$$)