Logic Colloquium
- ITAY NEEMAN
- Professor of Mathematics
- University of California, Los Angeles
- will speak on
- Forcing with Ultrafilters
- on
- Friday, May 1, 2009
- in
- 60 Evans Hall
- at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) (with support from the Graduate Assembly).
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.
- GRIGORI MINTS
- Professor of Philosophy and of Mathematics
- Stanford University
- will speak on
- Cut-free Formulation of Predicate Logic of Here-and-There
- on
- Friday, April 24, 2009
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
- JONATHAN KIRBY
- Postdoctoral Research Fellow, University of Oxford
- Visiting Scholar, University of California, Berkeley
- will speak
- on
- Complex Exponentiation and Zilber’s Pseudo-exponentiation
- on
- Friday, April 3, 2009
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
- JOHN KRUEGER
- Morrey Assistant Professor of Mathematics
- University of California, Berkeley
- will speak
- under the title
- On the Weak Reflection Principle
- on
- Friday, March 20, 2009
- in
- 60 Evans Hall
- at
4:10 p.m.
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 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.
- BRANDEN FITELSON
- Associate Professor of Philosophy
- University of California, Berkeley
- will speak on
- The Wason Task(s)
- and the Paradox of Confirmation
- on
- Friday, March 6, 2009
- in
- 60 Evans Hall
- at
4:10 p.m.
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).
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).
- LEO HARRINGTON
- Professor of Mathematics
- University of California, Berkeley
- will speak
- on
- A Perfect Kondo-Addison Theorem
- on
- Friday, February 20, 2009
- in
- 60 Evans Hall
- at
- 4:10 p.m.
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.
- CHRISTOS H. PAPADIMITRIOU
- C. Lester Hogan Professor of Electrical Engineering and Computer Sciences
- University of California, Berkeley
- will speak
- on
- On Brouwer, Nash, and Other Nonconstructive Proofs
- on
- Friday, February 6, 2009
- in
- 60 Evans Hall
- at
4:10 p.m.
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 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.
- CHARLES CHIHARA
- Emeritus Professor of Philosophy
- University of California, Berkeley
- will speak on
- Two Nominalistic Views of Mathematics
- on
- Friday, January 23, 2009
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
- THOMAS SCANLON
- Associate Professor of Mathematics
- University of California, Berkeley
- will speak on
- Algebraic Dynamics and the Model Theory of Difference Fields
- on
- Friday, December 5, 2008
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- The biweekly LOGIC TEA will be held in the Mathematics Common Room (1015 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).
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.
- Benjamin Miller
- Ph.D., University of California, Berkeley
- will speak on
- Forceless, Ineffective, Powerless Proofs
- of Descriptive Set-theoretic Dichotomy Theorems
- on
- Friday, November 14, 2008
- in
- 60 Evans Hall
- at
4:10 p.m.
The biweekly LOGIC TEA will be held in the Mathematics Common Room (1015 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).
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.
- DANA S. SCOTT
- University Professor, Emeritus
- Carnegie Mellon University
- Visiting Scholar in Logic and the Methodology of Science
- University of California, Berkeley
- will speak on
- Higher-Order Modal Modeling
- on
- Friday, October 31, 2008
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
- PETER KOELLNER
- John L. Loeb Associate Professor of the Humanities
- Harvard University
- will speak on
- Truth in Mathematics: The Question of Pluralism
- on
- Friday, October 17, 2008
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
- HERMAN RUGE JERVELL
- Professor of Computer Science
- University of Oslo
- will speak on
- How to Well Order Finite Trees and Get Good Ordinal Notations
- on
- Friday, October 3, 2008
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
- ANTONIO MONTALBAN
- Assistant Professor of Mathematics
- University of Chicago
- will speak on
- Equimorphism Types of Linear Orderings
- on
- Friday, September 5, 2008
- in
- 60 Evans Hall
- at
- 4:10 p.m.
- 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).
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.
