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:

1. $A$ is recursive or
2. 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!