Events 2017-2018

Logic Colloquium

August 25, 2017, 4:10 PM (60 Evans Hall)

Andrew Marks
U.C. Los Angeles

A constructive solution to Tarski’s circle squaring problem

In 1925, Tarski posed the problem of whether a disc in ℝ² can be partitioned into finitely many pieces which can be rearranged by isometries to form a square of the same area. Unlike the Banach-Tarski paradox in ℝ³, it can be shown that two Lebesgue measurable sets in ℝ² cannot be equidecomposed by isometries unless they have the same measure. Hence, the disk and square must necessarily be of the same area.

In 1990, Laczkovich showed that Tarski’s circle squaring problem has a positive answer using the axiom of choice. We give a completely constructive solution to the problem and describe an explicit (Borel) way to equidecompose a circle and a square. This answers a question of Wagon.

Our proof has three main ingredients. The first is work of Laczkovich in Diophantine approximation. The second is recent progress in a research program in descriptive set theory to understand how the complexity of a countable group is related to the Borel cardinality of the equivalence relations generated by its Borel actions. The third ingredient is ideas coming from the study of flows in networks.

This is joint work with Spencer Unger.

Logic Colloquium

September 08, 2017, 4:10 PM (60 Evans Hall)

Cameron Freer
Founder, Borelian Corporation and Chief Scientist, Remine LLC

Model theory of invariant probabilistic constructions

There is a long history of studying the logic obtained by assigning probabilities, instead of truth values, to first-order formulas. In a 1964 paper, Gaifman studied probability distributions on countable structures that are invariant under renaming of the underlying set – which he called “symmetric measure-models”, and which are essentially equivalent to what today are known as S_∞-invariant measures. In this paper, he asked the question of which first-order theories admit invariant measures concentrated on the models of the theory.

We answer this question of Gaifman, a key first step towards understanding the model theory of these measures, which can be thought of as “probabilistic structures”. In this talk, we will also discuss related questions, such as how many probabilistic structures are models of a given theory, and when probabilistic structures are almost surely isomorphic to a single classical model.

Joint work with Nathanael Ackerman and Rehana Patel.

Logic Colloquium

September 22, 2017, 4:10 PM (60 Evans Hall)

Nadja Hempel
Assistant Adjunct Professor of Mathematics, UCLA

Mekler construction in generalized stability

Given a so called nice graph (no triangles, no squares, for any choice of two distinct vertices there is a third vertex which is connected to one and not the other), Mekler considered the 2-nilpotent subgroup generated by the vertices of the graph in which two elements given by vertices commute if and only if there is an edge between them. These groups form an interesting collection of examples from a model theoretic point of view. It was shown that such a group is stable if and only if the corresponding graph is stable and Baudisch generalized this fact to the simple theory context. In a joint work with Chernikov, we were able to verify this result for k-dependent and NTP₂ theories. This leads to the existence of groups which are (k+1)-dependent but not k-dependent, providing the first algebraic objects witnessing the strictness of these hierarchy.

Logic Colloquium

October 06, 2017, 4:10 PM (60 Evans Hall)

Yann Pequignot
Postdoctoral Fellow, Department of Mathematics, UCLA

Finite versus infinite: an insufficient shift

Analytic sets enjoy a classical representation theorem based on well-founded relations. I will explain a similar representation theorem for Sigma^1_2 sets due to Marcone which is based on an intriguing topological graph: the Shift Graph. The chromatic number of this graph is 2, but its Borel chromatic number is infinite. We use this representation theorem to show that the Shift Graph is not minimal among the graphs of Borel functions which have infinite Borel chromatic number. While this answers negatively the primary outstanding question from (Kechris, Solecki and Todorcevic; 1999), our proof unfortunately does not construct any explicit example of a Borel function whose graph has infinite Borel chromatic number and admits no homomorphism from the Shift Graph.

Logic Colloquium

October 20, 2017, 4:10 PM (60 Evans Hall)

Thomas Icard
Assistant Professor of Philosophy, Stanford University

Some Philosophical Uses of Randomized Computation

The aim of this talk will be to convey some of the ways that familiar ideas and tools from randomized and probabilistic computation might bear on issues of philosophical interest, focusing especially on questions about cognition, representation, and reasoning. A first question is when it would ever make sense for an agent to employ randomization in the course of decision making. Drawing on ideas from game theory, reinforcement learning, and statistics, we tentatively propose a unified answer to the question. A second set of questions revolves around the idea of characterizing an agent’s implicit causal knowledge of the world by appeal to the explicit causal structure of a probabilistic algorithm. This second topic raises novel questions about the logic of counterfactuals beyond the usual propositional setting. Much of this is work in progress.

Logic Colloquium

November 03, 2017, 4:10 PM (60 Evans Hall)

Lenore Blum
Distinguished Career Professor of Computer Science, Carnegie Mellon University

Alan Turing and the Other Theory of Computation

Most logicians and theoretical computer scientists are familiar with Alan Turing’s 1936 seminal paper setting the stage for the foundational (discrete) theory of computation. Most however remain unaware of Turing’s 1948 seminal paper introducing the notion of condition, setting the stage for a natural theory of complexity for what I call the “other theory of computation” emanating from the classical tradition of numerical analysis, equation solving and the continuous mathematics of calculus. This talk will recognize Alan Turing’s work in the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), how it provides a unifying concept for the two major traditions of the Theory of Computation, and its influence on complexity theory today.

Logic Colloquium

November 17, 2017, 4:10 PM (60 Evans Hall)

Wesley H. Holliday
Associate Professor of Philosophy, UC Berkeley

Possibilities for Boolean, Heyting, and modal algebras

In this talk, we describe an alternative to the standard representation theory for Boolean, Heyting, and modal algebras descending from Stone (1934, 1937) and Jónsson and Tarski (1951). While the standard theory leads to the well-known “possible world semantics” in logic, the alternative theory forms the basis of the recently investigated “possibility semantics” in logic. We will give an overview of this line of research, making connections to longstanding open problems and highlighting the contributions of University of California students.

The talk will be based on the following papers:

W. H. Holliday, “Possibility Frames and Forcing for Modal Logic,” 2015.

G. Bezhanishvili and W. H. Holliday, “Locales, Nuclei, and Dragalin Frames,” 2016.

G. Bezhanishvili and W. H. Holliday, “A Semantic Hierarchy for Intuitionistic Logic,” 2017.

N. Bezhanishvili and W. H. Holliday, “Choice-Free Stone Duality,” 2017.

Logic Colloquium

December 01, 2017, 4:10 PM (60 Evans Hall)

Marianna Antonutti
Marie Skłodowska-Curie Postdoctoral Fellow, Munich Center for Mathematical Philosophy

What is ordinary mathematics?

The term “ordinary mathematics” is used to denote a collection of areas that are, in some sense, central to the practice of most working mathematicians, typically taken to contain such fields as number theory, real and complex analysis, geometry, and algebra. This notion has been taken for granted by both philosophers and logicians; for example, reverse mathematics is often described as the study of what set existence axioms are necessary to prove theorems of ordinary mathematics, and the ability to recover ordinary mathematics has been considered a key measure of the success of a foundational framework at least since Russell. However, the precise extent of this notion has not been explicitly discussed. This talk will propose two ways in which this notion can be made more precise. According to the first, ordinary mathematics is that part of mathematics that concerns countable or countably representable objects. According to the second, ordinary mathematics is that part of mathematics that does not make essential use of intrinsically set theoretic methods or concepts. I will discuss potential counterexamples to both views, and assess the prospects for formulating a precise account of the notion of ordinary mathematics.

This is joint work with Benedict Eastaugh.

Logic Colloquium

January 26, 2018, 4:10 PM (60 Evans Hall)

John MacFarlane
Professor of Philosophy, University of California, Berkeley

Is Logic a Normative Discipline?

Various philosophers, including Kant, Frege, and more recently Hartry Field and Greg Restall, have held that logic is in some interesting sense a normative discipline. Field, in particular, has argued that we need a normative characterization of logical validity in order to understand what proponents of alternative logics are disagreeing about. I will discuss what one needs to say in order to sustain an interesting version of this claim, and I will consider whether Field gives good reasons for accepting it.

Logic Colloquium

February 09, 2018, 4:10 PM (60 Evans Hall)

Michael Beeson
Professor Emeritus, San Jose State University

Proof-checking Euclid

We used computer proof-checking methods to verify the correctness of our proofs of the propositions in Euclid Book I. We used axioms as close as possible to those of Euclid, in a language closely related to that used in Tarski’s formal geometry. We used proofs as close as possible to those given by Euclid, but filling Euclid’s gaps and correcting errors. Then we checked those proofs in the well-known and trusted proof checkers HOL Light and Coq. The talk will contain many geometrical diagrams and discuss both the geometry and the proof-checking. (This is joint work with Julien Narboux and Freek Wiedijk.)

Logic Colloquium

February 23, 2018, 4:10 PM (60 Evans Hall)

Douglas Marshall
Assistant Professor of Philosophy, Carleton College

An Approach to Two Puzzles Concerning the Applicability of Mathematics

In its applications to empirical science, mathematics allows us to represent and reason about the physical world. A similar phenomenon occurs internally to mathematics when one branch of mathematics allows us to represent and reason about the subject matter of another. I argue that taking seriously the close analogies between these two kinds of case will help us resolve two philosophical puzzles concerning the applicability of mathematics: 1. If (as some platonists contend) mathematics studies abstract objects, but the empirical sciences study concrete objects, then how is mathematics relevant to the empirical sciences? 2. How can one branch of mathematics be applied to another if (as some empiricists contend) mathematics has no factual content?