Liar Paradoxes and Godel Numbering: An Introduction to Incompleteness

Posted on June 4, 2014

The previous post on recursion had an ulterior motive: laying the groundwork for an explanation of Gödel’s Incompleteness Theorems.  It took me a long while to fully grok the underlying logic, but through no fault of the theorems themselves.  Rather, I’ve noticed a dearth of good online explanations.  The Wikipedia article is obtuse to say the least, Gödel Escher Bach and Gödel’s Proof cost money, and neither of them is web-based anyway.  So let’s fix that, shall we?
Just a short prewarning: the different parts of this post will feel somewhat disconnected at first, but it’ll all come together by the end.

The Liar Paradox
Ah, the Liar Paradox - we’ve all encountered it in one form or another, but the one most useful to us is this:

> This sentence is a lie

Or, if you like recursive acronym’s:

> INIAL’s name is a lie

Which expands to

> “INIAL’s name is a lie” is a lie

On and on to infinity.  The interesting thing about this sentence is that, while it doesn’t make sense to call it true, it doesn’t really mean anything to call it false either.  It is instead stuck in a strange oscillating limbo of contradiction where it’s not clear the statement has any meaning at all.  In a word, the statement is inconsistent, as is any system that can prove it.  This notion isn’t yet all that useful, but what we’ll find by the end of this article is that it’s actually quite portable.

Gödel Numbering
Let’s first take a short detour though.  At some level, we know we can represent any string of characters with a string of bits - after all, this is exactly what computers do to store text.  And, similarly, it’s pretty trivial to interpret a string of bits as a number.  Now, in and of itself this doesn’t seem that revolutionary, but the reducibility of strings to numbers actually leads to an incredibly important result in mathematics - namely, that you can reason about arithmetic from within itself.  After all, for any string (), “() is a valid theorem in Peano Arithmetic” becomes a valid predicate, as does “() is a true statement of number theory”.  Suddenly, we’ve found a way to get arithmetic to swallow its own tail and can begin to use it for metamathematical reasoning.
Indeed, all axiomatic systems can be embedded in some manner similar to this - all it takes is some sufficiently clever ways of doing typographical manipulations of numbers.

A Short Interlude: MIU Gödelized
You may or may not remember my post on the MIU System, but in case you don’t, here are the axioms again (note: I use lowercase characters for placeholders, and upper case for MIU characters)

- If we can construct x, we can construct xU
- If we can construct Mx, we can construct Mxx
- If we can construct xIIIy, we can construct xUy
- If we can construct xUUy, we can construct xy
- We can construct MI

A very primitive way to encode this is to make a number, where every M is a 3, every I is a 1, and every U is a 0.  If we do this, we can rephrase the axioms in terms of numerical operations:

- If we can construct x, we can construct ( x 10 )
- If we can construct ( 3 10^n + x ), we can construct ( 3 10^{2n} + x 10^n + x )
- If we can construct ( x 10^{n+3} + 111 10^n + y), we can construct (x 10^{n+1} + y )
- If we can construct ( x 10^{n+2} + y), we can construct (x 10^n + y )
- We can construct ( 31 )

Of course, this method of encoding is relatively primitive and hard to reason about, but it’s more than sufficient as a proof-of-concept.  And, importantly, it demonstrates one of the most important facts of positional notation - typographical operations become as simple as separating the positions out and doing funny operations on the individual pieces.  But, as much as I’d love to delve into a long rant about number and string encoding, we have a topic to get back to.

Bringing it all together
So, where are we going with all this nonsense?  Well, we’ve already seen how simple it is to embed statements like “() is a valid theorem in Peano Arithmetic”, so why not use the weaker notion “() is provable in Peano Arithmetic”?  (Or, more formally, “() such that () is a valid proof of ()”).  Or, similarly, “() is not provable in Peano Arithmetic”.  Now, this notion itself isn’t that useful, but we can construct a true statement () that reads “() is not provable in Peano Arithmetic” - suddenly, the statement is talking directly about its own provability.  And, in a similar vein to the liar paradox, it can’t be proven without also showing inconsistency.  So, either we can prove both () and () or we can’t prove () (and therefore () is true).  And, if we can’t prove (), then we’ve just constructed a statement that is both true and can’t be proven.  This creates a dichotomy: either a formal system is inconsistent, or it’s incomplete.  And so ends Hilbert’s Program.