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 the world of the celebrity, the hierarchy of publicity has replaced the hierarchy of descent and even of great wealth.”
—C. Wright Mills (1916–1962)
“A horse, a buggy and several sets of harness, valued in all at about $250, were stolen last night from the stable of Howard Quinlan, near Kingsville. The county police are at work on the case, but so far no trace of either thieves or booty has been found.”
—H.L. (Henry Lewis)
“Unfortunately there is still a cultural stereotype that it’s all right for girls to be affectionate but that once boys reach six or seven, they no longer need so much hugging and kissing. What this does is dissuade boys from expressing their natural feelings of tenderness and affection. It is important that we act affectionately with our sons as well as our daughters.”
—Stephanie Martson (20th century)
“I had but three chairs in my house; one for solitude, two for friendship; three for society. When visitors came in larger and unexpected numbers there was but the third chair for them all, but they generally economized the room by standing up.”
—Henry David Thoreau (1817–1862)