Events 2016-2017

Logic Colloquium

August 26, 2016, 4:10 PM (60 Evans Hall)

Martin Otto
Professor in Mathematical Logic, Department of Mathematics, Technische Universitaet Darmstadt (currently visiting the Simons Institute for Theory of Computing, Berkeley)

Back & Forth Between Malleable Finite Models

This talk attempts to survey some model-theoretic techniques, model transformations and constructions - especially for logics of a modal/guarded flavour - that can replace classical compactness arguments, which are not available in restriction to finite models or other non-elementary classes of interest. Even where these algebraic-combinatorial and game-oriented techniques concur with the usually smoother infinitary methods of classical model theory they occasionally offer additional constructive or quantitative information. Some of the underlying combinatorial constructions to be discussed involve rather generic finite coverings for graphs and hypergraphs and are of independent interest. They can also be used towards alternative proofs of powerful extension properties for partial isomorphisms, which also have applications for the finite model theory of related logics.

Logic Colloquium

September 09, 2016, 4:10 PM (60 Evans Hall)

Sam Buss
Professor of Mathematics and Computer Science, UC San Diego

Frege Proofs, Extended Frege Proofs, and Total NP Search Problems

This talk will discuss some of the fundamental problems of proof complexity and their connection to computational complexity. The talk focuses on the proof complexity of the Frege and extended Frege proof systems for propositional logic. Recent work includes new proofs for the pigeonhole principle (!), Frankl’s theorem, the AB=I theorem, and the Kneser-Lovasz theorem on chromatic numbers. These problems are closely related to Total NP Search Problems (TFNP), a complexity class that lies midway between P and NP. The consistency statements for exponentially large Frege and extended Frege proofs can be used to characterize the provably total functions of second-order theories of bounded arithmetic for polynomial space and exponential time.

Logic Colloquium

September 23, 2016, 4:10 PM (60 Evans Hall)

Andreas Blass
Professor of Mathematics, University of Michigan, and Visiting Scientist, Simons Institute for the Theory of Computing

Between countable and continuum

I plan to give a general introduction to cardinal characteristics of the continuum, including several examples of characteristics and of the sorts of results that the theory obtains. Afterward, if time permits, I’ll describe some recent work on a specific characteristic suggested by a familiar theorem from calculus. The talk will be aimed at people who are not set theorists.

Logic Colloquium

October 07, 2016, 4:10 PM (60 Evans Hall)

Dag Westerståhl
Professor of Theoretical Philosophy and Logic, Stockholm University

A Carnapian approach to the meaning of logical constants: the case of modal logic

Does a consequence relation in a language L, as a syntactic relation between sets of L-sentences and L-sentences, fix the meaning of the logical constants in L? In his 1943 book The Formalization of Logic, Carnap worried that this seems to fail even for classical propositional logic CL. However, by applying the viewpoint of modern formal semantics, which in particular requires meaning assignment to be compositional, Carnap’s worries about CL can be allayed. More importantly, it provides a precise framework for asking Carnap’s question about any logic. (To what extent) does classical first-order consequence determine the meaning of ? What about other (generalized) quantifiers? What about the intuitionistic meaning of the connectives? Or in (classical) modal logic? [1] answers the first of these questions. In this talk I focus on the last one. Despite obvious similarities between and , there are important differences. Roughly, while there is essentially just one first-order logic, there are innumerable modal logics. That makes answers to Carnap style questions about the meaning of more intricate, and more interesting, than in the case of . Although we in a sense cover extremely familiar ground, the perspective one gets, in particular of neighborhood semantics for modal logic, seems novel. This is joint work with Denis Bonnay.

[1] D. Bonnay and D. Westerståhl, ‘Compositionality solves Carnap’s Problem’, Erkenntnis 81 (4), 2016 (721–739).

Slides

Logic Colloquium

October 21, 2016, 4:10 PM (60 Evans Hall)

Erich Grädel
Professor of Mathematical Foundations of Computer Science, RWTH Aachen University

Back and Forth Between Team Semantics, Games, and Tarski Semantics

Team semantics, due to Wilfrid Hodges, is the mathematical basis of modern logics of dependence and independence in which, following a proposal by Väänänen, dependencies are considered as atomic statements, and not as annotations of quantifiers. In team semantics, a formula is evaluated not against a single assignment of values to the free variables, but against a set of such assignments.

Logics with team semantics have strong expressive power and some surprising properties. They can be analyzed in several different ways. First-order formulae with team semantics and dependencies can be translated into sentences of existential second-order logic, with an additional predicate for the team (and with classical Tarski semantics). We can thus understand the power of a specific logic of dependence or independence by identifying the fragment of existential second-order logic to which it corresponds. Further, logics can be understood through their games. In general the model-checking games for logics with team semantics turn out to be second-order reachability games.

We shall then have a closer look at the specific case of logics with inclusion dependencies, and reveal their connection with safety games and logics with greatest fixed-points.

Slides

Logic Colloquium

November 04, 2016, 4:10 PM (60 Evans Hall)

Mai Gehrke
Senior Research Director, CNRS & Université Paris Diderot - Paris 7

Canonical extensions and applications

In 1951-52 Jònsson and Tarski published a two part paper in which they cast Stone duality for Boolean algebras in algebraic form as so-called canonical extensions, and used this formulation to extend Stone duality to Boolean algebras with operators (BAOs). That is, Boolean algebras with additional operations which preserve join in each coordinate. In this way they obtained the relational semantics of modal logic. Since then the theory of canonical extensions, and thus duality for additional structure on lattices and Boolean algebras, has been generalised and better understood. These tools have played a central role in the discovery of the connection between formal language theory and Stone duality. In particular, the fact that the profinite completion of any abstract algebra is the Stone dual of the Boolean algebra of recognisable languages over the algebra equipped with certain residuation operations.

In this talk, I will give an introduction to these ideas and an overview of recent developments.

Working Group in the History and Philosophy of Logic, Mathematics, and Science

November 16, 2016, 6:00 PM (234 Moses Hall)

Juliette Kennedy
Associate Professor, Department of Mathematics and Statistics, University of Helsinki

Squeezing arguments and strong logics

G. Kreisel has suggested that squeezing arguments, originally formulated for the informal concept of first order validity, should be extendable to second order logic, although he points out obvious obstacles. We develop this idea in the light of more recent advances and delineate the difficulties across the spectrum of extensions of first order logics by generalised quantifiers and infinitary logics. This is joint work with Jouko Väänänen.

Logic Colloquium

November 18, 2016, 4:10 PM (60 Evans Hall)

Phokion G. Kolaitis
UC Santa Cruz & IBM Research - Almaden

Dependence Logic vs. Constraint Satisfaction

During the past decade, dependence logic has emerged as a formalism suitable for expressing and analyzing notions of dependence and independence that arise in different scientific areas. The sentences of dependence logic have the same expressive power as those of existential second-order logic, hence dependence logic captures the complexity class NP on the collection of all finite structures over a relational vocabulary. We identify a natural fragment of universal dependence logic and show that, in a precise sense, this fragment captures constraint satisfaction, a ubiquitous algorithmic problem encountered across different areas of computer science. This tight connection between dependence logic and constraint satisfaction contributes to the descriptive complexity of constraint satisfaction and elucidates the expressive power of universal dependence logic.

This is joint work with Lauri Hella, University of Tampere, Finland.

Slides

Logic Colloquium

December 02, 2016, 4:10 PM (60 Evans Hall)

Prakash Panangaden
Professor, School of Computer Science, McGill University

A Logical Characterization of Probabilistic Bisimulation

Labelled Markov Processes (LMPs) are a combination of traditional labelled transition systems and Markov processes. Discrete versions of such systems have been around for a while and were thoroughly explored by Larsen and Skou in the late 1980s and early 1990s. Our contribution has been to extend this study to systems with continuous state spaces.

The main technical contribution that I will discuss in this talk is a definition of probabilistic bisimulation for such systems and a logical characterization for it. The surprise is that a very simple modal logic with no negative constructs or infinitary conjunctions suffices to characterize bisimulation, even with uncountable branching. This is quite different from the traditional situation with Kripke structures where van Benthem and Hennessy and Milner characterized bisimulation using negation in an essential way.

Logic Colloquium

January 27, 2017, 4:10 PM (60 Evans Hall)

Ilijas Farah
Professor of Mathematics, York University

Model theory of operator algebras

Unexpected and deep connections between the theory of operator algebras and logic have been discovered in the past fifteen years. Even more remarkably, diverse areas of logic that are generally (and arguably) thought to have little connection to one another have found natural - and sometimes necessary - applications to operator algebras. In this talk I will emphasize applications of model theory to operator algebras.

Logic Colloquium

February 10, 2017, 4:10 PM (60 Evans Hall)

Clifton Ealy
Associate Professor of Mathematics, Western Illinois University

Residue field domination in real closed valued fields

In an algebraically closed valued field, as shown by Haskell, Hrushovski, and Macpherson, the residue field and the value group control the rest of the structure: tp(L/Ck(L)Γ(L) will have a unique extension to M ⊇ C, as long as the residue field and value group of M are independent from those of L. (Here k(L) and Γ(L) denote the residue field and value group, respectively, of L, and C is a maximal field.)

This behaviour is striking, because it is what typically occurs in a stable structure (where types over algebraically closed sets have unique extensions to independent sets) but valued fields are far from stable, due to the order on the value group.

Real closed valued fields are even further from stable since the main sort is ordered. One might expect the analogous theorem about real closed valued fields to be that tp(L/M) is implied by tp(L/Ck(L)Γ(L)) together with the order type of L over M. In fact we show that the order type is unnecessary, that just as in the algebraically closed case, one has that tp(L/M) is implied by tp(L/k(L)Γ(L)). This is joint work with Haskell and Marikova.

No knowledge of value fields will be assumed.

Slides

Logic Colloquium

February 24, 2017, 4:10 PM (60 Evans Hall)

Sean Walsh
Department of Logic and Philosophy of Science, University of California, Irvine

Realizability Semantics for Quantified Modal Logic

In 1985, Flagg produced a model of first-order Peano arithmetic and a modal principle known as Epistemic Church’s Thesis, which roughly expresses that any number-theoretic function known to be total is recursive. In some recent work ([1]), this construction was generalized to allow a construction of models of quantified modal logic on top of just about any of the traditional realizability models of various intuitionistic systems, such as fragments of second-order arithmetic and set theory. In this talk, we survey this construction and indicate what is known about the reduct of these structures to the non-modal language.

References: [1] B. G. Rin and S. Walsh. Realizability semantics for quantified modal logic: Generalizing Flagg’s 1985 construction. The Review of Symbolic Logic, 9(4):752–809, 2016.

Logic Colloquium

March 10, 2017, 4:10 PM (60 Evans Hall)

Caroline Terry
Brin Postdoctoral Fellow, University of Maryland, College Park, and Research Fellow, Simons Institute for the Theory of Computing

Structure and enumeration theorems for hereditary properties of -structures

The study of structure and enumeration for hereditary graph properties has been a major area of research in extremal combinatorics. Over the years such results have been extended to many combinatorial structures other than graphs. This line of research has developed an informal strategy for how to prove these results in various settings. In this talk we use tools from model theory to formalize this strategy. In particular, we generalize certain definitions, tools, and theorems which appear commonly in approximate structure and enumeration theorems in extremal combinatorics. Our results apply to classes of finite -structures which are closed under isomorphism and model-theoretic substructure, where is any finite relational language.

Slides

Logic Colloquium

March 24, 2017, 4:10 PM (60 Evans Hall)

Françoise Point
FNRS-FRS (UMons)

On expansions of (ℤ, +,0)

In the special case of the structure (ℤ, +,0), we will consider the following model-theoretic question: given a well-behaved first-order structure, which kind of predicates can one add and retain model-theoretic properties of the structure one started with, such as stability- like properties, quantifier elimination in a reasonable language, decidability. We will review recent results on stability properties of expansions of (ℤ, +,0) by a unary predicate and we will make the comparison with former results on the decidability and model-completeness of the corresponding expansions of (ℤ, +,0,  < ) (and if time permits, with the corresponding expansions of the field of real numbers).

Slides

Logic Colloquium

April 07, 2017, 4:10 PM (60 Evans Hall)

Pierre Simon
Assistant Professor of Mathematics, UC Berkeley

On omega-categorical structures and their automorphism groups

The study of omega-categorical structures and their automorphism groups has been for several decades a very active area of research and point of contact between model theory, group theory, combinatorics and descriptive set theory. A countable structure is omega-categorical if its automorphism group acts oligomorphically on it, that is has finitely many orbits on n-tuples, for all n. In this talk, I will introduce this subject by presenting the various angles of approach and talk about a selection of topics, in particular concerning countable subgroups of automorphism groups. I will present a recent work with Itay Kaplan on the existence of finitely generated dense subgroups and ask a number of questions.

Alfred Tarski Lectures

April 10, 2017, 4:10 PM (50 Birge Hall)

Lou van den Dries
Professor, Department of Mathematics, University of Illinois at Urbana-Champaign

Model Theory as a Geography of Mathematics

I like to think of model theory as a geography of mathematics, especially of its “tame” side. Here tame roughly corresponds to geometric as opposed to combinatorial-arithmetic. In this connection I will discuss Tarski’s work on the real field, and the notion of o-minimality that it suggested.

A structure M carries its own mathematical territory with it, via interpretability: its own posets, groups, fields, and so on. Understanding this “world according to M” can be rewarding. Stability-like properties of M forbid certain combinatorial patterns, thus providing highly intrinsic and robust information about this world.

Alfred Tarski Lectures

April 12, 2017, 4:10 PM (50 Birge Hall)

Lou van den Dries
Professor, Department of Mathematics, University of Illinois at Urbana-Champaign

Orders of Infinity and Transseries

The “orders of Infinity” of the title are du Bois Reymond’s growth rates of functions, put on a firm basis by Hardy and Hausdorff. This led to the notion of a Hardy field (Bourbaki). Other ways of describing these orders of infinity are transseries (formal series containing powers of the variable x as well as exponential and logarithmic terms like ex and log x), and Conway’s surreal numbers. These topics are all closely related, with the differential field 𝕋 of transseries taking center stage.

Alfred Tarski Lectures

April 14, 2017, 4:10 PM (50 Birge Hall)

Lou van den Dries
Professor, Department of Mathematics, University of Illinois at Urbana-Champaign

Model Theory of Transseries: Results and Open Problems

The book Asymptotic Differential Algebra and Model Theory of Transseries (arXiv:1509.02588) by Aschenbrenner, van der Hoeven, and myself will soon appear as the Annals of Mathematics Studies, number 195. It contains the main results of twenty years of investigating 𝕋. One of these results is easy to state: The theory of this differential field is completely axiomatized by the requirements of being a Liouville closed H-field with small derivation and the intermediate value property for differential polynomials. I will explain the meaning of these terms, further results on 𝕋 and some consequences for what is definable in 𝕋.

I will also discuss some of the many attractive open problems in this area.

Logic Colloquium

April 21, 2017, 4:10 PM (60 Evans Hall)

Jana Marikova
Assistant Professor of Mathematics, Western Illinois University

Convexly valued o-minimal fields

O-minimal structures are ordered structures in which the definable sets behave in a particularly tame fashion. For example, definable one-variable functions are piecewise continuous and differentiable. A prototypical example is the ordered real field in which the definable sets are precisely the semialgebraic sets.

Valuations yield a way of understanding an (expansion of) a field in terms of two, often simpler, associated structures, namely its residue field and value group.

We shall investigate o-minimal fields with valuations that are determined by convex subrings. In particular, we shall see that the class of o-minimal fields with onvex subrings that give rise to o-minimal residue fields have various desirable properties, including quantifier elimination in a suitable language.

Slides

May 05, 2017, 9:00 AM (McCone Hall, Room 141 from 9 AM to 2 PM; LeConte Hall, Room 3 from 2 PM to 5 PM)

Denis Hirschfeldt, Ehud Hrushovski, Michael Rathjen, John Steel

Logic at UC Berkeley

A two-day conference in mathematical logic and related areas organized by The Group in Logic and the Methodology of Science at UC Berkeley (logic.berkeley.edu). The conference is partly occasioned by the fact that the Group in Logic turns sixty this year.

In 1957, a group of faculty members, most of them from the departments of Mathematics and Philosophy, initiated a pioneering interdisciplinary graduate program leading to the degree of Ph.D. in Logic and the Methodology of Science. The Group has fostered interdisciplinary work in which logic has interacted with mathematics, philosophy, statistics, computer science, linguistics, physics and other disciplines.

While mathematical logic at UC Berkeley cannot be identified only with the Group in Logic, the Group has played a vital role in Berkeley’s worldwide prominence in mathematical logic and significantly contributed to making Berkeley a mecca since the fifties for people interested in mathematical logic and its applications. A full list of all those researchers in logic who taught at UC Berkeley, or studied at UC Berkeley, or visited Berkeley for shorter or longer periods would result in a who’s who of mathematical logic.

While marking an important moment for logic at UC Berkeley, the conference will be forward looking rather than merely celebratory. We have invited eight internationally prominent scholars to talk about the future of mathematical logic in their respective areas of specialization.

The first day of the conference will have four invited speakers in the so-called “foundational” areas: set theory, model theory, recursion theory, and proof theory. The second day will have four invited speakers in areas where mathematical logic plays a prominent role, namely philosophy of logic and mathematics, formal semantics for natural languages, modal logic, and logic in computer science. The line up is given below.

For a map showing the conference lecture rooms, see the red arrows here.

May 5 (141 McCone Hall 9AM-2PM; 3 LeConte Hall 2-5PM)

introductory remarks (9-9:30am): Paolo Mancosu (UC Berkeley), “A brief history of the Group in Logic and the Methodology of Science” (slides)

set theory (9:30-10:45am): John Steel (UC Berkeley), “Absolutely ordinal definable sets” (slides)

model theory (11am-12:15pm): Ehud Hrushovski (Hebrew University, Oxford University), “Reflections on model theory and foundations

recursion theory (2:15-3:30pm): Denis Hirschfeldt (University of Chicago), “Computability Theory” (slides)

proof theory (3:45-5:00pm): Michael Rathjen (Leeds University), “On relating type theories to (intuitionistic) set theories” (slides)

May 6 (105 North Gate Hall)

philosophy of logic and mathematics (9:30-10:45am): Jeremy Avigad (Carnegie Mellon University), “Modularity of Mathematics” (slides)

formal semantics for natural languages (11am-12:15pm): Barbara Partee (University of Massachusetts at Amherst), “The Intertwining Influences of Logic, Philosophy, and Linguistics in the Development of Formal Semantics and Pragmatics” (slides)

modal logic (2:15-3:30pm): Johan van Benthem (University of Amsterdam, Stanford University, Tsinghua University), “Modal logic, on the cusp of philosophy and mathematics” (handout)

logic in computer science (3:45-5:00pm): Ronald Fagin (IBM Almaden Research Center), “Applying logic to practice in computer science” (slides)

May 06, 2017, 9:30 AM (North Gate Hall, Room 105)

Jeremy Avigad, Johan van Benthem, Ronald Fagin, Barbara Partee

Logic at UC Berkeley

A two-day conference in mathematical logic and related areas organized by The Group in Logic and the Methodology of Science at UC Berkeley (logic.berkeley.edu). The conference is partly occasioned by the fact that the Group in Logic turns sixty this year.

In 1957, a group of faculty members, most of them from the departments of Mathematics and Philosophy, initiated a pioneering interdisciplinary graduate program leading to the degree of Ph.D. in Logic and the Methodology of Science. The Group has fostered interdisciplinary work in which logic has interacted with mathematics, philosophy, statistics, computer science, linguistics, physics and other disciplines.

While mathematical logic at UC Berkeley cannot be identified only with the Group in Logic, the Group has played a vital role in Berkeley’s worldwide prominence in mathematical logic and significantly contributed to making Berkeley a mecca since the fifties for people interested in mathematical logic and its applications. A full list of all those researchers in logic who taught at UC Berkeley, or studied at UC Berkeley, or visited Berkeley for shorter or longer periods would result in a who’s who of mathematical logic.

While marking an important moment for logic at UC Berkeley, the conference will be forward looking rather than merely celebratory. We have invited eight internationally prominent scholars to talk about the future of mathematical logic in their respective areas of specialization.

The first day of the conference will have four invited speakers in the so-called “foundational” areas: set theory, model theory, recursion theory, and proof theory. The second day will have four invited speakers in areas where mathematical logic plays a prominent role, namely philosophy of logic and mathematics, formal semantics for natural languages, modal logic, and logic in computer science. The line up is given below.

For a map showing the conference lecture rooms, see the red arrows here.

May 5 (141 McCone Hall 9AM-2PM; 3 LeConte Hall 2-5PM)

introductory remarks (9-9:30am): Paolo Mancosu (UC Berkeley), “A brief history of the Group in Logic and the Methodology of Science” (slides)

set theory (9:30-10:45am): John Steel (UC Berkeley), “Absolutely ordinal definable sets” (slides)

model theory (11am-12:15pm): Ehud Hrushovski (Hebrew University, Oxford University), “Reflections on model theory and foundations

recursion theory (2:15-3:30pm): Denis Hirschfeldt (University of Chicago), “Computability Theory” (slides)

proof theory (3:45-5:00pm): Michael Rathjen (Leeds University), “On relating type theories to (intuitionistic) set theories” (slides)

May 6 (105 North Gate Hall)

philosophy of logic and mathematics (9:30-10:45am): Jeremy Avigad (Carnegie Mellon University), “Modularity of Mathematics” (slides)

formal semantics for natural languages (11am-12:15pm): Barbara Partee (University of Massachusetts at Amherst), “The Intertwining Influences of Logic, Philosophy, and Linguistics in the Development of Formal Semantics and Pragmatics” (slides)

modal logic (2:15-3:30pm): Johan van Benthem (University of Amsterdam, Stanford University, Tsinghua University), “Modal logic, on the cusp of philosophy and mathematics” (handout)

logic in computer science (3:45-5:00pm): Ronald Fagin (IBM Almaden Research Center), “Applying logic to practice in computer science” (slides)