Events 2012-2013
Logic Colloquium
August 24, 2012, 4:10 PM (60 Evans Hall)
Dana Scott
University Professor Emeritus, Carnegie Mellon University; Visiting Scholar, University of California, Berkeley
Lambda Calculus: Then and Now
A very fast development in the early 1930’s following Hilbert’s codification of Mathematical Logic led to the Incompleteness Theorems, Computable Functions, Undecidability Theorems, and the general formulation of Recursive Function Theory. The so-called Lambda Calculus played a key role. The history of these developments will be traced, and the much later place of Lambda Calculus in Mathematics and Programming-Language Theory will be outlined.
Logic Colloquium
September 07, 2012, 4:10 PM (60 Evans Hall)
Maryanthe Malliaris
L. E. Dickson Instructor in Mathematics, University of Chicago
Saturation of Ultrapowers and the Structure of Unstable Theories
The talk will be about some very recent progress on Keisler’s order, a far-reaching program of understanding basic model-theoretic structure through the lens of regular ultrapowers. The focus of the talk will be on classification of unstable theories; some applications to problems in set theory/general topology will also be mentioned, including a recent result of Malliaris and Shelah solving the oldest problem on cardinal invariants of the continuum.
I will assume basic familiarity with ultraproducts, Los’s theorem, and saturation, and plan to give most other relevant definitions. Papers mentioned in the talk are available at http://math.uchicago.edu/~mem.
Logic Colloquium
September 21, 2012, 4:10 PM (60 Evans Hall)
Antonio Montalban
Associate Professor of Mathematics, University of California, Berkeley
A Computability-Theoretic Equivalent to Vaught’s Conjecture
We find two computability-theoretic properties on the models of a theory T which hold if and only if T is a counterexample to Vaught’s conjecture.
Logic Colloquium
October 05, 2012, 4:10 PM (60 Evans Hall)
Seth Yalcin
Associate Professor of Philosophy, University of California, Berkeley
Some Aspects of the Logical Structure of Conversation
Normally, uttering a sentence changes the state of a conversation. Suppose we thought a natural language as determining a state transition system, where each state corresponds to a state of a possible conversation, and each sentence corresponds to a label inducing a state transition. Then we can ask: what properties are characteristic of the state transition systems appropriate to modeling conversation in natural language (or various fragments thereof)? A leading idea in the philosophy of language, and in linguistic semantics and pragmatics, is that the central effect of uttering a declarative sentence in conversation is to add a proposition to the common background assumptions of the interlocutors. We give a representation theorem indicating what formal properties are characteristic of this effect from a state transition system perspective. We then go on to discuss some fragments of language that appear to lack these properties. I connect the results to the debate about how ‘dynamic’ natural language is, and to debates about what a compositional theory of meaning should look like. (This work is joint with Daniel Rothschild, All Souls College, Oxford.)
Logic Colloquium
October 19, 2012, 4:10 PM (60 Evans Hall)
Thomas Scanlon
Professor of Mathematics, University of California, Berkeley
A Logic for General Differential Equations
Differential and difference equations have been studied from the point of view of model theory through the theories of model-complete differential and difference fields. The known theorems are similar, but the theories have been developed in parallel. I will report on joint work with Rahim Moosa in which we propose a general theory of D-fields, proving the existence of model companions, describing the definable sets, and establishing the fine-structural Zilber trichotomy principle uniformly. Our theory also grounds a general Galois theory for difference/differential equations and provides a rigorous framework for understanding the confluence from difference to differential equations.
Logic Colloquium
November 02, 2012, 4:10 PM (60 Evans Hall)
Joseph Mileti
Assistant Professor of Mathematics and Statistics, Grinnell College
Computable Combinatorics
We survey the history and some recent results analyzing theorems about trees, graph colorings, and other combinatorial structures from the viewpoint of computable mathematics. By analyzing the complexity of solutions to computable instances of these problems, we discover some striking connections across different theorems and gain insight into the techniques required in every possible proof.
Logic Colloquium
November 16, 2012, 4:10 PM (60 Evans Hall)
Grigori Mints
Professor of Philosophy and Mathematics, Stanford University; Senior Computer Scientist, SRI International, Menlo Park (July 2012 - April 2013)
Failure of Interpolation for Intuitionistic Logic of Constant Domains
The intuitionistic logic CD of constant domains is axiomatized by adding the schema (∀x)(C ∨ A(x)) → C ∨ (∀x)A(x) (x is not free in C) to the familiar axiomatization of intuitionistic predicate logic. CD is sound and complete for Kripke semantics with constant individual domains. The interpolation theorem says that for any provable implication A → B there is an interpolant I such that A → I and I → B are both provable, and I contains only predicates common to A and B. There are at least two claimed proofs of the interpolation theorem for CD, both published in The Journal of Symbolic Logic (v. 42, 1977 and v. 46, 1981). We prove that in fact the interpolation theorem fails for CD: the provable implication ((∀x)(∃y)(Py&(Qy → Rx))&¬(∀x)Rx) → ((∀x)(Px → (Qx ∨ r)) → r) does not have an interpolant. Posted as http://arxiv.org/abs/1202.3519. This is a joint work with Grigory Olkhovikov (Ural State University) and Alasdair Urquhart (University of Toronto).
Logic Colloquium
November 30, 2012, 4:10 PM
Martin Davis
Professor Emeritus of Mathematics and of Computer Science, Courant Institute, New York University, and Visiting Scholar in Mathematics, University of California, Berkeley
Pragmatic Platonism
It will be argued that Platonism in mathematics comes from the empirical fact of the success of mathematicians in dealing with the infinite and not from metaphysical speculation. Thus, absolute certainty is no more to be expected of mathematical knowledge than it is of empirical science.
Logic Colloquium
February 01, 2013, 4:10 PM
John MacFarlane
Professor of Philosophy, University of California, Berkeley
On the Motivation for the Medieval Distinction between Formal and Material Consequence
Fourteenth-century logicians define formal consequences as consequences that remain valid under uniform substitutions of categorematic terms, but they say little about the significance of this distinction. Why does it matter whether a consequence is formal or material? One possible answer is that, whereas the validity of a material consequence depends on both its structure and “the nature of things”, the validity of a formal consequence depends on its structure alone. But this claim does not follow from the definition of formal consequence by itself, and the fourteenth- century logicians do not give an argument for it. For that we must turn to Abelard, who argues explicitly that consequences that hold under uniform substitutions of their terms take their validity from their construction alone, and not from “the nature of things”. I will look at Abelard’s argument in its historical context. If my reconstruction is correct, the argument, and hence also the significance of the distinction between formal and material consequence, depends on a conception of “the nature of things” that we can no longer accept. This should give pause to contemporary thinkers who look to medieval notions of formal consequence as antecedents of their own.
Logic Colloquium
February 15, 2013, 4:10 PM
Itay Neeman
Professor of Mathematics, University of California, Los Angeles
Forcing Axioms
Forcing axioms are statements about the existence of filters over partially ordered sets, meeting given collections of dense open subsets. They have been used for several decades as center points for consistency proofs. A forcing axiom is shown consistent, typically through an iterated forcing construction, and then the consistency of other statements can be established by deriving them from the axiom.
In my talk I will begin with background on forcing and on some of the most important forcing axioms, including Martin’s Axiom (MA), and the Proper Forcing Axiom (PFA). I will discuss some key points in the axioms’ consistency proofs, and difficulties in adapting the proofs to obtain analogues of PFA that involve meeting more than aleph-sub-one dense open sets. I will end with recent work on new consistency proofs, and higher analogues of PFA.
Logic Colloquium
March 01, 2013, 4:10 PM
Wesley H. Holliday
Assistant Professor of Philosophy, University of California, Berkeley
Recent Work in Epistemic Logic
Epistemic logic provides a formal framework for modeling the knowledge of agents. Used by philosophers, theoretical computer scientists, AI researchers, game theorists, and others, epistemic logic has become one of the main application areas for modal logic. In this talk, I will survey some recent work in epistemic logic related to my research. The focus will be on how the formalization of philosophical ideas has led to interesting logical issues. Examples will include new kinds of preservation theorems and axiomatization results, as well as open problems. Some of the papers mentioned in the talk are available at http://philosophy.berkeley.edu/people/page/128.
Logic Colloquiium
March 15, 2013, 4:10 PM
Farmer Schlutzenberg
Visiting Scholar in Mathematics, University of California, Berkeley
Jónsson Cardinals in L(R)
The standard axioms of set theory leave many natural questions undecided. Determinacy axioms and large cardinal axioms give a much more complete picture, one that is natural and compelling. Strong connections are known to exist between these two families of axioms.
The Axiom of Determinacy states that in any infinite two- player game of perfect information on the natural numbers one player has a winning strategy. AD implies large cardinal axioms. It also contradicts the Axiom of Choice, and even implies all sets of reals are Lebesgue measurable. Therefore AD fails in the full universe of sets, where Choice holds. However, there are important subuniverses where AD may hold, among them the universe L(R) of all sets constructible from the reals. Assuming AD holds in L(R), a detailed analysis of L(R) is possible, extending classical results of descriptive set theory on analytic and Borel sets.
A cardinal is Jónsson if every structure of that size has a proper elementary substructure of that size. They were introduced by Bjarni Jónsson in 1972. We will survey the above background and sketch a proof that, given AD, there are many Jónsson and Rowbottom cardinals in L(R). Both results use the same key argument. (The result for Jónsson cardinals was first announced by Woodin.)
Logic Colloquium
April 05, 2013, 4:10 PM (60 Evans Hall)
C. Ward Henson
Professor Emeritus of Mathematics, University of Illinois at Urbana-Champaign
Continuous Model Theory and Gurarij’s Universal, Homogeneous, Separable Banach Space
Gurarij’s Banach space was constructed in the 1960s using a metric version of a Fraisse construction; it is universal isometrically (for separable Banach spaces) and is homogeneous in an almost-isometric sense relative to its finite-dimensional subspaces. It is the analogue (for Banach spaces) of such structures as the random graph and Urysohn’s metric space. General results in Banach space theory from the 1960s show that its dual space is of the form L1(μ) for some measure μ, so it falls into the important class of “classical Banach spaces”, a fact that is far from obvious based on the original construction. Wolfgang Lusky showed in the 1970s that the Gurarij space is isometrically unique, a surprising result. He also indicated that the set of smooth points of norm 1 is an orbit of its automorphism group. In this talk it will be shown how these results can be seen and extended using continuous model theory. In particular, the class of separable Gurarij spaces can be realized as the class of separable models of a certain continuous theory T (of unit balls of Banach spaces); this theory has quantifier elimination and is the model completion of the theory of all Banach spaces. An optimal amalgamation result yields a simple formula for the induced metric on the type spaces of T over sets of parameters, which is a key to the applications that will be discussed in this talk. A highlight of recent research is the following: let X be Gurarij’s space and let E be any finite dimensional space. Then there is anisometric linear embedding J of E into X such that J (E) has the unique Hahn-Banach extension property in X; moreover, the set of all such embeddings forms a full orbit under the action of the automorphism group of X. Model-theoretically this situation is equivalent to saying that X expanded by naming all elements of J(E) is an atomic model of its theory. This is joint work with Itai Ben Yaacov, and our paper is available at the arXiv. [Note: Earlier Gurarij’s name was transliterated “Gurarii” and in the west it is always pronounced “Ger-ar-eee”.]
Logic Colloquium
April 19, 2013, 4:10 PM (60 Evans Hall)
W. Hugh Woodin
Professor of Mathematics, University of California, Berkeley
Ultimate Truth or Ultimate Chaos?
Set Theory is arguably reaching a tipping point. But which way will it tip?
Tarski Lectures
April 22, 2013, 4:10 PM (TBA)
Jonathan Pila
Reader in Mathematical Logic, University of Oxford
Rational Points of Definable Sets and Diophantine Problems
Tarski Lectures
April 24, 2013, 4:10 PM (TBA)
Jonathan Pila
Reader in Mathematical Logic, University of Oxford
Special Points and Ax-Lindemann
Tarski Lectures
April 26, 2013, 4:10 PM (60 Evans Hall)
Jonathan Pila
Reader in Mathematical Logic, University of Oxford
The Zilber-Pink Conjecture