**MW:** OK, back to the main plotline. Enayat asks for a “natural” axiomatization of PA^{T}. Personally, I don’t find PA^{T} 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.)

# Monthly Archives: September 2019

## Non-standard Models of Arithmetic 13

Filed under Conversations, Peano Arithmetic

## First-Order Categorical Logic 6

**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

## First-Order Categorical Logic 5

**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

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

## Non-standard Models of Arithmetic 12

**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 PA^{T} 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

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

Filed under Logic