Primitive recursive functions and sets (i) Show that the set of Fibonnaci numbers is a primitive recursive set.
(ii) Show that there is not a "minimal non-recursive set". That is to show that for all $A$ non-recursive there is a $B \subsetneq A$ such that $B$ is non-recursive.
(iii) Show that tha subset $A \subseteq \mathbb{N}$ is finite if and only if every subset of $A$ is recursive.
My attemp:
(i) I have consider the function definied by recursion $\mathcal{F}: \mathbb{N} \longrightarrow \mathbb{N}$:
$$\mathcal{F}(x) = \left\{ \begin{array}{l}
\mathcal{F}(0) = \mathcal{F}(1)  = 1\\
\mathcal{F}(n+1) = \mathcal{F}(n+2) + \mathcal{F}(n)\end{array}\right.$$
Then I tried to reduce it to a recursion but I fail because I have "two base cases" and recursion only uses one of them. I found on the web a function called paring function. I think is helpfull because turns two naturals into one and is primitive recursive.
(ii) I think I should go togh contradition. want should I suppose? I have two options:

*

*Let A recursive set. Suppose that for all set $B$, $A \subseteq B$ or $B$ is recursive.

*Suppose that exists a set $A$ shuch that:


*

*$A$ is recursive or

*exists $B$ such that $B \subsetneq A$ and $B$ is non-recursive.

(iii) Let $ A \subseteq \mathbb{ N} $. We test by double implication:
$ (\Rightarrow) $ Suppose $ A $ is finite, we want to see that every subset of $A $ is recursive. For this we consider an arbitrary subset of $ A $, $ B $. Since again this set is finite, we can consider a numbering with indices $ I = \{1,2, \cdots, n \} $:
$$ B = \{a_{i} \}_{i = 1}^{n} \text{ with } i \in I $$
Notice that its characteristic function given by:
$$ \ chi_{B} (x) = \left \{\begin{array}{r c l}
                1 & \text { if } & x \in B \\
                0 & \text { if } & x \not\in B
            \end{array} \right. $$
Let's see that this function is recursive. For this, it should be noted that:
$$ \chi_{B} (x) = \prod_{i = 1}^{n} \left[\chi_{=} (x \,,\, a_{i}) \right] $$
Since $ \chi_{=} $ and the finite product are recursive functions and the function $ \chi_{B} $ is being considered as a composition of these we can say that $ \chi_{B} $ is recursive. Just as you wanted to see.
$( \Leftarrow) $ To test this direction, the counterpossitive asociated with this direction says:
"If $ A $ is an infinite set then there is a subset $ B $ of $ A $ that is non-recursive "
So, suppose $ A $ is infinite, we want to see that there exists a subset of $ A $ that is not recursive. [Here I die!]
Can you help me, I feel I am very near to the solution!
 A: *

*Yes, the pairing function accomplishes what you need.

*Just delete any single element $x_0\in A$ from $A$, and the resulting $B=A-\{x_0\}$ will be non-recursive... otherwise you could construct a decision procedure for $A$ by taking the decision procedure for $B$ and then additionally checking that the number in question is not $x_0.$

*The forward direction is much simpler: any subset of a finite set is finite, hence recursive. You are correct that the crux of the other direction is to show that any infinite set $A$ has a non-recursive subset. If $A$ is non-recursive, we're done, so assume it is recursive. Then there is a computable bijection $f:\mathbb N\to A.$ (Since $A$ is recursive, it is recursively enumerable. Run the enumeration algorithm till $n$ distinct elements have come off, then return the $n$-th distinct element.) Then let $X$ be any non-recursive subset of $\mathbb N.$ Then $f(X)$ is a nonrecursive subset of $A,$ since from a decision procedure for $f(X)$ you could get a decision procedure for $X$ as follows: given $n$, compute $f(n)$ and then decide if it is in $f(X)$ (which decides whether $n\in X$ faithfully, since $f$ is a bijection).

