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

Set	Enumerable (countable)?	Recursive?	Primitive recursive?	Recursively enumerable/semirecursive?	Co-recursively enumerable?
Set of natural numbers	Yes	Yes	Yes	Yes	Yes
Set of even positive integers	Yes	Yes	Yes	Yes	Yes
Set of rational numbers	Yes	Yes	Yes	Yes	Yes
Set of real numbers	No	No	No	No
${\mathsf {HALT}}=\{\langle m,n\rangle :{\text{Machine }}m{\text{ halts on input }}n\}$	Yes	No	No	Yes	No
$K=\{x:x\in W_{x}\}$ (where $W_{x}$ is the domain of $\varphi _{x}$)	Yes	No	No	Yes	No
${\overline {K}}={\overline {\{x:x\in W_{x}\}}}=\{x:x\notin W_{x}\}$	Yes	No	No	No	Yes
$\{x:\varphi _{x}(x)=0\}$	Yes	No	No	Yes	No
$\{x:\varphi _{x}(x)=1\}$	Yes	No	No	Yes	No
Set of theorems of Peano arithmetic	Yes	No	No	Yes	No
Set of truths of arithmetic (true arithmetic)	Yes	No	No	No

add expressible and capturable as columns to the table?

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.

See also

• User:IssaRice/Computability and logic/Property table of theories of arithmetic