$\mathcal{R}$-relation in full transformation semigroup

Question

Let $T_{X}$ be the full transformation semigroup on $X$. For $\alpha$, $\beta \in T_{X}$ $$\alpha \mathcal{R}\beta \text { if and only if there exist }\gamma,\gamma' \in T_{X}:\alpha\gamma=\beta\gamma' .$$

This question that looks trivial, takes us into about an hour with my course mates. We argue that by definition $\alpha R\beta$ implies $\alpha T_{X}^1=\beta T_{X}^1$.

So, there exist $\gamma,\gamma' \in T_{X}$ such that $\alpha\gamma=\beta\gamma'$. Hence the result.

But our professor rejected our proof since $\gamma,\gamma' \in T_{X}$ not in $T_{X}^1$ as given in the statement of the problem. The lecture notes by Tero Harju are here, chapter 5 page 52.

---

Note that: In any semigroups S the relation $\mathcal{L}$, $ \mathcal{R}$ and $\mathcal{J}$ are define by $$x \mathcal{L}y \Leftrightarrow S^1x=S^1y$$ $$x \mathcal{R}y \Leftrightarrow xS^1=yS^1$$ $$x \mathcal{J}y \Leftrightarrow S^1xS^1=S^1yS^1$$.

The set $T_{X}$ is the set of all mappings from $X$ to $X$ known as the full transformation semigroup on X with the operation of composition of mappings.

Answer 1

You want to show that for $\alpha,\beta\in T_X$,

$$\alpha \mathcal{R}\beta \text { if and only if there exist }\gamma,\gamma\,' \in T_{X}\text{ such that }\alpha\gamma=\beta\gamma\,'\;.$$

You know that if $\alpha\mathcal{R}\beta$, then $\alpha T_X^1=\beta T_X^1$, so there are certainly $\gamma,\gamma\,'\in T_X^1$ such that $\alpha\gamma=\beta\gamma\,'$; the question is whether you can find them in $T_X$ itself. HINT: Is $T_X$ a monoid?

This still leaves the other direction. Suppose that there are $\gamma,\gamma\,' \in T_X$ such that $\alpha\gamma=\beta\gamma\,'$; you need to show that $\alpha T_X^1=\beta T_X^1$. Unfortunately, unless I’m misunderstanding something, this appears not to be true in general. Consider $T_X$ for $X=\{0,1\}$; it has four elements, $\alpha,\beta,\gamma,\delta$ described by the following table:

$$\begin{array}{r|c} &0&1\\ \hline \alpha&0&0\\ \beta&0&1\\ \gamma&1&0\\ \delta&1&1 \end{array}$$

It’s easy to check that $\beta\alpha=\alpha^2=\alpha$, so there are indeed $\gamma,\gamma\,'\in T_X$ such that $\alpha\gamma=\beta\gamma\,'$: just take $\gamma=\gamma\,'=\alpha$. But it’s not true that $\alpha\mathcal{R}\beta$: $\alpha T_X^1=\{\alpha\}$, but $\beta T_X^1=T_X^1$.

Answer 2

The claim is incorrect, as Brian M. Scott's answer shows. Actually, you can see this from the statement which the claim was intended as part of the proof of, which is:

$\textbf{Proposition:}$ If $\alpha, \beta\in T_X$, then $\alpha \cal {R} \beta$ if and only if $\alpha(X) = \beta(X)$.

Suppose $\gamma(X) = \gamma'(X) = \{x\}$. Then $\alpha\gamma = \beta\gamma'$ if and only if $\alpha(x) = \beta(x)$. Clearly if $|X|>1$ this does not imply $\alpha(X) = \beta(X)$.

It might be a good exercise to give a correct proof of the proposition (it's not hard).

Answer 3

First, by definition in Harju's notes (Pp.7), $S^1 = S$ if $S$ is a monoid.

$T_X$ is the set of ALL functions $\alpha : X \to X$, which includes the identity map. Thus, it is not only a semigroup but also a monoid. By definition, $T_X = T_X^1$.

I hope that I just answered the OP's question. I had the same issue years ago when I first studied semigroup theory. Then I figured out that people call $T_X$ the full transformation semigroup by convention. It's not wrong because a monoid is always a semigroup. It's just misleading. Can any semigroup theorist tell us why people use this convention?