A function agreeing with a primitive recursive function at all but finitely many points is primitive recursive

Question

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.

Answer 1

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.