User:IssaRice/Computability and logic/Summary table of sets in computability

Set	Enumerable?	Recursive?	Primitive recursive?	Recursively enumerable/semirecursive?
Set of natural numbers	Yes	Yes	Yes	Yes
Set of even positive integers	Yes	Yes	Yes	Yes
Set of rational numbers	Yes	Yes	Yes	Yes
Set of real numbers	No
{encoding of (m, n) : Turing machine m halts on input n}	Yes	No
$K=\{x:x\in W_{x}\}$	Yes	No	No	Yes
$\{x:\phi _{x}(x)=0\}$
$\{x:\phi _{x}(x)=1\}$
${\overline {K}}={\overline {\{x:x\in W_{x}\}}}=\{x:x\notin W_{x}\}$
Set of truths of arithmetic	Yes	No	No	No

I thing one thing to stress is that some sets are bad on account of their size (i.e. they are "too big") while other sets are bad on account of their shape. For instance, subsets of the natural numbers that are not recursive are fully contained in sets that are recursive; so it is not that they are "too big" (because even some proper supersets are recursive), but that their shape is too intricate. On the other hand, a set like $\mathbf {R}$ just has too many elements, so it is not the shape that matters.