George Boolos and Gödel's Second Incompleteness Theorem

And so on. In fact, if a claim can be proved, then it can be proved that the claim can be proved. And that too can be proved.

Now, two plus two is not five. And it can be proved that two plus two is not five. And it can be proved that it can be proved that two plus two is not five, and so on.

Thus: it can be proved that two plus two is not five. Can it be proved as well that two plus two is five? It would be a real blow to math, to say the least, if it could. If it could be proved that two plus two is five, then it could be proved that five is not five, and then there would be no claim that could not be proved, and math would be a lot of bunk.

So, we now want to ask, can it be proved that it can't be proved that two plus two is five? Here's the shock: no, it can't. Or, to hedge a bit: if it can be proved that it can't be proved that two plus two is five, then it can be proved as well that two plus two is five, and math is a lot of bunk. In fact, if math is not a lot of bunk, then no claim of the form "claim X can't be proved" can be proved.

...and...

...yes, it can be proved that if it can be proved that it can't be proved that two plus two is five, then it can be proved that two plus two is five. [i.e. what's asserted above can be proved]

[parentheticals added by me]

Please excuse the potentially ignorant questions:

1. Why proving that two plus two is four does not constitute as a proof that two plus two cannot be five (thus cannot be proved as such)?
2. Should I understand that the only way to prove that it cannot be proved that two plus two cannot make five is to prove that the system within we work is consistent, and that there is no other way? (If so, what is the proof that there is no other way?)

3 Answers

While $2+2=4$ seems like an easy target for a way to prove $2+2\neq 5$, you're implicitly assuming that $4\neq 5$ and that $4=5$ cannot be proved. But if arithmetic is inconsistent, you can prove that $4=5$, in which case $2+2=5$ as well.

So stating that $2+2=5$ is not provable is a way of saying that $0=1$ is not provable. But now recall that the standard formulation of $\operatorname{Con}(T)$ is "$T$ does not prove $0=1$".

To your second question, the answer is more subtle than that. You need to assume that the system you work in is consistent, but that's why we have a meta-theory. Set theory proves that arithmetic is consistent, so working inside set theory you can prove that $2+2=5$ is not provable from the axioms of arithmetic. Of course, now you might want to ask, could set theory prove that $2+2=5$ is impossible? And Gödel snarks in the corner and says "try again". So you have to move to a stronger theory, and so on and so forth.

It's turtles all the way down.

• What's the distinction between proving that 2+2=5 is not provable from the axioms of arithmetic and proving that 2+2=5 is impossible? – Graham Aug 24 '18 at 12:44
• Well, "impossible" has an implicit (and thus vague) context. – Asaf Karagila Aug 24 '18 at 13:06

Why proving that two plus two is four does not constitute as a proof that two plus two cannot be five (thus cannot be proved as such)?

A proof that $2+2=4$ does indeed constitute a proof that $2+2\neq 5$ (assuming you can also prove that $4\neq 5$, which presumably your system of mathematics is strong enough to do). The problem is in your final parenthetical. Just because we can prove that $2+2\neq 5$ does not mean that no proof of $2+2=5$ exists. Maybe there exist proofs of false statements!

Should I understand that the only way to prove that it cannot be proved that two plus two cannot make five is to prove that the system within we work is consistent, and that there is no other way? (If so, what is the proof that there is no other way?)

Well, it's not so much that there is no other way, but rather that the two statements are basically identical. If the system in which we work were inconsistent, then it could prove everything, since anything follows from a contradiction. So if we prove that our system cannot prove $2+2=5$ (or any other statement), that would in itself immediately prove that our system is consistent. Conversely, if we prove our system is consistent, then we conclude that it cannot prove that $2+2=5$ (since if it could, our system would prove a contradiction since we can also prove that our system proves $2+2\neq 5$). So proving that our system cannot prove $2+2= 5$ is essentially the same thing as proving that our system is consistent.

• If $4=5$, then $2+2=4$ does not constitutes a proof that $2+2\neq 5$. All you do is dress the problem in a different hat, and claim it's a different problem. – Asaf Karagila Aug 23 '18 at 7:03
• @Eric Obviously, proving the consistency of the system solves the problem. I just do not see how your argument proves that proving the consistency of the system is the only way to prove that it cannot be proved that two plus two is five. What is the proof of that statement? – blackened Aug 23 '18 at 7:05
• @blackened Ultimately that depends on the definition of "only way". To me, and apparently to Eric as well, a good way to define "the only way to prove X is proving Y" is that whatever proves X proves Y automatically (and in this case, you can even require the converse as well - that whatever proves Y proves X automatically - and it still works for this question). Assuming this definition of "only way", Eric proved in his answer that proving consistency is indeed the only way, because he showed that proving X proves Y and vice-versa (where X is 2+2=5 and Y is consistency). – Pedro A Aug 23 '18 at 10:43
• @AsafKaragila: OK, but any reasonable system of mathematics can also prove that $4\neq 5$. This together with $2+2=4$ does prove that $2+2\neq 5$. (Of course, this still doesn't mean that you can't also prove $2+2=5$, and that $4=5$.) – Eric Wofsey Aug 23 '18 at 14:56
• @AsafKaragila: Right, but I never claimed that you can't prove $4=5$. I only claimed that you can go from a proof of $2+2=4$ to a proof of $2+2\neq 5$ (which is because you can also prove that $4\neq 5$). – Eric Wofsey Aug 23 '18 at 15:03
1. From a proof of $2 + 2 = 4$ it follows a proof of $2 + 2 \neq 5$, but it does not follow that the system cannot prove $2 + 2 = 5$ because if the system is not consistent, then the system can prove everything according to the principle of explosion, in particular for every statement $A$ the system can prove $A$ and its negation $\lnot A$.

2. As a consequence, the only way to be sure that $2 + 2 = 5$ cannot be proved in the system is the fact that the system is consistent. According to the principle of explosion, to prove$-$in the meta-theory$-$that the system is consistent it is enough to show that there is a formula that the system cannot prove.

Gödel's second incompleteness theorem claims that for any consistent and computable axiomatic system $S$ that is powerful enough to describe the arithmetic of the natural numbers (e.g., the Peano axioms or Zermelo–Fraenkel set theory with the axiom of choice), the consistency of $S$ cannot be proved within $S$ itself. This means that:

• in $S$ it is possible to canonically define a formula $Cons(S)$ expressing the consistency of $S$; typically, $Cons(S)$ states "there is no natural number that codes a derivation of '$0=1$' in $S$";

• $S \not\vdash Cons(S)$, that is, there is no derivation of $Cons(S)$ in $S$; this is enough to prove that $S$ is consistent in the meta-theory, but it means that you cannot prove the consistency of $S$ within $S$.

Of course, you can prove the consistency of $S$ in a stronger system $S'$ containing $S$, but if $S'$ is consistent then the you cannot prove the consistency of $S'$ within $S'$ (or within $S$).

• Hello, I did not downvote, but upvoted. Great answer. I'd like to ask for some clarification by the way (I'm new to all these Godel stuff): According to your second bullet, Godel's theorem implies that there is no way to start from the axioms of ZFC and conclude Con(S), right? In other words, none of the countably infinite proofs that can exist in ZFC is a proof of Con(S), right? And what I just said is not a proof of Con(S) within S because in my reasoning I used Godel's Theorem, which does not follow from S alone, right? – Pedro A Aug 23 '18 at 10:58
• Your first claim is false. "2+2≠5" is abbreviation for "¬(2+2=5)" which can be proven from "2+2=4". The principle of explosion has nothing to do with this. – user21820 Aug 23 '18 at 11:37
• @user21820 - Of course, "$2+2\neq 5$" is abbreviation for "$\lnot (2+2=5)$". But the fact that you can prove that $2+2 = 4$ is not enough to conclude that you can prove that $2+2 \neq 5$. Indeed, if your system is inconsistent, then you can prove whatever you want, in particular $2+2=5$ (and $2+2 \neq 5$) as well. If you assume that your system is consistent, then a proof of $2+2=4$ implies a proof of $2+2 \neq 5$. – Taroccoesbrocco Aug 23 '18 at 11:44
• @Taroccoesbrocco: Look you are simply wrong about that. By your own words in your last comment, what I stated is perfectly correct, since if the system is inconsistent then you can prove "2+2≠5" from "2+2=4", exactly as I claimed. – user21820 Aug 23 '18 at 11:46
• @user21820 - You are totally right, thank you! What a mistake! I'm still in holiday... I fixed the sentence. – Taroccoesbrocco Aug 23 '18 at 12:21