August 25, 2017, 4:10 PM (60 Evans Hall)
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.
September 08, 2017, 4:10 PM (60 Evans Hall)
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.