# Where am I wrong?: "countability" and "recursive enumerability"

I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i have made?

Countability (C=Countable): A set $X$ is C when a bijection exists between the set of natural numbers and the set $X$

Recursive Enumerability (RE= Recursively Enumerable): Say set $S'$ is a subset of another set $S$. When there exists a turing machine with alphabet $A$ (where $S$ is a subset of $A^*$) which halts if the input to it belongs to the set $S'$ and does not halt if the input belongs to $S-S'$ then I say that the set $S'$ is recursively enumerable (given the fact that inputs comes only from the set $S$ and not from $A^*-S$ hence the latter will not concern us.) I have referred to the book "Elements of the theory of Computation" by Papadimitrou for this definition, though the introduction of an alphabet A is my own addition to make things more firm

Now I will prove 2 statements:

1. if a set $X$ is RE then it is C
2. if a set $X$ is C then it is RE

Hence proving 3. RE iff C

I will prove 2 first.

I can write a Turing Machine $M$ which when asked to check if an element $x$ belongs to $X$ or not will follow the algorithm:

There exists a mapping from the set of natural numbers to $X$ call it $f$. $M$ can search for $x$ (like a linear search algorithm running on $X$) starting from $f(1)$ going to $f(2)$... and it keeps going till it finds $x$. By this method, $M$ terminates iff $x$ belongs to $X$.

The behaviour above proves that $X$ is RE

Now I prove 1- Given a Turing Machine $M$ exists which halts iff $x$ belongs to $X$

I can construct a bijective map from the set of naturals to $X$ as follows: To map $x$ (given it belongs to $X$) , we run it as input against $M$. I take the concatenation of all configurations (Configuration=tape head position+tape content+state) of $M$ which it goes through from the starting of a computation to the end and decode that string as a natural number. It will be unique.

Hence 1. is proven and so is 3.

But then I find certain resources on the internet which tell me that enumerability and recursive enumerability are different things. How is it possible? Furthermore- We know that the power set of a countably infinite set is uncountably infinite. If $X$ was countably infinite, it would be RE (see 2.). Now we know that the subset of a set which is C is also C. Hence all subsets of $X$ would be C hence they would be RE. Now there would be an uncountable number of RE sets.

Now for each RE set, we can write a turing machine (with appropriate halting behaviour) which can be encoded as a natural number implying that the "set of all RE sets" must be C. This contradicts the conclusion of the previous paragraph.

Where exactly am I wrong? Thankyou in advance!

• Let C be recursive, then that's not true. If X is C then it is RE, But If X is RE then it's not necessarily C (recursive). Jun 13, 2013 at 19:43
• I understand the relation between "recursive" and "recursively enumerable" but what is confusing me is the relation between countability (i.e. enumerability in the set theoretic sense) and recursive enumerability. Jun 13, 2013 at 19:52

Your algorithm for recursively enumerating any given set doesn't work since the bijection between a countable set $X$ and the natural numbers can be arbitrarily complicated. For example, consider the following set $X$: $$X = \{ P : \text{the program coded by P doesn't halt on the empty string as input} \}.$$ The set $X$ is countable: there are only countably many programs. However, there is no computable bijection between $X$ and the natural numbers, since otherwise RE=coRE (as your argument shows; $X$ is coRE-complete).
Here is a more tangible example of a countable set for which there is no computable bijection: $$Y = \{ 2P : \text{program P halts on the empty string} \} \cup \{ 2P+1 : \text{program P doesn't halt on the empty string} \}.$$ If there was a computable bijection between $Y$ and the natural numbers, then you could solve the halting problem (how?).