Revisions - MathOverflow

Return to Answer

Explain about making them distinct

view source

edited Apr 28 2011 at 3:11

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.

edited body; added 6 characters in body

view source

edited Apr 27 2011 at 18:33

Joel David Hamkins
76.8k●8●192●355

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

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. 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([\psi],[\phi])$.B([\phi],[\psi])$.

Observe that $\phi\iff \theta_1(n,m)\iff A(\text{Sub}(n,n,m),\text{Sub}(m,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(\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

Added proof of double fixed point lemma

view source

edited Apr 27 2011 at 18:27

Joel David Hamkins
76.8k●8●192●355

I believe the

The answer is no, because I believe thatSmullyan's and here is acounterexample. The proof relies on the double recursion theorem allows us fixed pointlemma, a generalization of the usual Goedel fixed pointlemma producing two statements forming a fixed point withrespect to a system, and I provide a proof below. Using it,we may produce two sentences $\phi$ and $\psi$ such that

(I couldn't find a good reference to cite for

Here is the double-fixed-point double fixed point lemma, so if someone could provide thatwhich I believe isdue to Smullyan, or correct my argument if connected with his double recursiontheorem. I have made a mistake in 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, Iwould then there are sentences $\phi$and $\psi$ such that

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

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

Proof. Let $\text{Sub}$ be very grateful.)the substitution operator, theprimitive 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)\iffA([\theta_1(n,m)],[\theta_2(n,m)])\iff A([\phi],[\psi])$.

Also observe $\psi\iff \theta_2(n,m)\iffB([\theta_1(n,m)],[\theta_2(n,m)])\iff B([\phi],[\psi])$,as desired. QED

deleted 5 characters in body

view source

edited Apr 27 2011 at 16:25

Joel David Hamkins
76.8k●8●192●355

I believe the answer is no, because I believe that Smullyan's double recursion theorem allows us to produce two 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$, with a having no smaller standard proof of $\psi$. ThusIn particular, $\psi$ \phi$ would also be truea provable, and so there would be an even smaller proof of $\phi$. Thusfalse statement, there could be no smallest proof of $\phi$, contradicting PA. $\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 as above, there would have to be a smaller standard proof of $\psi$, and hence so $\psi$ would be true, and so there would be an even smaller standard proof of $\phi$, so again\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 proof statement could be have the smallest proof. 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.

(I couldn't find a good reference to cite for the double-fixed-point lemma, so if someone could provide that, or correct my argument if I have made a mistake in that, I would be very grateful.)

view source

answered Apr 27 2011 at 15:05

Joel David Hamkins
76.8k●8●192●355

I believe the answer is no, because I believe that Smullyan's double recursion theorem allows us to produce two 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$, with a smaller standard proof of $\psi$. Thus, $\psi$ would also be true, and so there would be an even smaller proof of $\phi$. Thus, there could be no smallest proof of $\phi$, contradicting 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 as above, there would be a smaller standard proof of $\psi$, and hence an even smaller standard proof of $\phi$, so again, 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 proof could be smallest. 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.

(I couldn't find a good reference to cite for the double-fixed-point lemma, so if someone could provide that, or correct my argument if I have made a mistake in that, I would be very grateful.)