6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Iancovici Jun 13 '13 at 19:43
  • $\begingroup$ 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. $\endgroup$ – swanar Jun 13 '13 at 19:52
6
$\begingroup$

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?).

$\endgroup$
  • $\begingroup$ Thankyou! I understood your explanation.Given P,run the algorithm I gave and at some pt. it definitely halts (because the set is countable so all elements are necessarily mapped) by getting f(n)=2P or f(n)=2P+1 by which you can tell if P halts or it doesnt halt on the empty string which essentially reduces to the deciding the halting problem. So I can safely assume that "C does not imply RE". I have to ask if my proofs for "RE implies C" (statement 1.) and "Set of all RE sets is C" (last paragraph) is correct or not. $\endgroup$ – swanar Jun 13 '13 at 21:01
  • $\begingroup$ Your proof of "every r.e. set is countable" is wrong - the mapping you present is not a bijection. What you give is a mapping from a given r.e. set X to N. If X is furthermore infinite that this implies that there is some other bijection between X and N, but that's of course not the case if X is finite. You have the same problem with your second proof, though you don't mention the word "bijection". Note, however, that it is well-known that every infinite subset of N is countable, and so these proofs are essentially correct (as long as you don't claim you are constructing a bijection). $\endgroup$ – Yuval Filmus Jun 13 '13 at 21:26
  • $\begingroup$ So the correct way of proving in both problems would be to show that once an "element of an RE set"("element of the set of RE sets") is mapped to unique natural numbers by the scheme provided in both the proofs, we use the fact it is equivalent to an infinite subset of the natural numbers which is known to be countable. Hence both the statements are proven correct. Thanks Again! $\endgroup$ – swanar Jun 14 '13 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.