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 firmNow I will prove 2 statements:if a set $X$ is RE then it is Cif a set $X$ is C then it is REHence 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 RENow 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!
Where am I wrong?: countability and recursive enumerability
computability;turing machines;uncountability
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?).