Right equivalent elements arising in the proof of the Schützenberger Theorem

Question

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in line 11, namely in the equation: $$" \gamma ( f x ) M ( = mM = mM \cdot M)"$$ But I will break this down in my own words to make this understandable (hopefully).

Let $M$ be an aperiodic monoid, $\Sigma$ a finite alphabet and $\gamma : \Sigma^* \to M$ a surjective monoid-homomorphism. Fix an element of $m \in M$, whose generated right ideal satisfies $m M \neq MmM$ and $mM \neq M$.
With these define the language $L = \gamma^{-1}(mM)$ and $\hat{L} = L \setminus (L\Sigma^+)$ (one can prove that $\hat{L}$ is the smallest set satisfying $L = \hat{L}\Sigma^*$) and $M'' = \{m'\in M \mid \gamma^{-1}(m')\Sigma \cap \hat{L} \neq \varnothing\}$.
For a fixed $m' \in M''$ one can find a $w \in \gamma^{-1}(\{m'\})$ and a $\sigma \in \Sigma$, such that $w \sigma \in \hat{L}$. Now one has to show, that $mM = \gamma(w \sigma) M$.

Well in my opinion $\gamma(w \sigma)M \subseteq mM$ is rather easy, because $w\sigma \in \hat{L} \subseteq L$, therefore $\gamma(w\sigma) \in mM$, which implies ($M \cdot M = M$) this direction.

But I have trouble proving the opposite direction. I gladly appreciate every hint you give me, because I seem to have some kind of blockade in thinking about this. My guess is that the special property of $\hat{L}$ (above in parentheses) is somehow involved.

Reference:
$^{[1]}$ M.P. Schützenberger. On finite Monoids having only trivial subgroups. Inform. and Computation, 8:190-194, 1965.
A copy can be obtained here: Schützenberger Theorem

Answer 1

As suggested by J.-E. Pin in the comments, this claim is wrong in the general case. To prove this statement a counter-example shall be constructed, but this will be done by a Haskell-program (at the bottom of this answer). But first I want to explain what it should do. The program looks onto a special kind of maps that map Maybe [-2,-1,0,1,-2] to itself. It suffices to look at maps that only go from [-2,...,2] to Maybe [-2,...,2]. The set of maps that this program looks at is even more limited, because it shall only be those maps, that can be generated by a and b only. The function calculateAll should calculate the all the elements in the monoid generated by these two functions and the identity (this is a rather large monoid with 56 Elements). isAperiodic does what the name suggests, but it does not fail, therefore it is unsafe. Next this program can calculate all the "interesting" candidates, that are those elements of the monoid, whose principal right ideal does not equal the whole monoid and not the principal two-sided ideal. This is done by getCandidates. Then testForOneCandidate generates all the counterexamples for the claim for a fixed element $m$, where only completion with the letter $a$ is considered. This is done as follows: An element in $m''$, which does not lie in $mM$, but $m''\ast a \in mM$, is in $M''$. For such an element one only needs to test if $m'' M \neq mM$. This is what testForOneCandidate does. Retranslating the first result of the call testForOneCandidate (head getCandidates) into potencies of a and b one gets the following in ghci testable counter-example (after loading the code):

*Main> let ba = b `mappend` a
*Main> ba `elem` rightPrincipalIdeal a
False
*Main> let ba2 = ba `mappend` a
*Main> ba2 `elem` rightPrincipalIdeal a
True
*Main> (fromList $ rightPrincipalIdeal ba2) < (fromList
    $ rightPrincipalIdeal a)
True

That is a rather complicated example, but I'm sure that there are simpler ones, it's just the first that I encountered.

Here is the code:

import Data.List (nub,(\\))
import Data.Set (fromList)

data Element = Element (Int -> Maybe Int)

instance Show Element where
  show (Element f) = show (map f [-2..2])

instance Eq Element where 
  (==) (Element f) (Element g) = (map f [-2..2]) == (map g [-2..2])

instance Ord Element where
  (<=) (Element f) (Element g) = (map f [-2..2]) <= (map g [-2..2])

instance Monoid Element where
  mempty = Element dropOutside
  mappend (Element f) (Element g) = Element $ \i -> ((f i) >>= g)    

-- Helper function
dropOutside :: Int -> Maybe Int
dropOutside i
  | abs (i) <= 2 = Just i
  | otherwise = Nothing

-- First elements that "generate" the monoid
a :: Element
a = Element $ \i -> dropOutside (i+1)

b :: Element
b = Element $ \i -> dropOutside (i-1)

nullElement :: Element
nullElement = Element $ \_ -> Nothing

-- Generates the monoid by the neutral element, a and b.
calculateAll :: [Element]
calculateAll =
  let
      calculateAllRec :: [Element] -> [Element]
      calculateAllRec acc =
          let
              newEs = nub [z| x <- acc, y <- acc,let z = x `mappend` y,z `notElem` acc]
          in case newEs of
               [] -> acc
               _ -> calculateAllRec (acc ++ newEs)
in calculateAllRec [mempty,a,b]

-- Checks whether a given element is aperiodic. (Unsafe)
isAperiodicElement :: Element -> Bool
isAperiodicElement x = isApElRec x x where
  isApElRec x' y'
      | y' == (x' `mappend` y') = True
      | otherwise = isApElRec x' (x' `mappend` y')

-- Checks if the whole monoid is aperiodic. (Unsafe)
isAperiodic :: Bool
isAperiodic = all isAperiodicElement calculateAll

-- Calculates the right ideal generated by a given element.
rightPrincipalIdeal :: Element -> [Element]
rightPrincipalIdeal x = nub [x `mappend` y | y <- calculateAll]

-- Calculates the twosided ideal generated by a given element.
twoSidedPrincipalIdeal :: Element -> [Element]
twoSidedPrincipalIdeal x = nub [z `mappend` x `mappend` y | z <- calculateAll , y <- calculateAll]

-- Calculates all those elements, that generate a right ideal, which is not
-- equal to the whole monoid and the twosided ideal generated by that same element.
-- Results in all elements besides the neutral and the null element.
getCandidates :: [Element]
getCandidates =
  let
      fLcA = fromList calculateAll
  in [x| x <- calculateAll,
         let z = fromList $ rightPrincipalIdeal x,
         z /= fromList (twoSidedPrincipalIdeal x),
         z /= fLcA]     


-- Tests for an element m from getCandidates, if there is an element in M withouth mM
-- that reaches mM by adding an a (which amounts to saying that this element m' is in
-- M''). Therefore m'a is in mM. But also m'aM must not be mM.
testForOneCandidate :: Element -> [Element]
testForOneCandidate m =
  let
     mM = fromList $ rightPrincipalIdeal m
     factorsWithA = [m' | m' <- calculateAll ,
                                m' `notElem` mM,
                                let x = m' `mappend` a,
                                x `elem` mM,
                                fromList (rightPrincipalIdeal x) /= mM ]
  in factorsWithA