Skip to main content
3 of 6
oops, missed \neg; added 26 characters in body
none
  • 21
  • 2
  • 4

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

I think the actual answer is "yes". If $\phi$ and $\psi$ are both independent and are both $\Pi^0_1$ then they are both true. Now consider the Turing machine T that checks for $i=1,2,3\ldots$ whether $i$ is a witness to $\neg(\phi\vee\psi)$, stopping if it finds one. If we can prove T halts, that means one of $\phi,\psi$ is false and therefore not independent. If we can prove T does not halt, that shows $\phi$ and $\psi$ are both true, therefore not independent. So the halting problem for T is independent and therefore $\phi\vee\psi$ is independent.

I'm not that confident in the correctness of the above either, though.

none
  • 21
  • 2
  • 4