I think Carl's answer has the same error I originally made--it doesn't address that both formulas have to be $\Pi_1^0$.  The negation of a $\Pi_1^0$ formula is $\Sigma_1^0$.