Better Know a Theorem: Łoś and Löb

Over the break I finished a re-read of Gödel Escher Bach: an Eternal Golden Braid. I got the book exactly 26 years ago for Christmas from my uncle (another David Pritchard). The book is really timeless in Douglas Hofstadter’s excellent exposition of its core topics (paraphrased):

• Gödel’s incompleteness theorem: there are true statements about integers that have no formal axiomatic proof
• The Church-Turing thesis: anything that can be computed, can be computed using any computer
• The chemical basis of life: DNA encodes all your body’s functionality, including how to propagate DNA
• Art is cool: Many examples of patterns and interesting structures in the work of Escher, Bach, Magritte, Lewis Carroll and others; many cool character-based dialogues.

In re-reading it after many years, I tried to chase down any technical bits that were foreign to me, to wring it for all it’s worth. Compared to my readthrough back in the last millennium, there is a mountain of supporting information on the internet; I’m grateful since this was really helpful for my understanding of these cool theorems. Mathoverflow in particular helped me comprehend these, as I got quick answers to perplexing issues.

Both theorems are in the following context. The book spends a bunch of time looking at the expression of mathematical statements using a simplified language (TNT or “typographical number theory”), then demonstrating that proofs (built from Peano Arithmetic 1st-order axioms) can be encoded as number theory statements in TNT, finally enabling self-referential statements and the proof of Gödel’s incompleteness theorem.

Here are what I thought were the 2 most notable side nuggets:

1. Łoś’s theorem. [See “Supernatural Addition and Multiplication” within chapter XIV] The Peano axioms all hold true about the natural numbers. Are they also true about larger sets of objects? Yes! Hofstadter calls these “supernatural numbers”. Satisfying the axioms means they satisfy arithmetical properties (e.g. they form collections of sequences additively isomorphic to the integers) and also that anything which can be proven by induction holds true for them. The least weird construction is to take all infinite whole number sequences 𝐍^𝐍 and an ultrafilter (an axiom-of-choice-derived special collection of subsets of 𝐍, see a fuller definition here), with two sequences equivalent when “most” components of their sequences have the same value. Łoś’s theorem proves that this quotient satisfies all Peano axioms. (This is not the smallest model of supernatural numbers! But, the smallest model is also super weird. It’s order-isomorphic to 𝐍+(𝐐×𝐙), but it entails that neither addition nor multiplication is computable.) I highly recommend this exposition by Rising Entropy for more details, especially chapter 2 and 4 helped me a lot.
2. Löb’s Theorem. [See “Henkin Sentences and Viruses” within chapter XVI]. Gödel’s incompleteness theorem is proven by constructing a quasi-self-referential sentence S of TNT equivalent to “S has no proof in TNT”. (Incompleteness then follows as: if S has a proof, it’s true, but then it has no proof, a contradiction; so it must have no proof, and is thus true.) Löb’s Theorem asks: what’s the deal when we construct a simpler quasi-self-referential sentence S like “S does have a proof in TNT”. The deal is: they’re also always true. I find the result and proof method amazing/mystifying. (Technically Lob’s theorem is more general, this is the result of applying it to Henkin sentences.) See The Cartoon Guide here as well as Wikipedia and here and here; the boxes confused me at first as I thought my browser wasn’t rendering characters, but they’re actual math symbols. The individual steps are simple and the larger design involves lifting proofs up out of arithmetic encoding, but I lack intuition for the whole thing. [Edit: I made a new post with some additional intuition I could find from new sources.]

There are other great tidbits I learned this time around, such as how to solve the exercise “find a TNT formula for powers of 10.” There’s a beautiful proof here. The internet knows all!

PS: Props to WordPress as well for the new year