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:
- if a set $X$ is RE then it is C
- 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!