Range or Domain of Primitive Recursive Function?

895 Views Asked by At

We are given that $A$ is R.E set. I think all of the following are equivalent to that:

(1) A is the range of one primitive recursive function,
(2) A is the domain of one strictly increasing recursive function,
(3) A is the range of one strictly increasing recursive function, and
(4) $\{ x \in A | x=2k \}$ is a R.E set.

My problem is: we say (set) $A$ is recursive iff $|A|$ is finite or is the range of one strictly increasing recursive function. Why does my TA says the third sentence is incorrect?

1

There are 1 best solutions below

19
On BEST ANSWER

WLOG we might assume $A$ is not finite and $0\in A$.

We take the definition of r.e. sets to be a set is r.e. if its characteristic function is partial recursive.

Then A set is r.e. iff A is a domain of a strictly increasing partial recursive function.

Proof: (only if) $A=\Phi_e$, define the strictly increasing partial recursive function $f(n)=n, if \Phi_e(n)\downarrow=1$, otherwise undefined. (if) The characteristic function for A would just be $\chi_A(n)=1$ if $f(n)\downarrow$, which is partial recursive.

$A$ is $r.e.$ iff $A$ is the range of a primitive recursive function (i.e. (1)).

Proof:

(if) Suppose $A=range(f)$ where $f$ is primitive recursive, then $y\in A \Leftrightarrow\exists n f(n)=y$ so $A$ is r.e. (Only if) If $A$ is r.e., let $e$ be the index of partial recursive function that computes $A$, i.e. $A=\Phi_e$. Then A would be the range of the following primitive recursive function: $f: \omega\times \omega \to \omega$ such that $f(n,s)=n, if \ \Phi_{e,s}(n)\downarrow=1; 0, otherwise$.

It is not clear what you mean by the domain of a recursive function, as normally recursive functions are assumed to be total. So I think you mean partial recursive functions. Being domain of a partial recursive function does give you equivalent characterisation of r.e sets. However, (3) is wrong since it says that $A$ is recursive (range of an increasing total recursive function). Halting set ($\{e: \varphi_e(e)\downarrow\}$) is a non-recursive r.e. set.

Added: A is r.e. $\Leftrightarrow$ (1) $\Leftrightarrow$ (2); A is recursive $\Leftrightarrow$ (3). I don't understand the $>x=2k$ part in (4), but you can infer from here.

Well (4) is a strict consequence of r.e (1) (2) are equivalent to r.e Under the assumption of r.e They are equivalent for trivial reasons.