Do recursively enumerable subsets of $\mathbb{N}$ have a least element

Question

I've been studying MK set theory and computability and I think I'm misunderstanding something. I'm considering some (nonempty) infinite recursively enumerable subset of $\mathbb{N}$. I'm trying to show that this is the range of an injective recursive function.

Now I know that our subset (call it B) has to be the range of a recursive function (call it b) so I can obviously recursively construct a function by just picking out the distinct elements of $b$.

But I was also thinking, since B is a subset of $\mathbb{N}$ I know that it has a least element (lets call it a). I would now like to define a function where $f(0)=a$. So now $B\setminus\{a\}$ is a subset of $\mathbb{N}$ and hence also has a least element (call it a+) if I set $f(1)=a+$ then I was thinking that I could inductively define my $f$ like this.

I'm pretty sure what I've suggested above is wrong, but I'm not sure why it is wrong. Is it simply that I'm trying to treat B as a recursive subset, or is there an 'easier to grasp' reason as to why the above won't work?

Answer 1

For any infinite set $A\subseteq\mathbb{N},$ there is a natural function $p_A$ associated to $A$, namely the function that enumerates $A$ in order:

$p_A(n)$ is the unique element $b$ of $A$ such that $\vert\{a\in A: a<b\}\vert=n$.

(We can extend this to arbitrary sets of naturals by allowing $p_A$ to be partial.)

This is the principle function of $A$, and is sort of dual to the more common characteristic function. It is total (for infinite $A$) and injective, and satisfies $ran(p_A)=A$. So why doesn't it solve the exercise?

The issue is that the principle function can be quite complicated: even if $A$ is (infinite and) c.e., we may have $p_A$ not computable, even though there will by definition be a computable total $h$ with $A=ran(h)$. We can see this by noting the following:

• For every infinite set $A$, we have $A\equiv_Tp_A$.

Proof: That $A\ge_Tp_A$ is immediate. Conversely, given $p_A$ we can tell whether $n\in A$ by computing $p_A(0), p_A(1),..., p_A(n)$ and checking whether any of these values equals $n$; if so, then $n\in A$, and otherwise $n\not\in A$. $\quad\Box$

In particular, this means that whenever $A$ is noncomputable, $p_A$ is also noncomputable. So any noncomputable c.e. set gives a counterexample to your argument.

---

EDIT: It's worth noting that when we look more closely than Turing reducibility, we see real differences between $A$ and $p_A$. In general, $p_A$ is much more complicated than $A$.

For example, suppose $A$ is c.e.. The graph of $p_A$ - that is, $\{\langle x, y\rangle: p_A(x)=y\}$ is in general not c.e. We can see this immediately by remembering that any total function with a c.e. graph is in fact computable and has a computable graph.

A useful tool for gauging differences in this context the difference hierarchy:

• A set is $1$-c.e. if it is c.e.

• A set is $(n+1)$-c.e. if it is of the form $X\setminus Y$ where $X$ is c.e. and $Y$ is $n$-c.e.

It's easy to show that there are $(n+1)$-c.e. sets which are not $n$-c.e. for each $n$; it is harder to show, but still true, that there are $(n+1)$-c.e. sets which are not Turing equivalent to any $n$-c.e. set for each $n$.

It's not too hard to show, then, that:

• If $A$ is c.e., then the graph of $p_A$ is $2$-c.e. (but not $1$-c.e. unless $A$ is computable).

It's also worth noting that we can consider transfinite extensions of the difference hierarchy, but we run into the usual "notation issues"; see this paper for some basic facts. The resulting hierarchy is called the Ershov hierarchy, and one of the basic facts about it is the following:

• For a set $A\subseteq\mathbb{N}$, the following are equivalent:

  • $A$ is $\Delta^0_2$ (equivalently by Shoenfield, computable from $0'$; again equivalently by Shoenfield, limit computable)

  • $A$ is $e$-c.e. for some ordinal notation $e$;

  • $A$ is $e$-c.e. for some ordinal notation $e$ corresponding to $\omega^2$.

It's worth observing that this last bulletpoint shows that without fixing a notion of "nice notation" we can't have a non-collapsing linear version of the Ershov hierarchy; meanwhile, any niceness notion can't reach all the way up the computable ordinals without being quite complicated. So there isn't really any way to turn this into a good linear hierarchy of the $\Delta^0_2$ sets. (This phenomenon happens frequently whendealing with computable ordinals; one major exception is that "$0^{(\alpha)}$" makes sense for every computable $\alpha$, that is, we can define a notion of iterated jump in a simple way and get something which is independent on the notation used up to Turing degree.)