2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

Answer for Corrected Question

Short answer, no.

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.

$\endgroup$
  • $\begingroup$ My apologies for the typo. I have updated the question. $\endgroup$ – Paradox Feb 27 '18 at 2:10
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.