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

Question

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?

Answer 1

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.

Answer 2

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.