CS486 Problem Set 10 DUE: 4/24/03

1.

We show how to express the following functions as $\mu$-recursive functions.

(a)

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

Define

$$const_k \equiv \mathsf{pr}(c_k, \pi^2_2)$$

(b)

$$exp(x,y) = x^y$$

Define

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

Define

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

Define

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

(c)

$$Sum_f(y) = \sum_{i=0}^y f(i)$$

Define

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

2.

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

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

$$x\boldsymbol{\leq}y \equiv {(x\boldsymbol{<}y)}{\lor }{(x\boldsymbol{=}y)}$$

$$x\boldsymbol{\vert}y \equiv ({\exists }{z}){(x\boldsymbol{*}z\boldsymbol{=}y)}$$

(a)

$$div(x,y) = x \div y$$

Define

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

(b)

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

Define

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

(c)

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

Define

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

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{array}{cll} & x\boldsymbol{=}y \\ \land & ... ... \mbox{\texttt{add-base}[$y$],\texttt{subst}} \end{array}$$

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

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

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{array}{c} U = \mathbb{N}\cup \{ \omega, \zeta \} ... ...mega & \omega & \omega \\ \hline \end{array} \end{array}$$

We show that the following laws are not valid in this model:

(a)

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

$$\omega\boldsymbol{+}\mathbf{0} = \omega \neq \zeta = \mathbf{0}\boldsymbol{+}\omega$$

(b)

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

$$\omega\boldsymbol{+}(\mathbf{0}\boldsymbol{+}\omega ) =... ...a = (\omega\boldsymbol{+}\mathbf{0})\boldsymbol{+}\omega$$

(c)

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

$$\mathbf{0}\boldsymbol{+}\omega = \zeta \neq \omega$$

(d)

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

$$\omega\boldsymbol{*}\mathbf{0} = \mathbf{0} \neq \omega = \mathbf{0}\boldsymbol{*}\omega$$

(e)

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

$$\mathbf{0}\boldsymbol{*}\omega = \omega \neq \mathbf{0}$$

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

non-surjective:

$$\omega\boldsymbol{+}\mathbf{1} = \zeta \neq \mathbf{0}\quad\quad \zeta\boldsymbol{+}\mathbf{1} = \omega \neq \mathbf{0}$$

injective:

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

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

nonzero:

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

add-base:

$$\omega\boldsymbol{+}\mathbf{0} = \omega \quad\quad \zeta\boldsymbol{+}\mathbf{0} = \zeta$$

add-step:

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

mul-base:

$$\omega\boldsymbol{*}\mathbf{0} = \mathbf{0}\quad\quad \zeta\boldsymbol{*}\mathbf{0} = \mathbf{0}$$

mul-step:

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

5.

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

$$\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}$$

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

$$\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}$$

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

$$p \equiv \mathsf{pr}(c_0,\pi^2_1)$$

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

$$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$$

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

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

$$A(0, 0) = 1 \quad A(0, 1) = 2 \quad A(0, y) = y + 2$$

Obvious from the definition of $A$.

$$A(1, 0) = 1 \quad A(1, y) = 2 * y$$

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$.

$$A(2, y) = 2^y$$

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$.

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

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$.

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

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{array}{rcl} A(4,4) & = & 2\uparrow\uparrow4 \\... ...\left(2^{16}\right) \\ & = & 2\uparrow65536 \end{array}$$