How do I prove this claim? I understand that there are countably many recursive as well as recursively enumerable sets, and that the natural numbers have uncountably many subsets.
Asked
Active
Viewed 259 times
1 Answers
5
If you have one recursively enumerable but not recursive set, you can turn it into infinitely many. Let the recursively enumerable but not recursive set be $A$. Let $C=\{2n+1|n \in A\}$. It is also recursively enumerable but not recursive. To enumerate it, just enumerate $A$ and as each element comes out, double it and add one. If it were recursive, so would $A$ be. Now define the family $B_i$ as $B_i=C \cup \{2j|0 \lt j \le i\}$
Ross Millikan
- 374,822
-
3Or just $B_i={in\mid n\in A}$. – hmakholm left over Monica Feb 02 '16 at 22:02
-
@Ross Millkian And those are all different because C only consists of odd numbers and I add a few even ones to every one of the $B_i$s? – azureai Feb 02 '16 at 23:01
-
1That is correct. $B_i$ has the $i$ smallest even numbers in it plus all the odd ones from $C$ – Ross Millikan Feb 02 '16 at 23:54
-
@HenningMakholm: yes, that is even simpler. Thanks – Ross Millikan Feb 02 '16 at 23:55