4
$\begingroup$

Show that if $f:\mathbb{N} \rightarrow \mathbb{N}$ is primitive recursive, $A \subseteq \mathbb{N}$ is a finite set, and $g$ is a total function agreeing with $f$ at every point not in $A$, then $g$ is primitive recursive.

This is exercise 10.17 from Introduction to Languages and the Theory of Computation (4th Edition) by John Martin.


My train of thought:

I have $g$ defined as:

$$ g(n) = \begin{cases} f(n),&\text{if }n\notin A\\ w(n),& \text{if }n \in A \end{cases}$$ where $w(n):A \rightarrow \mathbb{N}$ is an unknown function, because the exercise doesn't give me a complete definition of $g$, yet I need to prove $g$ is primitive recursive.

I need to prove $w$ is primitive recursive in order to prove $g$ is primitive recursive. The fact that $w$ is defined only on the finite set $A$ makes it primitive recursive? If so, why?


EDIT1:

If I assume $A$ as a primitive recursive set with characteristic function $\chi_{A}:\mathbb{N} \rightarrow \{0,1\}$: $$ \chi_{A}(n) = \begin{cases} 1,&\text{if }n=k_{1}\\ 1,&\text{if }n=k_{2}\\ \vdots &\vdots \\ 1,&\text{if }n=k_{n}\\ 0,& \text{otherwise} \end{cases}$$ where $\{k_{1},k_{2},...,k_{n}\} = A$.

Then I could define $g$ as $$g(n) = w(n)\chi_{A}(n)+f(n)(1-\chi_{A}(n)).$$

But I still have the unknown $w(n)$ which I don't know if it's primitive recursive.


EDIT2:

If $A = \{k_{1},k_{2},...,k_{n}\}$, I can define predicates $P_1, P_2, \ldots, P_k, P_f$ by $$ P_{z}(i) = \begin{cases} \text{true},&\text{if }i=k_{z}\\ \text{false},&\text{otherwise} \end{cases}$$ for $z=1,2,...,n$, and $$ P_{f}(i) = \begin{cases} \text{true},&\text{if }\neg(P_{1}(i)\vee P_{2}(i) \vee ... \vee P_{n}(i))\\ \text{false},&\text{otherwise.} \end{cases}$$

Defining $$ g(i) = \begin{cases} l_{1},&\text{if }P_{1}(i)\\ l_{2},&\text{if }P_{2}(i)\\ \vdots & \vdots \\ l_{n},&\text{if }P_{n}(i)\\ f(i),& \text{if }P_{f}(i) \end{cases}$$ where $l_1, l_2 , \ldots , l_n \in \mathbb{N}$.

The constant functions are primitive recursive, and $f$ is primitive recursive. The predicates $P_{1},P_{2},\ldots,P_{n}$ and $P_{f}$ are primitive recursive. I can apply the following theorem from the text (p.336) to conclude that $g$ is primitive recursive:

Theorem 10.7 Suppose $f_{1},f_{2},\ldots,f_{k}$ are primitive recursive function from $\mathbb{N}^{m}$ to $\mathbb{N}$, $P_{1},P_{2},...,P_{k}$ are primitive recursive $n$-place predicates, and for every $X\in \mathbb{N}^{n}$, exactly one of the conditions $P_{1}(X)\ldots,P_{k}(X)$ is true. Then the function $f: \mathbb{N}^{m} \rightarrow \mathbb{N}$ defined by $$ f(X)=\begin{cases} f_{1}(X),&\text{if }P_{1}(X) \text{ is true}\\ f_{2}(X),&\text{if }P_{2}(X) \text{ is true}\\ \vdots & \vdots \\ f_{k}(X),&\text{if }P_{k}(X) \text{ is true} \end{cases}$$ is primitive recursive.

$\endgroup$
  • $\begingroup$ Can you prove that $A$ is a primitive set so that it's characteristic function is primitive recursive and then construct $g(n)$ via addition of weighted characteristic functions? $\endgroup$ – JSchlather Oct 6 '13 at 5:42
  • $\begingroup$ @JSchlather The only information I have of A is that it is a finite set. I think I cannot prove A is a primitive recursive set. I can assume A is one, but even if I assume that, see(EDIT1). $\endgroup$ – Anna Oct 6 '13 at 6:41
1
$\begingroup$

Instead of viewing your function $g$ as some weird combination of $f$ and an unknown function $w$, look at the set $A$ as $\{ k_1, \ldots , k_n \}$, and now look at the function $g$ as being of the form $$g(i) = \begin{cases}\ell_1, &\text{if }i = k_1 \\ \vdots \\ \ell_n, &\text{if }i = k_n \\ f(i), &\text{otherwise}\end{cases}$$ (for some natural numbers $\ell_1 , \ldots , \ell_n$).

Now it almost looks like an induction: Show that a function which differs from a primitive recursive function in at most one place is itself primitive recursive.

  • If $f : \mathbb{N} \to \mathbb{N}$ is primitive recursive, $k \in \mathbb{N}$, and $g : \mathbb{N} \to \mathbb{N}$ is such that $g(i) = f(i)$ for all $i \neq k$, then consider the singleton set $\{ k \}$, which is primitive recursive, and so its characteristic function $\chi = \chi_{\{k\}}$ is primitive recursive. If $g(k) = \ell$, note that the constant function $c$ defined by $c(i) = \ell$ is primitive recursive. Then $$g(i) = \chi(i) c(i) + (1 - \chi(i)) f(i).$$ You should have theorems showing that functions combined in this way from primitive recursive function are primitive recursive.

After the last edit to the question, it seems that Theorem 10.7 does all the work I suggested above.

  • All finite sets are primitive recursive, so the predicates $P_1 , \ldots , P_n$ you describe are primitive recursive.
  • Primitive recursive predicates are closed under the basic Boolean operations, so $P_f \equiv \neg ( P_1 \vee \cdots \vee P_n )$ is primitive recursive.
  • It is easy to show that exactly one of $P_1(i) , \ldots P_n(i)$ or $P_f(i)$ is true for each $i$ (assuming that your enumeration of $A$ lists each element exactly once).
  • All constant functions are primitive recursive, and we are given that $f$ is primitive recursive.

Then the theorem automatically gives that the function $g$ described above is primitive recursive.

$\endgroup$
  • $\begingroup$ Thanks!. Check EDIT2. I think it's a valid proof. I defined g your way, but with predicates in order to use a theorem I found. $\endgroup$ – Anna Oct 7 '13 at 4:20
  • $\begingroup$ @Anna: So in edit 2 you are essentially using the fact that all constant functions are PR, as well as the fact finite sets (really singleton sets) are PR. And then Theorem 10.7 does all the hard work. Looks good! $\endgroup$ – user642796 Oct 7 '13 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.