Arithmetic Reducibility and Degrees
Arithmetical reducibility is an intermediate notion between Turing reducibility and hyperarithmetic reducibility.
A set is arithmetical (also arithmetic and arithmetically definable) if it is defined by some formula in the language of Peano arithmetic. Equivalently X is arithmetical if X is or for some integer n. A set X is arithmetical in a set Y, denoted, if X is definable a some formula in the language of Peano arithmetic extended by a predicate for membership in Y. Equivalently, X is arithmetical in Y if X is in or for some integer n. A synonym for is: X is arithmetically reducible to Y.
The relation is reflexive and transitive, and thus the relation defined by the rule
is an equivalence relation. The equivalence classes of this relation are called the arithmetic degrees; they are partially ordered under .
Read more about this topic: Arithmetical Hierarchy
Famous quotes containing the words arithmetic and/or degrees:
“‘Tis no extravagant arithmetic to say, that for every ten jokes,—thou hast got an hundred enemies; and till thou hast gone on, and raised a swarm of wasps about thine ears, and art half stung to death by them, thou wilt never be convinced it is so.”
—Laurence Sterne (1713–1768)
“Complete courage and absolute cowardice are extremes that very few men fall into. The vast middle space contains all the intermediate kinds and degrees of courage; and these differ as much from one another as men’s faces or their humors do.”
—François, Duc De La Rochefoucauld (1613–1680)