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:
“Under the dominion of an idea, which possesses the minds of multitudes, as civil freedom, or the religious sentiment, the power of persons are no longer subjects of calculation. A nation of men unanimously bent on freedom, or conquest, can easily confound the arithmetic of statists, and achieve extravagant actions, out of all proportion to their means; as, the Greeks, the Saracens, the Swiss, the Americans, and the French have done.”
—Ralph Waldo Emerson (1803–1882)
“For the profit of travel: in the first place, you get rid of a few prejudices.... The prejudiced against color finds several hundred millions of people of all shades of color, and all degrees of intellect, rank, and social worth, generals, judges, priests, and kings, and learns to give up his foolish prejudice.”
—Herman Melville (1819–1891)