% This work is licensed under the Creative Commons Attribution 3.0 Unported License.
% To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/
% or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, 
% California, 94105, USA.
%
% Author: Alejandro Diaz-Caro <alejandro.diaz-caro@imag.fr>
% Date: October 2010
\documentclass[12pt,a4paper]{article}

\usepackage{amsmath,amsfonts,amssymb}
\usepackage[top=1.5cm,right=1.5cm,bottom=1.5cm,left=1.5cm]{geometry}
\usepackage{vaucanson-g}
\newcommand{\N}{\ensuremath{\mathbb{N}_0}}
\newcommand{\ie}{{\em i.e.}}
\newcommand{\cf}{{\em cf.}}
\newcommand{\eg}{{\em e.g.}}
\newcommand{\PRF}{{\bf PRF}}
\newcommand{\PRS}{{\bf PRS}}
\newcommand{\PRR}{{\bf PRR}}
\newcommand{\RF}{{\bf RF}}
\newcommand{\D}{\ensuremath{{}^\circ\! D}}
\newcommand{\dif}{\ensuremath{{}^\circ\! d}}

\makeindex

\title{Exercise sheet 3: Decidability}
\author{Alejandro D\'iaz-Caro}
\date{2010}

\begin{document}
\begin{center}
 \textbf{\begin{large}Exercise sheet 4: Primitive recursive functions\end{large}}
\end{center}

\begin{enumerate}
\subsection*{Primitive recursive functions}
 \item Show that for all $n\in\N$, the constant function $g_n(x)=n$  is primitive recursive.
 \item Show that each of the following are primitive recursive functions.
	\begin{enumerate}
	 \item $\Sigma(x,y)=x+y$
	 \item $\Pi(x,y) = xy$
	 \item $Exp(x,y) = x^y$
	 \item $Fac(x) = x!$
	 \item $Pd(x)=\left\{\begin{array}{ll}
		               x-1 & \textrm{ if }x\geq 1\\
						0  & \textrm{ if }x=0
		               \end{array}\right.$
	 \item $\dif(x,y)=\left\{\begin{array}{ll}
		               x-y & \textrm{ if }x\geq y\\
						0  & \textrm{ if }x < y
		               \end{array}\right.$
	 \item $\D(x)=\left\{\begin{array}{ll}
		                1 & \textrm{ if }x=0\\
						0  & \textrm{ if }x\neq 0
		               \end{array}\right.$
	 \item $k(x,y)=|x-y|$
	 \item $E(x,y)=\left\{\begin{array}{ll}
		                1 & \textrm{ if }x=y\\
						0  & \textrm{ if }x\neq y
		               \end{array}\right.$
	\end{enumerate}
\item Summation and Products
	\begin{enumerate}
	 \item Let $f^{(2)}:\N^2\to\N$. We define $F^{(2)}$ and $G^{(2)}$ by 
	$$F(x,y)=\sum_{k=0}^y f(x,k)$$
	$$G(x,y)=\prod_{k=0}^y f(x,k)$$
	Show that $F$ and $G$ are in $\PRF$.
	\item More general, let $f^{(k+1)}\in\PRF$. We define $F^{(k+1)}$ and $G^{(k+1)}$ by 
	$$F(X,y)=\sum_{k=0}^y f(X,k)$$
	$$G(X,y)=\prod_{k=0}^y f(X,k)$$
	where $X$ is a $k$-tuple. Show that $F$ and $G$ are in $\PRF$.
	\end{enumerate}
 \item Let $f^{(1)}\in\PRF$. We define a new function $F^{(2)}$, called {\em power function of $f$}, as 
$$F(x,y)=(\underbrace{f\circ f\circ\dots\circ f}_{y\textrm{ times}})(x)$$
	or more formally, 
	$$F(x,y)=\left\{\begin{array}{ll}
	                x & \textrm{ if }y=0\\
					(f\circ F)(x,y-1)	& \textrm{ if }y>0
	                \end{array}\right.$$
	Notation: $F(x,y)=f^y(x)$.
	\begin{enumerate}
	 \item Show that $\Sigma(x,y)=s^y(x)$.
	 \item Show that if $f\in\PRF$, then $F\in\PRF$.
	 \item Write the function $\dif$ using the power function.
	\end{enumerate}

\subsection*{Primitive recursive sets}

Reminder: Let $k\in\mathbb{N}$. A subset $A\subseteq\N^k$ is said to be a primitive recursive set ($A\in\PRS$) if its characteristic function $\chi_A:\N^k\to\mathbb{N}$ is primitive recursive.
\item Show that every unitary subset of $\N$ is in \PRS.

\item Show that if $A,B\subseteq\N$ are in $\PRS$, then $A\cup B$, $A\cap B$ and $\N\setminus A$ are in $\PRS$.

\item Show that every finite subset of $\N$ is in $\PRS$.

\item Repeat the previous three exercises considering subsets of $\N^k$ with $k\in\mathbb{N}$.

\item Show that the set of even numbers is in $\PRS$.

\item Show that the set of numbers multiple of $3$ 	is in \PRS.

{\em Tip:} Show that the function $r_3:\N\to\N$ which takes a natural number and outputs the rest of its division by $3$ is in $\PRF$. Then write the characteristic function of the set of multiple of $3$ in terms of $r_3$.

\subsection*{Primitive recursive relations}

Reminder: A relation $R\subseteq\N\times\N$ is said to be a primitive recursive relation ($R\in\PRR$) if it is in $\PRS$.
\item Show that $=$, $\neq$, $\leq$ and $>$ are in $\PRR$.
\item Prove that if $R,S\in\PRR$, then the following relations are also in $\PRR$
	\begin{enumerate}
	 \item $xTy = xRy\wedge xSy$
	 \item $xUy = xRy \vee xSy$
	 \item $x(\neg R)y=\neg(xRy)$
	\end{enumerate}
\item Looking at the last exercises, is there any other way to prove $=, >\in\PRR$?

\item Let $R\in\N\times\N$. We define $\bigwedge R$ and $\bigvee R$ as follows.
	$$x(\bigwedge R)y = \forall k\in\N\bullet 0\leq k\leq y\Rightarrow xRk$$
	$$x(\bigvee R)y = \exists k\in\N\bullet 0\leq k\leq y\wedge xRk$$
	Show that if $R$ is in $\PRR$, then $\bigwedge R$ and $\bigvee R$ are also in $\PRR$.

\subsection*{Extra}
\item Show that the following function is primitive recursive.
$$f(x)=\left\{\begin{array}{ll}
		x^2	& \textrm{ if }x\textrm{ is multiple of }3\\
		x+3 & \textrm{ if }x\textrm{ has a rest of }1\textrm{ when dividing by }3\\
		x!		& \textrm{ if }x\textrm{ has a rest of }2\textrm{ when dividing by }3
             \end{array}\right.$$
\item Show that the divisibility relation between natural numbers is in \PRR.

{\em Tip:} Define the family of functions $r_a^{(1)}$ for $a=1,2,\dots$ such that $r_a^{(1)}(n)$ outputs the rest of the division of $n$ by $a$. Then write the characteristic function of the relation in terms of those functions.
\end{enumerate}

\end{document}
