CS486 Problem Set 10 DUE: 4/24/03
1.
We show how to express the following functions as $\mu$-recursive functions.
(a)

\begin{displaymath}const_k(x) = k \quad\quad \mbox{for arbitrary $k \in \mathbb{N}$} \end{displaymath}

Define

\begin{displaymath}const_k \equiv \mathsf{pr}(c_k, \pi^2_2) \end{displaymath}

(b)

\begin{displaymath}exp(x,y) = x^y \end{displaymath}

Define

\begin{displaymath}add \equiv \mathsf{pr}(\pi^1_1, s \circ \pi^3_3) \end{displaymath}

Define

\begin{displaymath}mul \equiv \mathsf{pr}(const_0, add \circ \pi^3_1,\pi^3_3) \end{displaymath}

Define

\begin{displaymath}exp \equiv \mathsf{pr}(const_1, mul \circ \pi^3_1,\pi^3_3) \end{displaymath}

(c)

\begin{displaymath}Sum_f(y) = \sum_{i=0}^y f(i) \end{displaymath}

Define

\begin{displaymath}Sum_f \equiv \mathsf{pr}(f \circ c_o, add \circ (f \circ s \circ \pi^2_1),\pi^2_2) \end{displaymath}

2.
We show how to express the following functions in Peano arithmetic. First, define

\begin{displaymath}x\boldsymbol{<}y \equiv ({\exists }{z}){(x\boldsymbol{+}(z\boldsymbol{+}\mathbf{1})\boldsymbol{=}y)} \end{displaymath}


\begin{displaymath}x\boldsymbol{\leq}y \equiv {(x\boldsymbol{<}y)}{\lor }{(x\boldsymbol{=}y)} \end{displaymath}


\begin{displaymath}x\boldsymbol{\vert}y \equiv ({\exists }{z}){(x\boldsymbol{*}z\boldsymbol{=}y)} \end{displaymath}

(a)

\begin{displaymath}div(x,y) = x \div y \end{displaymath}

Define

\begin{displaymath} R_{div}(x,y,z) \equiv ({\exists }{a}){({(a\boldsymbol{<... ...{\land }{(x\boldsymbol{=}z\boldsymbol{*}y\boldsymbol{+}a)})} \end{displaymath}

(b)

\begin{displaymath}divides(x,y) = \left\{ \begin{array}{ll} 1 & \mbox{if $x$\ divides $y$} \\ 0 & \mbox{otherwise} \end{array} \right. \end{displaymath}

Define

\begin{displaymath} R_{divides}(x,y,z) \equiv {({(x\boldsymbol{\vert}y)}{\su... ...ldsymbol{\vert}y)}}{\supset }{(z\boldsymbol{=}\mathbf{0})})} \end{displaymath}

(c)

\begin{displaymath}prime(x) = \left\{ \begin{array}{ll} 1 & \mbox{if $x$\ is a prime number} \\ 0 & \mbox{otherwise} \end{array} \right. \end{displaymath}

Define

\begin{displaymath} R_{prime}(x,z) \equiv \begin{array}[t]{c} ({(({\forall... ...}})})}{\supset }{(z\boldsymbol{=}\mathbf{0})}) \end{array} \end{displaymath}

3.
We prove $({\forall }{x}){({\sim }{(x\boldsymbol{+}\mathbf{1}\boldsymbol{=}x)})}$ in Peano arithmetic. We first prove a useful lemma:
lemma1: $({\forall }{x,y}){({(x\boldsymbol{=}y)}{\supset }{(x\boldsymbol{+}\mathbf{1}\boldsymbol{=}y\boldsymbol{+}\mathbf{1})})}$

\begin{displaymath} \begin{array}{cll} & x\boldsymbol{=}y \\ \land & ... ... \mbox{\texttt{add-base}[$y$],\texttt{subst}} \end{array} \end{displaymath}

thm: $({\forall }{x}){({\sim }{(x\boldsymbol{+}\mathbf{1}\boldsymbol{=}x)})}$

\begin{displaymath} \begin{array}{cll} & & \mbox{\texttt{base}[$x$]} \\ ... ...\boldsymbol{+}\mathbf{1}$,$x$],\texttt{subst}} \end{array} \end{displaymath}

4.
We show that the following laws are not valid in $\mathcal{Q}$.
(a)
$({\forall }{x,y}){(x\boldsymbol{+}y\boldsymbol{=}y\boldsymbol{+}x)}$
(b)
$({\forall }{x,y,z}){(x\boldsymbol{+}(y\boldsymbol{+}z)\boldsymbol{=}(x\boldsymbol{+}y)\boldsymbol{+}z)}$
(c)
$({\forall }{x}){(\mathbf{0}\boldsymbol{+}x\boldsymbol{=}x)}$
(d)
$({\forall }{x,y}){(x\boldsymbol{*}y\boldsymbol{=}y\boldsymbol{*}x)}$
(e)
$({\forall }{x}){(\mathbf{0}\boldsymbol{*}x\boldsymbol{=}\mathbf{0})}$
Consider the following model of $\mathcal{Q}$:

\begin{displaymath} \begin{array}{c} U = \mathbb{N}\cup \{ \omega, \zeta \} ... ...mega & \omega & \omega \\ \hline \end{array} \end{array} \end{displaymath}

We show that the following laws are not valid in this model:
(a)
$({\forall }{x,y}){(x\boldsymbol{+}y\boldsymbol{=}y\boldsymbol{+}x)}$

\begin{displaymath} \omega\boldsymbol{+}\mathbf{0} = \omega \neq \zeta = \mathbf{0}\boldsymbol{+}\omega \end{displaymath}

(b)
$({\forall }{x,y,z}){(x\boldsymbol{+}(y\boldsymbol{+}z)\boldsymbol{=}(x\boldsymbol{+}y)\boldsymbol{+}z)}$

\begin{displaymath} \omega\boldsymbol{+}(\mathbf{0}\boldsymbol{+}\omega ) =... ...a = (\omega\boldsymbol{+}\mathbf{0})\boldsymbol{+}\omega \end{displaymath}

(c)
$({\forall }{x}){(\mathbf{0}\boldsymbol{+}x\boldsymbol{=}x)}$

\begin{displaymath} \mathbf{0}\boldsymbol{+}\omega = \zeta \neq \omega \end{displaymath}

(d)
$({\forall }{x,y}){(x\boldsymbol{*}y\boldsymbol{=}y\boldsymbol{*}x)}$

\begin{displaymath} \omega\boldsymbol{*}\mathbf{0} = \mathbf{0} \neq \omega = \mathbf{0}\boldsymbol{*}\omega \end{displaymath}

(e)
$({\forall }{x}){(\mathbf{0}\boldsymbol{*}x\boldsymbol{=}\mathbf{0})}$

\begin{displaymath} \mathbf{0}\boldsymbol{*}\omega = \omega \neq \mathbf{0} \end{displaymath}

We show that the axioms of $\mathcal{Q}$ are satisfied by this model:
non-surjective:

\begin{displaymath}\omega\boldsymbol{+}\mathbf{1} = \zeta \neq \mathbf{0}\quad\quad \zeta\boldsymbol{+}\mathbf{1} = \omega \neq \mathbf{0}\end{displaymath}

injective:

\begin{displaymath} \begin{array}[t]{cl} & \omega\boldsymbol{+}\mathbf{1}\... ...omega \\ \supset & x\boldsymbol{=}\omega \end{array} \end{displaymath}


\begin{displaymath} \begin{array}[t]{cl} & \zeta\boldsymbol{+}\mathbf{1}\b... ...}\zeta \\ \supset & x\boldsymbol{=}\zeta \end{array} \end{displaymath}

nonzero:

\begin{displaymath} \begin{array}[t]{cl} & \omega\boldsymbol{+}\mathbf{1} ... ...\boldsymbol{+}\mathbf{1}\boldsymbol{=}\zeta )} \end{array} \end{displaymath}

add-base:

\begin{displaymath}\omega\boldsymbol{+}\mathbf{0} = \omega \quad\quad \zeta\boldsymbol{+}\mathbf{0} = \zeta \end{displaymath}

add-step:

\begin{displaymath} \begin{array}{c} \omega\boldsymbol{+}(j\boldsymbol{+}\ma... ...ldsymbol{+}\zeta )\boldsymbol{+}\mathbf{1} \\ \end{array} \end{displaymath}

mul-base:

\begin{displaymath}\omega\boldsymbol{*}\mathbf{0} = \mathbf{0}\quad\quad \zeta\boldsymbol{*}\mathbf{0} = \mathbf{0}\end{displaymath}

mul-step:

\begin{displaymath} \begin{array}{c} \omega\boldsymbol{*}(j\boldsymbol{+}\ma... ... \zeta\boldsymbol{*}\zeta \boldsymbol{+}\zeta \end{array} \end{displaymath}

5.
The function $A: \mathbb{N}^2 \to \mathbb{N}$ is defined recursively as follows:

\begin{displaymath} \begin{array}{rcl} A(0,0) & = & 1 \\ A(0,1) & = & 2 \... ...& = & 1 \\ A(n+1,y+1) & = & A(n, A(n+1, y)) \end{array} \end{displaymath}

We show that $A$ is $\mu$-recursive. First, define the function $F: \mathbb{N}^3 \to \mathbb{N}$ recursively as follows:

\begin{displaymath} \begin{array}{rcl} F (n,0,x) & = & 0 \\ F (n,m,0) & =... ... (n,m,x+1) & = & A (n - x + 1, F(n, m, x) - 1) \end{array} \end{displaymath}

We note that the evaluation of $A(n,m)$ only requires the evaluation of $A(x,y)$ where $0 \leq x \leq n$ and $0 \leq y \leq F(n,m,x)$. Recall that $\langle\rangle: \mathbb{N}^2 \to \mathbb{N}$ is the bijective encoding of pairs of numbers, defined as $\langle i,j\rangle \equiv j + (i+j)(i+j+1)/2$. Recall that $\star: \mathbb{N}^2 \to \mathbb{N}$ is the selection function, which yields $y_i$ for $\hat{y} \star i$. Define

\begin{displaymath}p \equiv \mathsf{pr}(c_0,\pi^2_1) \end{displaymath}


\begin{displaymath}sub \equiv \mathsf{pr}(\pi^1_1, p \circ \pi^2_2) \end{displaymath}


\begin{displaymath} F \equiv pr(const_0 \circ \pi^3_3, \\ \mathsf{pr}(\pi... ...4),\pi^5_2,\pi^5_3 ) \circ \pi^4_1,\pi^4_3,\pi^4_4,\pi^4_2 \end{displaymath}


\begin{displaymath} A(n,m) \equiv \mathsf{min} \left\{ z \left\vert \... ... \end{array} \right. \right\} \star \langle n,m\rangle \end{displaymath}

We calculate $A(4,4)$. We first prove the following:

\begin{displaymath}A(0, 0) = 1 \quad A(0, 1) = 2 \quad A(0, y) = y + 2\end{displaymath}

Obvious from the definition of $A$.

\begin{displaymath}A(1, 0) = 1 \quad A(1, y) = 2 * y\end{displaymath}

Proceed by induction on $y$. Note $A(1, 0) = 1$ by the definition of $A$. Note $A(1, 1) = A(0, A(1, 0)) = A(0, 1) = 2$ by the definition of $A$. Suppose $A(1, y) = 2 * y$ for $1 \leq y$. Note $A(1, y + 1) = A(0, A(1, y)) = A(0, 2 * y) = 2 * y + 2 = 2 * (y + 1)$ for $1 \leq y$.

\begin{displaymath}A(2, y) = 2^y\end{displaymath}

Proceed by induction on $y$. Note $A(2, 0) = 1$ by the definition of $A$. Suppose $A(2, y) = 2^y$ for $0 \leq y$. Note $A(2, y + 1) = A(1, A(2, y)) = A(1, 2^y) = 2 * 2^y = 2^{y+1}$ for $0 \leq y$.

\begin{displaymath}A(3, y) = 2\uparrow y = \begin{array}[t]{c} \underbrace{... ...dot^{\cdot^{\cdot^2}}}}} \\ \mbox{$y$\ times} \end{array}\end{displaymath}

Proceed by induction on $y$. Note $A(3, 0) = 1$ by the definition of $A$. Suppose $A(3, y) = 2\uparrow y$ for $0 \leq y$. Note $A(3, y + 1) = A(2, A(3, y)) = A(2, 2\uparrow y) = 2^{2\uparrow y} = 2\uparrow(y+1)$ for $0 \leq y$.

\begin{displaymath}A(4, y) = 2\uparrow\uparrow y = \begin{array}[t]{c} \und... ...parrow(\cdots\uparrow2))} \\ \mbox{$y$\ times} \end{array}\end{displaymath}

Proceed by induction on $y$. Note $A(4, 0) = 1$ by the definition of $A$. Suppose $A(4, y) = 2\uparrow\uparrow y$ for $0 \leq y$. Note $A(4, y + 1) = A(3, A(4, y)) = A(3, 2\uparrow\uparrow y) = 2\uparrow(2\uparrow\uparrow y) = 2\uparrow\uparrow(y+1)$ for $0 \leq y$.
Hence

\begin{displaymath} \begin{array}{rcl} A(4,4) & = & 2\uparrow\uparrow4 \\... ...\left(2^{16}\right) \\ & = & 2\uparrow65536 \end{array} \end{displaymath}


Juanita Heyerman 2003-04-30