Green's equivalences on the bicyclic semigroup.

Question

This is Exercise 2.1.2 of Howie's "Fundamentals of Semigroup Theory".

Definition 1: Consider $B=\Bbb N^0\times \Bbb N^0$ under $$(m, n)(p,q)=(m-n+\max(n, p), q-p+max(n, p))$$. This is the bicyclic semigroup $B$.

The Question:

Show that

a) $(m, n)\mathcal{R} (p, q)$ if and only if $m=p$.

b) $(m, n)\mathcal{L} (p, q)$ if and only if $n=q$.

c) $\mathcal D= \mathcal J= B\times B$.

My Attempt:

a) Suppose $(m, n)\mathcal R (p, q)$. Then there exist $(x, y), (u, v)\in B$ such that $(m, n)(x,y)=(p,q)$ & $(p, q)(u, v)=(m, n)$. Thus $$p=m-n+\max(n, x)\tag{1}$$ & $$q=y-x+\max(n, x)\tag{2}$$ and $$m=p-q+\max(q, u)\tag{3}$$ & $$n=v-u+\max(q, u).\tag{4}$$

Since there are four equations and four unknowns, I suppose I could solve $(1)$ to $(4)$ for $x,y,u,v$ in terms of $m,n,p,q$, but I don't suppose this'll get me far.

By $(3)$, $$m=\begin{cases} p &: q=\max(q, u) \\ p-q+u &: u=\max(q, u). \end{cases}$$ If $u=\max(q, u)$, then $n=v$ by $(4)$.

That's all I have there.

b) The solution to this should be dual to (a).

c) I'm stuck.

Please help :)

Answer 1

I'll use the more intuitive (for me) description of the bicyclic subgroup as the set of all strings $a^m b^n$, under the operation of composition followed by repeated annihilation of any occurrence of $ba$. Thus:

• (a) Given a string $a^m b^n$ , right-composition lets us add as many $a$s as we want after killing all the $b$s, and then add $b$s back, but we can't remove any of the original $a$s. So $a^m b^n B = \{a^k b^\ell | k \geq m, \ell \in \mathbb{N}_0\}$. Therefore, $a^m b^n B = a^p b^q B$ iff $m = p$.
• (b) Symmetrical.
• (c) $B a^m b^n B = B (a^m b^n B) = B \{a^k b^\ell | k \geq m, \ell \in \mathbb{N}_0\}$. By left-composing $a^k b^\ell$ with a string of $b$s, we can kill as many of the $a$s as we want, so $B a^m b^n B = B$. This means that every element $x \in B$ has the same $BxB$, so $J$ is the everything-to-everything relation $B \times B$. $D$ is defined as $x D y$ iff $(\exists r) x L r \wedge r R y$. In this case, if $x = a^m b^n$ and $y = a^p b^q$, then by our previous results, take $r = a^p b^n$; this shows that $D$ is also everything-to-everything.