Recursively enumerable in a one-to-one manner

59 Views Asked by At

I've encountered a statement like this (I hope it's correct, if not, let me know)

The sets that can be recursively enumerated in a one-to-one manner are the infinite recursively enumerated sets.

But I don't really understand what the infiniteness condition has to do with one-to-one enumeration. First, to enumerate a set $A$ in a one-to-one manner amounts to (from what I understand) having an enumerator that outputs all the elements of $A$ (and only them) exactly once. Now, if $A$ is recursively enumerable, we have an access to the code of its enumerator. Can't we just modify that code by saying "before outputing something, check whether this 'something' had already been spit out, and if so, don't output it for a second time"? I don't see how infiniteness is used here.

1

There are 1 best solutions below

7
On BEST ANSWER

Our "enumerator" is assumed to have domain $\mathbb{N}$. Since there are no injections of any complexity from $\mathbb{N}$ to a finite set, the infinitude requirement is essential.

The precise theorem is:

Suppose $A$ is an infinite r.e. set. Then there is a total computable injective function $f: \mathbb{N}\rightarrow\mathbb{N}$ with $ran(f)=A$.