LOGIC FACING OUTWARDS

LOGIC FACING OUTWARDS

Special session at the 2020 Joint Mathematics Meetings, Denver, CO, USA

Co-organized by Karen Lange & Russell Miller


Description

This session is aimed at a general mathematical audience. We intend to introduce various specific applications of mathematical logic in areas including algebraic differential equations, combinatorics, dynamical systems, geometry, number theory, probability, and real analysis. These talks will not assume any substantial background in logic, but will reveal many ways in which principles and techniques from logic can be brought to bear on problems from all over mathematics.

After the AMS-MAA Invited Address by Karen Lange on January 15, the special session will begin the same afternoon and continue through the morning of January 16. Each of the eight special-session talks will last forty minutes, with time for questions and discussion afterwards.



AMS-MAA Invited Address

Different Problems, Common Threads: Computing the Difficulty of Mathematical Problems
Karen Lange, Wellesley College
Wednesday, January 15 11:10 am - 12:00, Four Seasons Ballroom 2, 3, 4, Lower Level, Colorado Convention Center.

Abstract: Mathematics is filled with existence theorems such as "every vector space has a basis." Such statements do not address how one goes about finding the known-to-exist object. The prior theorem naturally leads to the question "given a vector space, can we compute a basis for it?" The answer to this "Basis Problem" is no, so we say that the problem is not "computable."

We can further ask just how far from computable the Basis Problem is and what other problems have the same computational power. A natural way to compare the algorithmic difficulty of two problems is to determine whether having the ability to solve one allows for the solution of the other. Under this problem-reduction approach, two problems have the same computational power if each can be used to solve the other.

In this talk, we will explore the key ideas behind taking a "computable" perspective on mathematics and how this compares to an "existence" one. We will illustrate the problem-reduction approach using theorems from across mathematics. The overall structure of problem-difficulty is extremely rich and helps to illuminate what makes problems "tick." Moreover, this approach has strong connections to calibrating exactly which axioms are needed to prove the original existence theorems. pdf download


Algebra & Number Theory

The Model Theory of Differential Closures
David Marker, University of Illinois at Chicago
Wednesday, January 15 2:15 - 2:55 pm, Room 404, Colorado Convention Center.

Abstract: Differentially closed fields play a role in differential algebra and differential algebraic geometry analogous to the role played by algebraically closed fields in algebraic geometry. Interestingly, the existence and uniqueness of differential closures was first proved using model theoretic techniques and, while these proofs have been given algebraic translations they do not avoid the issues of the general model theoretic results. Differential closures also exhibit interesting phenomena not found in the classical case. I will survey these results. pdf download

What is the Difference Between Sets of Primes?
Alexandra Shlapentokh, East Carolina University
Wednesday, January 15 3:15 - 3:55 pm, Room 404, Colorado Convention Center.

Abstract: We will consider the following question: what are the interesting properties of infinite sets of primes, and what determines whether an infinite set of primes has a particular property? We will start with an obvious fact that each set of primes is Turing equivalent to a set of positive integers, and therefore sets of primes inherit the Turing degree structure of N. We will next note that each set of primes also corresponds to a subring of Q and is also Turing equivalent to the set of elements of the ring. Now these rings possess different arithmetic and logical properties that we can now attach to the sets of primes. Some of the questions we will discuss is whether two sets of primes differing by a finite number of elements always have the same properties, and whether some logic properties of the sets of primes are equivalent to some arithmetic properties of these sets. pdf download


Analysis & Geometry

Passing Hilbert's Final Test
Jack Lutz, Iowa State University
Wednesday, January 15 5:15 - 5:55 pm, Room 404, Colorado Convention Center.

Abstract: We review recent developments in which computability-theoretic dimensions of individual points have been used to answer open questions in classical geometric measure theory, questions whose statements do not involve computability theory or logic. pdf download

A Constructive Solution to Tarski's Circle Squaring Problem
Andrew Marks, University of California at Los Angeles
Wednesday, January 15 4:15 - 4:55 pm, Room 404, Colorado Convention Center.

Abstract: In 1925, Tarski posed the problem of whether a disc in R2 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 R3, it can be shown that two Lebesgue measurable sets in R2 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 complexity 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. pdf download

Lusin's Theorem: How Computability Theory Proves a Real-Analysis Result
Russell Miller, Queens College & CUNY Graduate Center
Thursday, January 16 8:00 - 8:40 am, Room 404, Colorado Convention Center.

Abstract: Lusin's Theorem, from real analysis, states that for every Borel-measurable function f from R to R, and for every ε > 0, there exists a continuous function g on R such that { x ∈ R : f(x) ≠ g(x) } has measure < ε. This result appears in most introductory real analysis courses, and is often viewed as one of Littlewood's Three Principles. Here we will give a proof of Lusin's Theorem using computability theory and computable analysis. In addition to the theorem itself, the proof will establish an effective way of producing g from f and ε, and will pick out, for each f, the specific measure-0 set of troublemakers x ∈ R that create all the discontinuities.

This talk will not assume any background in logic or computability theory. It will introduce a few standard computability results, bearing no obvious connection to real analysis, and by the end it will show how those results are precisely enough to establish Lusin's Theorem. pdf download


Dynamical Systems, Combinatorics & Probability

Logic and Combinatorics
Natasha Dobrinen, University of Denver
Thursday, January 16 10:00 - 10:40 am, Room 404, Colorado Convention Center.

Abstract: Combinatorics is a vast subject with connections to many areas of mathematics. Important problems in general mathematics often turn out to have combinatorial content as the core problem. Ramsey's Theorem was actually motivated by a problem in logic posed by Hilbert: Is there a way to decide exactly when a logic formula is valid? Currently, there are multiple facets of logic informing and providing methods for solving problems in combinatorics. Conversely, problems in logic are leading to progress in combinatorics. We will sample some highlights of the beautiful historical and modern interactions between Ramsey theory and logic, how progress in each field has motivated and helped solve problems in the other, as well as in other areas of mathematics. pdf download

Exchangeable Constructions via Model Theory
Rehana Patel, African Institute for Mathematical Sciences - Senegal
Thursday, January 16 9:00 - 9:40 am, Room 404, Colorado Convention Center.

Abstract: The Erdos-Renyi "coin flip" construction of the countable infinite random graph is exchangeable, in the sense that the resulting distribution does not depend on the order in which edges are decided. In a 2016 paper Ackerman, Freer and I characterised those countable infinite structures that have exchangeable constructions. Our method generalises one used by Petrov and Vershik (2010) to produce exchangeable constructions of Henson's homogeneous-universal Kn-free graphs; it involves building a "probabilistic Henkin structure" that, in the case of graphs, is what is known as a graphon. In this talk I will discuss how the model-theoretic perspective enables such a generalisation, providing a broad view of the phenomenon of exchangeability. No prior knowledge of model theory will be assumed, and all definitions will be explained. The talk will also serve as a prelude, for the non-logician, to Freer's plenary talk in the ASL sub-meeting at the JMM, which will look at exchangeability from a computability-theoretic perspective. pdf download

Computation and Universality in Multidimensional Symbolic Dynamics
Linda Brown Westrick, Pennsylvania State University
Thursday, January 16 11:00 - 11:40 am, Room 404, Colorado Convention Center.

Abstract: In symbolic dynamics, the simplest systems to describe are the shifts of finite type (SFTs). However, a simple description does not guarantee simple behavior. It is well-known (but not currently well-exploited) that arbitrary computations can be embedded into the dynamics of Z2-SFTs. As a result, these "simple" shifts often have behavior just as rich as unrestricted topological dynamical systems. We present a recent example of this phenomenon: the property of topological completely positive entropy is no simpler in Z2-SFTs than in general topological dynamical systems. pdf download


Schedule:

Invited Address: Different Problems, Common Threads: Computing the Difficulty of Mathematical Problems, by Karen Lange.
Wednesday, Jan. 15, 11:10 am - 12:00, Four Seasons Ballroom 2, 3, 4, Lower Level, Colorado Convention Center.

Special Session I: Wednesday Jan. 15, 2020, 2:15-6:00 pm, Room 404, Colorado Convention Center.
2:15-2:55pm: David Marker, The Model Theory of Differential Closures.
3:15-3:55pm: Alexandra Shlapentokh, What is the Difference Between Sets of Primes?.
4:15-4:55pm: Andrew Marks, A Constructive Solution to Tarski's Circle Squaring Problem.
5:15-5:55pm: Jack H. Lutz, Passing Hilbert's Final Test.

Special Session II: Thursday Jan. 16, 2020, 8:00 am-12:00, Room 404, Colorado Convention Center.
8:00-8:40am: Russell Miller, Lusin's Theorem: How Computability Theory Proves a Real-Analysis Result.
9:00-9:40am: Rehana Patel, Exchangeable Constructions via Model Theory.
10:00-10:40am: Natasha Dobrinen, Logic and Combinatorics.
11:00-11:40am: Linda Brown Westrick, Computation and Universality in Multidimensional Symbolic Dynamics.