\documentclass[11pt]{article}
\usepackage{amsfonts, amssymb}
\usepackage{latexsym}
\addtolength{\textwidth}{3.5cm} \addtolength{\oddsidemargin}{-2cm}
\addtolength{\topmargin}{-3.cm} \addtolength{\textheight}{2.25cm}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mbb}[1]{\mathbb{#1}}
\pagestyle{empty}
\begin{document}

\hfill \textbf{April  27, 2015}

\vspace{0.5 cm} \centerline{ \textbf{\large{Homework 5\hspace{1 cm}
Math 6303}}}

\vspace {1 cm}
\begin{enumerate}
\item Hungerford, p. 96, Exercises 1, 2, 3, 5, 6.
\item
Let $X$ be any set. The set $X^*$ of all words $w=x_0\ldots x_{n-1}$
becomes a monoid if a binary operation is defined as concatenation:
Let $w=x_0\ldots x_{n-1}$ and $w'=y_0\ldots y_{m-1}$ be two elements
of $X^*$ then the  product is defined as the word $w \cdot
w'=x_0\ldots x_{n-1}y_0\ldots y_{m-1}$. With respect to this
operation, the empty word $w=e$ is the unit. Prove that $X^*$ is the
free monoid, freely generated by the set $X$.
 \textit{Remark:} A word $w=x_0\ldots x_{n-1}$ is shorthand for a
 function $w:\{0,\ldots,n-1\}\to X$. The length $l(w)$ of $w$ is $n$.
 Clearly, $l(ww')=l(w)+l(w'), l(e)=0$. Thus, $l:X^* \to
 (\mbb{N},+,0)$ is a homomorphism between monoids.

\item
Let $M$ be any set and $F$ be a set of operation symbols $f_i$ for
the type $\Delta=(n_i)_{i \in I}$. Let $X=M\cup F$ where we assume
that $M$ and $F$ are disjoint and $i \to f_i$ is injective. Then a
subset $S$ of $X^*$ is called \textit{closed} if the following holds:
\begin{description}
\item[(i)] $M\subseteq S$
\item[(ii)] For any  $f_i$ and $w_0,\ldots, w_{n_i-1}$ in $S$ the
word $f_iw_0\ldots w_{n_i-1}$ belongs to $S$.
\end{description}
 Then the set of \textit{terms} is defined as the smallest closed subset $T$ of
$X^*$.

\noindent  Define the \textit{valency} function on the algebra of
words to the integers by:
\begin{description}
\item[(a)]$v(f_i)=-n_i+1$, $v(m)=1$.
\item[(b)]
For a word $w$ define $v$ as the sum of valencies of its letters
$c\in M\cup F$.
\end{description}

\noindent Prove  the following theorem of \textbf{P. Hall}: A word
$w=c_1c_2\ldots c_n$ is a term if and only if
\begin{description}
\item[(a)]$v(w)=1$,
\item[(b)]
$v(s_i)>0$ for every right segment $s_i=c_i\ldots c_n$.
\end{description}
\noindent Moreover, $w$ is a product of $r-$many terms if and only
if the first condition is replaced by  $v(w)=r$.
\item
Assume that $w=t_0\ldots t_{n-1}$ and $w'=s_0\ldots s_{m-1}$ are
products of terms and that  $w=w'$. Then $n=m$ and $t_i=s_i$.



\end{enumerate}









\end{document}
