I have been led to believe that the following statement
$X \in NP \land Y \not\in NP \implies X \not\le^m_p Y$
But I am having difficult proving it. And I'm not even sure it IS true anymore.
At first it seemed reasonable that it was true. Since X is in NP there must exist some NP-complete problem Z that it reduces to and my thinking is that any other problem that X reduces to must also reduce to this NP-complete problem Z, that is, since X is in NP both it and any problem it can be reduced to must also reduce to an NP-complete problem Z so it cannot be the case that X can be reduced to a problem Y that is NOT in NP. This is not my proof but simply my intuition for why the statement is True.
I was hoping initially to prove it by contradiction:
suppose not, that is, suppose $X \in NP \land Y \not\in NP$ but $X \le^m_p Y$
since $X \in NP$ it must be that $\exists$ a poly-time verifier algorithm $B$ such that
$\forall$ inputs $x \in X$ : $\exists$ certificate $t$ s.t. $B(x,t) = yes$
and since $X \le^m_p Y$ it must be that $\exists$ a poly-time reduction $f$ such that
$\forall$ inputs $x$ $x \in X \iff f(x) \in Y$
it follows then that $f(x) \in Y \iff x \in X \iff \exists t B(x,t) = yes$
Then at this point I was hoping to reverse engineer the verifier B to come up with a poly-time verifier for Y thus contradicting the supposition that $Y \not\in NP$ similar to what the answer to this question does:
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
But that direction doesn't really work and I haven't found way to use the reasoning above to try and show that $X \not\in NP$ and achieve contradiction that way
And so this is where I am stuck. Am I missing something or am I wrong in my intuition that the statement is true?