George Boolos and Gödel's Second Incompleteness Theorem

Question

In Mind, Vol. 103, January 1994, pp. 1-3, George Boolos wrote:

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?)

Answer 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)?

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.

Answer 2

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

Answer 3

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.