\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\newcommand{\baexp}{\text{BAexp}}

\newcommand{\ms}[1]{\mathop{\text{#1}}}

\providecommand{\ide}{\ms{id}}
\providecommand{\EF}{\ms{F18}}
\providecommand{\T}{\ms{ST}}

\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}


\begin{document} 
\inclassproblems{4, Mon.}


%%F03 PSET5

\begin{problem}
Provide simple \emph{recursive} definitions of the following sets:

\begin{problemparts}

\problempart The set $S \eqdef \set{ 2^k 3^m 5^n \suchthat k,m,n \in
\naturals}$.

\solution{We can define the set $S$ recursively as follows:

\begin{enumerate}
\item $1 \in S$
\item If $n \in S$, then $2n$, $3n$, and $5n$ are in $S$.
\end{enumerate}
}

\problempart  The set $T \eqdef \set{2^k 3^{2k+m} 5^{m+n} \suchthat k,m,n \in
\naturals}$.

\solution{We can define the set $T$ recursively as follows:

\begin{enumerate}
\item $1 \in T$
\item If $n \in S$, then $18n$, $15n$, and $5n$ are in $T$.
\end{enumerate}
}

\problempart The set $L \eqdef \set{ (a, b) \in \integers^2
\suchthat a + 2b = 3k\text{ for some }k \in \integers }$.

\solution{In other words
\[
L = \set{ (a, b) \suchthat a +2b \equiv 0 \pmod 3} = \set{ (a, b)
\suchthat a \equiv b \pmod 3}.
\]

So we can define the set $L$ recursively as follows:

\begin{enumerate}
\item $(0, 0), (1,1), (2,2) \in L$
\item If $(a, b) \in L$, then $(a + 3, b)$, $(a - 3, b)$, $(a, b +3)$, and
$(a, b -3)$ are in $L$.
\end{enumerate}

Lots of other definitions are also possible.
}

\end{problemparts}
\end{problem}


\begin{problem}
The Elementary 18.01 Functions ($\EF$'s) are the set of functions of
one real variable defined recursively as follows:
\begin{enumerate}
\item The identity function, $\ide(x) \eqdef x$ is an $\EF$,\label{identfunc}

\item any constant function is an $\EF$,\label{const}

\item the sine function is an $\EF$,\label{basefunc}\\

\item if $f,g$ are $\EF$'s, then so are
\begin{enumerate}

\item $f + g$, $fg$, $e^g$ (the constant $e$),\label{+-}

\item the inverse function $f^{-1}$,\label{inversefunc}

\item the composition $f \compose g$.\label{cmp}

\end{enumerate}
\end{enumerate}

Prove, by Structural Induction on this definition, that the Elementary
18.01 Functions are \emph{closed under taking derivatives}.  That is, show
that if $f$ is an $\EF$, then so is $df/dx$.

\solution{
\begin{proof}
By Structural Induction on def of $\EF$.
\begin{description}
  
\item[Base Cases:] We want to show that the derivatives of all the
  functions mentioned in
  rules~\ref{identfunc}.,~\ref{const}.,~\ref{basefunc}.\ are in $\EF$.
  This is easy: for example, $\deriv \ide(x) = 1$ (constant) and so by
  rule~\ref{const}., it is in $\EF$. Similarly, $\deriv \sin(x) =
  \cos(x)$ which is also in $\EF$ since $\cos(x) = \sin(x+\pi/2) \in
  \EF$ by rules~ \ref{const}, \ref{basefunc} and rule \ref{cmp}.

\item[Induction Case:] ($f^{-1}$).  Assume $f, df/dx \in \EF$ to prove
$\deriv f^{-1}(x) \in \EF$.  

Letting $y = f(x)$, so $x=f^{-1}(y)$, we know from Leibniz' rule in
calculus that
\begin{equation}\label{Leib}
df^{-1}(y)/dy = dx/dy = \frac{1}{dy/dx}.
\end{equation}
For example,
\[
d \sin^{-1}(y)/dy = 1/(d \sin(x)/dx) = 1/\cos(x) = 1/\cos(\sin^{-1}(y)).
\]
Stated as in ~(\ref{Leib}), this rule is easy to remember, but can easily
be misleading because of the variable switching between $x$ and $y$.
It's more clearly stated using variable-free notation:
\begin{equation}\label{Leib2}
(f^{-1})' = (1/f') \compose f^{-1}.
\end{equation}
Now, since $f' \in \EF$ (by assumption), so is $1/f' = f'^{(-1)}$ (by~\ref{+-}.) and
$f^{-1}$ (by~\ref{inversefunc}.), and therefore so is their composition
(by~\ref{cmp}).  Hence the righthand side of equation~(\ref{Leib2})
defines a function in $\EF$.

\item[Induction Case:] ($f \compose g$).  Assume $f, g, df/dx, dg/dx \in \EF$
to prove prove $d(f \compose g)(x)/dx \in \EF$.

The Chain Rule states that
\[
\frac{d(f(g(x)))}{dx} = \frac{d f(g)}{dg}\cdot\frac{dg}{dx}.
\]
Stated more clearly in variable-free notation, this is
\[
(f \compose g)' = (f' \compose g) \cdot g'.
\]
The righthand side of this equation defines a function in $\EF$ by
rules~\ref{cmp}.\ and~\ref{+-}.

The other Induction cases are similar.

\end{description}
\end{proof}

}
\end{problem}


\begin{problem}

$\baexp$'s are defined in the Appendix.

\bparts

\ppart The value of $\text{flatten}(e)$ for $e \in \baexp$ is the sequence
of integers in $e$ obtained by ``erasing'' everything but the integers
that appear within tagged variables and tagged \texttt{int}'s.  For
example,
\begin{align*}
e & \eqdef \ang{\texttt{sum}, \ang{\texttt{var},
3}, \ang{\texttt{sum}, \ang{\texttt{var}, 2},\ang{\texttt{int}, 2}}}\\
f & \eqdef \ang{\texttt{prod}, \ang{\texttt{var},4},\ang{\texttt{var}, 5}}\\
g & \eqdef \ang{\texttt{prod}, e,  \ang{\texttt{sum}, \ang{\texttt{var},7}, f}}\\
\text{flatten}(g) & = \ang{3,2,2,7,4,5}.
\end{align*}
Give a recursive definition of flatten.  (You may use the operation of
\emph{concatenation} (append) of two sequences.)

\solution{
\begin{itemize}
\item \textbf{Base cases:}
\begin{enumerate}
\item $\text{flatten}(\ang{\texttt{int}, n}) \eqdef \ang{n}$
\item $\text{flatten}(\ang{\texttt{var}, n}) \eqdef \ang{n}$
\end{enumerate}
\item \textbf{Constructor cases:}
\begin{enumerate}
\item $\text{flatten}(\ang{\texttt{sum}, e_1, e_2}) \eqdef \text{flatten}(e_1)\text{flatten}(e_2)$
\item $\text{flatten}(\ang{\texttt{prod}, e_1, e_2}) \eqdef \text{flatten}(e_1)\text{flatten}(e_2)$
\end{enumerate}
\end{itemize}
}

\ppart Prove by structural induction on the definition of $\baexp$
that for all $e \in \baexp$,
\[
2\cdot \text{length}(\text{flatten}(e)) = \card{e}+1
\]

\solution{

\begin{itemize}
\item \textbf{Base cases:}
\begin{enumerate}
\item $2 \cdot \text{length}(\text{flatten}(\ang{\texttt{int}, n})) = 2\cdot 1 =
  2 = 1 + 1 = \card{\ang{\texttt{int}, n}} + 1.$
\item \texttt{var} case the same.
\end{enumerate}
\item \textbf{Constructor cases:}
\begin{enumerate}

\item
\begin{align*}
\lefteqn{2 \cdot \text{length}(\text{flatten}(\ang{\texttt{sum}, e_1, e_2}))}\\
  & = 2\cdot \text{length}(\text{flatten}(e_1)\text{flatten}(e_2)) 
        & \text{(def of flatten)}\\
  & = 2\cdot \text{length}(\text{flatten}(e_1))+
     2 \cdot \text{length}(\text{flatten}(e_2))
        & \text{(length of a string)}\\
  & = (\card{e_1}+1) + \card{e_2}+1 & \text{(structural induction hyp.)}\\
  & = \card{(\ang{\texttt{sum}, e_1, e_2})} + 1. & \text{(def. of $\card{\cdot}$)}
\end{align*}
\item \texttt{prod} the same.
\end{enumerate}
\end{itemize}
}

\eparts
\end{problem}

\iffalse

\begin{problem} 
We define the family $\T$ of \emph{search trees} as follows:
\begin{enumerate}
\item  Any single number $x$ is in $\T$.
\item  If $T$ and $T'$ are in $\T$, and a number $x$ is larger than every
number in $T$ but smaller than every number in $T'$, then the structure
$\makeb(T,x,T')$ formed by attaching a left-pointing arrow from $x$ to
$T$ and a right-pointing arrow from $x$ to $T'$ is also in $\T$. See
Figure \ref{fig:searchtree}
\end{enumerate}

\begin{figure}[h]
\begin{center}
\input{figures/cp5F-searchtree.latex}
\end{center}
\caption{Creating a new search tree by applying rule 2}
\label{fig:searchtree}
\end{figure}


The number $x$ is called the \emph{root} of the tree that is formed.

\begin{problemparts}

\problempart Draw all the different search trees in $\T$ that have nodes
1, 2, 3, 4, 5.


\solution{
See Figure \ref{fig:possibilities}
%(1 2 (4 3 5)) and ((1 3 2) 4 5).

\begin{figure}[h]
\begin{center}
\input{figures/cp5F-st.latex}
\end{center}
\caption{The two possible search trees}
\label{fig:possibilities}
\end{figure}

}

\ppart
Define a function $\membern:\naturals \cross \T \to \set{0,1}$
recursively as follows:
\begin{eqnarray}
\membern(n,n)  & \eqdef & 1,\\
\membern(n,m)  & \eqdef & 0, \text{ for } n \neq m \in \naturals,\\
\membern(n,\makeb(T,n,T')) & \eqdef & 1,\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T)) \text{ for } n < m,\label{mn<}\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T')) \text{ for } n > m.
\end{eqnarray}

Prove that
\[
\membern(n,T) = 1 \iff n \in \nodes(T).
\]

\solution{
\begin{proof}
Note that we are asked to prove \emph{both} directions! ($\iff$). The
proof will be by structural induction on the definition of $\T$. 
\begin{description}
\item[Base Case:] $|T|=1$. The tree has only one node
representing a natural number $t$. 
\begin{description}
\item[($\Longleftarrow$)]If $n\in \nodes(T)$ then $n=t$ and so by rule
(1), $\membern(n,t)=1$.
\item[($\Longrightarrow$)]If $\membern(n,t)=1$ then, by rule (2), it is
impossible to have  $n\neq t$ because in that case
$\membern(n,t)=0$. Therefore, $n=t$ and so $n \in \nodes(T)$
\end{description}

\item[Induction Step:] There is only one operation to consider, namely $\makeb(T,x,T')$. Assume that
\begin{eqnarray*}
\membern(n,T) = 1 \iff n \in \nodes(T),\label{mnT}\\
\membern(n,T') = 1 \iff n \in \nodes(T')
\end{eqnarray*}
to prove
\begin{equation*}
\membern(n,\makeb(T,x,T')) = 1 \iff n \in \nodes(\makeb(T,x,T')).
\end{equation*}
\begin{description}
\item[Case 1: ($n = x$)] Then, by the definiton of ``nodes'' $n \in
\nodes(\makeb(T,x,T'))$. At the same time, $\membern(n,\makeb(T,x,T')) = 1$ by definition of
$\membern$. Notice that there is no if-then statement here. If $n=x$
then both sides of the double implication ($\iff$) have to be true.

\item[Case 2: ($n < x$)] Then $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)
\union \nodes(T')$ by definition of $\nodes$.  But since $\makeb(T,x,T')
\in \T$, we know $x < \min(\nodes(T'))$, so $n \notin \nodes(T')$.
Therefore, $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)$.
By~(\ref{mnT}), $n \in \nodes(T)$ iff $\membern(n,T) =1$.  But
$\membern(n,\makeb(T,x,T')) = \membern(n,T)$ by~(\ref{mn<}), completing
the proof.

\item[Case 3: ($n > x$)] Symmetric to Case 2.
\end{description}
\end{description}
\end{proof}
}

\end{problemparts}
\end{problem}


\begin{problem} %{S01-PS2}              

The set, $W$, of ``well-formed parenthesis strings'' can be defined by
the following rules:

\begin{enumerate}
\item the empty string, $\emptystring$, is in $W$, and
\item if $s$ and $t$ are in W then the string $\lp s\rp t$ is
in $W$.
\end{enumerate}

For example, the string
\begin{quote}
\texttt{(()())()}
\end{quote}
is a well-formed parenthesis string, but the string
\begin{quote}
\texttt{)(())}
\end{quote}
isn't.

Use structural induction to prove that any prefix of any well-formed
parenthesis string has at least as many left parentheses as right
parentheses.

\solution{Let $L(t)$ be the predicate that $t$ is a string of parentheses
with at least as many left as right parentheses, and define
\[
P(t) \eqdef\quad  \forall p\  [\text{($p$ is a prefix of $t$)} \implies L(p)].
\]
We prove by structural induction that $P(r)$ holds for all $r \in W$.

\textbf{Base Case} ($r = \emptystring$): $P(r)$ holds because the only
prefix of $r$ is $r$ itself, and $L(r)$ holds because $r$ has the
\emph{same} number of left or right parentheses, namely, none.

\textbf{Inductive Step:} Let $s, t$ be any strings in $W$, and let $r\eqdef
\lp s\rp t$.  Assuming that $P(s)$ and $P(t)$ hold, we want to prove
$P(r)$.  So we let $p$ be any prefix of $r$ and prove $L(p)$ by considering
the following exhaustive set of cases:

\begin{itemize}

\item \text{} [$p = \emptystring$] We already observed that $L(p)$ holds.

\item  \text{} [$p = \lp $] $L(p)$ holds immediately.

\item  \text{} [$p = \lp u$, for some prefix, $u$, of $s$].  Since $P(s)$
holds, it follows that $L(u)$ holds.  But $p$ has the same number of right
parentheses and one more left parenthesis than $u$, so $L(p)$ holds \emph{a
fortiori}.

\item \text{} [$p = \lp s\rp u$, for some (possibly empty) prefix,
$u$, of $t$].  Say $s$ has $m_1$ left parentheses and $n_1$ right
parentheses.  Since $P(s)$, and hence $L(s)$, holds, we have $m_1 \ge n_1$.
Similarly, suppose $u$ has has $m_2$ left parentheses and $n_2$ right
parentheses.  Since $P(t)$ holds, we have that $L(u)$ holds, namely, $m_2
\ge n_2$.  So the number of left parentheses in $p$ is $m_1+m_2 +1 \ge
n_1+n_2 +1$ which equals the number of right parentheses in $p$.
This proves $L(p)$.
\end{itemize}

Thus, for any prefix, $p$, of $r$, we conclude that satisfies $L(p)$ holds,
that is, $P(r)$ holds, completing the proof by structural induction.
}

\end{problem}

\begin{problem}

\emph{Pure list expressions (PLEs)} are defined recursively as follows:
\begin{enumerate}
\item $\lp\rp$ is a PLE,
\item if $T_1,\dots,T_n$ are PLEs for $n\ge 1$, then
\begin{quote} $\lp T_1\ \dots\ T_n\rp$ is a PLE.
\end{quote}
\end{enumerate}

\emph{Pure Cons-cell Expressions (PCEs)} are defined recursively as
follows:
\begin{enumerate}
\item \nil\ is a PCE,
\item if $P_1,P_2$ are PCE's, then \texttt{(cons $P_1$ $P_2$)} is a PCE.
\end{enumerate}
A PCE can be understood as an expression whose \emph{value} is a PLE.  We
can define this value function, $\nu:\text{PCE} \to \text{PLE}$,
by recursion on the definition of PCE.  First, let $\mkp:\text{PLE}^2 \to
\text{PLE}$ be defined by the rules:
\begin{eqnarray}
\mkp(T, \lp\rp) &\eqdef& \lp T\rp, \label{mkone} \\
\mkp(T, \lp T_1\ \dots\ T_n \rp) &\eqdef &\lp T\ T_1\ \dots\ T_n \rp \label{mkmore}.
\end{eqnarray}

Now we define:
\begin{eqnarray}
\nu(\nil) &\eqdef& \lp\rp, \label{nunil} \\
\nu(\texttt{(cons $P_1$ $P_2$)}) &\eqdef& \mkp(\nu(P_1),\nu(P_2)) \label{nucon}.
\end{eqnarray}

\bparts

\ppart For any PCE, $P$, let $\#P$ be the number of occurrences of
\texttt{cons} in $P$.  We use the notation $\card{s}$ for the length of a
string, $s$.  Prove that
\begin{equation}\label{1P}
1+ \#P = \card{\nu(P)}/2.
\end{equation}


\solution{
\begin{proof}
The proof is by structural induction on the definition of a PCE,
$P$, with~(\ref{1P}) as the induction hypothesis.

\textbf{Base case} $P = \nil$: So $\nu(P) = \lp\rp$,
and
\[
1 + \#P = 1 + 0 = 1 = 2/2 = \card{\lp\rp}/2,
\]
so~(\ref{1P}) holds for \nil.

\textbf{Inductive case} $P = \texttt{(cons $P_1$ $P_2$)}$ for some PCEs
$P_1,P_2$ satisfying~(\ref{1P}), \ie
\begin{eqnarray}
1+ \#P_1 & = &\card{\nu(P_1)}/2,\label{P1}\\
1+ \#P_2 & = & \card{\nu(P_2)}/2.\label{P2}
\end{eqnarray}
We now prove that~(\ref{1P}) holds:

\begin{align*}
1+\#P & = 1+ (1+ \#P_1 + \#P_2) & \text{by def of $\#P$}\\
      & = (1+ \#P_1) + (1 + \#P_2)\\
      & = \card{\nu(P_1)}/2 + \card{\nu(P_2)}/2 & \text{by~(\ref{P1}) and~(\ref{P2})}\\
      & = \frac{\card{\nu(P_1)} + \card{\nu(P_2)}}{2}\\
      & = \frac{\card{\mkp(\nu(P_1),\nu(P_2))}}{2} & \text{by def of $\mkp$}\\
      & = \frac{\card{\nu(\texttt{(cons $P_1$ $P_1$)})}}{2}
          & \text{by def of $\nu$}\\
      & = \frac{\card{\nu(P)}}{2}.
\end{align*}


This completes the proof of the inductive case, and we conclude by
structural induction that~(\ref{1P}) holds for all PCEs, $P$.

\end{proof}
}

\eparts
 
The correspondence between a PCE, $P$, and the PLE, $\nu(P)$, is exact.
More precisely, there is a function $q:\text{PLE} \to \text{PCE}$ which is
the inverse of $\nu$, namely,
\begin{eqnarray}
\nu(q(T)) = & T  & \text{for all PLEs, $T$},\label{nq}\\
q(\nu(P)) = & P  & \text{for all PCEs, $P$.}\label{qn}
\end{eqnarray}

\bparts

\ppart\label{defq} Give a recursive definition of the function $q$.

\solution{
\begin{itemize}
\item $q(\lp \rp) \eqdef \nil$.

\item $q(\lp T_1\rp) \eqdef \texttt{(cons $q(T_1)$ \nil)}$.

\item For, $n \geq 2$,
\[
q(\lp T_1\ T_2 \dots\ T_n\rp) \eqdef \texttt{(cons $q(T_1)$ $q(\lp T_2\
\dots\ T_n\rp)$)}.
\]

\end{itemize}
}

\ppart Prove one of the equations~(\ref{nq}) or~(\ref{qn}).

\solution{

\begin{proof}
First, we prove~(\ref{nq}) by structural induction on definition of a PLE, $T$,
with induction hypothesis $\nu(q(T)) = T$.

\textbf{Base case} $T = \lp \rp$: 
\begin{align*}
\nu(q(T)) & = \nu(q(\lp \rp)) \\
          & = \nu(\nil) & \text{by def in part~(\ref{defq})} \\
          & = \lp \rp   & \text{by~(\ref{nunil})} \\
          & = T
\end{align*}

\textbf{Inductive case} $T = \lp T_1 \rp$:
\begin{align*}
\nu(q(T)) & = \nu(q(\lp T_1 \rp)) \\
          & = \nu(\texttt{(cons $q(T_1)$ \nil)}) & \text{by def in part~(\ref{defq})} \\
          & = \mkp(\nu(q(T_1),\nu(\nil))) & \text{by~(\ref{nucon})} \\
          & = \mkp(T_1, \lp\rp) & \text{by induction hypothesis} \\
          & = \lp T_1 \rp & \text{by~(\ref{mkone})} \\
          & = T
\end{align*}

\textbf{Inductive case} for $n \ge 2$, $T = \lp T_1 T_2 \dots\ T_n\rp$:
\begin{align*}
\nu(q(T)) & = \nu(q(\lp T_1 T_2 \dots\ T_n\rp)) \\
          & = \nu(\texttt{cons $q(T_1)$ $q(\lp T_2 \dots\ T_n \rp)$}) & \text{by def in part~(\ref{defq})} \\
          & = \nu(\texttt{cons $P_1$ $P_2$}) & \text{by func $q:\text{PLE} \to \text{PCE}$} \\
          & = \mkp(\nu(P_1),\nu(P_2)) & \text{by~(\ref{nucon})} \\
          & = \mkp(\nu(q(T_1)),\nu(q(\lp T_2 \dots\ T_n \rp))) \\
          & = \mkp(T_1, \lp T_2 \dots\ T_n \rp) & \text{by induction hypothesis} \\
          & = \lp T_1 T_2 \dots\ T_n \rp & \text{by~(\ref{mkmore})} \\
          & = T
\end{align*}

We conclude by structural induction that~(\ref{nq}) holds for all PLEs, $T$.

We then prove~(\ref{qn}) by structural induction on definition of a PCE, $P$,
with induction hypothesis $q(\nu(P)) = P$.

\textbf{Base case} $P = \nil$:
\begin{align*}
q(\nu(P)) & = q(\nu(\nil)) \\
          & = q(\lp \rp) & \text{by~(\ref{nunil})} \\
          & = \nil & \text{by def in part~(\ref{defq})} \\
          & = P
\end{align*}

\textbf{Inductive case} $P = (\texttt{cons $P_1$ $P_2$})$:
\begin{align*}
q(\nu(P)) & = q(\nu(\texttt{cons $P_1$, $P_2$})) \\
          & = q(\mkp(\nu(P_1),\nu(P_2))) & \text{by~(\ref{nucon})} \\
          & = q(\mkp(T_1, T_2)) & \text{by func $\nu:\text{PCE} \to \text{PLE}$} \\
          & = (\texttt{cons $q(T_1)$ $q(T_2)$}) & \text{by def in part~(\ref{defq})} \\
          & = (\texttt{cons $q(\nu(P_1))$ $q(\nu(P_2))$}) \\
          & = (\texttt{cons $P_1$ $P_2$}) & \text{by induction hypothesis} \\
          & = P
\end{align*}

We conclude by structural induction that~(\ref{qn}) holds for all PCEs, $P$.

\end{proof}
}

\ppart Conclude that for all $n\ge 1$ there are the same number of PCEs
with $n-1$ occurrences of \textbf{cons} as there are PLEs of length $2n$.

\solution{
$\nu:\text{PCE} \to \text{PLE}$ defines a function from PCEs to PLEs,
and the existence of $q:\text{PLE} \to \text{PCE}$ implies that
$\nu$ defines a bijection between PLEs and PCEs. $q$
defines a bijection between PCEs and PLEs as well.

From~(\ref{1P}), if $\#P = n-1$ (\eg PCEs with $n-1$ occurrences of 
cons) then $\card{\nu(P)} = 2n$ (\eg PLEs of length $2n$). 
That is, $\nu$ maps a PCE with $n-1$ cons to a PLE with length $2n$. 
Since $\nu$ is a bijection,  $\text{(number of PCEs
with $n-1$ occurrences of cons)} \le \text{(number of PLEs with length $2n$)}$.

On the other hand, we re-write~(\ref{1P}) as
\begin{equation}
1+ \#q(T) = \card{T}/2.
\end{equation}
If $\card{T} = 2n$ then $\#q(T) = n-1$. That is, $q$ maps a PLE with
length $2n$ to a PCE with $n-1$ cons. Since $q$ is a bijection, $\text{(number
of PLEs with length $2n$)} \le \text{(number of PCEs with $n-1$ cons)}$.

In summary, for all $n\ge 1$ there are the same number of PCEs
with $n-1$ occurrences of \textbf{cons} as there are PLEs of length $2n$.
}

\eparts

\end{problem}


\begin{problem}
Ackermann's function is an extremely fast-growing function of two natural
number arguments, whose inverse -- which is extremely slow-growing --
turns out to characterize the average efficiency of the Union-Find
algorithm for maintaining finite equivalence classes that was mentioned in
lecture.  We won't go further into the story of the Union-Find algorithm
and how Ackermann's function enters into its analysis; you will learn
about this if you take the Algorithms course, 6.046.  In this problem, we
simply examine the somewhat unusual recursive definition of Ackermann's
function, $A(m,n)$.

Ackermann's function is usually described as being defined by the
following equations:
\begin{align}
f(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Am0}\\ 
f(m,n) &=  f(m-1,f(m,n-1)), &&\text{if $m > 0$ and $n > 1$}.\label{AA}
\end{align}
That is, if we regard equations~(\ref{Am0}) and~(\ref{AA}) as defining a
predicate $P(f,m,n)$ on numbers $m, n \in \naturals$ and a function
$f:\naturals^2 \to \naturals$, then $A$ is \emph{defined} to be the
\emph{unique} two-argument function on natural numbers such that $\forall
m,n\ P(A,m,n)$.

But how do we know that equations~(\ref{Am0}) and~(\ref{AA}) actually
define anything, and in particular that they define a total function?
Justifying this definition really breaks down into two parts, namely
\begin{itemize}
\item \emph{existence}: $\exists f: \naturals^2 \to \naturals\, \forall m,n\
P(f,m,n)$,

\item \emph{uniqueness}: $[\forall m,n\ P(f,m,n) \land P(g,m,n)] \implies f = g$.
\end{itemize}

\bparts

\ppart Use the well-ordering principle for lexicographic order, $\lexle$,
on $\naturals^2$ to prove uniqueness.  \hint Suppose $\forall m,n\
P(f,m,n) \land \forall m,n\ P(g,m,n)$.  Consider the least pair $(m,n) \in
\naturals^2$ such that $f(m,n) \neq g(m,n)$ and reach a contradiction.

\solution{
\begin{proof}
Assume for the sake of contradiction that there is a function,
$f:\naturals^2 \to \naturals$, such that $\forall m,n\ P(f,m,n)$, and
another function, $g$, such that $\forall m,n\ P(g,m,n)$, but $f \neq g$.

Let $S$ be the set of pairs $(m,n)$ such that $f(m,n) \ne g(m,n)$.  Since
$f \neq g$, the set, $S$, is nonempty.  Since lexicographic order, $\lex<$,
is a well-order (\viz a total and well-founded partial order), it follows
that there is a \emph{least} element $(m_0,n_0) \in S$ under $\lex<$.
In particular, 
\begin{equation}\label{m0n0}
f(m_0,n_0) \neq g(m_0,n_0).
\end{equation}

But if $m_0 = 0$ or $n_0 \le 1$, then according to (\ref{Am0})
\begin{align*}
f(m_0,n_0) & = 2n_0       & \text{since $P(f,m_0,n_0)$ holds},\\
           & = g(m_0,n_0) & \text{since $P(g,m_0,n_0)$ holds},
\end{align*}
contradicting~(\ref{m0n0}).  So, we may assume that $m_0 >0$ and $n_0 > 1$,
and therefore
\begin{equation}\label{fm0}
f(m_0,n_0) = f(m_0-1,f(m_0,n_0-1)),
\end{equation}
by~(\ref{AA}) since $P(f,m_0,n_0)$ holds, and likewise
\begin{equation}\label{gm0}
g(m_0,n_0) = g(m_0-1,g(m_0,n_0-1)).
\end{equation}

But $(m_0,n_0-1) \lex< (m_0,n_0)$ by definition of lexicographic order, so
$(m_0, n_0-1) \notin S$ since $(m_0,n_0)$ was the lexicographically least
element of $S$.  Therefore,
\begin{equation}
f(m_0, n_0-1) = g(m_0,n_0-1).\label{j0}
\end{equation}
Let $j_0 \eqdef f(m_0, n_0-1)$.

But now $(m_0-1,j_0)\lex< (m_0,n_0)$ by definition of $\lex<$, so
$(m_0-1,j_0) \notin S$ and
\begin{equation}
f(m_0-1,j_0) = g(m_0-1,j_0).\label{k0}
\end{equation}
So,
\begin{align*}
f(m_0,n_0) & = f(m_0-1,f(m_0,n_0-1)) & \text{by~(\ref{fm0})},\\
           & = f(m_0-1,j_0) & \text{by def of $j_0$},\\
           & = g(m_0-1,j_0) & \text{by~(\ref{k0})},\\
           & = g(m_0-1,g(m_0,n_0-1)) & \text{by~(\ref{j0})},\\
           & = g(m_0,n_0) & \text{by~(\ref{gm0})},\\
\end{align*}
contradicting~(\ref{m0n0}).
\end{proof}
}

\eparts

We can prove existence by using~(\ref{Am0}) and~(\ref{AA}) to give a
recursive definition of the graph of a \emph{relation}, $A$, and then
proving that the relation is actually a function satisfying these
equations.

Namely, define a set, $A$, of pairs in $\naturals^2 \cross \naturals$
recursively as follows:
\begin{enumerate}
\item $((m,n),2n) \in A$ if $m=0$ or $n \le 1$, \label{rel1}

\item if $(m-1,j),k) \in A$ and $((m,n-1),j) \in A$, then $((m,n),k) \in
A$, for all $m,n,j,k \in \naturals$ such that $m > 0$ and $n >
1$. \label{rel2}
\end{enumerate}

\bparts

\ppart\label{relation}w Use the well-ordering principle for $\lexle$ to
show that $A$ is a \emph{total} relation, \ie $\domain{A} = \naturals^2$.
\hint Consider the \emph{least} $(m,n) \notin \domain{A}$ and reach a
contradiction.

\solution{
\begin{proof}
Assume for the sake of contradiction that $\domain{A} \ne \naturals^2$.
So $\bar{\domain{A}}$ is not empty, and therefore has a least element,
$(m_0,n_0)$, under $\lexle$.  In particular,
\begin{equation}\label{m0n0A}
(m_0,n_0) \notin \domain{A}.
\end{equation}

But if $m_0 = 0$ or $n_0 \le 1$, then $((m_0,n_0),2n_0) \in A$ by
condition~\ref{rel1}.\ in the recursive definition of $A$, and in
particular $(m_0,n_0) \in \domain{A}$, contradicting~(\ref{m0n0A}).  So,
we may assume that $m_0 >0$ and $n_0 > 1$.

But $(m_0,n_0-1) \lex< (m_0,n_0)$ by definition of lexicographic order, so
$(m_0, n_0-1) \in \domain{A}$ since $(m_0,n_0)$ was the lexicographically
least element not in $\domain{A}$.  In particular, there must be some $j_0
\in \naturals$ such that
\begin{equation}\label{j0A}
((m_0, n_0-1),j_0) \in A.
\end{equation}

But now $(m_0-1,j_0)\lex< (m_0,n_0)$ by definition of $\lex<$, so
$(m_0-1,j_0) \in \domain{A}$, and there must be some $k_0 \in \naturals$
such that
\begin{equation}
((m_0-1,j_0),k_0) \in A.\label{k0A}
\end{equation}
But now from~(\ref{j0A}),~(\ref{k0A}), and condition~\ref{rel2}.\ of the
definition of $A$, we conclude that $(m_0,n_0) \in \domain{A}$,
contradicting~(\ref{m0n0A}).
\end{proof}
}

\ppart\label{func} Use the well-ordering principle for $\lexle$ to prove
that $A$ is the graph of a \emph{function}.  \hint Consider the
\emph{least} $(m,n)$ such that $((m,n),x) \in A$ and $((m,n),y) \in A$ and
$x \neq y$, and reach a contradiction.

\solution{
\begin{proof}
Assume for the sake of contradiction that $A$ is not the graph of a
function.

Let $S$ be the set of pairs $(m,n)$ such that $((m,n),x),((m,n),y) \in A$
for some integers $x \neq y$.  Since $A$ is not the graph of a function,
the set, $S$, is nonempty, and therefore has a lexicographically
\emph{least} element $(m_0,n_0) \in S$.  In particular, there are integers
$k_1, k_2 \in \naturals$ such that
\begin{equation}\label{m0n0x}
((m_0,n_0),k_1),((m_0,n_0),k_2) \in A\ \text{ and }\ k_1 \neq k_2.
\end{equation}

As in the previous parts, we must have that $m_0 > 0$, $n_0 > 1$, so the
fact that $((m_0,n_0),k_1) \in A$ must be a consequence of
condition~\ref{rel2}.\ in the definition of $A$.
That is, there must be an $j_1 \in \naturals$ such that
\begin{equation}\label{x1}
((m_0-1,j_1),k_1) \in A \ \text{ and }\ ((m_0,n_0-1),j_1) \in A.
\end{equation}
Likewise, there must be a $j_2 \in \naturals$ such that
\begin{equation}\label{y1}
((m_0-1,j_2),k_2) \in A\ \text{ and }\ ((m_0,n_0-1),j_2) \in A.
\end{equation}

But $(m_0,n_0-1) \lex< (m_0,n_0)$, and since $((m_0,n_0-1),j_1) \in A$
by~(\ref{x1}) and $((m_0,n_0-1),j_2) \in A$ by~(\ref{y1}), we conclude
from the definition of $(m_0,n_0)$ that $j_1 = j_2$.  Likewise,
$(m_0-1,j_1) \lex< (m_0,n_0)$, and since $((m_0-1,j_1),k_1) \in A$
by~(\ref{x1}) and $((m_0-1,j_1),k_2) = ((m_0-1,j_2),k_2) \in A$
by~(\ref{y1}), we conclude from the definition of $(m_0,n_0)$ that $k_1 =
k_2$, contradicting~(\ref{m0n0x}).
\end{proof}
}

\ppart Use parts~(\ref{relation}) and~(\ref{func}) to prove that $A$
satisfies~(\ref{Am0}) and~(\ref{AA}).

\solution{
\begin{proof}
We know from parts~(\ref{relation}) and (\ref{func}) that the relation $A$
is a total function, \ie
\begin{equation}\label{mnj}
((m,n), j) \in A \qiff j= A(m,n).
\end{equation}
But if $m=0$ or $n \le 1$, then $((m,n),2n) \in A$ by
condition~\ref{rel1}.\ of the definition of the relation, $A$, so
\[
A(m,n) =  2n.
\]
Therefore, $A$ satisfies~(\ref{Am0}).

Now suppose $m >0$ and $n > 1$, and let $j \eqdef A(m, n-1)$.  Then
by~(\ref{mnj}),
\begin{align*}
((m,n-1), j) & \in A,\\
((m-1,j), A(m-1,j)) & \in A,
\end{align*}
so by condition~\ref{rel2}.\ of the definition of the relation, $A$, we
conclude that
\[
((m,n), A(m-1,A(m,n-1))) = ((m,n), A(m-1,j)) \in A.
\]
By~(\ref{mnj}) again, this means that
\[
A(m,n) = A(m-1,A(m,n-1)).
\]
Hence, $A$ satisfies~(\ref{AA}).
\end{proof}
}       

\ppart Generalize the way Ackerman's function was defined.  Namely, describe a
format for recursively defining functions on \emph{any} well-founded
partial order that is guaranteed to uniquely define a total function on
the domain of the partial order.  The definition of Ackerman's function
should be a special case of the format you describe.  You need \emph{not}
prove that your format guarantees existence and uniqueness.

\solution{ On way to generalize the ideas above is to allow any function,
$f:A \to B$, where $A$ is the domain of a well-founded partial order,
$\preceq$, to be defined by a rule of the form
\[
f(a) \eqdef h(\set{(a', f(a')) \suchthat a' \prec a})
\]
where $h$ is any total function from $\power(A \cross B)$ to $B$.  By
exactly the same reasoning used above to verify that Ackerman's function
was properly defined, we could prove that this rules defines a unique
partial function $f$ from $A$ to $B$ and this unique $f$ is in fact total.

Note that Ackermann's function fits this rule if we define
$h:\power(\naturals^2 \cross \naturals) \to \naturals$ as follows.  First,
say that a relation $R \subseteq \naturals^2 \cross \naturals$ is
\emph{relevant} when
\begin{itemize}
\item $R$ is the graph of a partial function from $\naturals^2$ to $\naturals$, and

\item there is a pair $(m_0,n_0) \in \naturals^2$ such that
\[
\domain{R} =\ \  (\lex<)\set{(m_0,n_0)},
\]
where
\[
(\lex<)\set{(m_0,n_0)} \eqdef  \quad \set{(m,n) \suchthat (m,n) \lex< (m_0,n_0)}.
\]
\end{itemize}

Then define
\[
h(R) \eqdef 
\begin{cases}
0, & \text{if $R$ is not relevant, or else}\\
0, & \text{if $\domain{R} =\ \  (\lex<)\set{(m,0)}$ for some $m \in \naturals$, or else}\\
2,  & \text{if $\domain{R} =\ \  (\lex<)\set{(m,1)}$ for some $m \in \naturals$, or else}\\
2n, & \text{if $\domain{R} =\ \  (\lex<)\set{(0,n)}$, or else}\\
R(m-1,R(m,n-1)).
\end{cases}
\]
}

\eparts

\end{problem}
%%%%%%%%%END F03 PSET 5


\begin{problem}
How many children does the root of a game tree for chess have?  What is
the first level of the tree where two nodes on that level have different
numbers of children?

\solution{20 moves from the root (level 0), namely 16 pawn moves and 4
knight moves.  Same at level 1 for the second player.  But at level 2,
corresponding to first player's second move, there are different numbers
of choices.}

\end{problem}

\fi


\section*{Appendix}

The set, $\baexp$, of \emph{Basic Arithmetic Expressions}
is defined recursively as tagged data type as follows:
\begin{itemize}
\item \textbf{Base cases:}
\begin{enumerate}
\item If $n \in \integers$, then $\ang{\texttt{int}, n} \in \baexp$.
\item If $n \in \integers$, then $\ang{\texttt{var}, n} \in \baexp$.
\end{enumerate}
\item \textbf{Constructor cases:} if $e,e' \in \baexp$, then
\begin{enumerate}
\item $\ang{\texttt{sum}, e, e'} \in \baexp$,
\item $\ang{\texttt{prod}, e, e'} \in \baexp$.
\end{enumerate}
\end{itemize}

The size, $\card{e}$, of $e \in \baexp$ is defined recursively on this
definition by:

\begin{itemize}
\item \textbf{Base cases:}
\begin{enumerate}
\item $\card{\ang{\texttt{int}, n}} \eqdef 1$
\item $\card{\ang{\texttt{var}, n}} \eqdef 1$
\end{enumerate}
\item \textbf{Constructor cases:}
\begin{enumerate}
\item $\card{\ang{\texttt{sum}, e_1, e_2}} \eqdef \card{e_1}+ \card{e_1} +
  1$
\item $\card{\ang{\texttt{prod}, e_1, e_2}} \eqdef \card{e_1}+
  \card{e_1} + 1$
\end{enumerate}
\end{itemize}

\end{document} 
