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
    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?**2012-03-19
  • 0
    @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$2012-03-19
  • 0
    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$?2012-03-19
  • 0
    @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?2012-03-19
  • 0
    @ArturoMagidin: yes of course you are right.2012-03-19
  • 0
    Thanks for the correction Brian.2012-03-19
  • 0
    Did you think about Brian M. Scott's hint about how $T_X^1$ is related to $T_X$?2012-03-19
  • 0
    @TaraB: Yes, but the only relation I can think of is $T_{X} \subset T_{X}^1$. An element in $T_{X}^1$ need not to be in $T_{X}$2012-03-19
  • 0
    It's true it needn't be. But I guess the point is that you never needed to bother taking $T_X^1$ rather than $T_X$ in the first place.2012-03-19
  • 0
    If $S$ is a semigroup, the only possible element in $S^1\setminus S$ is an identity. If $S$ is already a monoid, then, as @Tara suggests, $S^1=S$. And that’s certainly the case with $T_X$, the full transformation semigroup on $X$: one of those transformations is the identity map.2012-03-20
  • 0
    @BrianM.Scott: But $S$ is not a monoid. It is just a semigroup. I am wondering whether a full transformation semigroup is a monoid in general.2012-03-20
  • 1
    Of course it is, for the reason that I gave in my previous comment: it includes the identity transformation, which is the semigroup identity.2012-03-20
  • 0
    @Brian: Well, I didn't quite suggest that, because I have sometimes seen $S^1$ used to mean $S$ with an identity adjoined, regardless of whether $S$ was already a monoid. (This is a perfectly reasonable construction.) But in the definition of Green's relations, I'm pretty sure $S^1$ is intended to mean just $S$ if $S$ is already a monoid.2012-03-20
  • 0
    @Tara: Example 5.1 would make that pretty clear, I think, even if the definition on p. 7 didn’t make it absolutely explicit.2012-03-20
  • 0
    @BrianM.Scott: I understand that $T_{X}$ and $T_{X}^1$ means the same thing in this context.2012-03-20
  • 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
    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\}$.2012-03-19
  • 0
    *'thing' I could think of...2012-03-19
  • 0
    @Tara: Yes, I thought of that too, but the functions in the notes definitely act on the left.2012-03-20
  • 0
    @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.2012-03-20
  • 0
    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.2012-03-20
  • 0
    The other thing I considered was whether he possibly meant $\alpha S_X = \beta S_X$, because that would work in the direction that currently doesn't work. But it breaks the other direction, so that can't be it. So yes, I believe it's simply a mistake.2012-03-20
  • 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
    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$.2012-03-19
  • 0
    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.2012-03-20
  • 0
    @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.2012-03-20
  • 0
    @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.2012-03-20
  • 0
    @Hassan: That’s correct; you’ll have to find another approach. You might find the statement just above Lemma 5.1 useful: $x\mathcal{R} y\iff \exists r,r'\in S^1$ etc.2012-03-20
  • 0
    @BrianM.Scott: The statement above Lemma 5.1 was derived from the definition. In logic, particularly mathematics, proofs are transitive, if $P\implies Q$ and $Q\implies S$ then $P\implies S$. So, if the first statement implies the second, and the second implies the third, what will make the first not to imply the third?2012-03-20
  • 1
    @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.2012-03-20
  • 0
    @TaraB: My intention is to prove $\alpha\mathcal{R} \beta$ iff there exist $\gamma,gamma'\in T_{X}$: $\alpha\gamma=\beta\gamma'$.2012-03-26
  • 0
    @TaraB: My intention is to prove $\alpha\mathcal{R} \beta$ iff there exist $\gamma,\gamma'\in T_{X}$: $\alpha \gamma=\beta \gamma'$. You go straight and prove the other claim. Do you answer my question? Brian M. Scott point out the error in the claim and you said so. If that is case, can we accept a wrong claim and try to prove another claim with it? If you really wants me to accept your answer edit your answer such that it answers my problem. Thanks.2012-03-26
  • 0
    @HassanMuhammad: No, of course we don't want to accept the wrong claim. What I am saying is that the result Harju was trying to prove is still true, and is easy to prove, and I think it would be a good idea for you to try it. I am certainly not suggesting that you should use the wrong claim in your proof, because then it wouldn't be a proof.2012-03-26
  • 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
    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.2012-03-20
  • 0
    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.2012-03-20
  • 0
    If I call $S_n$ a symmetric semigroup, it doesn't carry any implication it's not a group. Would it sound strange, though?2012-03-20
  • 0
    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.2012-03-20
  • 0
    @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.2012-03-20
  • 0
    @scaaahu: I agree with you. The full transformation semigroup is a monoid. Harju's is silence about this.2012-03-20