Gödel’s proof is the (meta-)mathematical counterpart of the paradoxical statement This sentence is false. In his epic 1979 debut book Gödel, Escher, Bach Douglas Hofstadter intertwines computer science, math, art, biology with a simplified version of the proof. In 2007 he revisits these ideas in I Am a Strange Loop. Hofstadter writes:
… at age fourteen I ran across Ernest Nagel and James R. Newman’s little gem, Gödel’s Proof, and through it I fell under the spell of the paradox-skirting ideas on which Gödel’s work was centered.
Nagel and Newman provide a succinct version of Gödel’s proof. You can feel how deeply it had influenced Hofstadter. NNs’ book arms the reader with the essential history of mathematics and logic, then presents the proof without bells and whistles.
Gödel’s ‘sentence’ does not say it is false. It says that it cannot be proved, actually I cannot be proved. ‘Proved’ means: Derived from a set of a few axioms, following a few allowed rules of transformation. Axioms and rules form a rigorous axiomatic system.
Theorems look familiar, containing the symbols for and, or, if…then. But they can also be seen as mere strings of concatenated characters. Strings are manipulated by purely typographical rules. Before Gödel shattered their world, logicians as Bertrand Russell had hoped that churning out all strings reachable by following the rules would result in the complete set of all true theorems, whereas no false statement would be generated. However, Gödel’s special theorem cannot be proved. But because it says of itself that it cannot be proved, it is true. Any system powerful enough to potentially express all true theorems will be incomplete.
Manipulating strings according to rules is isomorphic to performing arithmetic transformation on large integer numbers. Maybe this is more obvious today, as we learned to think about words as streams of bits processed by computers. In the 1930s Karl Gödel used an ‘elaborate hack with prime numbers to program without programming’, as computer scientist Scott Aaronson says in his book Quantum Computing Since Democritus.
Gödel assigned integer numbers to each character, as well as to each ‘line’ in a proof, and to the whole chain of steps in a proof. A single number represents the code needed to proceed from axioms to a theorem. His assignment of so-called Gödel numbers is unambiguous: The numbers assigned are used as exponents of a series of the lowest successive prime numbers in ascending order. Each prime is raised to the power of the Gödel number of a symbol; then all these exponentiated primes are multiplied. Via factorization of the final Gödel number the original ‘plain text’ could be recovered.
The first few integers – 1–12 in NN’s account – become the Gödel numbers of constants and characters. For example, the equal sign is gödelized as 5, and the existential quantifier ∃ (There exists) as 4. In the formal system all integer numbers are represented as successors of zero using the shorthand s for successor of: Number 1 is s0, number 2 is ss0, etc. Only the strings s and 0 need to be gödelized.
Example – a string of symbols who are commonly understood as: There exists an x, so that x is the successor of y.
(∃x)(x = sy)
(, ), ∃, s and = are assigned integers lower equal than 12. x and y are variables, placeholders for integer numbers. An unlimited set of variables is available: They are associated with prime numbers higher than 12.
The string of symbols is encoded in a series of integers:
8, 4, 13 ,…
( ∃ x ) ( x = s y ) | | | | | | | | | | 8 4 13 9 8 13 5 7 17 9
The Gödel number of the whole string / statement is obtained by using these numbers as exponents of the first primes:
28 . 34 . 513 . …
In a sequence of several steps, a Gödel number is assigned to each statement; then the statements’ numbers are used as exponents of the series of the ascending prime numbers. A whole proof is encoded in a unique number.
If theorem with Gödel number z can be proved, there exists a proof with Gödel number x. The fact that something can be proved, turned into a relation between integers. NN explain that Gödel took great pains in his paper to show that the relation between these numbers is primitive recursive. A primitive recursive function behaves in a predictable way – it makes only use of loops with known upper bounds.
The powerful axiomatic system under consideration has been designed to speak about all theorems in number theory. It can also express the relation between the Gödel numbers of proof and theorem. This function involving numbers is translated into the formal language, replacing e.g. each number by ssssss[an enormous number of s]ssss0. NN denote this formal relation by Dem(x.z) (Dem for demonstration).
If a proof exists, there exists a Gödel number x so that the theorem with Gödel number z cam be demonstrated via x:
(∃x)Dem(x,z)
(x is a bound variable; it could be called anything. There is no relation to x as used in the first equation. I am sticking to NNs’ notation).
If z cannot be proved, there does not exist any proof with Gödel number x:
~(∃x)Dem(x,z)
If a theorem should speaks about itself, you need to feed it its own number. But by inserting the Gödel number ‘into itself’ would make the string longer and thus its own Gödel number would change. To circumvent this, substitution has to be implemented in a multi-level process, and by describing its own number using a calculation, rather that writing down all the digits.
A substitution function Sub with three parameters is introduced:
- The Gödel number of the statement to be changed, say n. The statement with this is number is yet to be defined.
- The Gödel number of the (free) variable to the replaced by a number, e.g. 17 (for y)
- The number to be inserted for the variable. To obtain the desired loop, this should also be n.
As Dem, Sub is written in the formal language. n is shorthand for a string of [n times s]0. Its output is the Gödel number of the statement after the substitution. Sub(n,17,n) is a number as a function of numbers, all numbers encoded in the formal language. It is not a simple replace() function – Sub takes care of rearranging the prime numbers – of adding a lot of factors in the multiplication that represent the many s in the number n.
The following first statement is nearly Gödel’s statement. It says that there is no proof for the theorem whose Gödel number is expressed as Sub(y,17,y).
I) ~(∃x)Dem(x,Sub(y,17,y))
has Gödel number n
The functions Dem and Sub are expressions in the formal language. It a well-formed string with a Gödel number which we call n. y is a free variable. The statement does not talk about itself. Nothing has happened yet.
The variable y shall be replaced by the number n – this is where self-referentiality is obtained:
II) also called G) ~(∃x)Dem(x,Sub(n,17,n))
with n as a shorthand for [n times s]0
Going from statement I) with Gödel number n to statement G) – we did a substitution:
- Input: The statement I) which has Gödel number n
- The Gödel number of the character to be replaced: 17 – which is associated with y. (We do not replace the string ’17’ in between the two y’s as that ’17’ would be gödelized as sss…sss0)
- The number we insert instead: Number n.
What we did was what we expect Sub(n,17,n) to do. As an output we expect the Gödel number of the statement after the replacement: The output of Sub(n,17,n) is the Gödel number of statement G) written in den formal language!
But this number – called g by NN – is the number referred to in the Dem function in G: G says that there is no proof for the theorem with Gödel number expressed as Sub(n,17,n).
If you imagined that G could be proved, you’d say there exists a proof with Gödel number x for the theorem whose Gödel number expressed formally is the result of Sub(n,17,n):
(∃x)Dem(x,Sub(n,17,n))
This is the negation of G – we’ve demonstrated ~G- If G would be demonstratable, ~G would also be demonstrable. If the axiomatic system is consistent, a theorem and its negation cannot be both demonstratable. Thus G cannot be demonstratable.
But either G or ~G must be true – and which of them it is, can be decided on the meta level: G says of itself that it is not a provable theorem, whereas ~G states that G has a proof. What G says is true, although is cannot be proved directly within the system, but only by resorting to meta-mathematical reasoning about the system. Only on the meta level we use the isomorphism between the characters used in the formal system and our familiar interpretation in terms of logic.
elkemental Force 
Hi Elke,
This is a very nice post to discover on your blog. I hate that I can’t keep up with reading and commenting as you post. But it is nice to come back here to see where your thoughts and work have been in the past year.
I have been skirting around Godel for a long time now, aware of his work but not reading it directly. I think this is one of the best discussions I’ve seen on the Incompleteness Theorem that gets right to the main issue and makes it clear what Godel accomplished. Perhaps I will look into finding some of his papers.
I suspect that having a background in linguistics has introduced some difficulty into learning mathematics (esp. proving things) that I don’t think the discipline or its teachers generally expect students to have. I have really struggled to hold on to both disciplines, allowing them to be equally important reflections of what we humans think reality to be, without being swayed into accepting one at the cost of the other when apparent contradictions between them arise. I have probably spent as much time reviewing/relearning philosophy as I have spent studying math in order to integrate (versus compartmentalize) the two disciplines. In the end, and still not fully appreciating proofs of more abstract theorems, Godel’s work has been key to integrating what I know (and still accept as ‘true’) about language systems and what I take as ‘provable’ and how we use mathematical logic.
It’s been a slow, and often frustrating process, one which has put me into the occasional Nassim Nicholas Taleb style of rant about philosopher-mathematicians who do compartmentalize one system and disregard it while working in the other. But, now coming out on the other side of it, I feel a lot stronger than had there been no struggle at all.
That said, I do especially like the connection you make to coding. I find that writing an algorithm to solve a problem on the computer is much easier to do than writing a proof for a human (usually a grad student who is marking an assignment) to read. This is true even when the algorithm and proof is not much different from each other.
Michelle
Hi Michelle, thanks for taking the time and writing such a great comment!! I feel I am time-traveling back to the glory days of the early WordPress community :-)
I really appreciate the feedback and I am humbled as number theory is certainly not what you get to study in depth as a physicist, and also as a “cybersecurity practitioner” it is only nice-to-have to really know about the algorithms juggling prime numbers in all details …
I can relate to what you say about linguistics and mathematics – I think I feel the same when a problem has both a “physics side” and an “engineering side”, or when you can view something from a “physics perspective” or a “math perspective”. I am intrigued by Paul Dirac’s writings: Co-founder of quantum mechanics, yet first trained as an engineer, and then as a mathematician – and I think that all of these perspectives shine through. Again and again I am attracted to older textbooks – and I wonder if this is some sort of nostalgia, or maybe it is because these pioneer scientists had an “unusual background” per definition, as they were just forging the discipline they were writing about.
Maybe I returned to reading Gödel, Escher, Bach and this brief book, because – for me – Gödel, Escher, Bach was an attempt to view all kinds of things in science and art from different perspectives … and I once figured, naively, that this is what somebody with a PhD in physics does :-) … as Hofstadter actually majored in physics – and still went on to write about self-referential codes, DNS molecules, and Zen and whatnot. And he has been fascinated by (and did research on) language, metaphor, and translation.
The connection to coding has been on my mind for a long time, maybe since I noticed that breaking down a (“natural”) process into steps translated to code feels easier to do than “keeping a whole interacting tangle of analogue stuff” in one’s mind, big-picture-like. For example, I noticed that seemingly simple hydraulic setups can be challenging to comprehend (“at once”), but turning each component into an object of code (literally, object orientation in this context serves its purpose well) you can concentrate on simple inputs and outputs. Then you let a machine do its job … and wonder about the result… and it feels hard (again) to backtrack and see which action finally caused which effect though. I felt exactly the same on comparing the analogue prime number hack with the pragmatic way computer scientists describe (nearly) the same theorem in terms of code that is fed its own source code (the halting problem).
And finally I have the chance to spell out that I really enjoyed your series about hyperbolic crochet!! That series was in fact so awesome that I mulled too long about a comment ;-) (other than “Wow, awesome!”) and then I missed the time window for leaving comments (and this was the time of pandemic panic, too) It was such a great blend of science and art – done in a tangible “analogue” way. This is also where my heart is “in science”, and what I am re-discovering time and time again … and what let me grab my old tattered version of Gödel, Escher, Bach …
I confess that I often miss the glory days of our old WordPress community. We have had so many conversations across a wide range of topics. There are always so many interesting connections to be shared and discovered!
I should say that I would not position myself as any kind of number theorist. I know about Russell and Gödel only because I found them on my own, usually in the middle of a crisis about mathematical communication and some sense that I had turned down a sketchy logic path in proofs and couldn’t find my way out again. I was very lucky to have met a grad student a few years ago with the right background to show me that with my literary/philosophical training I may be having a unique difficulty transitioning to mathematical logic. Since then, I have found that the only way forward has been to go back to philosophy. I am excited now to read what you say about reading Gödel, Escher, Bach and how it was your attempt “to view all kinds of things in science and art from different perspectives”. I doubt this was naïve. It was probably ahead of its time! But of course, I understand what you mean in that this way of thinking is not readily accepted in the mainstream of academics.
I have found a few others who are interested in combining these things. One example was an algebraist who was using new kinds of quilting methods she had developed to teach abstract algebra to her grad students.
One of my mathematical friends sent me an article about a physics Ph.D. student completing work on the elasticity of knitting. The idea is to understand this mathematically and apply it to material science.
In fact, I am planning on following up on those crochet projects with some self-study in differential geometry and elasticity. I will start this soon. For the moment, I feel I need to work out some of these language problems we are discussing. I finally got a (long) first post up on it. I hope I can develop some better insights about coding versus proof-writing as I go along.
I am really delighted that you enjoyed the crochet and prime number posts from last year. I was (and still am) surprised by this pattern. When we look at things like leaves, fruit and seed pods, and shellfish, we can see these patterns in nature. As I was crocheting, I was imagining how the prime number sequences could be codes that trigger growth in certain areas of shells to make these shapes. Later, I found Alan Turing wrote a paper combining math, biology and chemistry to discuss this process, called “The Chemical Basis of Morphogenesis” which I read has recently been proven correct in describing certain kinds of natural patterns like spots or stripes on an animal’s skin.
I have chosen to pursue numerical analysis and mathematical computation as my area of study and will focus on non-linear and partial differential equations over my next year. I am hoping to come out on the other side with a few new questions and maybe some better insight. (I am particularly excited that the program is jointly taught between applied math and theoretical physics, so hopefully some new physics applications will be brought in!)
As always, our exchanges excite so many ideas. I had better cut it off here for now.
I am still marveling at all the connections that are sprouting from this comment only!! I can relate to the excitement about differential equations as I’ve played with the heat transfer equation in simulations. But the more eerie coincidence is differential geometry: A while ago I’ve started to (self-)study topology again, reading Roger Penrose to stop freaking out in the scary second wave of the pandemic. At first it was only about General Relativity, but I have now finally realized that one should perhaps view all of physics from a geometrical perspective, even if you could get away (for many “practical purposes”) with “believing” you live in an R3 co-ordinate chart and not in a manifold.
Penrose also made me see the aesthetics of Complex Analysis – maybe because his books are decorated with beautiful “old-school” drawings he crafted himself. Not that I need that for anything remotely close to engineering work, but these functions are just so mysterious and beautiful. I had a thorough introduction a long time ago, but complex functions never felt interesting in this way – but more like another tool to solve integrals or calculate electrostatic potentials. But last summer I spent quite a while with trying to visualize exp(-1/x^2) really looks like https://elkement.wordpress.com/2021/01/24/motivational-function/ or integrating Dirac’s Delta function in a different ways and putting it into poetry form :-) It’s weird, but I feel the pandemic gave me permission to do so!
This just came to my inbox, a Zoom conference on topics I think would be of interest! https://www.logicmathphysics.uwo.ca/?page_id=280
Thank you for this. Not exactly a walk in the park, is it.
Yes, these books require some careful re-readings until that self-referential loop seems ‘intuitive’.