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)
“How have I been able to live so long outside Nature without identifying myself with it? Everything lives, moves, everything corresponds; the magnetic rays, emanating either from myself or from others, cross the limitless chain of created things unimpeded; it is a transparent network that covers the world, and its slender threads communicate themselves by degrees to the planets and stars. Captive now upon earth, I commune with the chorus of the stars who share in my joys and sorrows.”
—Gérard De Nerval (1808–1855)