# If A is mapping reducible to B and A is recognizable, then is B recognizable too?

I learned the proof for the theorem:
If A $\leq_m$ B and B is recognizable, then A is recognizable
and was provided with the theorem:
If A $\leq_m$ B and A is unrecognizable, then B is unrecognizable

So does this work both ways? i.e. does this also hold?

If A $\leq_m$ B and A is recognizable, then B is recognizable
If A $\leq_m$ B and B is unrecognizable, then A is unrecognizable

Answer for Corrected Question

You can think of reductions as "making problems harder" (somewhat inline with using $\leq$ as the base symbol for reductions of).

In this case we only have two levels of "hardness", a problem/language is either recognizable ("easy") or unrecognizable ("hard") (but this obviously extends to other degrees of computability and complexity).

So if $A \leq B$, and $B$ is "easy", $A$ must be "easy" too (because it's "less than" $B$). Contrapositively, if $A \leq B$ and $A$ is "hard, then $B$ must also be "hard" (because it's "greater than" $A$).

Using this intuition, it may be a bit easier to see why the latter two are wrong:

• If $A \leq B$ and $A$ is "easy", this doesn't tell us much about $B$ (it could be "easy" or "hard").
• Similarly, if $B$ is "hard", it doesn't tell us much about $A$.

Note that as with the first pair, the second are really the same statement, just logically inverted.

Old Answer, Just Here for Posterity

I think you may have misread something. The second (provided) theorem is not correct, it should be if $A \leq_{m} B$ and $A$ is unrecognizable, then $B$ is unrecognizable.

This is just the contrapositive of the first statement.

Following from this, the final two are mistaken.

• My apologies for the typo. I have updated the question. Feb 27, 2018 at 2:10

The second is a corollary of the first.

Using logic

This is the easy and short answer. Assume the first theorem has been proved. That is, $B$ is recognizable (statement $S_B$) implies $A$ is recognizable (statement $S_A$).

In logic algebra, you write this as

$S_B \Rightarrow S_A$

Now these are valid:

• $S_B$ is true and $S_A$ is true
• $S_B$ is false and $S_A$ is true
• $S_B$ is false and $S_A$ is false

However this

• $S_B$ is true and $S_A$ is false is invalid.

Rewriting our algebraic notation back to English answers all your questions:

• If $B$ is recognizable, then $A$ is recognizable
• If $B$ is not recognizable, then $A$ may or may not be recognizable
• IF $A$ is not recognizable, then $B$ must not be recognizable.

This is usually all implied by the book. That's why it's a corollary. But we can explicitly invoke reductions to reach the same conclusions.

Bonus: Using reductions

A mapping reduction implies a function $f:A\mapsto{}B$ such that

• if $x\in{}A$, then $f(x)\in{}B$
• if $x\notin{}A$, then $f(x)\notin{}B$

If $B$ is recognizable, then so is $A$

So if $B$ is recognizable, then using $f(·)$ you can devise a Turing Machine that halts for every $f(x)\in{}B$ as well as for every $x\in A$. This proves your first statement.

If $A$ is unrecognizable, then neither is $B$

Let us continuing assuming that $B$ is recognizable. And let us now assume that $A$ isn't. But wait, we just proved that this can't happen. We are in contradiction!

Conclusion: if you can prove that $A$ us unrecognizable, then it is impossible for $B$ to be recognizable.

Now, for the other two, it depends on whether $B\leq_mA$ is also true. If it is true, then the same theorem applies the way back. That's boring, so let us assume this is not true.

If $A$ is recognizable, what about $B$?

If all you have is a mapping from $A$ to $B$, then there are strings $y\in{}B$ which you can't find with $f$. So knowing that $A$ is recognizable does not help you with $B$. You may list all strings in $A$, but that still leaves a subset of $B$ for which you can't say anything.

If $B$ is unrecognizable, what about $A$?

On the other hand, if you know that $B$ has strings that cannot be recognized, that says nothing about $A$, because all strings in $A$ might map to the portions of $B$ that are recognizable. So even though $B$ is unrecognizable, it still might help you recognize $A$.