[proofplan] We prove the two directions separately. $(\Rightarrow)$: If $X$ is computably enumerable with witness $\psi_X$ (computable partial function whose domain is $X$), modify $\psi_X$ so that when it converges it outputs its input rather than whatever $\psi_X$ would have output. The modified partial function $f$ has the same domain as $\psi_X$ (namely $X$) and its image is exactly $\operatorname{dom} \psi_X = X$. $(\Leftarrow)$: If $X = \operatorname{Im} f$ for some computable partial function $f$, write $X$ as a $\Sigma_1$ set. Using the timed simulation function of [Computability of the Configuration Function](/theorems/1818), the predicate "$f$ converges on $v$ in at most $\#u$ steps to output $w$" is computable, so the set $Z$ of triples $(w, v, u)$ satisfying it is computable. Collapsing $v$ and $u$ into one witness by a computable pairing gives a computable $Y$ with $X = p(Y) \in \Sigma_1$, and then [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824) converts back to computable enumerability. [/proofplan] [step:Fix definitions and the two equivalent descriptions of computable enumerability] Fix the course alphabet $\Sigma$ with distinguished accept letter $a \in \Sigma$, and write $\mathbb{W} = \Sigma^*$. The course fixes a computable coding of register machines $\operatorname{code} : \{\text{register machines}\} \to \mathbb{W}$; we write $f_{c, k} : \mathbb{W}^k \rightharpoonup \mathbb{W}$ for the arity-$k$ computable partial function computed by the machine with code $c$ (with $f_{c, k}$ everywhere-undefined when $c$ is not a valid code), as in the proof of [Halting Sets Are Computably Enumerable](/theorems/1822). A set $X \subseteq \mathbb{W}$ is *computably enumerable* iff $X = \varnothing$ or there is a computable partial function $\psi_X : \mathbb{W} \rightharpoonup \mathbb{W}$ with $\operatorname{dom} \psi_X = X$. The image of a partial function $f : \mathbb{W} \rightharpoonup \mathbb{W}$ is \begin{align*} \operatorname{Im} f &= \{f(v) : v \in \operatorname{dom} f\} = \{w \in \mathbb{W} : \exists v,\; v \in \operatorname{dom} f \text{ and } f(v) = w\}. \end{align*} Handle the empty case at the outset. $\varnothing = \operatorname{Im} f$ for $f : \mathbb{W} \rightharpoonup \mathbb{W}$ the everywhere-undefined partial function, which is computable (e.g., by any register machine that enters an immediate infinite loop on every input). Conversely, $\operatorname{Im}$ of the everywhere-undefined function is $\varnothing$, which is computably enumerable by convention. Both directions of the biconditional hold for $X = \varnothing$ via this one function, so from now on assume $X \neq \varnothing$. [/step] [step:Prove $(\Rightarrow)$: computably enumerable implies image of a computable partial function] Let $X \subseteq \mathbb{W}$ be computably enumerable and non-empty. Fix a computable partial function $\psi_X : \mathbb{W} \rightharpoonup \mathbb{W}$ with $\operatorname{dom} \psi_X = X$, witnessed by a register machine $M_{\psi_X}$. Define \begin{align*} f : \mathbb{W} &\rightharpoonup \mathbb{W}, \\ w &\mapsto \begin{cases} w & \text{if } \psi_X(w) \downarrow, \\ \uparrow & \text{if } \psi_X(w) \uparrow. \end{cases} \end{align*} [claim:$f$ is computable] A register machine $M_f$ witnessing $f$ runs as follows. On input $w$ in register $0$: (a) Save a master copy of $w$ in a scratch register $R$. (b) Run $M_{\psi_X}$ on $w$. If $M_{\psi_X}$ diverges, so does $M_f$; if it halts, its output (whatever it is in register $0$) is discarded. (c) Restore register $0$ from $R$ to recover $w$, erase all other registers, halt. The composition is exactly what L1 (closure under composition, Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)) allows: $f = \operatorname{id}_{\mathbb{W}} \circ \psi_X$ interpreted as "wait for $\psi_X$ to converge, then discard its value and output the original input". More formally, this is a composition $f = \pi_1^1 \circ (\psi_X, \pi_1^1)$ where $\pi_1^1 : \mathbb{W} \to \mathbb{W}$, $w \mapsto w$ is the projection (total computable by L0 in Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)) and $(\psi_X, \pi_1^1) : \mathbb{W} \rightharpoonup \mathbb{W}^2$ is the pair function which converges exactly when $\psi_X$ does, then outputs the pair $(\psi_X(w), w)$. The convergence behaviour matches the definition. [/claim] [claim:$\operatorname{dom} f = X$ and $\operatorname{Im} f = X$] By construction, $f(w) \downarrow$ iff $\psi_X(w) \downarrow$, so $\operatorname{dom} f = \operatorname{dom} \psi_X = X$. For the image: if $w \in \operatorname{Im} f$, then $w = f(v)$ for some $v \in \operatorname{dom} f = X$, and by the definition of $f$, $f(v) = v$, so $w = v \in X$. Conversely, if $v \in X$, then $f(v) = v$, so $v \in \operatorname{Im} f$. Hence $\operatorname{Im} f = X$. [/claim] This establishes $(\Rightarrow)$. [/step] [step:Prove $(\Leftarrow)$: image of a computable partial function implies computably enumerable — set up the $\Sigma_1$ description] Let $X = \operatorname{Im} f$ for some computable partial function $f : \mathbb{W} \rightharpoonup \mathbb{W}$. Fix a register machine $M$ of arity $1$ computing $f$, and let $c := \operatorname{code}(M)$ so that $f = f_{c, 1}$. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), it suffices to show $X \in \Sigma_1$, i.e. to exhibit a computable $Y \subseteq \mathbb{W}^2$ with $X = p(Y)$. *The timed simulation function.* By [Computability of the Configuration Function](/theorems/1818), there is a total computable function \begin{align*} t_{c, 1} : \mathbb{W} \times \mathbb{W} &\to \mathbb{W}, \\ (v, u) &\mapsto \begin{cases} a & \text{if } M \text{ on input } v \text{ halts in at most } \#u \text{ steps}, \\ \varepsilon & \text{otherwise}, \end{cases} \end{align*} where $\#u \in \mathbb{N}$ is the shortlex index of $u$ (see [Shortlex Is Order-Isomorphic to $\mathbb{N}$](/theorems/1815)). The key consequence: $f_{c, 1}(v) \downarrow$ iff $\exists u \in \mathbb{W},\ t_{c, 1}(v, u) = a$, because halting at some finite step $n$ is witnessed by any $u$ with $\#u \ge n$. Moreover, when $t_{c, 1}(v, u) = a$, we may extract the output $f_{c, 1}(v)$. By [Computability of the Configuration Function](/theorems/1818), the "output after $\#u$ steps" is itself a total computable function — explicitly, define \begin{align*} \mathrm{out}_{c, 1} : \mathbb{W} \times \mathbb{W} &\to \mathbb{W}, \\ (v, u) &\mapsto \begin{cases} f_{c, 1}(v) & \text{if } t_{c, 1}(v, u) = a, \\ \varepsilon & \text{if } t_{c, 1}(v, u) = \varepsilon \end{cases} \end{align*} (the value on non-halting $(v, u)$ can be chosen arbitrarily; the $\varepsilon$ choice is convenient). The function $\mathrm{out}_{c, 1}$ is total computable because we can read off the output register of the bounded simulation. Define the computable witness set of triples: \begin{align*} Z &:= \{(w, v, u) \in \mathbb{W}^3 : t_{c, 1}(v, u) = a \text{ and } \mathrm{out}_{c, 1}(v, u) = w\}. \end{align*} [/step] [step:Verify that $Z$ is computable] [claim:$Z$ is computable] The indicator $\mathbb{1}_Z(w, v, u)$ outputs $a$ if both $t_{c, 1}(v, u) = a$ and $\mathrm{out}_{c, 1}(v, u) = w$, else $\varepsilon$. The predicate $t_{c, 1}(v, u) = a$ is a computable one-letter equality test applied to a total computable function, hence computable (L2 in Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)). The predicate $\mathrm{out}_{c, 1}(v, u) = w$ is a computable word-equality test applied to the total computable $\mathrm{out}_{c, 1}$ and the input $w$, hence computable. Conjunction of two computable predicates is computable by L2. Hence $\mathbb{1}_Z$ is total computable, so $Z$ is computable. [/claim] [/step] [step:Collapse $(v, u)$ into a single witness and build the computable $Y$] $Z$ has two witness coordinates ($v$ and $u$) per input $w$; the $\Sigma_1$ definition requires a single witness coordinate. Use a computable pairing $\pi : \mathbb{W} \to \mathbb{W} \times \mathbb{W}$ as in Step 4 of the proof of [Computable Sets Are $\Delta_1$](/theorems/1825): a total computable bijection with total computable inverse and component extractions $\pi^{(0)}, \pi^{(1)} : \mathbb{W} \to \mathbb{W}$. Define \begin{align*} Y &:= \{(w, x) \in \mathbb{W}^2 : (w,\, \pi^{(0)}(x),\, \pi^{(1)}(x)) \in Z\}. \end{align*} [claim:$Y$ is computable] The indicator $\mathbb{1}_Y(w, x) = \mathbb{1}_Z(w, \pi^{(0)}(x), \pi^{(1)}(x))$ is the composition of the total computable $\mathbb{1}_Z$ (by Step 4) with the total computable pair $(\pi^{(0)}, \pi^{(1)})$ and the identity on $w$. By L1, it is total computable. [/claim] [/step] [step:Show $X = p(Y)$ and conclude $X \in \Sigma_1$, hence $X$ is computably enumerable] We verify $X = p(Y)$. $(\subseteq)$ Let $w \in X = \operatorname{Im} f_{c, 1}$. Fix $v \in \mathbb{W}$ with $f_{c, 1}(v) \downarrow = w$. Then $M$ halts on $v$ in some number of steps, say $n$. Pick any $u \in \mathbb{W}$ with $\#u \ge n$; such $u$ exists because $(\mathbb{W}, <) \cong (\mathbb{N}, <)$ is cofinal (by [Shortlex Is Order-Isomorphic to $\mathbb{N}$](/theorems/1815)). Then $t_{c, 1}(v, u) = a$ and $\mathrm{out}_{c, 1}(v, u) = f_{c, 1}(v) = w$, so $(w, v, u) \in Z$. Let $x := \pi^{-1}(v, u)$; then $(w, x) \in Y$, so $w \in p(Y)$. $(\supseteq)$ Let $w \in p(Y)$. Then there exists $x \in \mathbb{W}$ with $(w, x) \in Y$, i.e. $(w, \pi^{(0)}(x), \pi^{(1)}(x)) \in Z$. Set $v := \pi^{(0)}(x)$ and $u := \pi^{(1)}(x)$. From $(w, v, u) \in Z$ we have $t_{c, 1}(v, u) = a$, so $M$ halts on $v$ by step $\#u$, meaning $f_{c, 1}(v) \downarrow$; and $\mathrm{out}_{c, 1}(v, u) = w$ forces $f_{c, 1}(v) = w$ (because when the machine has halted, the $\mathrm{out}_{c, 1}$ value equals the computed function's value). Hence $w = f_{c, 1}(v) \in \operatorname{Im} f_{c, 1} = X$. Therefore $X = p(Y)$ with $Y$ computable (Step 5), so $X \in \Sigma_1$. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), $X$ is computably enumerable. [guided] We unpack the $(\Leftarrow)$ direction, which is the substantive half. *The question.* If $X = \{f(v) : v \in \operatorname{dom} f\}$ for some computable partial $f$, why is $X$ computably enumerable? *The intuitive answer.* Run $f$ on all $v \in \mathbb{W}$ and collect the outputs; the collection is $X$. This works as an *enumeration* idea, but the formalism of "computably enumerable = domain of a computable partial function" demands we produce an explicit such partial function whose domain is $X$ — not a procedure that outputs $X$. *The formal bridge: $\Sigma_1$.* The equivalence [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824) lets us reformulate "computably enumerable" as "$\Sigma_1$": $X$ is computably enumerable iff $X = p(Y)$ for some computable $Y \subseteq \mathbb{W}^2$. This shifts the task to constructing a computable $Y$ with $X = p(Y)$. *What should $Y$ capture?* Intuitively, $w \in X$ means "there exists some input $v$ on which $f$ converges to $w$". The existential over $v$ suggests making $v$ the witness coordinate: $Y = \{(w, v) : f(v) \downarrow \text{ and } f(v) = w\}$. But this $Y$ is *not* computable, because "$f(v) \downarrow$" is only semi-decidable — no total algorithm tests it. *The fix: add a time bound.* Replace "$f(v) \downarrow$" by "$f(v)$ halts in at most $\#u$ steps", which *is* decidable for each fixed $u$. This introduces a second witness coordinate $u$, giving the computable set \begin{align*} Z = \{(w, v, u) : f \text{ on } v \text{ halts by step } \#u \text{ with output } w\}. \end{align*} Since halting at all is equivalent to halting at some finite step, existentially quantifying over $u$ recovers the original condition: \begin{align*} \exists u,\ (w, v, u) \in Z \iff f(v) \downarrow \text{ and } f(v) = w. \end{align*} *Packing $v$ and $u$ into one witness.* The $\Sigma_1$ definition asks for a single existential witness. We pack $(v, u)$ into one word $x$ by a computable pairing $\pi : \mathbb{W} \to \mathbb{W} \times \mathbb{W}$. This yields $Y$ with $p(Y) = X$. *Tools used.* (1) [Computability of the Configuration Function](/theorems/1818) provides the timed simulation $t_{c, 1}$ and the bounded output extraction $\mathrm{out}_{c, 1}$, both total computable. This is the workhorse that makes "halt by step $\#u$" decidable. (2) The computable pairing $\pi$ — the same pairing used in Step 4 of the proof of [Computable Sets Are $\Delta_1$](/theorems/1825) — packs two witnesses into one. (3) [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824) is the conversion from the $\Sigma_1$ description to a computable partial function whose domain is $X$; its proof constructs the function via minimisation over the witness space, which is the standard dovetail search. *Why is this argument parallel to the corresponding $\Sigma_1$ arguments in [Closure Properties of Computably Enumerable Sets](/theorems/1829)?* Because all three (union closure, concatenation closure, image-is-c.e.) use the same machinery: express the set as a projection of a computable witness set that combines (i) the "semantic" witness (a splitter, an inverse-image point, etc.) with (ii) a time witness $u$ that replaces "halts" with "halts by step $\#u$". [/guided] [/step] [step:Conclude] Step 2 proves $(\Rightarrow)$: every non-empty computably enumerable $X \subseteq \mathbb{W}$ equals the image of the computable partial function $f$ that is the identity restricted to $X$. Steps 3–6 prove $(\Leftarrow)$: every image $X = \operatorname{Im} f$ of a computable partial function $f$ equals $p(Y)$ for the computable $Y$ built from the timed simulation and a computable pairing, hence $X \in \Sigma_1$ and $X$ is computably enumerable by [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824). The empty case is handled in Step 1: $\varnothing$ is both computably enumerable (by convention) and the image of the everywhere-undefined computable partial function. Therefore $X \subseteq \mathbb{W}$ is computably enumerable if and only if $X = \operatorname{Im} f$ for some computable partial function $f : \mathbb{W} \rightharpoonup \mathbb{W}$. [/step]