Logic Colloquium

In algebraic dynamics, one studies the properties of repeated application of rational functions while the work on the model theory of difference fields concerns the structure of the definable sets in fields considered in the language of rings augmented by a function symbol for a distinguished automorphism, but there are deep connections between the two subjects. I will discuss several of these connections including a dynamical consequence of Hrushovski’s theorem on the nonstandard Frobenius due to Poonen, some results on descent of algebraic dynamical systems due to Chatzidakis and Hrushovski, and some theorems on the arithmetic of polynomial dynamical systems due to Medvedev and myself.

Over the last 30 years, a great variety of dichotomy theorems concerning Borel structures in Polish spaces have been discovered. Despite the fact that these results only deal with classical notions, many of their proofs require somewhat sophisticated ideas from logic, e.g., recursion theory and forcing. We will discuss an approach to giving classical proofs and generalizations of these theorems which utilizes ideas from graph theory.

Models of set theory using Boolean algebra (for classical logic) or Heyting algebras (for intuitionistic logic) are well known and have generalization in Topos Theory. Such models show that higher-order logic has natural models different from the standard semantics. Not as much attention has been given to analogous models for modal logic. The lecture will review some background and suggest some possibilities and questions.

In his classic work “The Logical Syntax of Language” (1934) Carnap defends three distinctive claims: (1) The thesis that logic and pure mathematics are analytic and hence without content and purely formal. (2) A radical pluralist conception of pure mathematics (embodied in his Principle of Tolerance) according to which we have great freedom in choosing the fundamental postulates. (3) A minimalist conception of philosophy on which most traditional questions are rejected as pseudo-questions and philosophy is identified with the study of the logical syntax of the language of science. Carnap’s discussion is quite sophisticated metamathematically and his position is quite subtle. Indeed I think it is the most sophisticated defense of pluralism in mathematics that has appeared to date and that is my reason for concentrating on it. I will begin by criticizing both Carnap’s radical form of pluralism and his minimalist conception of philosophy. I will then turn to the question of what it would take to establish pluralism in mathematics. My focus will be on approaches where (in contrast to the approach of Carnap and many recent approaches) the question of pluralism is sensitive to actual developments in mathematics. This will involve describing various “bifurcation scenarios” in set theory that are made available by some recent results (joint with Hugh Woodin). These scenarios are sensitive to the Omega Conjecture.

We will give a concrete well order of all finite trees. This well order is an extension of the usual embedding relation between trees. It gives a system of ordinal notation with a 1–1 correspondence between finite trees and the ordinals up to the (so-called) small Veblen ordinal—and there is a nice correspondence to ordinal notations Oswald Veblen made 100 years ago. The important proof-theoretic ordinals like epsilon–0 and gamma–0 correspond to some simple trees. Using finite labeled trees we can extend this to stronger systems—and get systems close to Gaisi Takeuti’s ordinal diagrams.

We analyze the structure of equimorphism types of linear orderings ordered by embeddability. (Two linear orderings are equimorphic if they can be embedded in each other.) Our analysis is mainly from the viewpoints of Computable Mathematics and Reverse Mathematics. But we also obtain results, as the definition of equimorphism invariants for linear orderings, which provide a better understanding of the shape of this structure in general.

Here are our main results: Spector proved in 1955 that every hyperarithmetic ordinal is isomorphic to a computable one. We extend his result and prove that every hyperarithmetic linear ordering is equimorphic to a computable one. From the viewpoint of Reverse Mathematics, we look at the strength of Fraïssé’s conjecture.

From our results we deduce that Fraïssé’s conjecture is sufficient and necessary to develop a reasonable theory of equimorphism types of linear orderings.