The ancient Greeks grappled in vain with three geometrical problems: the duplication of the cube, the trisection of the angle, and the squaring of the circle. What drove them to these endeavors? Divine inspiration? Well, yes—of a sort. The origin of the duplication of the cube is well-known. The story behind the trisection of the angle however has been lost to history—until now.
Filed under Bagatelles
MW: Recap: we showed that PAT implies ΦT, where ΦT is the set of all formulas
Now we have to show the converse, that PA+ΦT implies PAT. But first let’s wave our hands, hopefully shaking off some intuition, like a dog shaking off water.
Filed under Conversations, Peano Arithmetic
Awhile back, the BBC website History Extra had a post that included this tidbit:
AD 0… the date that never was
The AD years of the Christian calendar are counted from the year of Jesus Christ’s birth, and, as the number zero was then unknown to the west, Dionysius began his new Christian era as AD 1, not AD 0. …
This evoked the ire of the noted historian Thony Christie. In a post Something is Wrong on the Internet, he explained:
Filed under Bagatelles, History
MW: OK, back to the main plotline. Enayat asks for a “natural” axiomatization of PAT. Personally, I don’t find PAT all that “unnatural”, but he needs this for Theorem 7. (It’s been a while, so remember that Enayat’s T is a recursively axiomatizable extension of ZF.)
Filed under Conversations, Peano Arithmetic
MW: An addendum to the last post. I do have an employment opportunity for one of those pathological scaffolds: the one where B(0) is the 2-element boolean algebra, and all the B(n)’s with n>0 are trivial. It’s perfect for the semantics of a structure with an empty domain.
The empty structure has a vexed history in model theory. Traditionally, authors excluded it from the get-go, but more recently some have rescued it from the outer darkness. (Two data points: Hodges’ A Shorter Model Theory allows it, but Marker’s Model Theory: An Introduction forbids it.)
Filed under Categories, Conversations, Logic
JB: Okay, let me try to sketch out a more categorical approach to Gödel’s completeness theorem for first-order theories. First, I’ll take it for granted that we can express this result as the model existence theorem: a theory in first-order logic has a model if it is consistent. From this we can easily get the usual formulation: if a sentence holds in all models of a theory, it is provable in that theory.
Filed under Categories, Conversations, Logic
[This post is available in pdf format, sized for small and medium screens.]
Lewis Carroll Epstein wrote a book Relativity Visualized. It’s been called “the gold nugget of relativity books”. I wouldn’t go quite that far, but Epstein has devised a completely new way to explain relativity. The key concept: the Epstein diagram. (I should mention that Relativity Visualized is a pop-sci treatment.)
JB: It’s been a long time since Part 11, so let me remind myself what we’re talking about in Enayat’s paper Standard models of arithmetic.
We’ve got a theory T that’s a recursively axiomatizable extension of ZF. We can define the ‘standard model’ of PA in any model of T, and we call this a ‘T-standard model’ of PA. Then, we let PAT to be all the closed formulas in the language of Peano arithmetic that hold in all T-standard models.
This is what Enayat wants to study: the stuff about arithmetic that’s true in all T-standard models of the natural numbers. So what does he do first?
Filed under Conversations, Peano Arithmetic
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.
Filed under Logic
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.
Diagonal Argument 