Editing Post's theorem (section)

===Recursively enumerable sets===
Let <math>S</math> be a set that can be recursively enumerated by a [[Turing machine]]. Then there is a Turing machine <math>T</math> that for every <math>n</math> in <math>S</math>, <math>T</math> halts when given <math>n</math> as an input.

This can be formalized by the first-order arithmetical formula presented above. The members of <math>S</math> are the numbers <math>n</math> satisfying the following formula:

<math>\exists n_1:\varphi(n,n_1)</math>

This formula is in <math>\Sigma^0_1</math>. Therefore, <math>S</math> is in <math>\Sigma^0_1</math>.
Thus every recursively enumerable set is in <math>\Sigma^0_1</math>. 

The converse is true as well: for every formula <math>\varphi(n)</math> in <math>\Sigma^0_1</math> with k existential quantifiers, we may enumerate the <math>k</math>&ndash;tuples of natural numbers and run a Turing machine that goes through all of them until it finds the formula is satisfied. This Turing machine halts on precisely the set of natural numbers satisfying <math>\varphi(n)</math>, and thus enumerates its corresponding set.