Let $\phi,\psi\in\Pi\_1^0$ be independent of PA.
Is the disjunction $\phi\vee\psi$ independent of PA?



The disjunction property in Peano Arithmetic?
The answer is no, and here is a counterexample. The proof
relies on the double fixed point lemma, a generalization of
the usual Goedel fixed point lemma producing two statements
forming a fixed point with respect to a system, and I
provide a proof below. Using it, we may produce two
distinct sentences $\phi$ and $\psi$ such that


* $\phi$ asserts that for every proof of $\phi$, there is
a smaller proof of $\psi$, and
* $\psi$ asserts that for every proof of $\psi$, there is
a smaller proof of $\phi$.


In this case, each of these statements has complexity
$\Pi^0\_1$. Let me argue that they are independent.


First, observe that both $\phi$ and $\psi$ must be true in
$\mathbb{N}$. If $\phi$ were false, then there would be a
standard proof of $\phi$, having no smaller standard proof
of $\psi$. In particular, $\phi$ would be a provable, false
statement, contradicting $\mathbb{N}\models$PA. A symmetric
argument applies to $\psi$.


Second, observe that neither is provable (meaning provable
in PA throughout). If $\phi$ were provable, then there
would be a standard proof of $\phi$, and thus there would
have to be a smaller standard proof of $\psi$, and so
$\psi$ would be true, and so there would be an even smaller
standard proof of $\phi$. Thus, there could be no smallest
proof of $\phi$, a contradiction. And the same for $\psi$.


Thus, both the sentences are true unprovable assertions,
and hence independent.


Finally, observe that the disjunction $\phi\vee\psi$ is
provable. If both $\phi$ and $\psi$ fail in a model of PA,
then that model would have proofs of both $\phi$ and
$\psi$, but neither statement could have the smallest
proof, for if it did, then the other statement would be
true, contrary to assumption. This contradicts PA, since
the smallest proof of one of them must be smaller than any
proof of the other.


Thus, we have independent $\Pi^0\_1$ statements $\phi$ and
$\psi$, such that $\phi\vee\psi$ is provable.




---


Here is the double fixed point lemma, which I believe is
due to Smullyan, connected with his double recursion
theorem. I use $[\phi]$ here to denote the Goedel code of
$\phi$.


**Double Fixed Point Lemma.** Suppose that $A(x,y)$ and
$B(x,y)$ are two formulas, then there are sentences $\phi$
and $\psi$ such that


* $\phi$ is provably equivalent to $A([\phi],[\psi])$, and
* $\psi$ is provably equivalent to $B([\phi],[\psi])$.


Proof. Let $\text{Sub}$ be the substitution operator, the
primitive recursive function such that
$\text{Sub}([\eta(x,y)],n,m)=[\eta(n,m)]$. Let
$\theta\_1(x,y)=A(\text{Sub}(x,x,y),\text{Sub}(y,x,y))$ and
$\theta\_2(x,y)=B(\text{Sub}(x,x,y),\text{Sub}(y,x,y))$. Let
$n=[\theta\_1(x,y)]$ and $m=[\theta\_2(x,y)]$. Finally, let
$\phi=\theta\_1(n,m)$ and $\psi=\theta\_2(n,m)$.


Observe that $\phi\iff \theta\_1(n,m)\iff
A(\text{Sub}(n,n,m),\text{Sub}(m,n,m))$ $\iff
A([\theta\_1(n,m)],[\theta\_2(n,m)])\iff A([\phi],[\psi])$.


Also observe $\psi\iff \theta\_2(n,m)\iff
B(\text{Sub}(n,n,m),\text{Sub}(m,n,m))$ $\iff
B([\theta\_1(n,m)],[\theta\_2(n,m)])\iff B([\phi],[\psi])$,
as desired. QED


Note that we can arrange that $\phi$ and $\psi$ are
distinct simply by ensuring that $\theta\_1(n,m)$ and
$\theta\_2(n,m)$ are not syntactically the same sentence,
such as by replacing $\theta\_1(x,y)$ with its conjunction,
but ensuring that $\theta\_2(x,y)$ does not have such a
form.


The lemma easily generalizes to any size system and indeed,
to infinite systems of fixed points.


