# Logic Colloquium 2016

#### LC 2016

Schedule

Plenary and Tutorial talks are 50 min + 10 min of questions
Special Session talks are 40 min + 5 min of questions
Contributed talks are 20 min + 5 min of questions

 Monday 1st August 9.00 - 9.15 Opening 9.15 - 10.15 Plenary (BLC Lecture): Laurent Bienvenu, Randomized algorithms in computability theory [Slides] Laurent Bienvenu, Randomized algorithms in computability theory Are randomized algorithms more powerful than deterministic ones? This is perhaps one of the most important general questions in computational complexity, the problem P ?= BPP perhaps being the best known instance of it. In computability theory, this question is typically less considered because of a theorem of De Leeuw et al., which states that if a given sequence/language can be probabilistically computed, it can in fact be deterministically computed. However the problem remains interesting if one consider classes of objects: there are some classes $\mathcal{C}$ containing no computable element but for which there is a probabilistic algorithm which produces an element of $\mathcal{C}$ with positive probability. We will discuss some some positive and negative examples and will explain how to get a quantitative analysis of such classes using Kolmogorov complexity, with numerous applications to algorithmic randomness. Finally, we will see how the theorem of De Leeuw et al. can be turned around to get the existence of computable objects from probabilistic algorithms. References [1] Kelty Allen, Laurent Bienvenu and Theodore Slaman, On zeros of Martin-Löf random Brownian motion, Journal of Logic and Analysis, vol. 6 (2014). [2] Laurent Bienvenu and Ludovic Patey, Diagonally Non-Computable Functions and Fireworks, Available at http://arxiv.org/abs/1411.6846. [3] Laurent Bienvenu and Christopher Porter, Deep $\Pi^0_1$ Classes, Bulletin of Symbolic Logic, to appear. Available at http://arxiv.org/abs/1403.0450. [4] Samuel Epstein and Leonid A. Levin, Sets have simple members, Available at http://arxiv.org/abs/1107.1458. [5] Steven M. Kautz, Degrees of Random Sets, Ph.D. dissertation, Cornell University, 1991. [6] Andrei Rumyantsev and Alexander Shen, Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma, Fundamenta Informaticae, vol. 132 (2014), no. 1, pp. 1–14. Available at http://arxiv.org/abs/1305.1535. [Close] 10.15 - 10.45 Coffee break 10.45 - 11.45 Tutorial A: Thierry Coquand, Univalent Type Theory [Slides] Thierry Coquand, Univalent Type Theory This tutorial will be an introduction to dependent type theory, and to the univalence axiom (V. Voevodsky, 2010). Simple type theory, as formulated by A. Church (1940), constitutes an elegant alternative of set theory for representing formally mathematics. The stratification of mathematical objects in a type of propositions, a type of individuals and a type of functions between two types is indeed quite natural. The axiom of extensionality (the first axiom of set theory) comes in two forms: the fact that two equivalent propositions are equal, and the fact that two pointwise equal functions are equal. Simple type theory as a formal system has however some unnatural limitations, in that we cannot express the notion of an arbitrary structure, for instance the type of an arbitrary group. Dependent type theory solves this issue by introducing in type theory the notion of universe. What was missing until the work of V. Voevodsky was a formulation of the extensionality axiom for universe. This is the univalence axiom, which generalizes propositional extensionality. When introducing universes, we also can use the principle of propositions-as-types and proofs-as-programs, so that the logical operations themselves, and their proofs, can be represented as type theoretic operations. The lectures will roughly proceed as follows. The first lecture will be an introduction to simple type theory and dependent type theory, where we shall try to point out the connections and differences with set theory and end with a formulation of the univalence axiom. The second lecture will explore some consequences of this axiom, such as a proof of a strong form of the axiom of "unique choice", from which we can derive results that would require the full axiom of choice in set theory. We will end with a presentation of a model of the univalence axiom. [Close] 11.45 - 12.45 Plenary: Itay Kaplan, Developments in unstable theories focusing on NIP and NTP$_2$ [Slides] Itay Kaplan, Developments in unstable theories focusing on NIP and NTP$_2$ For many years after Morley's celebrated categoricity theorem [2], and Shelah's discovery [4] of stable theories, abstract model theory was stability theory: the study of stable theories and related subclasses (totally transcendental, strongly minimal, etc.). However, since the (re)discovery of simple theories [1, 6], and of $o$-minimal theories [3], there has been much research going into these classes. In recent years there was much focus in NIP and NTP$_2$ theories. NIP theories (introduced by Shelah in [5]) generalize both $o$-minimal and stable theories and NTP$_2$ theories (defined in [7]) generalize both NIP and simple theories. In this talk I will review some of the progress done in recent years in the study of NIP and NTP$_2$. The talk will be aimed at a wide audience. References [1] Byunghan Kim. Simple first order theories. PhD thesis, University of Notre Dame, 1996. [2] Michael Morley. Categoricity in power. Transaction of the American Mathematical Society, 114:514–538, 1965. [3] Anand Pillay and Charles Steinhorn. Definable sets in ordered structures. I. Trans. Amer. Math. Soc., 295(2):565–592, 1986. [4] Saharon Shelah. Stable theories. Israel J. Math., 7:187–202, 1969. [5] ―. Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory. Ann. Math. Logic, 3(3):271–362, 1971. [6] ―. Simple unstable theories. Ann. Math. Logic, 19(3):177–203, 1980. [7] ―. Classification theory and the number of nonisomorphic models, volume 92 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, second edition, 1990. [Close] 12.45 - 14.15 Lunch break Special Sessions (titles: see below) Homogeneous structures (G.02) Set Theory (G.31) Proof theory and reverse mathematics (1.33) 14.15 - 15.00 Ross Willard Ross Willard, The decidable discriminator variety problem This talk is an advertisement for an old, unsolved problem in which universal algebra meets homogeneous structures. An equational class is any class in an algebraic signature (i.e., constants and function symbols only) which is axiomatized by universally quantified equations. Such a class is locally finite if every finitely generated substructure of a member is finite. The problem in question is that of describing all locally finite equational classes with finite signature whose first-order theory is decidable. The work of Burris, McKenzie and Valeriote [1, 3] in the 1980s reduced this problem to two special kinds of equational classes: For a given finite ring $R$, the class ${}_R\mathcal M$ of all $R$-modules. Locally finite "discriminator varieties" in a finite signature. What are discriminator varieties? They are equational classes $\mathcal E$ which resemble the class of Boolean algebras in certain ways. In particular, (i) the class $\mathcal S$ of simple algebras in $\mathcal E$ is $\forall_1$-axiomatizable, and (ii) each algebra in $\mathcal E$ has a Stone-like representation via a sheaf over $\mathcal S$. In practice [4, 2], the question of whether a locally finite discriminator variety $\mathcal E$ has a decidable first-order theory hinges on how well-structured are the members of $\mathcal S$, and in particular on the degree to which the countable members of $\mathcal S$ fail to be homogeneous. In this talk I will make this precise and explain the current state of the problem. References [1] Stanley Burris and Ralph McKenzie, Decidability and Boolean representations, Memoirs of the American Mathematical Society, vol. 32 (1981), no. 246. [2] Dejan Delić, Decidable discriminator varieties arising from dihedral varieties of groups, Journal of Pure and Applied Algebra, vol. 198 (2005), no. 1–3, pp. 75–92. [3] Ralph McKenzie and Matthew Valeriote, The Structure of Decidable Locally Finite Varieties, Progress in Mathematics, Birkhäuser, Boston, 1989. [4] Ross Willard, Decidable discriminator varieties from unary classes, Transactions of the American Mathematical Society, vol. 336 (1993), no. 1, 311-333. [Close] David Schrittesser David Schrittesser, Definable discrete sets, forcing, and Ramsey theory Let $\mathcal R$ be a family of finitary relations on a set $X$. A set $A\subseteq X$ is called $\mathcal R$-discrete if no relation $R \in \mathcal R$ relates any elements of $A$; $A$ is called maximal discrete if it is maximal with respect to subset-inclusion among $\mathcal R$-discrete subsets of $X$. For any family of relations $\mathcal R$, maximal $\mathcal R$-discrete sets exist by the axiom of choice; whether such sets can be definable is contentious. Maximal discrete sets have been widely studied: instances are maximal co-finitary groups, maximal almost disjoint families, and maximal orthogonal families of measures. In many (but not all) cases one can show such objects cannot be analytic (i.e. projections of closed sets). On the contrary, certain definable (in fact, co-analytic) maximal discrete sets have been shown to exist under the assumption that every set is constructible. We present some new results, exhibiting definable maximal discrete sets in forcing extensions, e.g. extensions where the continuum hypothesis fails. In most cases, these results rely on Ramsey theoretic considerations. [Close] Sam Sanders Sam Sanders, The unreasonable effectiveness of Nonstandard Analysis As suggested by the title, we will uncover the vast computational content of classical Nonstandard Analysis. To this end, we formulate a template $\mathfrak{CI}$ which converts a theorem of pure' Nonstandard Analysis, i.e. formulated solely with the nonstandard definitions (of continuity, integration, differentiability, convergence, compactness, et cetera), into the associated effective theorem. The latter constitutes a theorem of computable mathematics no longer involving Nonstandard Analysis. The template often produces theorems of Bishop's Constructive Analysis ([1]). \medskip To establish the vast scope of $\mathfrak{CI}$, we apply this template to representative theorems from the Big Five categories from Reverse Mathematics ([3, 5]). The latter foundational program provides a classification of the majority of theorems from ordinary', that is non-set theoretical, mathematics into the aforementioned five categories. The Reverse Mathematics zoo ([2]) gathers exceptions to this classification, and is studied in [4] using $\mathfrak{CI}$. Hence, the template $\mathfrak{CI}$ is seen to apply to essentially all of ordinary mathematics, thanks to the Big Five classification (and associated zoo) from Reverse Mathematics. Finally, we establish that certain highly constructive' theorems, called Herbrandisations, imply the original theorem of Nonstandard Analysis from which they were obtained via $\mathfrak{CI}$. Acknowledgement. This research is generously sponsored by the John Templeton Foundation and the Alexander Von Humboldt Foundation. References [1] E. Bishop, D. Bridgess Constructive analysis, Grundlehren der Mathematischen Wissenschaften, vol. 279, Springer, 1985, xii+477 [2] D. Dzhafarov, The Reverse Mathematics zoo, {http://rmzoo.uconn.edu/} [3] U. Kohlenbach, Higher-order Reverse Mathematics, Lect. Notes Log., Reverse Mathematics 2001, vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 281-295 [4] S. Sanders, The refining of the taming of the Reverse Mathematics zoo, to appear in Notre Dame Journal for formal logic, 2016 [5] S. Simpson, Subsystems of Second-order Arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge, 2009 [Close] 15.00 - 15.45 Josh Wiscons Josh Wiscons, The status of Cherlin's conjecture for primitive structures of relational complexity 2 The relational complexity of a structure $\mathbf{X}$ is the least $k<\omega$ for which the orbits of $\operatorname{Aut}(\mathbf{X})$ on $X^k$ "determine" the orbits of $\operatorname{Aut}(\mathbf{X})$ on $X^n$ for all $n<\omega$. This invariant originated in Lachlan's classification theory for homogeneous finite –and more generally, countable stable– relational structures, but not much was known about the complexities of specific structures until de work of Cherlin, Martin and Saracino in the 1990's. In this talk, I will present some background on relational complexity and discuss recent work on Cherlin's conjecture regarding the classification of the finite primitive structures of complexity 2. [Close] Anush Tserunyan Anush Tserunyan, Integer cost and ergodic actions A countable Borel equivalence relation $E$ on a probability space can always be generated in two ways: as the orbit equivalence relation of a Borel action of a countable group and as the connectedness relation of a locally countable Borel graph, called a graphing of $E$. Assuming that $E$ is measure-preserving, graphings provide a numerical invariant called cost, whose theory has been largely developed and used by Gaboriau and others in establishing rigidity results. A well-known theorem of Hjorth states that when $E$ is ergodic, treeable (admits an acyclic graphing), and has integer cost $n \ge 1$, then it is generated by an a.e. free measure-preserving action of the free group $\mathbf{F}_n$ on $n$ generators. We give a simpler proof of this theorem and the technique of our proof, combined with a recent theorem of Tucker-Drob, yields a strengthening of Hjorth's theorem: the action of $\mathbf{F}_n$ can be arranged so that each of the $n$ generators acts ergodically. [Close] David R. Belanger David R. Belanger, A computable perfect-set theorem We gauge the difficulty of finding a perfect subtree in a tree of a given Cantor-Bendixson rank. To simplify the analysis we introduce half-derivative, and extend the definition of rank to include values of the form $n$-and-a-half; each increase of one-half in the rank corresponds to one added jump in the perfect-subtree problem. [Close] 15.45 - 16.15 Coffee break 16.15 - 17.30 Contributed talks (see below) 18.00 - 20.00 Reception (Parkinson Court)