Logic Colloquium

In 1989 Woodin and others asked whether, for a singular cardinal kappa of cofinality omega, the tree property at kappa plus implies the singular cardinal hypothesis (SCH) at kappa. At the time, the only models in which SCH failed were obtained by singularizing a regular cardinal where the GCH fails, and the question was intended to test whether this was the only way. Later results by Gitik-Magidor showed that there are other ways, yet the test question itself persisted. it has since become a motivator for several results on square principles, considered possible intermediaries on the way from the tree property to the SCH. We settle the question in this talk. We show that the tree property at kappa plus does not imply SCH at kappa. The model where the tree property holds and SCH fails is obtained by forcing with ultrafilters. We give a survey of this technique and of related results, starting with some of the most well known instances. The talk is self-contained and accessible to a general audience in mathematical logic.

Predicate logic SQHT had been introduced by V. Lifschitz, D. Pearce, and A. Valverde to characterize strong equivalence of logic programs with variables and equality with respect to stable models. The semantics for this logic is determined by intuitionistic Kripke models with two worlds “here” and “there”, constant individual domain, and decidable equality. Our sequent formulation has special rules for implication and for pushing negation inside formulas. The soundness proof allows us to establish that SQHT is a conservative extension of the logic of weak excluded middle with respect to sequents without positive occurrences of implication. The completeness proof uses a nonclosed branch of a proof search tree. The interplay between rules for pushing negation inside and truth in the “there” (non-root) world of the resulting Kripke model can be of independent interest. We prove that existence is definable in terms of the remaining connectives.

I will discuss aspects of the programme to study the algebra and geometry of the complex exponential function. Zilber constructed an exponential field and conjectured that it is isomorphic to complex exponentiation. The difficult conjecture of Schanuel in transcendental number theory is central, but I will focus more on theorems and more accessible questions. In particular, I will explain how Schanuel’s conjecture is “geometrically true”, that is, some important geometric consequences of it are true. Along the way I will explain Zilber’s construction.

The Weak Reflection Principle for omega_2 is the statement that for every stationary set S contained in the collection of countable subsets of omega_2, there is an uncountable ordinal alpha in omega_2 such that S reflects to alpha. The Reflection Principle for omega_2 is the statement that for every stationary set S contained in the collection of countable subsets of omega_2, there is an ordinal alpha in omega_2 with cofinality omega_1 such that S reflects to alpha. A long outstanding problem in set theory has been the question whether the Weak Reflection Principle for omega_2 implies the Reflection Principle for omega_2. In this talk I will discuss my recent solution to this problem.

I will sketch out the analogy between the Wason Task(s) and the Paradox of Confirmation. This will mainly involve going through some existing historical discussions concerning the analogy, and developing a precise framework for refining and critiquing the analogy. I will explain what I think is right about the existing literature, and also what I think is wrong with it (i.e., what I think the disanalogies are). Along the way, I will make various historical observations about confirmation theory and some of the contemporary evaluative assessments of the behavior of subjects faced with Wason Task(s).

The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium. (with support from the Graduate Assembly).

The Kondo-Addison theorem says that there is a uniform way, given a coanalytic set which is nonempty, of selecting a coanalytic subset which is a singleton. The perfect Kondo-Addison theorem says that there is a uniform way, given a coanalytic set which has a perfect subset, of selecting a coanalytic subset which is perfect. This talk will sketch a proof of this theorem.

The proofs of several existence theorems in mathematics involve at some step a simple combinatorial argument such as “if a finite graph has an odd-degree vertex, then it must have another”. Examples are Brouwer’s theorem, Kakutani’s theorem, Sperner’s lemma, Nash’s theorem on the existence of equilibria in games, the Arrow-Debreu theorem on price equilibria, Tucker’s lemma, the Borsuk-Ulam theorem its many corollaries such as the ham sandwich theorem, Chevalley’s theorem, Smith’s theorem, and many others. We discuss a complexity- treatment of the computational problems associated with computing or the objects whose existence is guaranteed by such results. One result to come out of this investigation is the recent proof that computing Nash equilibria is an intractable problem.

I describe two approaches to the problem of devising a view of mathematics that will account for applications of mathematics within a nominalistic framework. The first, Hartry Field’s fictionalist view of mathematics, holds that the theorems of mathematics are, like sentences in works of fiction, not true. Applications of mathematics are explained in terms of a property that good mathematical systems are supposed to possess, namely that of being “conservative” over nominalistic theories. My own account of mathematics takes a very different approach which is devised to explain important features of pure mathematics and the history of the calculus that Field’s view does not explain.

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.