[proofplan]
We first convert the two directional hypotheses into the single biconditional required by a many-one reduction, restricted to valid source instances. The yes-to-yes implication gives the forward direction, while the no-to-no implication gives the contrapositive of the reverse direction. We then define a total map on all encoded strings by sending malformed source strings to a fixed no-instance of $B$, and verify both the polynomial-time bound and the membership biconditional.
[/proofplan]
[step:Extract the forward implication on valid source instances]
Let $x \in V_A$ be a valid source instance. The first hypothesis states directly that
\begin{align*}
x \in L_A \implies f(x) \in L_B.
\end{align*}
Since $f: V_A \to V_B$, the string $f(x)$ is a valid encoding of an instance of $B$, so the membership statement $f(x) \in L_B$ is well-defined.
[/step]
[step:Turn the no-to-no implication into the reverse implication]
Let $x \in V_A$. The second hypothesis says
\begin{align*}
x \notin L_A \implies f(x) \notin L_B.
\end{align*}
By contraposition, this is equivalent to
\begin{align*}
f(x) \in L_B \implies x \in L_A.
\end{align*}
Combining this reverse implication with the forward implication from the previous step gives, for every $x \in V_A$,
\begin{align*}
x \in L_A \iff f(x) \in L_B.
\end{align*}
[guided]
Fix a valid source instance $x \in V_A$. The no-to-no hypothesis is
\begin{align*}
x \notin L_A \implies f(x) \notin L_B.
\end{align*}
The desired definition of many-one reduction needs the reverse yes-direction,
\begin{align*}
f(x) \in L_B \implies x \in L_A.
\end{align*}
These two implications are logically equivalent by contraposition: an implication $P \implies Q$ is equivalent to $\neg Q \implies \neg P$. Here $P$ is the assertion $x \notin L_A$, and $Q$ is the assertion $f(x) \notin L_B$. Therefore $\neg Q$ is $f(x) \in L_B$, and $\neg P$ is $x \in L_A$.
Thus the no-to-no direction supplies exactly the reverse implication:
\begin{align*}
f(x) \in L_B \implies x \in L_A.
\end{align*}
Together with the yes-to-yes hypothesis
\begin{align*}
x \in L_A \implies f(x) \in L_B,
\end{align*}
we obtain the biconditional
\begin{align*}
x \in L_A \iff f(x) \in L_B.
\end{align*}
This is the central correctness condition for a many-one reduction on valid instances.
[/guided]
[/step]
[step:Extend the map to all encoded source strings]
Define the total map
\begin{align*}
\widetilde f: \Sigma_A^* &\to \Sigma_B^*
\end{align*}
by the following rule. If $x \in V_A$, set $\widetilde f(x) = f(x)$. If $x \notin V_A$, set $\widetilde f(x) = b_0$.
This definition is total because every string $x \in \Sigma_A^*$ either belongs to $V_A$ or does not. It is polynomial-time computable because membership in $V_A$ is decidable in polynomial time, $f$ is computable in polynomial time on inputs in $V_A$, and the output $b_0$ is a fixed string.
[/step]
[step:Verify the many-one reduction equivalence for every encoded string]
Let $x \in \Sigma_A^*$.
If $x \in V_A$, then $\widetilde f(x) = f(x)$ by definition, and the biconditional proved above gives
\begin{align*}
x \in L_A \iff \widetilde f(x) \in L_B.
\end{align*}
If $x \notin V_A$, then $x \notin L_A$ because $L_A \subseteq V_A$. Also $\widetilde f(x) = b_0$, and $b_0 \notin L_B$ by hypothesis. Hence both sides of
\begin{align*}
x \in L_A \iff \widetilde f(x) \in L_B
\end{align*}
are false, so the equivalence holds.
Therefore $\widetilde f: \Sigma_A^* \to \Sigma_B^*$ is polynomial-time computable and satisfies the defining correctness condition for a polynomial-time many-one reduction from $A$ to $B$.
[/step]
