%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-4/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thrm}{Theorem}[section]
\newtheorem{lmma}{Lemma}[section]

\title{On Finitely Generated Idempotent Semigroups}
\author{Tom Brown and Earl Lazerson}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and Earl Lazerson, \emph{On finitely generated idempotent
  semigroups}, Semigroup Forum \textbf{78} (2009), 183--183.}\bigskip\end{center}

\begin{abstract}We give two short proofs of the well-known fact that every finitely generated
idempotent semigroup is finite.
~\\~\\
\noindent Keywords: idempotent semigroup, band, locally finite, finitely generated.
~\\~\\
\noindent AMS Classification: 20M05
\end{abstract}


\section{Introduction}

There are at least 6 published proofs (see \cite{brown1964,green+rees1952,lallement1979,
lazerson1961,mclean1954,lothaire1997}) of the fact that every idempotent semigroup
(i.e. semigroup in which $x^2 = x$ for every element $x$) is locally finite (every
finitely generated idempotent semigroup is finite). Usually this fact is proved as
a corollary to more general results. In this note we give two additional proofs
which are shorter than previous proofs and which are, we believe, of independent
interest. The first proof, adapted from \cite{lazerson1961}, gives some standard
structure theory along the way. (In particular, it shows that every idempotent
semigroup is a semilattice of rectangular idempotent semigroups.) The second
proof is short and self-contained, and shows directly that idempotent semigroups
are locally finite.

\section{The First Proof}

\begin{lmma} Let $S$ be an idempotent semigroup, and let $\mathcal{T}$ denote the
collection of all non-empty subsets $T$ of $S$ such that $xyz = xz$ for all $x,y,
z \in T$. Partially order $\mathcal{T}$ by inclusion. Then every $T\in\mathcal{T}$
is contained in a maximal element $T'$ of $\mathcal{T}$. Furthermore, each maximal
element of $\mathcal{T}$ is a subsemigroup of $S$.\label{shostakovich}\end{lmma}
\begin{proof} Given $T$, Zorn's lemma shows that $T'$ exists, and if $x,y\in T'$,
then $T\cup\{xy\}\in\mathcal{T}$, so $xy\in T'$.\end{proof}

\begin{lmma} The set of maximal elements of $\mathcal{T}$ is a partition of $S$.
\label{beethoven}\end{lmma}
\begin{proof} Since $\{x\}$ satisfies $xyz = xz$, $x$ belongs to a maximal element
$T\in\mathcal{T}$, by Lemma \ref{shostakovich}, so $\bigcup\mathcal{T} = S$. To show
that the maximal elements of $\mathcal{T}$ are pairwise disjoint, suppose that $T_1,
T_2$ are maximal with $e\in T_1\cap T_2$. Then for all $x,y\in T_1\cup T_2$, as a
first step
\[ e(xy)e = (eye)(xy)(exe) = e(yexyex)e = e(yex)e = (eye)(exe) = ee = e \]
If $x,y,z\in T_1\cup T_2$, then using $e(xy)e = e$,
\[ xyz = (xex)(yeey)(zez) = x(exye)(eyze)z = xeez = x(exze)z = (xex)(zez) = xz \]
Hence by the maximality of $T_1,T_2$ we have $T_1 = T_1\cup T_2 = T_2$.\end{proof}

Let the equivalence relation on $S$ corresponding to the partition in Lemma
\ref{beethoven} be denoted by $\sim$, and let the equivalence class containing
an element $x$ of $S$ be denoted by $T_x$. Thus for $x,y\in S$, $T_x = T_y
\Leftrightarrow x\sim y \Leftrightarrow $ [both $x$ and $y$ belong to some maximal
element of $\mathcal{T}$].

\begin{lmma} For all $x,y\in S$, $T_x = T_y \Leftrightarrow $ [$xyx = x$ and $yxy = y$].
\label{korngold}\end{lmma}
\begin{proof} One direction is trivial. Suppose now that $xyx = x$ and $yxy = y$.
Then the set $\{x,y\}$ satisfies the identity $xyz = xz$, so by Lemma \ref{shostakovich}
can be extended to a maximal element of $\mathcal{T}$.\end{proof}

Lemma \ref{korngold} shows that $T_x = T_y \Leftrightarrow SxS\cup\{x\} = SyS\cup\{y\}$,
so that the sets $T_x$ are the $J$-classes of $S$.

\begin{lmma} For all $x,y\in S$, $xy\sim yx$. Furthermore, $\sim$ is a congruence on
$S$, that is, for all $x,y,x',y'\in S$, if $x\sim x'$ and $y\sim y'$ then $xy\sim x'y'$.
\label{yannick}\end{lmma}
\begin{proof} Clearly $(xy)(yx)(xy) = xy$ and $(yx)(xy)(yx) = yx$, hence by Lemma
\ref{korngold}, $xy\sim yx$. Now assume that $x\sim x'$ and $y\sim y'$. Then
\[ xy = (xx'x)(yy'y)\sim(x'xx')(y'yy') = x'y' \]
\end{proof}

Let $Q(S) = S/\sim$. The elements of $Q(S)$ are the sets $T_x$, $x\in S$, and the
multiplication is defined by $T_xT_y = T_{xy}$. In the standard terminology, Lemma
\ref{korngold} shows that each $T_x$ is a rectangular idempotent semigroup $(xyx =
x$ for all $x,y$), and Lemma \ref{yannick} shows that $Q(S)$ is a semilattice
(commutative idempotent subgroup). (As remarked by McLean \cite{mclean1954}, every
rectangular idempotent semigroup is ``anticommutative'' in the sense that $xy = yx
\Rightarrow x = xyx = yxy = y$. Conversely, every anticommutative idempotent semigroup
is rectangular: $x\cdot xyx = xyx\cdot x \Rightarrow x = xyx$.)

Let $S$ be generated by $g_1,g_2,\ldots,g_n$, and let $x \in S$. The \emph{content} of
$x$ is the set $C(x) = \{ g_i : x = ag_ib\text{ for some } a,b\in S\}$. The \emph{reduced
form} of $x$ is $\pi(x) = g_{i_1}g_{i_2}\cdots g_{i_k}$, where $C(x) = \{ g_{i_1},
g_{i_2}, \cdots, g_{i_k} \}$ and $i_1 < i_2 < \cdots < i_k$. (Of course these definitions
depend on the set of generators.)

\begin{lmma} For all $x\in S$, $x\sim\pi(x)$. \label{ludwig}\end{lmma}
\begin{proof} This follows immediately from \ref{yannick}.\end{proof}

According to Lemma \ref{ludwig}, $Q(S)$ is isomorphic to a subsemigroup of the semigroup
of all non-empty subsets of $\{1,2,\ldots,n\}$, with set union as the operation.

\begin{thrm} For all $n\geq 1$, every idempotent semigroup $S$ on $n$ generators
is finite.\end{thrm}
\begin{proof} Let $S$ have generators $g_1,g_2,\ldots,g_n$. The proof has just two
ingredients. The first is the fact that if $C(x) = C(z) = \{g_1,g_2,\ldots,g_n\}$,
then for any $y\in S$, $C(x) = C(yz) = C(z)$, so that $x,yz,z\in T_x$ and $xyz
= x(yz)z = xz$. The second ingredient is a natural definition of the \emph{length}
of an element of $S$. The length of an element of $S$ is defined below, and the
proof of the theorem is then identical with the proof below.\end{proof}

\section{The Second Proof}

Let $S$ be an idempotent semigroup generated by $g_1,g_2,\ldots,g_n$. Let us call
an element $x\in S$ \emph{complete} if for each $i$, $1\leq i\leq k$, there are
elements $a_i$ and $b_i$ of $S$ such that $x = a_ig_ib_i$. For example, $x = g_1
g_2\cdots g_n$ is complete. For each $x\in S$, the \emph{length} of $x$, denoted
by $|x|$, is the minimum $k$ such that $x = x_1x_2\cdots x_k$, where $x_i\in\{g_1,
g_2,\ldots,g_n\}$, $1\leq i\leq k$. Note that $|x| \geq 1$ for all $x\in S$.

\begin{lmma} If $w\in S$ and $w$ is complete, then $w = wxw$ for all $x\in S$.
\label{dmajor}\end{lmma}
\begin{proof} Let $w\in S$ be complete. We show that $w = wxw$ for all $x\in S$
by induction on $|x|$. If $|x| = 1$ then $w = axb$ since $w$ is complete, and
\begin{align*}
w &= (ax)b = (axax)b \\
&= a(xaxb) = a(xaxbxaxb) \\
&= (axax)bxaxb = (ax)bxaxb \\
&= (axb)x(axb) = wxw
\end{align*}
For the induction step, let $|x| > 1$ and assume that $w = wyw$ for all $y\in S$
with $|y| < |x|$. Let $x = yz$, where $|y| < |x|$ and $|z| < |x|$. Then $w = wyw$
and $w = wzw$, so
\begin{align*}
w &= ww = (wzw)wyw) = wzwyw \\
&= w(zwy)w = w(zwyzwy)w \\
&= (wzw)yz(wyw) = wyzw = wxw
\end{align*}
\end{proof}

\begin{lmma} If $x,y,z\in S_n$, and $x,z$ are complete, then $xyz = xz$.
\label{concerto}\end{lmma}
\begin{proof} Using Lemma \ref{dmajor}, $xyz = xy(zxz) = (xyzx)z = xz$.\end{proof}

\begin{thrm} For each $n \geq 1$, every idempotent semigroup $S$ with $n$ generators
is finite.\end{thrm}
\begin{proof} We will show by induction on $n$ that for each $n \geq 1$, there is a
finite upper bound $t_n$ for the largest possible length of an element of any
idempotent semigroup with $n$ generators. Clearly $t_1 = 1$ and $t_2 = 3$. Let
$n \geq3$ and assume that $t_{n-1}$ exists. Suppose that some element $w$ of an
idempotent semigroup $S$ with $n$ generators has length $|w| > 2(t_{n-1} + 1)$.
Write $w = xyz$, where $|x| = |z| = t_{n-1} + 1$. By the induction hypothesis,
$x$ and $z$ must be complete, i.e. each of the $n$ generators of $S$ occurs in each
of $x$ and $z$. By Lemma \ref{concerto}, $w = xyz = xz$, so $|w| \leq |x| + |z| =
2(t_{n+1} + 1)$, a contradiction. Hence $t_n$ exists and $t_n \leq 2(t_{n-1} + 1)$.
\end{proof}

% These spaces push the addresses to the bottom of the page, a bit of a hack..
~\\~\\~\\~\\
\begin{minipage}[b]{0.45\linewidth}
Department of Mathematics\\
¶¡ÏãÔ°AV\\
Burnaby, BC, V6G 1G4\\
Canada\\
tbrown@sfu.ca
\end{minipage}
\begin{minipage}[b]{0.45\linewidth}
Department of Mathematics\\
Southern Illinois University\\
Edwardsville, IL 62026\\
USA\\
elazerson@sbcglobal.net
\end{minipage}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}