1
$\begingroup$

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.

  • 0
    @Brian: Yes, I see that now, but at the time I only looked at the immediately relevant part of the notes, because I was quite busy.2012-03-20

3 Answers 3

2

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

  • 0
    @Hassan:$A$particular argument not working is no reason to believe that a claim is not true. Especially in this case, where the argument happens to be of the form: "For $\alpha, \beta\in T_X$, $A$, therefore $B$", where $A$ is the thing about the existence of $\gamma$ and $\gamma'$, which isn't true, and $B$ is '$\alpha {\cal R}\beta\Rightarrow \alpha(X)=\beta(X)$', which doesn't follow from $A$. Nevertheless, $B$ is true, as you'll see if you take Brian's hint in the comments on my answer.2012-03-20
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).

  • 0
    Also, I am not asking you to accept my answer. I just think that your question has been answered and so it would be good for you to indicate that by accepting an answer (probably Brian's), or else to explain why you are still not satisfied.2012-03-26
1

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?

  • 0
    @scaaahu: I agree with you. The full transformation semigroup is a monoid. Harju's is silence about this.2012-03-20