Finite Semigroups property
Let $a$ and $b$ be two elements of a finite semigroup. Show that if $abb = b$, then $bab = b$.
Now I did this: $abb = b$, so $bab = abbab$. But $abb = b$, so $bab = b$. I know in semigroups this doesn't work like in strings.
Solution 1:
Let $S$ be the finite semigroup and assume $a, b \in S$ are such that $ab^2 = b$. Define functions $f$ and $g$ on $S$ by $f(s) = as$ and $g(s) = bs$ and consider the set $bS \cup \{b\}$ (where $bS = \{ bs \mid s \in S\}$). If we restrict $g$ to $bS \cup \{b\}$ and restrict $f$ to the range of $g$, we have. \begin{align*} g &: bS \cup \{b\} \to b^2S \cup \{b^2\}, \\ f &: b^2S \cup \{b^2\} \to ab^2S \cup \{ab^2\} = bS \cup \{b\} \end{align*} given our assumption that $ab^2 = b$, which also implies that, for any $x \in bS \cup \{b\}$, $f(g(x)) = abx = x$, i.e., the composite $f \circ g$ is the identity function on $bS \cup \{b\}$. This implies that $\#(b^2S \cup \{b^2\}) \ge \#(bS \cup \{b\})$ (by fact 1 below). But $b^2S \cup \{b^2\} \subseteq bS \cup \{b\}$, so, as both sets are finite, we must have $b^2S \cup \{b^2\} = bS \cup \{b\}$. I.e., we have: \begin{align*} g &: bS \cup \{b\} \to bS \cup \{b\}, \\ f &: bS \cup \{b\} \to bS \cup \{b\} \end{align*} But, as $bS \cup \{b\}$ is finite and $f \circ g$ is the identity on $bS \cup \{b\}$, $g \circ f$ is also the identity on $bS \cup \{b\}$ (by fact 2 below), giving us that: $$ bab = g(f(b)) = b $$
which was what we wanted.
We have used two facts about functions involving finite sets $X$ and $Y$:
- If $f : Y \to X$, $g : X \to Y$ and $f \circ g$ is the identity, then $\#Y \ge \#X$ (i.e., $Y$ has at least as many elements as $X$).
- If $f : X \to X$, $g : X \to X$ and $f \circ g$ is the identity, then $g \circ f$ is also the identity on $X$.
(With a suitable interpretation of $\#X$ and $\#Y$, fact 1 is also true for infinite $X$ and $Y$, but we only need it for finite $X$ and $Y$ here. Fact 2 is not true for infinite $X$.)