6
$\begingroup$

It is my understanding that Gödel's second incompleteness theorem says roughly that

there exists a sentence $\varphi$ such that neither $\varphi$ nor $\neg\varphi$ is provable in Peano's arithmetic. However one of them is true (in the structure $\mathbb{N}$).

If $\varphi$ is a formula in the style : "for all integers $n$, then $\psi(n)$". For me, if $\varphi$ is false, proving it false is simply exhibing a counterexemple $n_f$ such that $\neg\psi(n_f)$. Therefore if it is false, then it must provably false, doesn't it?

Therefore, it someone manage to prove that it not provable, does it mean that $\varphi$ must be true?

Is this reasoning correct?

$\endgroup$
2
  • $\begingroup$ I think perhaps you meant to say "Therefore, if someone manages to prove that it is not decidable, does that mean..." , since provable means "proven true" but decidable means "proven true or proven false". $\endgroup$ – DanielV Apr 10 '19 at 21:18
  • $\begingroup$ Someone call it a Goldbach-like sentence and we have that "A $\Pi_1$ sentence $\varphi$ is true iff $\lnot \varphi$ is not provable from $\mathsf Q$". $\endgroup$ – Mauro ALLEGRANZA Apr 11 '19 at 6:30
10
$\begingroup$

No, because you may not be able to prove that the counterexample is false in Peano arithmetic. In other words, $\neg\psi(n_f)$ itself may be another statement that is true but not provable in PA.

However, if for every $n$, you know that either $\psi(n)$ or $\neg\psi(n)$ is provable in Peano arithmetic, then your conclusion is correct. For example, this will be the case if $\psi$ is quantifier-free, because then $\psi$ is a Boolean combination of purely numerical statements like 2+2=4 and you can always prove or refute such a statement in Peano Arithmetic.

$\endgroup$
3
  • $\begingroup$ Perfect thanks, yes I had in mind simple (quantifier free) statement. To be complete, would for example the Riemann hypothesis fit in here (I'm NOT pretending that someone would prove it this way, this is just a "mind game"). The negation would be quite simple no? just, there exist a complex number $x$ with real part different from 1/2, such that $\zeta(x)=0$. $\endgroup$ – Thomas Lesgourgues Apr 10 '19 at 17:22
  • $\begingroup$ @Thomas The usual statement of the Riemann hypothesis does not manifestly have the property that if a counterexample exists, it is provable (verifying a zero of a complex function is not an effective procedure.) Nonetheless, there are other versions of RH that do have this property, so it does fall into the “true if undecidable” category. math.stackexchange.com/questions/3157609/… $\endgroup$ – spaceisdarkgreen Apr 10 '19 at 21:05
  • $\begingroup$ @Thomas (Actually Carl’s answer in the same question addresses only this point, whereas mine has a lot of stuff that is irrelevant to your question, so maybe read that instead.) $\endgroup$ – spaceisdarkgreen Apr 10 '19 at 21:14
4
$\begingroup$

First of all, if I can prove that PA cannot prove $\varphi$, that does not mean that $\varphi$ is true ... for if $\varphi$ is false, then of course PA will not be able to prove it. To give a concrete example: I can (well, a good mathematical logician better than I am can do this) prove that PA cannot prove that $1+1=3$ ... but obviously that does not mean that $1+1=3$

So, I think what you are trying to say is: If I can prove that PA cannot prove either $\varphi$ or $\neg \varphi$, then that must mean that $\varphi$ is true.

Second, your argument for this works when $\varphi$ is of the form $\forall x \ \psi(x)$ where $\psi(x)$ is quantifier-free, for if it is false, then $\neg \psi(n)$ is true for some $n$, and since PA can prove all quantifier-free truths expressed in the language of arithmetic, PA can prove this, and hence would be able to prove $\neg \varphi$, which goes against the assumption that PA could not prove this. So yes, your reasoning is correct .... for those kinds of statements $\varphi$ ...

So, the question is: what kinds of interesting statements are there that contain a single quantifier, and for which you can prove that PA cannot prove either it or its negation?

$\endgroup$
2
  • $\begingroup$ Hi, I agree I need to restrict myself to quantifier free $\psi$. But I'm not suggesting that I would know that there is no counterexample to it. I'm assuming that someone might prove that the statement is not provable. And I use the fact that if it were false, it must be provably false, therefore it must be true. I'm never assuming that I know the statement false because I cannot exhibit a counterexample. $\endgroup$ – Thomas Lesgourgues Apr 10 '19 at 17:34
  • $\begingroup$ @ThomasLesgourgues I see. So what you claim is that any statement that is a single universal statement and that is proven (by some stronger theory than PA) to be unprovable_by_PA must be true, since PA should be strong enough (and indeed it is) to simply go through all numbers and find a counterexample. Well, I can agree with that ... but how many interesting statements can really be formulated in the language of arithmetic that consists of a single universal quantifier? Not that many, I would wager. $\endgroup$ – Bram28 Apr 10 '19 at 17:59
3
$\begingroup$

You are confusing theories and models. Theories are all the statements that are true given a number of axioms. Gödels incompleteness theorem deals with theories. A model is a mathematical structure that satisfies a theory. In a model every statement is either true or false and your counterexample idea would work, but that would only prove something for the model.

Consider groups for example. If we take the theory of group then we should not be able to prove $(\forall x)(\forall y)(xy=yx)$, i.e. every group is abelian as there exist abelian groups and non-abelian groups.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.