More than eighty five years ago  Kurt Gödel proved, roughly speaking, that no fixed set of a formal facts (like 23+14=37) and rules (like x+y = y+x) can establish the truth or falsity of every theorem about arithmetic over the counting numbers.

This result, known as Gödel’s Theorem, has a lot of formal and informal consequences. It means there is no computer program that can infallibly decide whether or not a statement about arithmetic is true or false. It means we will never know everything about arithmetic, though we may know more and more as time goes on. It means, however, that this knowledge will not come about purely as a result of manipulating formal facts and rules. We will have to rely on other sources, including experiment.

Even more interesting is the fact that this situation – the limits of facts and rules – reappears in other domains, including games, natural language, and even psychology.

Experiments? What can mathematicians learn from experiments? Experiments aren’t useless, they can, for example, lead to conjectures. But unless these conjectures are proved, how can they contribute to mathematical knowledge?

It all depends on what you mean by experiment. Almost all conventional mathematics can be done in an axiomatic system called Zermelo Fraenkel set theory,  (ZF), sometimes with the Axiom of Choice (ZFC). (If you want details consult Wikipedia). It’s obviously crucial that the facts and rules of ZFC be consistent (non contradictory). Otherwise every statement (and its opposite) can be formally derived.

Yet Gödel’s results implie that the consistency of ZFC cannot be proven in ZFC; in other words, the consistency of ZFC is not a theorem of conventional mathematics. Nevertheless we believe it, because we use ZFC. People win prizes and piles of money for proving things in ZFC. If ZFC were inconsistent, this would be money for old rope. So it’s safe to say that mathematicians strongly believe that ZFC is consistent.

But believing is not knowing, you say. The consistency of ZFC is not real mathematical knowledge. But what about all the results proved from the facts and rules of ZFC? They’re all tainted because they all assume consistency. So, strictly speaking, we cannot say we “know” that the four colour theorem is true even though there is now a proof. Strictly speaking, we only believe it.

It’s tempting to take refuge in simpler systems, like Peano Arithmetic (PA). PA consists of a handful of simple rules, basically the inductive definitions of the arithmetic operations. To these we add the principle of mathematical induction: to prove P(n) for all n, prove that P(0) is true, and prove that P(n+1) is true assuming P(n) is true.

All sensible and reliable. But how do we know that mathematical induction works?

In short, we know that induction is valid because (1) it makes complete sense, and (2) it has never let us down. In other words it feels right and in our (extensive) experience works in practice.

This last paragraph is not formal mathematics. We are invoking judgement and experience.

Nevertheless I would argue that we have the right to say we “know” (not just believe) that induction is valid. Because we believe with at least the same degree of certainty that the law of gravity is valid. And for the same reasons – judgement and experience. The law makes sense and has never let us down. We know it.

For that matter, how do we know that x+y=y+x is valid or even that 23+14=37 is true? By insight and experience. (These are not obvious to kids learning arithmetic.)

In other words, mathematics, like physics, has an empirical element. ZFC has been around for about a century and we can consider the experience of using it as a big experiment. The hypothesis is that ZFC is consistent and in a century of intensive use no contradiction has shown up. Hypothesis confirmed!

There are other formal systems of set theory that are strong enough to do mathematics. One is Gödel-Bernays (GB)  which has the advantage that there are only finitely many axioms (ZF has axiom schemas). But GB is equiconsistent with ZF (and ZFC): if one is consistent they all are. So we can use it with confidence.

There is another system, namely Quine’s New Foundations (NF). It’s not known to be equiconsistent with ZFC so the results of the century-long experiment don’t necessarily apply. NF makes sense and hasn’t produced a contradiction, but we don’t have nearly the same experience with NF as we have with ZFC. This means we can’t have nearly the same confidence in results obtained using NF that we do in results obtained using ZFC.

OK, but what does all this have to do with games, natural language, and psychology? Well, this is where is gets interesting … but look at that word count! This post is already too long.

I promise to take this up in the next post, which will be real soon. But think about facts and rules vs feelings and experience and you can probably figure it out for yourself.