Mathematical logic and foundations Definition

Many-one reduction

Builds on Computable function Computable set Computably enumerable set

Definition

Let $A$ and $B$ be subsets of $\N$ . A many-one reduction from $A$ to $B$ is a total computable function $f \colon \N \to \N$ such that for every $x \in \N$ , $x \in A \iff f(x) \in B.$ The set $A$ is many-one reducible to $B$ , written $A \le_m B$ , if such an $f$ exists. The sets $A$ and $B$ are many-one equivalent, written $A \equiv_m B$ , if $A \le_m B$ and $B \le_m A$ .

Remarks

Example: let $E$ be the set of even numbers and let $f(x) = 0$ for even $x$ and $f(x) = 1$ for odd $x$ . Then $f$ is total and computable, and $x \in E$ holds exactly when $f(x) \in \set{0}$ , so $E \le_m \set{0}$ .

Non-example: the empty set is not many-one reducible to $\N$ . For any $f$ , the point $0 \notin \emptyset$ would need $f(0) \notin \N$ , which is impossible.

The relation $\le_m$ is reflexive and transitive. If $A \le_m B$ and $B$ is a computable set, then $A$ is computable. If $A \le_m B$ and $B$ is computably enumerable, then $A$ is computably enumerable.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`H5CW67CCST`
URI	`m2://H5CW67CCST`
Kind	definition
Writing	W0 stub
MSC	03D30
Defines	Many-one reduction
Uses	Computable function, Computable set, Computably enumerable set
Changed	2 November 2026

Many-one reduction

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here