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

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.

• What is the question? You've given the definition of $\alpha R\beta$; then you said that you claim that if $\alpha R\beta$, then $\alpha T^1_X = \beta T^1_X$. Then you say "Hence the result". what result? – Arturo Magidin Mar 19 '12 at 16:58
• @ArturoMagidin: Initially, the definition of the relation $R$ is given by for all $x$,$y$ in a semigroup $S$, $xRy$ if and only if $S^1x=S^1y$. So $\alpha R\beta$ iff $\alpha T_{X}^1=\beta T_{X}^1$ – Hassan Muhammad Mar 19 '12 at 17:43
• You have it backwards, according to the notes: $x\mathcal{R}y$ iff $xS^1=yS^1$. So are you trying to prove the displayed statement in your question? If so, your professor is quite right: you’ve shown only that such $\gamma,\gamma'$ can be found in $T_X^1$, not necessarily in $T_X$. However, there’s an easy fix: exactly how is $T_X^1$ related to $T_X$? – Brian M. Scott Mar 19 '12 at 17:49
• @Hassan: Then please make your post self-contained; give the definition, then make it clear what it is you are trying to prove. As written, the post makes little sense. Presumably, if I were to download a large PDF file with notes and go to Chapter 5 I might make sense of it, but that's asking a little too much of your readers, don't you think? – Arturo Magidin Mar 19 '12 at 18:09
• Of course it is, for the reason that I gave in my previous comment: it includes the identity transformation, which is the semigroup identity. – Brian M. Scott Mar 20 '12 at 5:14

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

• I can't see what you could be misunderstanding. The only think I could think of was that perhaps composition is meant to be from left to right rather than right to left, but that still doesn't help, because your example would still work, but with $\alpha T_X^1 = \{\alpha, \delta\}$. – Tara B Mar 19 '12 at 20:42
• *'thing' I could think of... – Tara B Mar 19 '12 at 21:45
• @Tara: Yes, I thought of that too, but the functions in the notes definitely act on the left. – Brian M. Scott Mar 20 '12 at 2:04
• @BrianM.Scott: $T_{X}$ is a monoid in your example because $\beta$ is the identity. If I understand you the claim is not true in general, but why does the author claim it? He is trying to prove another claim $\alpha R\beta$ iff $\alpha(X)=\beta(X)$. If the first claim is wrong then I do not think the second will be true. – Hassan Muhammad Mar 20 '12 at 5:35
• He simply made a mistake: the claim is never true when $|X|>1$. However, as Tara points out in her answer, the proposition that he wants to prove is true, even though his proof is faulty. You should try to find a correct proof; it really isn’t terribly hard. – Brian M. Scott Mar 20 '12 at 5:55

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

• By the way, I should perhaps point out, just in case it confuses anyone, that this is all for $T_X$ acting on the left. In many papers and books (e.g. Howie), $T_X$ is taken to act on the right, in which case we get $\alpha \cal{L} \beta$ if and only if $(X)\alpha = (X)\beta$. – Tara B Mar 19 '12 at 21:38
• The proposition is not stated correctly, how can we give a correct proof? We have to contact the author for explanation of what he means by that. – Hassan Muhammad Mar 20 '12 at 5:41
• @Hassan: The Proposition that Tara states is true, even though the proof in Harju’s notes is wrong. It’s also not terribly hard to prove. – Brian M. Scott Mar 20 '12 at 5:56
• @BrianM.Scott: Assuming I can proof the proposition, I can not use his(Harju's) claim $\alpha \mathcal{R} \beta$ iff there exist $\gamma,\gamma' \in T_{X}:\alpha\gamma=\alpha\gamma'$, since you have already found a counter example that disprove the claim. – Hassan Muhammad Mar 20 '12 at 6:17
• @Hassan: Nothing. And I have no idea why you think that this is at all relevant. Of course the statement above Lemma 5.1 was derived from the definition; so what? It happens to be a useful way to look at the relation $\mathcal{R}$ when trying to prove correctly the proposition that Tara stated in her answer. – Brian M. Scott Mar 20 '12 at 6:58

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?

• I don't think it's misleading. Some semigroups are monoids; some are even groups. So calling it the full transformation semigroup doesn't carry any implication that it's not a monoid. However, it's not unheard of for it to be called the full transformation monoid. – Tara B Mar 20 '12 at 12:07
• Well, calling any subsemigroup of $T_X$ a semigroup is fine because we don't know if it's a monoid. But $T_X$ is always a monoid. That's why I think it's misleading. – scaaahu Mar 20 '12 at 12:27
• If I call $S_n$ a symmetric semigroup, it doesn't carry any implication it's not a group. Would it sound strange, though? – scaaahu Mar 20 '12 at 12:43
• I do agree that we might as well name things 'monoid' rather than 'semigroup' if they happen to be monoids. For example I prefer 'bicyclic monoid' rather than 'bicyclic semigroup'. But usually if you read that something is a semigroup, you don't (and shouldn't) assume it doesn't have an identity. So I think 'misleading' is a bit strong. – Tara B Mar 20 '12 at 12:43
• @Tara, okay, misleading might be too strong a word. It's at least strange to me. I just want to say I saw $T_X^1$ in Harju's notes and in this question all over the place. That's why I brought up this issue. – scaaahu Mar 20 '12 at 12:51