Back in the 60s, Kolmogorov and Chaitin independently found a way to connect information theory with computability theory. (They built on earlier work by Solomonoff.) Makes sense: flip a fair coin an infinite number of times, and compare the results with the output of a program. If you don’t get a 50% match, that’s pretty suspicious!
Three aspects of the theory strike me particularly. First, you can define an entropy function for finite bit strings, H(x), which shares many of the formal properties of the entropy functions of physics and communication theory. For example, there is a probability distribution P such that H(x)=−log P(x)+O(1). Next, you can give a precise definition for the concept “random infinite bit string”. In fact, you can give rather different looking definitions which turn out be equivalent; the equivalence seems “deep”. Finally, we have an analog of the halting problem: loosely speaking, what is the probability that a randomly chosen Turing machine halts? The binary expansion of this probability (denoted Ω by Chaitin) is random.
I wrote up my own notes on the theory, mostly to explain it to myself, but perhaps others might enjoy them.
The first sentence of Pollard’s review sums up my feelings perfectly: “This rewarding, exasperating book…” On balance, I found it more exasperating than rewarding. But it does have its charms.
I participated in a meetup group that went through the first two parts of S&F. My fellow participants possessed considerable mathematical knowledge and sophistication, but had only slight prior acquaintance with mathematical logic and none with axiomatic set theory. (The opinions here are strictly my own, but they reflect my experience in the meetup.) If I had just skimmed the book, glancing at familiar material, I would probably have a more positive impression.
I wrote an extensive set of notes for the meetup. This post is basically the last section of those notes.
I will begin with the book’s minuses, so as to end on a positive note.
Filed under Logic, Reviews
If you’re reading this blog, you probably know Stirling’s formula:
It’s not hard to estimate n! to within a factor of √2; I wrote up a note on this and even easier derivations. It’s quite a bit harder to show that the ratio of the two sides approaches a definite limit as n→∞ and that this limit is 1. You can find a variety of proofs in a number of places, one being Ahfors’ Complex Analysis. I wrote up a note about this too, expanding on some of the details.
Incidentally, the two sides are asymptotic not just for positive integers n. Replace n! with Γ(z+1) on the left, and both n‘s with z‘s on the right. Allow z to go to infinity in the complex plane, while staying at least a fixed finite distance to the right of the imaginary axis. Then the two sides remain asymptotic. Ahfors proves this stronger result, and uses it to derive the integral form for the Γ function.
Note that if you replace the n‘s with z‘s, you have zz on the right. So you’ve got to worry about branches of the complex logarithm (since zz is defined as ez log z). The note deals with this (and other things).
Prev TOC Next
MW: I made up a little chart to help me keep all these adjoints straight:
Prev TOC Next
JB: Okay, let’s talk more about how to do first-order classical logic using some category theory. We’ve already got the scaffolding set up: we’re looking at functors
You can think of as a set of predicates whose free variables are chosen from the set S. The fact that B is a functor captures our ability to substitute variables, or in other words rename them.
But now we want to get existential and universal quantifiers into the game. And we do this using a great idea of Lawvere: quantifiers are adjoints to substitution.
Prev TOC Next
MW: Time to start on Enayat’s paper in earnest. First let’s review his notation. M is a model of T, a recursively axiomatizable extension of ZF. He writes for the ω of M equipped with addition and multiplication, defined in the usual way as operations on finite ordinals. So is what he calls a T-standard model of PA.
Prev TOC Next
JB: So, last time you sketched the proof of the Paris–Harrington theorem. Your description is packed with interesting ideas, which will take me a long time to absorb. Someday I should ask some questions about them. But for now I’d like to revert to an earlier theme: how questions about the universe of sets cast their shadows down on the world of Peano arithmetic.