I am reading A Friendly Introduction to Mathematical Logic by Christopher Leary and Lars Kristiansen. In this section, the authors ask to prove that $A\subseteq\mathbb{N}$ is calculable iff $A$ is listable in increasing order.
Here are the definitions as given in the book:
A partial function $f : A \subseteq \mathbb{N} \rightarrow \mathbb{N}$ is calculable if there is an algorithm or computation that, given input $n \in \mathbb{N}$, does exactly one of the following: If $f \left( n \right)$ is defined, the algorithm computes the correct value of $f \left( n \right)$, outputs $f \left( n \right)$ and then halts; If $f \left( n \right)$ is not defined, the algorithm runs forever without halting. A set $S \subseteq \mathbb{N}$ is calculable if its characteristic function, $\chi_S$, is calculable.
A set $A$ is listable if there is a computer program $L$ such that $L$ prints out, in some order or another, the elements of $A$.
My attempt:
Suppose that $A$ was listable in increasing order. Then there is a computer program $L$ which prints the elements of $A$ in increasing order. We define an algorithm $P$ in the following way:
Given an input $n\in\mathbb{N}$, $P$ starts the execution of $L$ and
- if $L$ halts before printing $n$, $P$ returns $1$ and halts, else,
- if $L$ prints a number bigger than $n$ but $n$ does not appear in the output, $P$ stops the execution of $L$ and return $1$ and halts, else,
- if $n$ occurs in the output of $L$, $P$ stops the execution of $L$ and returns $0$.
By definition, this program $P$ makes $\chi _ A$ calculable.
I am finding it difficult to prove the other direction. Suppose that there was a program $P$ such that given an input $n\in\mathbb{N}$, if $\chi _A (n)$ is defined then it returns $0$ and halts, else, does not halt.
I am not sure how to do it. If $0$ is not in $A$, $P(0)$ will not halt. Now, I can never know using $P$ whether $0$ is not in $A$. How can I achieve this?
Any hints will be appreciated!