Reduction (computability theory): Difference between revisions

Revision as of 03:03, 19 December 2020

Revision as of 00:49, 20 December 2020

Line 14:

Every reducibility relation (in fact, every preorder) induces an equivalence relation on the powerset of the natural numbers in which two sets are equivalent if and only if each one is reducible to the other. In recursion theory, these equivalence classes are called the '''degrees''' of the reducibility relation. For example, the Turing degrees are the equivalence classes of sets of naturals induced by Turing reducibility.

The degrees of any reducibility relation are [[partial order|partially ordered]] by the relation in the following manner. Let ≤<math>\leq</math> be a reducibility relation and let <math>C</math> and <math>D</math> be two of its degrees. Then <math>C\leq D</math> if and only if there is a set <math>A</math> in <math>C</math> and a set <math>B</math> in <math>D</math> such that <math>A\leq B</math>. This is equivalent to the property that for every set <math>A</math> in <math>C</math> and every set <math>B</math> in <math>D</math>, <math>A\leq B</math>, because any two sets in ''A'' are equivalent and any two sets in <math>B</math> are equivalent. It is common, as shown here, to use boldface notation to denote degrees.

== Turing reducibility ==