Background
The statement of Post's theorem uses several concepts relating to definability and recursion theory. This section gives a brief overview of these concepts, which are covered in depth in their respective articles.
The arithmetical hierarchy classifies certain sets of natural numbers that are definable in the language of Peano arithmetic. A formula is said to be if it is an existential statement in prenex normal form (all quantifiers at the front) with alternations between existential and universal quantifiers applied to a quantifier free formula. Formally a formula in the language of Peano arithmetic is a formula if it is of the form
where ρ is a quantifier free formula and Q is if m is even and if m is odd. Note that any formula of the form
where contains only bounded quantifiers is provably equivalent to a formula of the above form from the axioms of Peano arithmetic. Thus it isn't uncommon to see formulas defined in this alternative and technically nonequivalent manner since in practice the distinction is rarely important.
A set of natural numbers A is said to be if it is definable by a formula, that is, if there is a formula such that each number n is in A if and only if holds. It is known that if a set is then it is for any, but for each m there is a set that is not . Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set.
Post's theorem uses the relativized arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set A of natural numbers is said to be relative to a set B, written, if A is definable by a formula in an extended language that includes a predicate for membership in B.
While the arithmetical hierarchy measures definability of sets of natural numbers, Turing degrees measure the level of uncomputability of sets of natural numbers. A set A is said to be Turing reducible to a set B, written, if there is an oracle Turing machine that, given an oracle for B, computes the characteristic function of A. The Turing jump of a set A is a form of the Halting problem relative to A. Given a set A, the Turing jump is the set of indices of oracle Turing machines that halt on input 0 when run with oracle A. It is known that every set A is Turing reducible to its Turing jump, but the Turing jump of a set is never Turing reducible to the original set.
Post's theorem uses finitely iterated Turing jumps. For any set A of natural numbers, the notation indicates the n-fold iterated Turing jump of A. Thus is just A, and is the Turing jump of .
Read more about this topic: Post's Theorem
Famous quotes containing the word background:
“Silence is the universal refuge, the sequel to all dull discourses and all foolish acts, a balm to our every chagrin, as welcome after satiety as after disappointment; that background which the painter may not daub, be he master or bungler, and which, however awkward a figure we may have made in the foreground, remains ever our inviolable asylum, where no indignity can assail, no personality can disturb us.”
—Henry David Thoreau (1817–1862)
“In the true sense one’s native land, with its background of tradition, early impressions, reminiscences and other things dear to one, is not enough to make sensitive human beings feel at home.”
—Emma Goldman (1869–1940)
“They were more than hostile. In the first place, I was a south Georgian and I was looked upon as a fiscal conservative, and the Atlanta newspapers quite erroneously, because they didn’t know anything about me or my background here in Plains, decided that I was also a racial conservative.”
—Jimmy Carter (James Earl Carter, Jr.)