The Alfred Tarski Lectures

Following the death of Group founder Alfred Tarski in 1983, an endowment fund was established in his memory. Using income from this fund, a series of annual Alfred Tarski Lectures was inaugurated in 1989. Each spring an outstanding scholar in a field to which Tarski contributed is selected to come to Berkeley to meet with faculty and students and to deliver several lectures. (List of past Tarski lectures.)

The Thirty-third Annual Alfred Tarski Lectures

Richard Shore (Cornell University)

Poster

Reverse Mathematics: A Multiverse

Monday, April 24, 2023
4 PM, Room 3, Physics
A reception in honor of the speaker will be held following the first lecture at 5:15 PM in 1015 Evans Hall.

The basic question that reverse mathematics attempts to address is how hard it is to prove particular theorems or carry out particular constructions of ordinary classical mathematics. Hard not in the sense of how many hours, days or years or cups of coffee it took a mathematician or many mathematicians to prove the theorem but hard in some more mathematical sense. This talk will be an introduction to the subject with hints of a new view. We primarily consider two related standard criteria of hardness and the relations between. One is based on the strength of formal systems of (second order) arithmetic in which theorems can be proved. The second is recursion theoretic and based on the computational complexity of the objects the theorems assert exist. We will also briefly discuss relations to common philosophical approaches to the foundations of mathematics as well as a number of newer approaches that vary the logic and formal systems allowed in the first case and variations on computation complexity notions in the second. Finally, we present a glimpse of a new setting for the universe of reverse mathematics. It is an analysis of the sort that has become common for recursion theoretic degree structures but yields drastically different results for proof theoretic strength.

Reverse Mathematics: A Global View

Wednesday, April 26, 2023
4 PM, Room 60, Evans Hall

We view the structure of reverse mathematics as a degree structure similar to that of the Turing degrees, 𝒟T with the ordering of Turing reducibility, ≤T. We define an ordering ≤P on sets of sentences of second order arithmetic S ≤P T ⇔ RCA0 ∪ T ⊢ φ for every φ ∈ S. As usual we consider the induced ordering ≤P on the equivalence classes s and t and the resulting structure 𝒟P. Important substructures are ℱP and ℛP consisting of the degrees of finitely and recursively axiomatizable sets of sentences. We prove a large number of global results about 𝒟P that differ remarkably from those for the analogous questions about 𝒟T and other degree structures. A few sample results are the following.

Theorem: 𝒟P is a complete algebraic lattice (with 0 and 1) and so pseudocomplemented. ℛP is an incomplete algebraic lattice. For each of them the compact elements are those in ℱP and the pseudocomplement of T in 𝒟P is ∨{φ | φ ∧ T = 0}. ℱP is the atomless Boolean algebra.

Theorem: The (first order) theories of ℱP and 𝒟P with ≤P (and so with ∨, ∧, 0, and 1) are decidable by applying major results of Tarski and Rabin.

Theorem: 𝒟P and ℱP have exactly 2ω many automorphisms

Theorem: There are only four finite sets which are definable in 𝒟P: ∅, {0}, {1} and {0,1}. There are only four countably infinite definable subsets of 𝒟P: ℱP, ℱP - {0}, ℱP - {1} and ℱP - {0,1}. In each case, no other such sets are fixed under all automorphisms of 𝒟P.

Theorem: Up to isomorphism, there are only four cones 𝒟Ps= {t | s ≤P t} in 𝒟P: {1}, {s, 1}, {s, s∨ t0, s∨ t1,1} and 𝒟P. We can characterize the few s that fall into each of the first three classes in terms of notions familiar in the general study of theories.

This analysis was prompted by my thinking about what I should talk about in these lectures. Much to my surprise, after I had worked out most of these results I discovered that Tarski had proven many of them some ninety years ago and so long before the rise of reverse mathematics.