Events 2010-2011

Logic Colloquium

September 03, 2010, 4:10 PM (60 Evans Hall)

W. Hugh Woodin
Professor of Mathematics, University of California Berkeley

Strong Axioms of Infinity and the Search for V

Professor Woodin plans to give a broad and nontechnical overview of the prospects of the existence of an ultimate version of Gödel’s Axiom of Constructibility. The talk will be essentially a repeat of the Plenary Lecture in Logic at the International Congress of Mathematicians in Hyderabad, India, which he delivered on Thursday, August 26.

Logic Colloquium

September 17, 2010, 4:10 PM (60 Evans Hall)

Alice Medvedev
Visiting Assistant Professor of Mathematics, University of California Berkeley

The Recursive Spectrum of a Strongly Minimal Modular Theory of Groups in a Finite Language

The recursive spectrum of a fixed strongly minimal theory T is the set of integers n such that the model of T of dimension n admits a recursive presentation. How complicated can this set be? Some interesting examples can be constructed by coding complicatedness into an infinite language, or by using Hrushovski constructions. We are working towards showing that the recursive spectrum of a strongly minimal locally modular theory in finite language must be nothing; everything; or only the prime model. The title describes the current state of this joint work with Uri Andrews.

Logic Colloquium

October 01, 2010, 4:10 PM (60 Evans Hall)

Solomon Feferman
Professor Emeritus of Mathematics and Philosophy, Stanford University

What’s Definite? What’s not?

Most axiomatizations of set theory that have been treated metamathematically have been based either entirely on classical logic or entirely on intuitionistic logic. But a natural conception of the set-theoretic universe is as an indefinite (or “potential”) totality, to which intuitionistic logic is more appropriately applied, while each set is taken to be a definite (“or completed”) totality, for which classical logic is appropriate; so on that view, set theory should be axiomatized on some correspondingly mixed basis. Similarly, in the case of predicative analysis, the natural numbers are conceived to form a definite totality, while the universe of sets (or functions) of natural numbers are viewed as an indefinite totality, so that, again, a mixed semi-constructive logic should be the appropriate one to treat the two together. In the first part of the talk I will present ways of formulating such semi-constructive systems of analysis and set theory and survey some results characterizing their proof-theoretic strength. Interestingly, though the logic is weakened, one can usefully strengthen certain principles. In the last part of the talk I will relate this work to the controversial discussion as to whether certain statements in the language of set theory such as the Continuum Hypothesis express definite or indefinite problems.

Logic Colloquium

October 08, 2010, 4:10 PM (60 Evans Hall)

Henry Towsner
Hedrick Assistant Adjunct Professor of Mathematics, University of California, Los Angeles

The Infinitary Approach to Finite Combinatorics

The “Correspondence Principle” makes it possible to take combinatorial problems about finite structures and translate them into questions about infinitary, measure-theoretic structures. While there are fairly elementary combinatorial approaches, it has recently become clear that the model-theoretic approach creates a particularly rich and flexible infinitary structure. We will outline the model-theoretic proof of the correspondence principle and point out some of its new applications. To illustrate the flexibility of this method, we will give a short proof of the Szemeredi regularity lemma, an important tool in the study of finite graphs.

Logic Colloquium

October 29, 2010, 4:10 PM (60 Evans Hall)

Isaac Goldbring
Hedrick Assistant Adjunct Professor of Mathematics, University of California, Los Angeles

A Survey of the Model Theory of Urysohn’s Metric Space

Urysohn’s metric space U is the unique (up to isometry) Polish (i.e. complete, separable) metric space which is universal, that is it contains an isometric copy of all Polish metric spaces, and ultrahomogeneous, that is any isometry between finite subspaces of U extends to an isometry of U. Urysohn’s metric space (and its isometry group) has been studied by topologists and descriptive set theorists for a plethora of reasons. In this talk, I will outline much of what is known on the model theory of Urysohn’s metric space in the context of model theory for metric structures, which I will introduce at the beginning of my talk. I will discuss matters such as axiomatizability, quantifier elimination, independence relations, and definability.

Logic Colloquium

November 12, 2010, 4:10 PM (60 Evans Hall)

G. Aldo Antonelli
Professor of Philosophy, University of California, Davis

The Abstraction Mystique

The logical status of abstraction principles, and especially Hume’s Principle, has been long debated, but the best currently available tool for explicating a notion’s logical character – the notion of permutation invariance introduced by Tarski in 1966 – has not received a lot of attention in this debate. This talk aims to fill this gap. After characterizing abstraction principles as particular classifiers, i.e., mappings from the subsets of a domain into that domain and exploring some of their properties, the paper introduces several distinct notions of permutation invariance for such principles, assessing the philosophical significance of each.

Logic Colloquium

December 03, 2010, 4:10 PM (60 Evans Hall)

John R. Steel
Professor of Mathematics, University of California, Berkeley

The Triple Helix

Many different foundational theories have been developed and studied by set theorists. Remarkably, no divergence at the level of statements about “concrete” objects (for example, natural numbers) has emerged, and indeed, these theories are linearly ordered by the inclusion order on their sets of arithmetic consequences. The place of a theory in this order is known as its consistency strength. Our methods for comparing the consistency strengths of set theories center on three intertwined canonical hierarchies of sets. In this talk we shall describe those three hierarchies in very general terms. We shall focus on the philosophical significance of the results and open questions concerning them.

Logic Colloquium

January 28, 2011, 4:10 PM (60 Evans Hall)

Thomas Scanlon
Professor of Mathematics, University of California, Berkeley

Number-theoretic Consequences of the Model Theory of Real Geometry

We say that a first-order structure (R, <, …) in some language expanding the language of orders is o-minimal if < linearly orders R and every definable subset of R is a finite union of points and intervals. Tarski’s quantifier elimination theorem for the real field implies that the real numbers considered as an ordered ring is o-minimal and subsequent work by various authors has established the o-minimality of more sophisticated structures on the real numbers. The definable sets in an o-minimal structure (in any number of variables) admit a very tame geometric structure theory, very much at odds with the Gödel phenomena in arithmetic. Nevertheless, Pila and Wilkie bridged the divide between geometry and arithmetic by establishing bounds on the number of rational points in sets definable in o-minimal expansions of the real numbers. In recent work, Pila employed this counting theorem to prove the celebrated André-Oort conjecture on algebraic relations on special points of modular curves. In this talk, I will describe the Pila-Wilkie counting theorem and some of my own work relating arithmetic questions about algebraic dynamical systems to o-minimality and the Pila-Wilkie bounds.

Logic Colloquium

February 11, 2011, 4:10 PM (60 Evans Hall)

Grigori Mints
Professor of Philosophy and of Mathematics, Stanford University

Extension of Epsilon Substitution to Second-Order Systems

The problem of extending the epsilon substitution method to second-order systems was posed by Hilbert in 1928 and repeated in “Grundlagen der Mathematik” (1939). In this talk I will describe the first-order formulation (due to Hilbert, Ackermann, von Neumann, and Bernays) and outline possible extensions to the second order, progress achieved up to now, and obstacles to a termination proof.

Logic Colloquium

February 25, 2011, 4:10 PM (60 Evans Hall)

Phokion G. Kolaitis
Professor of Computer Science, University of California Santa Cruz, and, Research Staff Member, IBM Almaden Research Center

Random Graphs and the Parity Quantifier [Slides]

The classical zero-one law for first-order logic asserts that the asymptotic probability of every first-order definable property of finite graphs always exists and is either zero or one. Over the years zero-one laws have been established for numerous extensions of first-order logic, including least-fixed point logic, finite-variable infinitary logics, and certain fragments of existential second-order logic. The zero-one law, however, fails to hold for any logical formalism that is powerful enough to express parity, that is, the property “there is an odd number of elements”; in fact, for such logical formalisms, even the convergence law fails to hold. In this work, we turn the parity barrier into a feature and systematically investigate the asymptotic probabilities of properties of finite graphs expressible in first-order logic augmented with the parity quantifier. Our main result is a “modular convergence law” that captures the limiting behavior of properties expressible in this extension of first-order logic on finite graphs. This is joint work with Swastik Kopparty, Institute for Advanced Study.

Logic Colloquium

March 11, 2011, 4:10 PM (60 Evans Hall)

Bjørn Kjos-Hanssen
Associate Professor of Mathematics, University of Hawaii at Manoa, and, Visiting Associate Professor of Mathematics, University of California, San Diego

Discerning Randomness from an Asymptotic Hamming Distance

A notion of asymptotic Hamming distance suitable for the study of algorithmic randomness of infinite binary sequences is developed. As an application, it is shown that there is no fixed procedure that computes a (weakly) Mises-Wald-Church stochastic sequence from an arbitrary complex sequence. Here a sequence is complex if its fixes have Kolmogorov complexity bounded below by an unbounded, nondecreasing computable function.

Herbert Enderton Memorial Gathering

March 15, 2011, 11:00 AM (Berkeley City Club, 2315 Durant Avenue, Berkeley, California)

You are invited to join us to celebrate Herbert’s life on April 15, his 75th birthday. The gathering will be in Berkeley, CA at the Berkeley City Club from 11 am to 3 pm. Lunch will be served.

Whether or not you can attend, we would love to have you send us short written stories and memories of Herbert that we can draw on for the eulogy and share with his loved ones.

Warmly, Cathy, Eric, and Bert

(Please forward this note to anyone whose address we might not have. All who wish to attend are welcome; we just need a head count. RSVP: cenderton@hotmail.com)

(A group rate is available for lodging at the Berkeley City Club. (510) 848-7800.)

Logic Colloquium

April 08, 2011, 4:10 PM (60 Evans Hall)

Ronald Fagin
Manager, Foundations of Computer Science, IBM Almaden Research Center

P vs. NP, and Community Refereeing in the Web Era

P and NP are “complexity classes”. The problem of whether they are the same is renowned in computer science and mathematics, and a solution yields a Clay Millennium Prize of one million dollars, mathematical immortality, and deep insight into efficient computation. In August of 2010 there was a lot of excitement over the announcement of a possible solution: a claimed mathematical proof that P and NP are different, using ideas from mathematical logic and statistical physics. We will describe the P vs. NP problem at a high level for a general scientific audience. What is this problem? How is it important? We will also discuss the fascinating sociological phenomenon of mathematical refereeing in “internet time”. Finally, we will discuss the idea of the attempted proof, and issues that were raised during the “internet refereeing” process.

Logic Colloquium

April 22, 2011, 4:10 PM (60 Evans Hall)

Matthew D. Foreman
Professor of Mathematics, University of California, Irvine

Classifying Measure Preserving Diffeomorphisms of the Torus

The statistical behavior of deterministic dynamical systems can be completely random. The ergodic theorem tells us that the statistical behavior of a system carrying an invariant ergodic measure is captured by the isomorphism class of that measure. Motivated by this type of phenomenon, in 1932 von Neumann proposed the program of classifying the ergodic measure preserving systems.

In this talk we will describe applications of the tools of descriptive set theory to show that this program is impossible. In earlier joint work with Weiss, it was shown that the isomorphism relation is “turbulent” and hence no generic class can be reduced to an S-infinity action. With Rudolph and Weiss it was shown that the isomorphism relation is a complete analytic set.

But what about concrete systems: C-infinity measure preserving transformations of the torus? Recent work with Weiss extends these results to such diffeomorphisms. Finally a very recent result shows that the “graph-isomorphism problem” can be reduced to isomorphism of measure preserving diffeomorphisms. As a corollary the isomorphism relation is complete for S-infinity actions.