Author Archives: Michael Weiss

Epstein Relativity Diagrams

[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.)

Continue reading

Leave a comment

Filed under Physics, Reviews

Non-standard Models of Arithmetic 12

Prev TOC Next

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?

MW: First Enayat offers a brief interlude, chatting about the strength of PAT for various T‘s. PAT is stronger than PA, because it can prove Con(PA) and PA can’t. That’s because T extends ZF, and ZF can prove that its \mathbb{N} is a model of PA. ZF would be a pretty poor excuse for a set theory if it couldn’t prove that!

Next: PAZF = PAZFC+GCH, where GCH is the generalized continuum hypothesis. Instead of looking at ZFC+GCH, let’s consider ZFL, i.e., ZF+“every set belongs to Gödel’s constructible universe L”. As Gödel showed, ZFL implies ZFC+GCH, and also Con(ZF) implies Con(ZFL); in fact any model M of ZF contains a so-called inner model LM of ZFL. Now, ordinals are absolute between transitive models of ZF; not only that, but ω is absolute, and the ordinal operations are absolute. (“We don’t have to search all over the kingdom to do arithmetic with finite ordinals.”) So M and LM have the same “\mathbb{N}” as their “standard model of PA”.

Since M and LM have the same “standard model of PA”, the same arithmetic statements hold in both of them. To see if some φ belongs to PAZF, we have to verify the truth of \varphi^\mathbb{N} in all models of ZF. But in the process, we also verify that truth in all inner models LM of ZFL. And when we’ve finished that task, we’ve actually verified that truth in all models of ZFL, just because every model of ZFL is the inner model of at least one model of ZF—namely itself! So PAZF = PAZFL.

Contrast this with ZFI, i.e., ZF+“there is an inaccessible cardinal”. PAZFI is strictly stronger than PAZF. Here’s why: ZFI proves Con(ZF), since if we gather all the sets of rank below the first inaccessible cardinal and toss them in a bag, we’ve got a model of ZF! ZF does not prove Con(ZF), by Gödel’s second incompeteness theorem. So Con(ZF) is our example of a statement in L(PA) that PAZFI delivers and PAZF doesn’t.

JB: By the way, just as a stupid little side note, you’re assuming here that ZF is consistent. But I’m willing to keep that as a background assumption in all these deliberations. (Maybe you already mentioned this and I forgot!)

MW: Yup. Kind of hard to talk about the omegas of models of ZF, if there are no models of ZF!

You might wonder what’s the chief difference between the two cases, ZFI and ZFL. Models of ZF contain inner models of ZFL, and models of ZFI contain inner models of ZF. Ah, but there are models of ZF not contained in any model of ZFI (at least if ZF is consistent). Namely, if ZF is consistent, then ZF+¬Con(ZF) is also consistent, as we’ve just seen. So it has a model. I leave it as an exercise that a model of ZF+¬Con(ZF) can’t possibly be contained in a model of ZFI.

JB: Nice!

Prev TOC Next

Leave a comment

Filed under Conversations, Peano arithmetic

Algorithmic Information Theory

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.

Leave a comment

Filed under Logic

Review: Smullyan & Fitting, Set Theory and the Continuum Problem

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.

Continue reading

Leave a comment

Filed under Logic, Reviews

Stirling’s Formula: Ahlfors’ Derivation

If you’re reading this blog, you probably know Stirling’s formula:

n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n

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).

1 Comment

Filed under Analysis

First-Order Categorical Logic 4

Prev TOC  Next

MW: I made up a little chart to help me keep all these adjoints straight:

Continue reading

Leave a comment

Filed under Categories, Conversations, Logic

Non-standard Models of Arithmetic 11

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 \mathbb{N}^M for the ω of M equipped with addition and multiplication, defined in the usual way as operations on finite ordinals. So \mathbb{N}^M is what he calls a T-standard model of PA.

Continue reading

1 Comment

Filed under Conversations, Peano arithmetic