Primitive recursive functions and sets

Question

(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!

Answer 1

1. Yes, the pairing function accomplishes what you need.
2. 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.$
3. 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).