MIT Logic Seminar

Both approaches can be combined to define randomness for individual objects such as infinite binary sequences. I will discuss various aspects of the following general question: Given an infinite binary sequence, does there exist a (non-atomic) probability measure with respect to which this sequence is random? I will argue that the view from logic opens up new and perhaps unexpected perspectives on the concept of randomness, in particular concerning the role of infinity, but also in relation to other areas like geometric measure theory.

We discuss recent work with Ackerman and Roy that settles this and related questions using techniques from computability theory. We present a computable extension of de Finetti's theorem, and highlight some applications to nonparametric Bayesian statistics and to the design of probabilistic programming languages. We also present a construction that implies the impossibility of a general algorithm for computing conditional distributions, and describe a new method for using forcing arguments in computable probability theory.

Toricity Theorem. Any p-torsion lies inside a divisible abelian group unless the ambient group of finite Morley rank contains an infinite elementary abelian p-group.

C(T) Theorem. The centralizer of a divisible abelian torsion group in a connected group of finite Morley rank is itself connected.

We shall give a flavor of the project demonstrating how the two theorems are applied together in the Prufer 2-rank two case, and we shall prove the C(T) Theorem.

However, many standard techniques from computability theory cannot be transferred over directly to the BSS context. In particular, there is no enumeration of all BSS machines because each may include real-valued parameters. Hence, the degree structure of the BSS-degrees (defined analogously to the Turing degrees) must be explored with novel techniques.

In this talk, we will introduce the BSS model and outline some of the foundational results and some new results (joint with Johanna Franklin) in the exploration of the degree structure. In particular, time permitting, we will discuss connections between BSS degrees and Julia sets from dynamical systems.

• A definable class of a member of the multiverse is also a member.
• A forcing extension of a member of the multiverse is also a member.
• Every member of the multiverse is countable/ill-founded from the perspective of another member.
• Every member of the multiverse is an internal ultrapower of another member; every definable elementary embedding of a member is an iterate of an embedding of another member.

In this talk, I will introduce the multiverse axioms and show that the collection of all countable computably saturated models of ZFC is a natural model of the multiverse axioms if it is non-empty. A model is computably saturated if it already realizes all its finitely realizable computable types. This is a joint work with Joel David Hamkins.

But we can also look at the real interval from a measure-theoretic point of view. In recent talks at Stanford and Berkeley, Dana Scott introduced a new model for the propositional modal language — the Measure Algebra. Elements in the Measure Algebra are Lebesgue-measureable subsets of the real interval, [0, 1], up to sets of measure zero, and the algebra is equipped with Boolean operators as well as an interior operator. In evaluating modal formulae to the Measure Algebra, we assign to a given formula an equivalence class of sets that differ from one another by a set of measure zero. This allows us to speak of the probability or weight of any formula under a given valuation. I show that the propositional modal logic S4 is complete for the Measure Algebra. This result extends the classic 1944 result of Tarski and McKinsey to the measure-theoretic structure of the real interval and opens the way for investigating the logic of measure spaces more generally. A first corollary to the proof of completeness that I present is that non-theorems of S4 can be falsified on subsets of [0, 1] of measure arbitrarily close to 1. A second corollary is that Intuitionistic logic is complete for the sub-lattice of open elements of the Measure Algebra.

There is one common base theory and four more standard systems beyond it. Most theorems of classical mathematics have turned out to be equivalent to one of these systems. We will briefly describe this state of affairs and then move on to a situation that falls far outside the realm of standard reverse mathematics: axioms of determinacy.

The story begins with Friedman's result [1971] that Borel determinacy is not provable in ZFC^– (no power set) and Martin's proof [1975] that it is provable in ZFC (with just the required number of iterations of the power set axiom). We then move to low levels of the Borel hierarchy and provability in second order arithmetic (Z₂). Friedman proved that Σ⁰₅ determinacy is not provable in second order arithmetic and Martin [1974] improved this to Σ⁰₄ and presented a proof of Δ⁰₄ determinacy that he claimed could be carried out in Z₂. Moving up from the bottom, Steel [1976] showed that open Σ⁰₁ determinacy is equivalent to the fourth of the standard systems while Tanaka [1990] showed that determinacy for the difference of two open sets is equivalent to the fifth and strongest of them. Various researchers then investigated the strength of Σ⁰₂ and Σ⁰₃ determinacy reaching about Π¹₃ comprehension.

Our recent work with Montalbán on this topic began with the realization that the proof by Martin apparently establishing the boundary between provability and unprovability for levels of arithmetic determinacy in second order arithmetic was not a proof in Z₂. We have now established the true results which turned out to be quite different and unusual. Determinacy at the various levels of the difference hierarchy on Π⁰₃ sets climb up the entire hierarchy of Π¹_n comprehension axioms in proof theoretic strength. Thus the provability boundary lies well below Δ⁰₄ determinacy. These results supply the first natural mathematical theorems that occupy any, let alone all, of the levels above Π¹₂. They also provide a Gödel like phenomena for Σ¹₂ sentences in second order arithmetic (or ZFC^–) with natural mathematical sentences: φ(n) is provable for each n but ∀ n φ(n) is not provable.

Joint work with Antonio Montalbán.