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

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?

• Sorry, it seems very wrong to me. The reduction $f$ takes an input $x \in \Sigma^*$, and outputs a word $f(x)\in \Sigma^*$, and the following must hold: $x\in A$ iff $f(x)\in A\setminus B$. The format of your reduction is incorrect. I don't see why the input is a pair "(encoding of a machine, a word in $\Sigma^*$)" and the output is an encoding of a machine. – Bader Abu Radi Jan 17 at 15:25

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.

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.

• Your intuition is okay, but the solution is not: the formalism is not good, and you seem to be confused between machines, words, and languages. Lets chat here: chat.stackexchange.com/rooms/118565/bader-chaos-predictor-chat – Bader Abu Radi Jan 17 at 18:07
• This time, with you help, I think it's solved @BaderAbuRadi – ChaosPredictor Jan 17 at 20:23
• I have edited the answer. Please read it, and see how I changed it, and compare that with what we've discussed in the chat. – Bader Abu Radi Jan 17 at 21:06
• Thank you! If I understood it right, the core (and the correctness) of my answer is ok – ChaosPredictor Jan 17 at 21:20
• Yes (ignoring some minor abuse of notations). I just wrote it more clearly. – Bader Abu Radi Jan 17 at 21:40