Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more elegant proof than what I have attempted, assuming my proof is correct (it may not be).
The problem is stated as in the title of this post, on page 32 problem 1.19.
We are told, btw, that a function f is increasing when f(x) < f(x+1) for all x. I add a definition that Soare does not: we say f enumerates a set A iff A = {f(0), f(1), . . .}.
PROOF:
SUBPROOF 1: Left to right direction of "iff".
Let A be infinite, and recursive. Thus
$\rightarrow$ A and A* (read complement of A) are recursively enumerable (r.e. hereon) -- by complementation theorem 1.12, page 30.
$\rightarrow$ (A* = $\emptyset$) v (A = Range of f*, where f* is total, recursive) -- By listing theorem 1.8 page 29.
$\rightarrow$ (A = $\emptyset$) v (A = Range of f, where f is total, recursive) -- Ditto.
$\rightarrow$ A $\neq$ $\emptyset$ -- Since A is infinite by hypothesis
$\rightarrow$ A = Range of f s.t f is total and recursive -- disjunctive syllogism, previous two lines
$\rightarrow$ A = {f(0), f(1), . . .} -- A is the range of f
$\rightarrow$ Suppose A* = $\emptyset$
$\rightarrow$ A* is r.e.
$\rightarrow$ Suppose on the other hand A* $\neq$ $\emptyset$.
$\rightarrow$ A* = Range of f* for f* recursive, total. -- disjunctive syllogism, last line and second line.
$\rightarrow$ A* = {f*(0), f*(1), . . . } -- A* is the range of f*
Hence either way, there is an r.e. function which enumerates A, A*, so that A must be the range of a recursive f.
END SUBPROOF 1.
SUBPROOF 2: Right to left direction of the "iff".
Let A be infinite, and let f be a recursive function s.t. f is increasing, and let A = Range of f. Need to show A = {y : f(x) = y} forms a recursive set. To this end, suppose otherwise. Thus there is some y $\in$ A for which f is undefined, i.e. for arbitrary choice of x $\in$ A under f, y$\ne$ f(x). Hence y > f(x). But then f is increasing for all x, y $\in$ A, so that y = f(x + 1); contradiction.
Right?
END SUBPROOF 2.
END PROOF.