# Does every r.e. set containing the set of total recursive functions contain all partial recursive functions?

Any r.e. subset of $A\subseteq\mathbb{N}$ which contains the set $$\mathrm{Tot}=\{i\mid i\ \mbox{is an index of a total function } f\}$$ must, by a standard argument (of Post?) contain some partial recursive function indices.

Given a partial function index (and every total function), it's pretty easy to construct many others, e.g. an index for the function which returns $0$ on prime inputs and is undefined otherwise.

But must $A$ contain all partial functions? This seems like a simple question, but I can't find an argument one way or the other.

Edit: I'm equally (more, actually) interested in the case where $A$ is recursive, e.g., represents the programs from some programing language.

• It can contain all but finitely many partial functions, so that's one example. – Ariel May 30 '17 at 14:23
• When does a set contain a function? How are you encoding functions? – Yuval Filmus May 30 '17 at 14:36
• It is very likely that there are some recursive sets which do not contain all partial recursive functions, for example an appropriate cofinite set. But the answer depends on the definitions of the terms that you use. – Yuval Filmus May 30 '17 at 14:37
• "by a standard argument" -- because R is not recursively enumerable. That tells you something else: $A \setminus \mathrm{Tot}$ can't be decidable, for instance. In fact, it can't be co-r.e. either. – Raphael May 30 '17 at 16:46
• @YuvalFilmus I'm fixing some standard Gödel encoding $\phi$ of partial recursive functions. A function $f$ is in a set if there is some $i$ such that $\phi_i=f$ and $i$ is in the set. – cody May 30 '17 at 18:19

Take $A = \{i\ |\ \phi_i(0) \downarrow \}$. It is obviously r.e., and includes $\mathrm{Tot}$.
Yet, it does not contain any index of, say, the always-undefined function $u$. Nor indices for any recursive partial function which is undefined at $0$.
The Kleene set also works: $K = \{i\ |\ \phi_i(i) \downarrow \} \supset \mathrm{Tot}$, yet it does not contain any index for $u$. (And it is r.e.)
• @cody Unfortunately my crystal ball was out of service :-P Still, what about a programming language whose syntax is $(n,p)$ and whose semantics is: if the input is $0$ return $n$, otherwise run the (say, Java) program $p$ on the predecessor of the input. In this language, programs can never diverge at $0$. This is more-or-less a PL related to set $A$ above. – chi May 30 '17 at 18:32