Effective enumerability and Enumerability

Question

I am reading the book by Peter Smith "An Introduction to Gödel's Theorems". I am struck at the point where he tries to construct an non effective enumerable set by using the diagonalisation idea.

Here is the sketch of the proof :

Denote by $\pi_{e}$ the enumerable set of algorithms. Denote their domain as $W_{e}$. Now consider the set $K=\{e:e \in W_e\}$.

He proves that this set's complement is not effectively enumerable. But in the construction of $K$ are we assuming the axiom of choice? If not, how do we justify the fact that $K$ exists ?

I am new to all this so any intuitive answer can help. Thanks in advance.

Answer 1

Peter Smith's argument is based on the existence of

an effectively generated list of versions of all the possible algorithms $\pi_0, \pi_1$,. . . [...]. Let the numerical domain of $\pi_e$ be $W_e$.

According to the

Theorem : $W$ is an effectively enumerable set of numbers if and only if it is the numerical domain of some algorithm $\pi$,

every effectively enumerable set of numbers is $W_e$ for some index $e$.

In order to show that the complement of $K = \{e : e \in W_e \}$ is not effectively enumerable, we must apply a "diagonal" argument.

By definition, for any $e$, $e \in \overline K$ if and only if $e \notin W_e$. Hence, $\overline K$ cannot be identical to any of the $W_e$ (since $e$ is in one but not the other). Therefore $K$ isn’t one of the effectively enumerable sets (since the $W_e$ are all of them).

If you consider Recursively enumerable sets and Recursive sets we have to apply the property of :

a set $A$ is a recursive set [or decidable] if and only if $A$ and the complement of $A$ are both recursively enumerable sets.

We can find the details into Herbert Enderton, Computability Theory. An Introduction to Recursion Theory (2011).

Being $K$ r.e. [see the algorithm described in fgp's answer], if also its complement $\overline K$ would be, we should be able to decide the Halting problem.

Thus, $\overline K$ is not r.e.

From Enderton, page 7 :

Turing’s 1936 article on what are now called Turing machines had proved the existence of a “universal Turing machine” to compute the $\Phi$ function :

$\Phi(e,x) =$ the result of applying the instructions coded by $e$ to the input $x$.

It is an effectively calculable partial function (where it is understood that $\Phi(e,x)$ is undefined whenever applying the instructions coded by $e$ to the input $x$ fails to halt and return an output).

The two-place partial function $\Phi$ is “universal” in the sense that any one-place effectively calculable partial function $f$ is given by the equation :

$f(x) = \Phi(e, x)$, for all $x$.

In this way, we may list all one-place effectively calculable partial function as $\pi_e$.

Using the universal partial function $\Phi$, we can construct an undecidable binary relation, the halting relation $H$ :

$(e,x) \in H \leftrightarrow \Phi(e,x)$ is defined, i.e. $\leftrightarrow$ applying the instructions coded by $e$ to input $x$ halts.

$H$ is semidecidable : given $e$ and $x$, we first calculate $\Phi(e,x)$. If and when this halts and returns a value, we give output “Yes” and stop.

But H is not decidable [see page 8] :

consider the following partial function:

$f(x) = Yes$ if $\Phi(x,x)$ is undefined; $f(x)$ undefined if $\Phi(x,x)$ is defined.

The partial function $f$ cannot possibly be effectively calculable. Consider any set of instructions that might compute $f$. Those instructions have some code number $k$ and hence compute the partial function $\pi_k$. Could that be the same as $f$ ? No, $f$ and $\pi_k$ differ at the input $k$.

We have that if we had a decision procedure for $H$, then we could calculate $f$. To compute $f(x)$, we first use that decision procedure for $H$ to decide if $(x,x) \in H$ or not. If not, then $f(x) = Yes$. But if $(x,x) \in H$, then the procedure for finding $f(x)$ should throw itself into an infinite loop because $f(x)$ is undefined.

Putting these two observations about $f$ together, we conclude that there can be no decision procedure for $H$. The fact that $H$ is undecidable is usually expressed by saying that “the halting problem is unsolvable”; i.e., we cannot in general effectively determine, given $e$ and $x$, whether applying the instructions coded by $e$ to the input $x$ will eventually terminate or will go on forever.

The function $f$ is the semicharacteristic function of the set :

$\overline K = \{ e : \Phi(e,e)$ undefined $\}$;

that is the complement of the set :

$K = \{ e : e \in W_e \}$.

This set $K$ is semidecidable. How might we check it? We try to compute $\Phi(e,e)$ (which is possible because $\Phi$ is an effectively calculable partial function). If and when the calculation halts and returns an output, we give the output “Yes” and stop. Until such time, we keep trying. (This argument is the same one that we saw for the semidecidability of $H$. And $e \in K \leftrightarrow (e,e) \in H$).

Answer 2

$K$ is effectively enumerable. The algorithmn to enumerate $K$ is basically

1. Set $n := 1$
2. Set $k := 1$
3. See if the $k$-th algorithm terminates for input $k$ in at most $n$ steps. If so, report that $k \in K$.
4. Set $k := k + 1$
5. If $k \leq n$, continue at (3)
6. Set $n := n + 1$ and continue at (2)

If indeed $k \in K$, i.e. if the $k$-th algorithm indeed terminates for input $k$, then it does so in some number of steps, say $s$. The algorithm above will then detect that once it reaches line (2) with $n \geq s$.

Answer 3

The specific question is:

But in the construction of K are we assuming the axiom of choice? If not, how do we justify the fact that K exists ?

In defining the set $K \subseteq \mathbb{N}$ we specify a determinate condition on numbers, and say that $e \in K$ just in case $e$ satisfies that condition. Note that, irrespective of what that condition is exactly, no choices are involved.

If it helps, we could put it this way: if you were fancying up the book's informal argument in a set-theoretic framework, it would be the Axiom of Separation that gives us $K$, not the Axiom of Choice.

For those who do not know the book, this construction comes very early on, and that's why it is talking about effective enumerability [informal] rather about recursive enumerability [the formally defined notion which doesn't appear until over 250 pages later] and also why there is no mention at this stage about halting problems or the like. The argument that $K$ is effectively enumerability and its complement is not which is given in the book ($\S3.5$ of the 2nd edition) is in fact very simple and short, and doesn't need to mention the halting problem. It is almost trivial that $\overline{K}$ is not effectively enumerable, and the proof that $K$ is effective enumerable just requires the sort of interleaving trick indicated by @fgp's answer. So the sort of details that Mauro's answer goes into aren't needed at this stage in the book.