Set of Sequence Codes is Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\operatorname{Seq}$ be the set of all code numbers of finite sequences in $\N$.

Then $\operatorname{Seq}$ is primitive recursive.


Proof

By the definition of a primitive recursive set, it is sufficient to show that the characteristic function $\chi_{\operatorname{Seq}}$ of $\operatorname{Seq}$ is primitive recursive.

Let $p: \N \to \N$ be the prime enumeration function.

Let $\map {\operatorname{len} } n$ be the length of $n$.

We note that $\map {\chi_{\operatorname{Seq}} } n = 1$ if and only if $\map p y$ divides $n$ for $1 \le y \le \map {\operatorname{len} } n$.

That is, if and only if $\map {\operatorname{div} } {n, \map p y} = 1$ for $1 \le y \le \map {\operatorname{len} } n$, where $\operatorname{div}$ is the divisor relation.

We then see that $\map {\operatorname{div} } {n, \map p y} = 1$ for $1 \le y \le \map {\operatorname{len} } n$ if and only if their product equals $1$.

So we can define $\chi_{\operatorname{Seq}}$ by:

$\map {\chi_{\operatorname{Seq}} } n = \begin{cases}

\ds \prod_{y \mathop = 1}^{\map {\operatorname{len} } n} \map {\operatorname{div} } {n, \map p y} & : n > 1 \\ 0 & : \text{otherwise} \end{cases}$


Then we define $g: \N^2 \to \N$ as:

$\map g {n, z} = \begin{cases}

1 & : z = 0 \\ \ds \prod_{y \mathop = 1}^z \map {\operatorname{div} } {n, \map p y} & : z \ne 0 \end{cases}$

We then apply Bounded Product is Primitive Recursive to the primitive recursive function $\map {\operatorname{div} } {n, \map p y}$, and see that $g$ is primitive recursive.


Finally, we have that:

$\map {\chi_{\operatorname{Seq}} } n = \begin{cases}

\map g {n, \map {\operatorname{len} } n} & : n > 1 \\ 0 & : \text{otherwise} \end{cases}$ is obtained by substitution from:

So $\chi_{\operatorname{Seq}}$ is primitive recursive.

Hence the result.

$\blacksquare$

Retrieved from "https://proofwiki.org/w/index.php?title=Set_of_Sequence_Codes_is_Primitive_Recursive&oldid=527758"