# Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$

I know that such sets exist and they are called sets that are not m-complete, but I am not sure how to find them. Can someone give examples?

• Could you define what $\le_m$ means?
– Jake
Sep 14, 2017 at 3:54
• many to one reductions Sep 14, 2017 at 3:55
• A quick trivial example: $A = \{ n \}$ (all numbers), $B = \{ 2n \}$ (even numbers)
– Vor
Sep 14, 2017 at 6:40
• @Vor, how is this connected to many-one reductions? Sep 14, 2017 at 6:40
• @rus9384: try to find a many-one-reduction from $B \to A$ ... how do you map the number $3 \notin B$?
– Vor
Sep 14, 2017 at 6:42

I post my comment, as an extended note, which shows a small "formal trick".

A trivial example over natural numbers $\mathbb{N} = \{n > 0 \}$, is:

$A = \{ n\} = \mathbb{N}$ and $B = \{2n \}$ (even numbers).

According to the definition of many-one reduction: a many-one reduction from $B$ to $A$ is a total computable function $f : \mathbb{N} → \mathbb{N}$ that has the property that each $x$ is in $B$ if and only if $f(x)$ is in $A$.

Clearly we have $A \leq_m B$: a many-one reduction that works is $f(x) = 2$

But $B \nleq_m A$ because given $x \notin B$ (e.g. $x = 3$) you cannot map it to a $f(x) \notin A$ because $A$ contains all elements.

Let $A$ be a computable set of all even nonnegative integers, and $H$ be the language of the Halting problem. Assume also that $w_1 \in H$ and $w_2 \notin H$. Then define a mapping as following:

$$f(x) = w_1 \text{ if } x \text{ is even}, w_2 \text{ if } x \text{ is odd }$$ This function is clearly computable and $x$ is even iff $f(x) = w_1 \in H$, i.e., $A \leq_m H$. However, $H \nleq_m A$, otherwise $H$ would be computable/recursive.