result in computability theory known as Post's theorem says that the prenex normal form of a formula defining a set or relation on the natural numbers is related to how difficult the set or relation is computationally. One corollary of Post's theorem is that if a set is definable by a formula whose prenex normal form contains only existential quantifiers, then the set is computably enumerable, meaning that there is an algorithm which can list the elements of the set. Show that the set of all non-primes (as a subset of N) is a computably enumerable set. (That is, first show that the set of all non-primes is definable in the language 1 of arithmetic. Then put the formula you gave defining the set of all non-primes into prenex normal form. It will be helpful to go back to section 2.2.3, page 62.) 2