5
$\begingroup$

Problem Statement

Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$

Yes, this is a homework question.

My Work

I proved that there are infinite number of definitions using the following construction

$$g_k(n) = \underbrace{P_{1}^1(P_{1}^1( \dots( P_{1}^1}_{k \text{ times}}(f(n))\dots), \ \forall \ k \in \mathbb{N}$$

Here $P_1^1$ is the projection basis function which picks the $1^{\text{st}}$ element from a vector of size $1$

Now $k$ is unbounded and we will get an equivalent definition for $f$ for each $k$

Now the issue is that this is not the only way to construct an infinite number of equivalent definitions i.e. I could have also use the multiplication operator and multiplied the output of $f$ by 1 as many times as I liked.

How can I show that there is a $1-1$ correspondence of the set of all primitive recursive definitions with the set of naturals numbers? Unlike bit strings, I am unable to comprehend in what way I should assign some number to each function. In fact I don't even know in how many ways can I create equivalent definitions, so how can I even start to enumerate these functions?

Any hints?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
1
$\begingroup$

I proved that there are infinite number of definitions using the following construction

That works in principle, but be careful about what $f$ is in that term, formally.

Now the issue is that this is not the only way to construct an infinite number of equivalent definitions

Right you are!

How can I show that there is a 1−1 correspondence of the set of all primitive recursive definitions with the set of naturals numbers?

You don't have to do this explicitly. Use that the class of countable sets is closed against taking subsets.

Improve this answer
$\endgroup$
4
  • $\begingroup$ When you say closed against taking subsets, do you mean that a) if I can show that a subset of a set is countably infinite then the set is also countable or b) if the set is countably infinite then every subset is also countably infinite? $\endgroup$ Commented Mar 29, 2016 at 13:41
  • $\begingroup$ a) and b) are clearly false and not what I wrote. "$A \subseteq U$ is closed against $f : A^k \to U$" means that if $a_1, \dots, a_k \in A$ then $f(a_1, \dots, f_k) \in A$. (Or, similarly, if $f : A^k \to 2^U$ then $f(\dots) \subseteq A$.) $\endgroup$ Commented Mar 29, 2016 at 14:31
  • $\begingroup$ Sorry, but I am not sure if I follow your train of thought :/ In your comment above, is $U$ the set of all primitive recursive functions and is $A$ a subset of definitions like the one given by $g_k(n)$ in my question? If yes, then I don't see how it is allowing me to do a proof. Also, in the first part, the function is mapping from $A^k \to U$ but in the second part $A^k \to 2^U$. Is that a typo? $\endgroup$ Commented Mar 29, 2016 at 15:22
  • $\begingroup$ @BanachTarski Sorry, but this is not the place to discuss basic mathematical terminology and notation. See here (or any basic mathematics textbook, I guess). $\endgroup$ Commented Mar 29, 2016 at 16:07
1
$\begingroup$

Suppose we are given a primitive recursive function $f$. Let us define the following sets: \begin{align*} A &= \text{"the set of all finite strings of symbols"} \\ B &= \text{"the set of all finite strings of symbols that define a primitive recursive function"} \\ C &= \text{"the set of all finite strings of symbols that define $f$"} \end{align*} Obviously we have $$C \subseteq B \subseteq A$$ You already know that $A$ is countably infinite. In your solution you constructed a countably infinite subset of $C$. Therefore, all three sets $A$, $B$ and $C$ are countably infinite. This is so because:

Theorem: If $X \subseteq A \subseteq Y$ and both $X$ and $Y$ have the same cardinality then $A$ has that cardinality as well.

Improve this answer
$\endgroup$
0
$\begingroup$

For any set of functions $X$, let $f(X)$ be the set of functions including

  1. all the initial functions
  2. the (generalized) composition of any functions in $X$
  3. the functions obtained from any $f,g \in X$ by applying the primitive recursion scheme on $f,g$.

If we consider $$ \emptyset \cup f(\emptyset) \cup f(f(\emptyset)) \cup ... = \bigcup_{n \in \mathbb N} f^n(\emptyset) $$ we build the exactly the set of primitive recursion functions. This is easy to check (and is also an immediate application of Kleene's fixed point theorem in domain theory).

Now, every set $f^n(\emptyset)$ is countable, and a countable union of countable set is also countable.

Note that this argument is applicable not only to the definition of the PR functions set, but to many inductive definitions as well. Indeed, we only need that $f(X)$ is countable when $X$ is such. In computer science, this happens very frequently.

Improve this answer
$\endgroup$
0
$\begingroup$

Just define a function $a(n)$ that adds 1 to non-zero (i.e., $a(n) = \operatorname{if} n = 0 \operatorname{then} 0 \operatorname{else} n + 1$) and another one $s(n) = \operatorname{if} n = 0 \operatorname{then} 0 \operatorname{else} n - 1$. For any given function $f(n)$, there are an infinite collection of functions computing the same result, like $s(a(f(\ldots))$, where the $s(a(\ldots))$ game can be repeated as often as you like.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.