For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$

Question

It's claim 1 from Bader Abu Radi's solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.

*Wrong from here
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$

When $M_A$ implemented on input $w$ like this:

1. Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$

$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$
till here

So the reduction $A \le_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.

Edit

$f(x)=x'=x\setminus x_B$ (when $x_B$ is all the $x$ that accepted by $M_B$), because $M_B$ halts on $B$ the reduction is applicable and work for any $x$.
It's implemented in the following way:

1. run $M_B$ on $x$ (halts), if $M_B$ accept, $x'$ reject
2. otherwise return $x$

If $x\notin A \Rightarrow x'\notin A \setminus B$
If $x\in A$:
$x\in B \Rightarrow M_B$ accept $x \Rightarrow x'$ reject $\Rightarrow x'\notin A\setminus B$
$x\notin B \Rightarrow M_B$ reject $x \Rightarrow x'=x\Rightarrow x'\in A\setminus B$

Is this one correct? Should something be added to it?

Answer 1

As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint.

Hint: consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not work. Then, think what is the simplest thing you can do in order to fix the identity reduction.

Answer 2

The language $B$ is finite, and thus decidable. Let $M_B$ be a TM that decides $B$. Also, as $B$ is strictly contained in $A$, we know that there is a word $y$ in $A\setminus B$.

The reduction operates as follows. Given input $x$, we check whether $x\in B$ (this can be done using $M_B$), then:

• if $x\in B$: the reduction outputs $y$.
• if $x\notin B$: the reduction outputs $x$.

For correctness, one direction is clear: if $x\notin A$, then $f(x) = x\notin A\setminus B$. Conversely, if $x\in A$, then we split into cases: i) if $x\in B$, then $f(x) = y \in A\setminus B$. ii) if $x\in A\setminus B$, then $f(x) = x \in A\setminus B$. In both cases, $f(x)\in A\setminus B$, and we're done.

Note that $y$ is some fixed word - you can think of it as a constant hardcoded in the reduction.