% Article template for Mathematics Magazine
% Revised 7/2002 Thanks for Greg St. George
\documentclass[12pt]{article}
\renewcommand{\baselinestretch}{1.2}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\usepackage{amsfonts}
\usepackage{xy} \xyoption{all}
%\usepackage{verbatim}
\usepackage[dvips]{graphics}
%\usepackage{amssymb}
%\usepackage{latexsym}
%\usepackage{amscd}
%\usepackage[mathscr]{euscript}
\def\et{\raisebox{.3em}{$\sim$}}
\def\V{W}
\def\qed{{\quad \vrule height 5pt width 5pt depth 0pt}}
\def\0{\textbf{0}}
\def\al{\alpha}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\newcommand{\uloopr}[1]{\ar@'{@+{[0,0]+(-4,5)}@+{[0,0]+(0,10)}@+{[0,0]
+(4,5)}}^{#1}}
\newcommand{\uloopd}[1]{\ar@'{@+{[0,0]+(5,4)}@+{[0,0]+(10,0)}@+{[0,0]+
(5,-4)}}^{#1}}
\newcommand{\dloopr}[1]{\ar@'{@+{[0,0]+(-4,-5)}@+{[0,0]+(0,-10)}@+{[0,
0]+(4,-5)}}_{#1}}
\newcommand{\dloopd}[1]{\ar@'{@+{[0,0]+(-5,4)}@+{[0,0]+(-10,0)}@+{[0,0
]+(-5,-4)}}_{#1}}
\newcommand{\luloop}[1]{\ar@'{@+{[0,0]+(-8,2)}@+{[0,0]+(-10,10)}@+{[0,
0]+(2,2)}}^{#1}}
\begin{document}
\pagestyle{myheadings} \thispagestyle{empty}
\begin{center}
\Large
% TITLE
Semigroups, groups, and {\it The Mad Veterinarian}
\end{center}
\normalsize
This handout / homework assignment consists of a slightly modified version of the first five sections of the nine section article ``The Graph Menagerie: Abstract Algebra and the Mad Veterinarian", by Gene Abrams and Jessica K. Sklar.\footnote{\, Gene Abrams, University of Colorado at Colorado Springs, abrams@math.uccs.edu; \\
Jessica K. Sklar, Pacific Lutheran University, sklarjk@plu.edu} The entire article appears in {\it Mathematics Magazine}, \textbf{83}(3), June 2010, pp. 168 - 179.
\bigskip
Jessica owns three adorable cats: Boo, Kodiak and Yoshi.
Yoshi, unfortunately, has a bad habit: He likes to damage
Jessica's carpet. Sometimes Jessica wishes she had a machine
that would magically change Yoshi into a tidier pet ... a
goldfish, perhaps. Of course, a goldfish is much smaller than
a cat, so perhaps Yoshi could instead be turned into two
goldfish. Or maybe two goldfish and a turtle? But goldfish
and turtles aren't too cuddly; Jessica might regret the
change, so she would want the machine to be able to turn two
goldfish and a turtle back into a cat.
In the parlance of recreational mathematics, Jessica sometimes
wishes she were a {\it Mad Veterinarian}. Mad Vet scenarios were originally presented by Harris \cite{B}, who posed questions as to which collections of animals can be transformed by Mad Vet machines into other collections. Recently, such scenarios have been used as the basis of various problem solving and Math Circle activities; see, for instance, \cite{Z}. In this article we take a different approach, using Mad Vet scenarios to explore the concepts of groups, semigroups, and directed graphs.
We have two main goals in analyzing Mad Vet scenarios. Corresponding to any Mad Vet scenario there is a naturally defined semigroup, which may or may not be a group. Our first main goal is to help readers gain some intuition about when a given semigroup is actually a group; to this end, we provide a number of not-so-run-of-the-mill examples involving these algebraic structures.
Our second main goal is to illustrate a practice common in mathematics: namely, answering a question in one area by recasting it in another area, answering the recast question there, and then using that result to answer the original question. There are numerous examples of such powerful cross-disciplinary pollination, including Euler's solution to the classic K\"{o}nigsberg Bridges Problem; see, for instance, Chapter 1 in Biggs et al. \cite{Biggs}. We provide a beautiful example of this technique, posing an abstract algebraic question and answering it using graph theory.
Along the way, we provide numerous examples and specific computations. We also present some follow-up questions and information which could be used to supplement the material in an abstract algebra course. We assume that the reader is familiar with first-semester abstract algebraic concepts such as groups and equivalence relations. A good source for these topics is Fraleigh \cite{F}.
\section{Mad Vet scenarios}\label{SemigroupSection}
A {\it Mad Vet scenario} posits a Mad Veterinarian in possession of
a finite number of transmogrifying machines, where
\begin{enumerate}
\item[1.] Each machine
transmogrifies a single animal of a given species into a finite nonempty collection of animals from any number of species;
\item[2.] Each machine can
also operate in reverse; and
\item[3.] There is a one-to-one correspondence between the species with which the Mad Vet works and the transmogrifying machines; moreover, each species' corresponding machine takes
as its input exactly one animal of that species.
\end{enumerate}
These three requirements do not explicitly appear in the puzzles posed by Harris \cite{B}, but they are certainly implicit there.
Let's consider an example.
\bigskip
\noindent
\textbf{Scenario \#1.} Suppose a Mad Veterinarian has three machines with the following properties.
\medskip
Machine 1 turns one ant into one beaver;
Machine 2 turns one beaver into
one ant, one beaver and one cougar;
Machine 3 turns one cougar into one ant
and one beaver.
\medskip
Starting with one ant, the Mad Vet could produce infinitely many different collections of animals. For example, she could use Machine 1 to turn the ant into a beaver, and then use Machine 2 repeatedly to continually increase the number ants and cougars in her collection. Alternatively, she could use Machine 1 followed by Machine 2, and put the resulting cougar into Machine 3, yielding a collection of two ants and two beavers. Then using Machine 1 twice in reverse, she'd obtain a collection consisting of exactly four ants. \qed
\bigskip
We now mathematize these Mad Vet scenarios. Given a scenario involving $n$ distinct species of animals, we let $A_i$ be the species of animal taken as input (in the forward direction) by Machine $i$, and denote by $d_{i,j}$ the number of animals of species $A_j$ which are produced by Machine $i$. For example, in Scenario \#1, $A_1$ = Ant, $A_2$~=~Beaver and $A_3$ = Cougar, and we have, for instance, $d_{1,1} = 0$, $d_{1,2}=1,$ and $d_{1,3}=0$.
Writing $\N$ for the set $\{0,1,2,\ldots\}$ and {\bf 0} for the trivial vector $(0,0,\ldots,0)$ of length $n$, we define a {\it menagerie} to be an element of the set $$S = \N ^n \setminus \{\0\}.$$ There is a natural bijective correspondence between menageries and nonempty collections of animals from species $A_1,A_2,\ldots,A_n$. For instance, in Scenario \#1
a collection of two beavers and five cougars would
correspond to $(0,2,5)$ in $S$.
\section{Mad Vet graphs}\label{MVgraphs}
We give here a brief introduction to some standard graph theory concepts.
For a more thorough examination of the topic, see, for example, West \cite{West} or Wilson and Watkins \cite{Wilson}. (Note that graph theory definitions vary widely from text to text; for instance, what we will call a {\it path} is what West calls a {\it walk} \cite{West}.)
A {\it directed graph} consists of a set $V$ of {\it vertices} and
a set $E$ of {\it edges}; the graph is {\it finite} if both $V$ and $E$ are finite. Each edge
$e$ in $E$ has an {\it initial vertex}, $i(e)$, and {\it terminal vertex},
$t(e)$, and is represented in the graph by an arrow pointing from $i(e)$ to $t(e)$. Loops (that is, edges $e$ for which $i(e)=t(e)$) are allowed, as are multiple
edges (that is, edges that have a common initial vertex and a common terminal vertex). A vertex is a
{\it sink}\, if it is not the initial vertex of any edge.
Given any Mad Vet scenario, its corresponding
{\it Mad Vet graph} is the directed graph
with
$V = \{A_1,A_2,\ldots,A_n\}$, and having, for each $A_i, A_j$ in $V$,
exactly $d_{i,j}$ edges with initial vertex $A_i$ and terminal vertex $A_j$. Note that any Mad Vet graph is sink-free, due to the third defining feature of a Mad Vet scenario.
\bigskip
\noindent {\bf Example.} Scenario \#1 has the following Mad Vet graph.
$$\quad {
\def\labelstyle{\displaystyle}
\xymatrix{ {} & A_1 \ar[rd] & & {} \\ A_3 \ar[ru]
\ar@/^{-15pt}/ [rr]& & A_2 \dloopr{} \ar[ll] \ar@/^{-10pt}/
[lu] & \qed}} $$
\bigskip
%We return to directed graphs in Section \ref{MVGT}.
\section{Menagerie equivalence classes}
Now we come to the key idea. In the context of a Mad Vet scenario, there is a relationship between various menageries. Clearly, a set consisting of two ants and a cougar is different from a set consisting of an ant and three beavers. But if the vet has machines that can be used to replace the first collection of animals with the second (and vice versa), it would make sense to somehow identify the menageries $(2,0,1)$ and $(1,3,0)$ in $S$. We have here a naturally arising relation $\sim$ on $S$, defined formally as follows. Given $a=(a_1,a_2,\ldots, a_n)$ and $b=(b_1,b_2,\ldots, b_n)$ in $S$, we say that $a$ is {\it related to} $b$, and write $a\sim b$, if there is a sequence of Mad Vet machines that will transmogrify the collection of animals associated with menagerie $a$ into the collection of animals associated with menagerie $b$. Using the three properties of a Mad Vet scenario, it is straightforward to show that $\sim$ is an equivalence relation on $S$.
The equivalence class of $a$ in $S$ under $\sim$ is $$[a]=\{b\in S\,:\, b\sim a\};$$ such equivalence classes partition $S$.
We now focus on the set $$\V=\{[a]\,:\, a\in S\}$$ of equivalence classes of $S$ under $\sim$. Though the elements of $\V$ are actually sets themselves, we will work with them primarily as individual elements of the set $\V$.
\bigskip
\noindent {\bf Example.} Suppose that our Mad Vet of Scenario \#1 starts with the menagerie $(1,0,0)$, that is, a collection consisting of just one ant. Then $(1,0,0) \sim (0,1,0)$ (using Machine 1); in fact, our previous discussion shows that
$$(1,0,0) \sim (0,1,0) \sim (1,1,1) \sim (2,2,0) \sim (4,0,0).$$
Using equivalence class notation, we've shown
$$[(1,0,0)]=[(0,1,0)]=[(1,1,1)]=[(2,2,0)]=[(4,0,0)],$$
that is, that these five expressions all represent same element of $\V$.
Now, let $(a,b,c)$ be any menagerie in this Mad Vet scenario. We claim that $(a,b,c)$ is equivalent to one of the menageries $(1,0,0)$, $(2,0,0)$, or $(3,0,0)$. If $c>0$, then using Machine 3 $c$ times we see that $(a,b,c)\sim (a+c,b+c,0)$; then if $b+c >0$, we can use Machine 1 in reverse $b+c$ times to show that $(a+c,b+c,0) \sim (a+b+2c,0,0)$. By the transitivity of $\sim$, we conclude that $(a,b,c) \sim (i,0,0)$ for some positive integer $i$ (namely, $i=a+b+2c$). We noted above that $(1,0,0) \sim (4,0,0)$, which implies that $(2,0,0) \sim (5,0,0)$, $(3,0,0) \sim (6,0,0)$, and, more generally, that $(j,0,0)\sim (i,0,0)$ for any positive integers $i$ and $j$ that are congruent modulo 3.
Thus, the only elements of $\V$ are $$[(1,0,0)], [(2,0,0)], \mbox{ and }[(3,0,0)].$$
We now rule out any redundancy among these three elements of $\V$. Given a menagerie $m=(a,b,c)$, define the sum $s_m=a+b+2c$. If we apply Machine 1 to $m$, we obtain menagerie $x=(a-1,b+1,c)$; if we apply Machine 2 to $m$ we obtain $y=(a+1,b,c+1)$; finally, if we apply Machine 3 to $m$ we obtain $z=(a+c,b+c,0)$. Since
$$s_x=(a-1)+(b+1)+2c = s_m=(a+c)+(b+c)=s_y$$ and $$s_z=(a+1)+b+2(c+1)=s_m+3,$$ we have that if menageries $m$ and $n$ are related under $\sim$ then $s_m$ and $s_n$ are congruent modulo 3. Since $s_{(1,0,0)}=1$, $s_{(2,0,0)}=2$ and $s_{(3,0,0)}=3$, the equivalence classes of menageries $(1,0,0)$, $(2,0,0)$ and $(3,0,0)$ under $\sim$ are all distinct. Hence, for this Mad Vet scenario, $\V$ is the 3-element set
$$\{[(1,0,0)],[(2,0,0)],[(3,0,0)]\}. \qed$$
\bigskip
\section{Mad Vet semigroups}\label{newsemigroupsection}
We can gain some understanding of a Mad Vet scenario by
studying its collection, $\V$, of menagerie equivalence classes simply as a set. But we can learn even more if we exploit a natural operation which combines menageries. We first remind the reader of some definitions.
Let $S$ be any set, and let $*$ be a binary operation on $S$.
Recall that $(S,*)$ is a {\it semigroup} if $*$ is associative; a semigroup $(S,*)$ is a {\it monoid} if it contains an identity element for $*$; and a monoid is a {\it group} if each of its elements has an inverse under $*$.
Three important types of semigroups arise in the context of Mad Vet scenarios. First, given a scenario, we have its set $S$ of menageries, equipped with the usual addition of vectors. (Such addition is an acceptable semigroup operation on $S$ since it is associative and since the sum of two nonzero vectors is again nonzero.) Next, we have the scenario's {\it Mad Vet semigroup}, which we discuss in this section. Finally, we introduce {\it graph semigroups} in Section \ref{MVGTexp}.
To create the Mad Vet semigroup of a Mad Vet scenario, we define addition on the scenario's set $\V$ of equivalence classes of menageries by setting
$$[x]+[y]=[x+y],$$ where addition on the righthand side of the equation takes place in $S$. Addition on $\V$ can be understood as follows. Suppose a Mad Vet has a collection of animals in her lab corresponding to menagerie $x$, and is given a new collection of animals corresponding to menagerie $y$. Then the sum $[x] + [y]$ in $\V$ is the equivalence class of the menagerie corresponding to the union of the animals in the two collections.
Since the elements of $\V$ are equivalence classes,
we must make sure that our addition on $\V$ is well defined.
But this is straightforward to see, by identifying our menageries with their associated collections of animals: If some sequence of machines transforms menagerie $x$ into menagerie $x'$, and some sequence transforms menagerie $y$ into menagerie $y'$, then these machines, used in tandem, transform menagerie $x + y$ into menagerie $x' + y'$.
Associativity of $+$ on $\V$ is inherited from the
associativity of $+$ on $S$. Thus, $(\V, +)$ is a semigroup, called the {\it Mad Vet semigroup} of its corresponding Mad Vet scenario. Since addition is clearly commutative on $S$, every Mad Vet semigroup $(\V,+)$ is commutative.
\bigskip
\noindent {\bf Example.}
We revisit Scenario \#1 and examine its Mad Vet semigroup $(\V,+)$.
We showed previously that in this case $\V$ is the 3-element set $$\V=\{[(1,0,0)], [(2,0,0)],[(3,0,0)]\}.$$ Using the operation $+$ in $\V$, we get, for instance,
$$[(1,0,0)] + [(1,0,0)] = [(1+1,0,0)]=[(2,0,0)],$$
as we'd expect. But perhaps it's a bit surprising that
$$[(1,0,0)] + [(3,0,0)] = [(4,0,0)] = [(1,0,0)].$$
In other words, $[(3,0,0)]$ behaves like an identity element with respect to the element $[(1,0,0)]$ in $\V$. In fact, $[(i,0,0)] + [(3,0,0)] = [(i,0,0)]$ for any $1\leq i \leq 3$.
So for this Mad Vet scenario the Mad Vet semigroup $(\V,+)$ is a monoid, with identity $[(3,0,0)]$. Further, since
$$[(1,0,0)]+[(2,0,0)] = [(3,0,0)]$$ in $\V$, every element in $(\V,+)$ has an inverse. Therefore, $(\V,+)$ is in fact a group; since its order is 3, it must be isomorphic to the group $\Z_3$. $\qed$
\bigskip
\section{Not all Mad Vet semigroups are groups}\label{notagrp}
Perhaps it is not surprising that the Mad Vet semigroup of Scenario \#1 is a group, in light of the explicit description of its elements. In many Mad Vet scenarios, $(\V,+)$ is indeed a group; however, we will later see a Mad Vet semigroup that is not even a monoid. Notably, given any Mad Vet semigroup $\V$, the ``obvious" choice, $[\0]$, for an identity element of $\V$ is not even contained in $\V$, since $\0$ is not in $S$.
\bigskip
\noindent {\bf Scenario \#2.} \ Suppose the same Mad Vet has
replaced two of her machines with new machines.
\medskip
Machine 1 still turns one ant into one beaver;
Machine 2 now turns one beaver into one ant
and one cougar;
Machine 3 now turns one cougar
into two cougars.
\medskip
In this situation $\V$ is a monoid, but not a group. First, we claim that $$\V = \{[(i,0,0)]\,:\, i\in \Z^+\} \cup \{[(0,0,1)]\},$$ where $\Z^+$ denotes the set of positive integers. Indeed, let $(a,b,c)$ be a menagerie for this scenario. If $a=b=0$ (that is, there are only cougars in the menagerie) then $c-1$ applications of Machine 3 yields that $(0,0,c) \sim (0,0,1)$. Else, suppose that at least one of $a$ or $b$ is nonzero. Since $(a,b,c)\sim (a+b,0,c)$ (using Machine 1 in reverse $b$ times), we may assume that the menagerie contains at least one ant and no beavers. If $c=0$, then we are done. If $c\neq 0$, then we can apply Machine 3 in the appropriate direction $|a-c|$ times, obtaining a menagerie that contains $a$ ants and $a$ cougars; thus, $(a,0,c) \sim (a,0,a)$. Then applying Machine 2 in reverse $a$ times yields $(a,0,a)\sim (0,a,0)$, which is equivalent to $(a,0,0)$ (using Machine 1).
Hence, $\V$ consists of the indicated elements. We may now use arguments similar to the argument utilized in studying Scenario \#1 to show that these elements are all distinct in $W$. This establishes our claim.
The same sorts of computations as before show that $[(0,0,1)]$ is an identity element for this Mad Vet
semigroup, and hence $\V$ in this case is a monoid.
But $\V$ is not a group, because, for instance, there is no
element $[x]$ in $\V$ for which $[(1,0,0)] + [x] = [(0,0,1)]$. \qed
\bigskip
Given a Mad Vet scenario, we can pose a variety of questions regarding the structure of its Mad Vet semigroup. For instance, is its semigroup finite or infinite? Is it a monoid? If it is a monoid, is it a group? Note that if it is a group, then that group is necessarily abelian (since all Mad Vet semigroups are commutative)---but is it necessarily cyclic?
To give some sense of just how diverse Mad Vet semigroups can be, we provide below five additional Mad Vet scenarios (Scenarios \#3-7) which include, in some order, a scenario for which (1) $\V$ is an infinite group; (2) $\V$ is a finite noncyclic group; (3) $\V$ is a finite nonmonoid; (4) $\V$ is a finite cyclic group, not isomorphic to $\Z_3$; and
(5) $\V$ is an infinite nonmonoid.
In fact, these five different structures even arise in scenarios where the Mad Vet has just three species in her lab.
Our readers are encouraged to try their hands at matching the above-described scenarios with those of Scenarios \#3-7. Teachers can also find a sample Mad Vet homework assignment, appropriate for a first-semester abstract algebra course, at the \textit{Magazine} website. Descriptions of the semigroups arising in the following five Mad Vet scenarios are provided at the end of the article, so that
readers can check their work.
\bigskip
\noindent{\bf Scenario \#3.}
%$\Z_2 \times Z_2$ example.
Machine 1 turns one ant into one beaver and one cougar;
Machine 2 turns one beaver into one ant
and one cougar;
Machine 3 turns one cougar
into one ant and one beaver.
\bigskip
\noindent{\bf Scenario \#4.}
%Finite NON-monoid example.
Machine 1 turns one ant into two ants;
Machine 2 turns one beaver into two beavers;
Machine 3 turns one cougar
two cougars.
\bigskip
\noindent{\bf Scenario \#5.}
%$\Z$ example
Machine 1 turns one ant into one beaver and one cougar;
Machine 2 turns one beaver into one ant
and one beaver;
Machine 3 turns one cougar
into one ant and one cougar.
\bigskip
\noindent{\bf Scenario \#6.}
%positive integer semigroup example.
Machine 1 turns one ant into one beaver;
Machine 2 turns one beaver into one cougar;
Machine 3 turns one cougar
into one cougar.
\bigskip
\noindent{\bf Scenario \#7.}
%$\Z_4$ example.
Machine 1 turns one ant into one ant, one beaver and one cougar;
Machine 2 turns one beaver into one ant
and one cougar;
Machine 3 turns one cougar
into one ant and one beaver.
\bigskip
\begin{thebibliography}{99}
%\bibitem{AA2} G. Abrams and G. Aranda Pino, Purely
%infinite simple Leavitt path algebras, \textit{J. Pure Appl.
%Algebra} \textbf{207} (2006) 553-563.
%\bibitem{AALP}G. Abrams, P. N. \'{A}nh, A. Louly, and E.Pardo, The classification question for Leavitt path algebras, \textit{Journal of Algebra} \textbf{320(5)} (2008) 1983-2026.
%\bibitem{AGP} P. Ara, K. Goodearl, and E. Pardo, $K_0$ of
% purely infinite simple regular rings, \textit{K-Theory}
%\textbf{26} (2002) 69-100.
%\bibitem{BPRS} T. Bates, D. Pask, I. Raeburn, and W. Szyma\'{n}ski, The C$^*$-algebras of row-finite graphs, \textit{New York J. Math.} \textbf{6} (2000) 307-324.
%\bibitem{MV} Gene Abrams and Jessica K. Sklar, {\it ``The Graph Menagerie" Supplementary Materials}, http://www.plu.edu/\et sklarjk/MadVet .
%\bibitem{AMP} P. Ara, M.A. Moreno, and E. Pardo, Nonstable K-Theory for graph algebras, \textit{Algebra Rep. Th.} \textbf{10}(2) (2007) 157-178.
%\bibitem{Workshop} G. Aranda Pino, F. Perera, and M. Siles Molina (eds.), \textit{Graph algebras: bridging the gap between analysis and algebra}, Universidad de M\'{a}laga Press, 2007.
\bibitem{Biggs} Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, {\it Graph Theory 1736-1936}, Oxford University Press, 1999.
\bibitem{F} John B. Fraleigh, \textit{A First Course in Abstract Algebra (7th ed.)}, Addison Wesley, 2002.
%\bibitem{G} P. A. Grillet, \textit{Commutative Semigroups}, Springer, 2001.
\bibitem{B} Robert S. Harris, \textit{Bob's Mad Veterinarian Puzzles},
http://www.bumblebeagle.org/madvet/index.html .
%\bibitem{Hog} Leslie Hogben (ed.), \textit{Handbook of Linear Algebra}, Chapman \& Hall/CRC, 2006.
%\bibitem{SmithNormalForm} William Stein, \textit{Finitely generated abelian groups}, http://modular.fas.harvard.edu/papers/ant/html/node9.html .
\bibitem{West} Douglas B. West, {\it Introduction to Graph Theory (2nd ed.)}, Prentice-Hall, Inc., 2000.
\bibitem{Wilson} Robin J. Wilson and John J. Watkins, {\it Graphs: An Introductory Approach---A First Course in Discrete Mathematics}, Wiley, 1990.
\bibitem{Z} Joshua Zucker, \textit{Math Teachers' Circle:} {\it An introduction to problem solving},\\
http://www.mathteacherscircle.org/materials/JZproblemsolvingstrategies.pdf~~.
\end{thebibliography}
\end{document}