# 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$$.

*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

## 2 Answers

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