Extensions and Variations
It is possible to define the arithmetical hierarchy of formulas using a language extended with a function symbol for each primitive recursive function. This variation slightly changes the classification of some sets.
A more semantic variation of the hierarchy can be defined on all finitary relations on the natural numbers; the following definition is used. Every computable relation is defined to be and . The classifications and are defined inductively with the following rules.
- If the relation is then the relation is defined to be
- If the relation is then the relation is defined to be
This variation slightly changes the classification of some sets. It can be extended to cover finitary relations on the natural numbers, Baire space, and Cantor space.
Read more about this topic: Arithmetical Hierarchy
Famous quotes containing the words extensions and/or variations:
“The psychological umbilical cord is more difficult to cut than the real one. We experience our children as extensions of ourselves, and we feel as though their behavior is an expression of something within us...instead of an expression of something in them. We see in our children our own reflection, and when we don’t like what we see, we feel angry at the reflection.”
—Elaine Heffner (20th century)
“I may be able to spot arrowheads on the desert but a refrigerator is a jungle in which I am easily lost. My wife, however, will unerringly point out that the cheese or the leftover roast is hiding right in front of my eyes. Hundreds of such experiences convince me that men and women often inhabit quite different visual worlds. These are differences which cannot be attributed to variations in visual acuity. Man and women simply have learned to use their eyes in very different ways.”
—Edward T. Hall (b. 1914)