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 2 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 3, it can be shown that two Lebesgue measurable sets in 2 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.