We denote $\mathcal{RE}$ as the universe set of recursively enumerable sets. A set is recursively enumerable iff its semi-charactersitic function is computable (one can write its semi-verifier). The question is, can we build a bijection between $\mathcal{RE}$ and the powerset of naturals?
Asked
Active
Viewed 73 times
0
-
2Obviously not, since a set is r.e. iff it is the domain of a Turing Machine. – Andrés E. Caicedo Jan 08 '13 at 21:30
-
Please remind that I mention the set of all recursive enumerable sets, not a set that is in $\mathcal{RE}$. – MeadowMuffins Jan 08 '13 at 22:03
-
2There are only countably many Turing machines, so there are only countably many r.e. sets. – Brian M. Scott Jan 08 '13 at 22:11
1 Answers
2
There are only countably many sets in $\mathcal{RE}$ and there are uncountably many sets in $P(\mathbb{N})$, so we cannot build a bijection between $\mathcal{RE}$ and $P(\mathbb{N})$. (This is a community-wiki answer so that the question is not marked as unanswered.)
Carl Mummert
- 81,604