Saturday, 14 October 2006

proof theory - Independence of PA implies independence of PA union all true $Pi_1$ statements

The claim you have asked us to prove is not true. If PA is consistent, then by the Incompleteness Theorem there are $Pi_1$ statements that are independent of PA, such as Con(PA), which can be seen to be $Pi_1$ when expressed in the form "no number is the code of a proof of a contradiction in PA". Thus, if PA is consistent, then Con(PA) is a statement that is independent of PA but provable in $PA_1$, so it is a counterexample to your claim.



Perhaps a more striking counterexample would be $negtext{Con(PA)}$, which is independent of PA, but refutable in $text{PA}_1$. More generally, any statement having complexity $Sigma_1$ or $Pi_1$ that is independent of PA will be a counterexample to your claim, since such statements are settled by $text{PA}_1$.



Perhaps the folklore result you meant to ask about is the following?



Theorem. If a $Pi_1$ statement is independent of PA, then it is true.



Proof. If a $Pi_1$ statement $sigma$ is independent of PA, then it is true in some model $Mmodels PA$. The standard model $mathbb{N}$ is an initial segment of $M$, and since the statement $sigma$ is $Pi_1$, it has the form $sigma = forall n varphi(n)$, where $varphi$ has only bounded quantifiers. Since $sigma$ holds in $M$, it holds for all standard $n$ in $M$ and hence $sigma$ is true in the standard model. In other words, it is true. QED



Note that the proof that $sigma$ is true is not a proof in PA, but rather in a theory, such as ZFC, that is able to theorize about models of PA. So another way to view the theorem is as the claim that if ZFC can prove that a given $Pi_1$ statement is independent of PA, then ZFC can also prove that it is true.

No comments:

Post a Comment