Réunion d'hiver SMC 2019

Toronto, 6 - 9 décembre 2019

Logique
Org: Bradd Hart (McMaster) et Rahim Moosa (Waterloo)
[PDF]

TABOKA PRINCE CHALEBGWA, Fields
Algebraic values of certain transcendental functions  [PDF]

The Bombieri-Pila theorem predicts a bound of the form $c(f,\epsilon)H^\epsilon$ for the number of rational points of height at most $H$ on the graph of a (real analytic) transcendental function $f$ restricted to a compact interval. Although this bound is sharp in general, for certain special cases (such as those arising under additional hypotheses on $f$) it can be improved to a poly-logarithmic bound in $H$ (that is, $C(\log H)^\eta$). After briefly pointing out the connections with logic, I shall give a survey of some of our recent results in this direction.

GREG COUSINS, McMaster University
Some model theory of large fields  [PDF]

Large fields tend to make up most of the "nice" fields which model theorists have come to love: algebraically closed, real closed, PAC, and p-adically closed fields are all large. In this talk, we aim to describe some work on the model theory of large fields under the assumption that they have small absolute galois group and enjoy a strong "algebraic" version of model completeness called "almost quantifier elimination".

ILIJAS FARAH, York University
Reduced powers as ultrapowers  [PDF]

The following result was inspired by a question that naturally arose in the Elliott classification program of C*-algebras, but C*-algebras will not be mentioned explicitly in the talk. Given a countable (or separable) first-order language L, there is a functor $K$ from the category of countable (separable) L-structures into itself such that the reduced power $B^\infty$ of $B$ associated with the Fréchet filter is isomorphic to the ultrapower $KB^U$ of $KB$ assocaited to a nonprincipal ultrafilter on $\mathbb N$ (the Continuum Hypothesis is assumed for simplicity). The ultrafilter $U$ can be chosen so that the exact sequence associated to the quotient map from $B^\infty$ onto $B^U$, $0\to c_U(B)\to B^\infty\to B^U\to 0,$ splits. Although these conclusions can fail in some models of ZFC in which the Continuum Hypothesis fails, they have ZFC analogs that suffice for all applications.

CHRIS KAPULKIN, University of Western Ontario
Internal languages of higher categories  [PDF]

Homotopy type theory is often described as the internal language of $\infty$-toposes in very much the same way as higher order (intuitionistic) logic is the internal language of elementary (1-)toposes. I will explain how one can make this conjecture precise, report on the progress towards proving it, and describe some of its surprising consequences, including the proof of Voevodsky's Homotopy Canonicity Conjecture.

MARCIN SABOK, McGill University
Measurable Hall's theorem for actions of abelian groups  [PDF]

I will discuss a measurable version of the Hall marriage theorem for actions of abelian groups. In particular, it implies that for free measure-preserving actions of such groups, if two equidistributed measurable sets are equidecomposable, then they are equidecomposable using measurable pieces. The latter generalizes a recent result of Grabowski, Máthé and Pikhurko on the measurable circle squaring and confirms a special case of a conjecture of Gardner. This is joint work with Tomasz Cieśla.

MARGARET THOMAS, Purdue University
Definable topologies in o-minimal structures  [PDF]

A definable set together with a definable family which forms a basis for a topology is a `definable topological space'. Our focus here is on topologies that are definable in o-minimal structures. We will present some progress towards understanding the nature of these spaces, related in particular to their classification and to the identification of suitable definable analogues of classical notions, such as compactness, in this setting. This is based on work arising from a joint project with Pablo Andújar Guerrero and Erik Walsberg.

ROSS WILLARD, University of Waterloo
Constraint Satisfaction Problem dichotomy update  [PDF]

Given a finite relational structure M in a finite signature L, the Constraint Satisfaction Problem for M, or CSP(M), is the decision problem which, given a primitive positive sentence in the signature of L as input, asks whether the sentence is true in M. Each such problem CSP(M) is clearly in NP. The CSP Dichotomy Conjecture, dating back to work of Feder and Vardi in the 1990s, posits that for each such M, CSP(M) is either in P or is NP-complete.

The Dichotomy Conjecture has (apparently) been proved by Andrei Bulatov and independently by Dmitriy Zhuk; see https://arxiv.org/abs/1703.03021 and https://arxiv.org/abs/1704.01914. In this talk I will briefly describe the (known) connection of such problems to universal algebra, discuss a key component of Zhuk’s proof, and indicate one way in which the proof can be strengthened.