Prev: All you have to do is c o m p r e h e n d this statement and diagonalisation falls apart
Next: math exercise
From: Ivan Karski on 12 Jun 2010 08:34
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Note: a typset .pdf of this article can be obtained by running the
following through pdflatex.

\documentclass{article}
\mathchardef\ISigma="7106

\begin{document}

Near the beginning of their article ``The Prime Decomposition Theorem
of the Algebraic Theory of Machines'' \cite{krt1}, Krohn et al assert
that ``The semigroup of the machine of the semigroup $S$ is written
$S^{fS}$ and clearly $S^{fS} \cong S$.'' They repeat this assertion
often in the article and seem to rely on it.

Sadly, the assertion seems to be refuted by the simple example $S =
(\{a,b\}, \cdot)$ where $x\cdot y = a$ for all $x,y \in \{a,b\}$.
$S^{fS}$ cannot be isomorphic to $S$ because $S$ has two elements
while $S^{fS}$ has only one.

If they had qualified that $S$ has to be \emph{regular} then the
assertion would be more plausible. But they didn't. ``Regular'' is
defined by two of the same authors in another article later in the
same volume on page~175. It is equivalent to each element being
regular, where an element $a \in S$ is regular if $a \in aSa$, i.e.,
if there is an element $b \in S$ such that $a=aba$.

I want to master their Decomposition Theorem, but such a blatant error
so prominent in the article is discouraging. Can you help?

Here are reminders of some of the definitions, if you're rusty.

A \emph{machine} is any function $f : \ISigma A \rightarrow B$ where
$A$ and $B$ are sets. The \emph{semigroup of the machine} $f$ is $f^S
= \ISigma A / \equiv_f$, where, for $t_1, t_2 \in \ISigma A, t_1
\equiv_f t_2$ iff for all $\alpha, \beta \in (\ISigma A)^1, f(\alpha
t_1 \beta) = f(\alpha t_2 \beta)$.

If $S$ is a semigroup, then the \emph{machine of the semigroup} $S$ is
$S^f : \ISigma S \rightarrow S$ given by $S^f(s_1, \ldots, s_n) = s_1
\cdots s_n$.

If $S_1$ and $S_2$ are semigroups, $S_1$ is \emph{isomorphic} to
$S_2$, written $S_1 \cong S_2$ iff there is an isomorphism $\varphi :
S_1 \rightarrow S_2$.

\begin{thebibliography}{1}

\bibitem{krt1} Kenneth Krohn and John L. Rhodes and Bret R. Tilson.
The Prime Decomposition Theorem of the Algebraic Theory of Machines.
In Michael A. Arbib, editor, \emph{Algebraic Theory of Machines,
Languages, and Semigroups}, chapter 5, Academic Press, 1968.
\end{thebibliography}

\end{document}

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8+ <http://mailcrypt.sourceforge.net/>

iEYEARECAAYFAkwTZ3IACgkQYpflG4Qs+dPBVQCgqEeVBVmuRO28gxoMLACkcb+k
GVgAnimNLPGoQ0D1ONs2snB3iKcrofFv
=6uR/
-----END PGP SIGNATURE-----

 | 
Pages: 1
Prev: All you have to do is c o m p r e h e n d this statement and diagonalisation falls apart
Next: math exercise