Skip to main content
1 of 3

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

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$.
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 $\langle M_A\rangle$ implemented on input $w$ like this:

  1. Run $\langle M_B\rangle$ 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$

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.