1
$\begingroup$

If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If it is true how to prove it?

Update

It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then $A$ is recursive. but by $A \leq_m\bar{A}$ I can't deduce that $\bar{A}$ is r.e.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$
    – David Richerby
    Mar 1, 2015 at 20:06
  • $\begingroup$ @DavidRicherby From what I know if $A$ is r.e. (turing recognizable) and $B \leq_m A$ then B is r.e. If $A$ and $\bar{A}$ are r.e. then $A$ is recursive. the problem is I can't deduce that $\bar{A}$ is r.e. $\endgroup$
    – M a m a D
    Mar 1, 2015 at 20:16
  • $\begingroup$ @DavidRicherby I posted my prove as the answer, would you please take a look at it to see if it is right? $\endgroup$
    – M a m a D
    Mar 2, 2015 at 8:44
  • $\begingroup$ @Drupalist We don't do homework grading, sorry. You should be able to convince yourself that your proof is correct (that's an advantage of mathematics). If you think there's a gap, that makes for a more specific question than "am I correct". $\endgroup$
    – Raphael
    Mar 2, 2015 at 11:50

2 Answers 2

Reset to default
2
$\begingroup$

Hint: If $A$ reduces to $\overline{A}$ then $\overline{A}$ reduces to $A$ (using the same reduction).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Your answer means there is no R.E. set say $A$ such that $\bar{A}$ is not R.E and $A \leq_m\bar{A}$ , is it really right?! $\endgroup$
    – M a m a D
    Mar 1, 2015 at 21:52
  • $\begingroup$ I meant what I wrote. You draw the conclusions. $\endgroup$
    – Yuval Filmus
    Mar 1, 2015 at 21:54
  • $\begingroup$ If $A$ is R.E and $\bar{A}$ is not then $\bar{A} \leq_m A$ is a contradiction, because this reduction says $\bar{A}$ must be R.E! If your answer is true then there must be two disjoint cases: whether $\bar{A}$ must be R.E or $A$ is not mapping reducible to $\bar{A}$ $\endgroup$
    – M a m a D
    Mar 1, 2015 at 22:00
  • $\begingroup$ I posted my prove as the answer, would you please take a look at it to see if it is right? $\endgroup$
    – M a m a D
    Mar 2, 2015 at 8:28
  • $\begingroup$ That's the job of your TA, not mine. $\endgroup$
    – Yuval Filmus
    Mar 2, 2015 at 15:29
1
$\begingroup$

Finally I proved it this way, first we need a few definitions:

$co-W = \{A | \overline{A} \in W\}$

set $W$ is called m-closed if for $A \in W$, and for any $B \leq_mA$ then $B \in W$

We already knew (Davis book page 209)

If $W$ is m-closed or 1-closed then so is $co-W$

Because the set of all $r.e.$ sets is m-closed so is $co-r.e.$,

$A \in r.e. \rightarrow \overline{A}\in co-r.e.$ //by definition

$A \leq_m \overline{A}$ because $\overline{A} \in co-r.e.$ and $co-r.e.$ set is m-closed so $A \in co-r.e.$

$A \in co-r.e.$ it implies $\overline{A} \in r.e.$

$A \in r.e. \land \overline{A}\in r.e. \rightarrow A \in recursive$

and the proof is completed

It implies any set $\psi$ that is m-closed or 1-closed, if $A\in\psi$ and $A \leq_m \overline{A}$ or $A\in\psi$ and $A \leq_1 \overline{A}$, then $\overline{A}\in\psi$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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