The Arithmetical Hierarchy of Sets of Natural Numbers
A set X of natural numbers is defined by formula φ in the language of Peano arithmetic if the elements of X are exactly the numbers that satisfy φ. That is, for all natural numbers n,
where is the numeral in the language of arithmetic corresponding to . A set is definable in first order arithmetic if it is defined by some formula in the language of Peano arithmetic.
Each set X of natural numbers that is definable in first order arithmetic is assigned classifications of the form, and, where is a natural number, as follows. If X is definable by a formula then X is assigned the classification . If X is definable by a formula then X is assigned the classification . If X is both and then is assigned the additional classification .
Note that it rarely makes sense to speak of formulas; the first quantifier of a formula is either existential or universal. So a set is not defined by a formula; rather, there are both and formulas that define the set.
A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of the natural numbers. Instead of formulas with one free variable, formulas with k free number variables are used to define the arithmetical hierarchy on sets of k-tuples of natural numbers.
Read more about this topic: Arithmetical Hierarchy
Famous quotes containing the words hierarchy, sets, natural and/or numbers:
“In a hierarchy every employee tends to rise to his level of incompetence.”
—Laurence J. Peter (1919–1990)
“Until, accustomed to disappointments, you can let yourself rule and be ruled by these strings or emanations that connect everything together, you haven’t fully exorcised the demon of doubt that sets you in motion like a rocking horse that cannot stop rocking.”
—John Ashbery (b. 1927)
“There are several natural phenomena which I shall have to have explained to me before I can keep on going as a resident member of the human race. One is the metamorphosis which hats and suits undergo exactly one week after their purchase, whereby they are changed from smart, intensely becoming articles of apparel into something children use when they want to “dress up like daddy.””
—Robert Benchley (1889–1945)
“Out of the darkness where Philomela sat,
Her fairy numbers issued. What then ailed me?
My ears are called capacious but they failed me,
Her classics registered a little flat!
I rose, and venomously spat.”
—John Crowe Ransom (1888–1974)