This post contains maths…

Unprovability and Beyond

In 1931 Kurt Gödel was 25 and published a paper following on from his doctoral work - titled “Über formal unentscheidbare Sätze der “Principia Mathematica” und verwandter Systeme”, or in English “On Formally Undecidable Propositions of ‘Principia Mathematica’ and Related Systems”, and provided to the world one of the world’s most significant achievements in Logic. As John von Neumann put it [1]:

“Kurt Gödel’s achievement in modern logic is singular and monumental – indeed it is more than a monument, it is a landmark which will remain visible far in space and time. … The subject of logic has certainly completely changed its nature and possibilities with Gödel’s achievement.”

But little is truly understood about this result, nor why what happened in the latter part of the 20th C. was so important in our ongoing search for suitable foundations of mathematics.

What foundations to build mathematics on?

Calculus Conundrums

It’s hard for non-mathematicians to appreciate what is wrong with mathematics. It seems so stoic, and objective, but anyone who takes some time to learn in any detail the actual work of mathematics will come to a startling realisation; mathematics is a language, and like any language, it can carry opinions coded into algorithms (more on this later) and theorems carry the weight of many human assumptions.

But mathematics just ‘works’ right? Right?

Well, yes. And no.

Bishop Berkeley, an 18th Century Irish Bishop of Cloyne, philosopher and mathematician, wrote a text called ‘The Analyst’ [2], subtitled

A DISCOURSE Addressed to an Infidel MATHEMATICIAN. WHEREIN It is examined whether the Object, Principles, and Inferences of the modern Analysis are more distinctly conceived, or more evidently deduced, than Religious Mysteries and Points of Faith

Heavy stuff, no? Well, he had a problem - ‘fluxions’. What are these? Well, he describes them as follows;

It must, indeed, be acknowledged, that [Newton] used Fluxions, like the Scaffold of a building, as things to be laid aside or got rid of, as soon as finite Lines were found proportional to them. But then these finite Exponents are found by the help of Fluxions. Whatever therefore is got by such Exponents and Proportions is to be ascribed to Fluxions: which must therefore be previously understood. And what are these Fluxions? The Velocities of evanescent Increments? And what are these same evanescent Increments? They are neither finite Quantities nor Quantities infinitely small, nor yet nothing. May we not call them the Ghosts of departed Quantities?

The problem that Berkeley had comes from the following descriptions; We are all familiar with taking the gradiant of a line. On an $xy$ plane, each point on a line is given as $(x,y)$ and for a function generating a line, where $y = f(x) = x+2$ each co-ordinate on the line is given by $(x,x+2)$ (such a set is called the graph of the function - graph refers to the set, not the line). The gradiant is given by the change in y, written $\Delta y$ divided by the change in x, or $\Delta y / \Delta x$. This makes sense - we’re asking ‘what change in $y$ happens for every singular change in $x$?’.

But what about a graph that has a ‘bend’? Like $y = f(x) = x^2$? Well, this is where stuff gets tricky. Take two points - $(2,4)$ and $(3,9)$, the gradient here is clearly 5 (x changed 1, y changed 5, so it follows). But now take the gradient of $(1,1)$ and $(2,4)$ - it’s clearly 3. Now take $(2,4)$ and $(2.5,6.25)$ - the gradient is now $2.25 / 0.5 = 4.5$… so how can we make any sense of this?!?

Well, this was the coincident genius of Newton and Leibniz; Pick 2 points $(x_1,x_1^2)$ and $(x_2,x_2^2)$ where $x_1 < x_2$. Calculate the gradient of the straight line between this pair, then choose some $x_3$ where $x_1 < x_3 < x_2$ and calculate the gradient between $(x_1,x_1^2)$ and $(x_3,x_3^2)$ and you’ll see that the gradient is not as steep; it is clear that, so long as there are no breaks in the line, then we get $\Delta x / \Delta y$ approaches some value based on which $x_1$ we chose. If we make choices of points that get closer and closer and closer to $x_1$ we eventually will see that the value is approaching $2x_1$, and if we imagine some infinitely small point, an infinitesimal or fluxion, distinct from but of zero distance from $x_1$, we get that the gradient of the line ‘at $x_1$’ is just $2x_1$.

This ‘going to the limit’ was the birth of calculus as we know it today. But think about what we’ve done? As our choices of $x_n$ get closer to $x_1$, the length of the line $\Delta x$ approaches 0, and when we use an infinitesimal, the length $\Delta x$ is zero, which means we are calculating our gradient as $\Delta y / 0$!! Anyone who did high-school mathematics will remember that ‘dividing by zero is the devil’ (exact cultural descriptions may vary).

And in many ways, this and other problems of something ‘so infinitely small it can’t exist’, formed the basis of Berkeley’s critique - and it still hasn’t been resolved philosophically to this day!

But surely we can just throw it away?!?

If only it were that simple - it’s so damn useful! Calculus and related topics (Linear analysis, Complex analysis, etc.) form at least one side of the backbone framework of pretty much all science (physics, chemistry, biology) rely on (the other side being statistics, but there is a like argument for Bayes Theorem and Bayesian Statistical models have their own special philosophical problems).

Foundational Quests

With the advent of modern science - Newton graduating Natural Philosophy to Physics by means of applying mathematical rigour, and the deep theoretical as well as experimental results of physicists like Maxwell, Kelvin, et al., we have come to rely on this idea. David Hilbert, famously, announced a project to give rigorous foundations to mathematics in such a way, as he claimed [3]

For us there is no ignorabimus … our slogan shall be: Wir müssen wissen — wir werden wissen!

Essentially, there will be nothing we cannot know for sure! A bold statement, but Hilbert was on of the eminent mathematicians of his age. Frege gave a full account of mathematics through the language of sets, and the resulting set theory was a monument of mathematics, but by the pricking of his thumbs…

Something Wicked This Way Comes.

Many are familiar with Russell’s Paradox;

Let $R$ be the set of all sets that are not members of themselves. Is $R \in R$?

The proof I will omit here (sorry peeps), but it is rarely appreciated how much of a headache this made for Frege! He had to add an addendum to his great work, the Grundlagen, stating that the paradox existed, and that actually the whole things may be wrong!

Russell had effectively pulled the rug out from under the efforts of some of the finest logicians of the 19th Century, and caused them to rethink their work.

This did not deter Russell himself from launching into the fray - along with Whitehead he composed the Principia Mathematica. By building a theory of types (the essential idea of a type being that something of one type (a set) cannot refer to things of another type (an atomic element) without lots of restrictions being satisfied) they created a monument of logical reasoning - from first principles, they built an entire system of mathematics that proved that $1+1=2$, but with sound, solid foundations that were, they thoughts, unshakeable.

They were badly wrong.

From Greek Truth to German Proof

We all know the ancient Greek paradox

This sentence is false.

Is that true of fales? Well, you can’t decide. If it’s true, then it must be false. If it is false, then by the double negative, it should be true. If we try to establish such a statements truth, we will fail.

But mathematical proof is a thing we just did - we showed with reasoning and argument that something can have ‘indeterminate truth’. So, for 2 millennia, mathematical proof was seen as the tour de force of rational reasoning. Anyone can read a proof and know something, if they work through all the details. Proofs last millennia, unchallenged (cf. Euclid’s Elements), and give our further reasoning solid basis. Indeed, the notions akin to ‘standing on the shoulders of giants’ (when not Newton calling Hooke a short-arse) rely on this notion that everyone who went before and provided work didn’t mess up.

Proof was seen as an absolute - if mathematics is the queen of the sciences, then proof is her ruling sceptre.

Try telling Gödel that. His theorems are fairly straightforward to grasp - I’m not going to put the technical details here (they’re all over a duckgo search). Gödel’s first incomleteness theorem is as follows: [4]

“Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$.”

So, essentially, if your theory is strong enough, then there are always sentences that you cannot prove.

So proof is not immutable. Proof is not absolute.

Part II - Where we went next…

[1] Halmos, P.R. “The Legend of von Neumann”, The American Mathematical Monthly, Vol. 80, No. 4. (April 1973), pp. 382–394

[2] Berkeley, George (1734). Wikisource The Analyst: a Discourse addressed to an Infidel Mathematician. London: Wikisource. p. 25.

[3] D. Hilbert (1902). “Mathematical Problems: Lecture Delivered before the International Congress of Mathematicians at Paris in 1900”. Bulletin of the American Mathematical Society. 8: 437–79.

[4] anu Raatikainen, 2015, “Gödel’s Incompleteness Theorems”, Stanford Encyclopedia of Philosophy.