Return to Answer

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\neg\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, we have a proof that $\phi$ and $\psi$ are both true, therefore they are 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.

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" but several edit attempts haven't got the proof right, so I'll see if I can fix it offline instead of keeping on repeatedly editing.

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, we have a proof that $\phi$ and $\psi$ are both true, therefore they are 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.

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\neg\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, we have a proof that $\phi$ and $\psi$ are both true, therefore they are 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.

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.

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, we have a proof that $\phi$ and $\psi$ are both true, therefore they are 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.