The UCLA Logic Colloquium meets on alternate Fridays,
at 4 p.m., in MS 6221.

The Logic Colloquium Chairs are
Andrew Marks and
Yiannis Moschovakis.

Here are links to the
UCLA Logic Center, the
Caltech-UCLA Logic Seminar, and the
Philosophy Colloquium.

Talks are listed here in ** reverse chronological order. **

Friday Jun 02 2017 | ||||

16:00-16:50 (MS 6627) | Jana Marikova (WIU) | TBA | ||

Abstract. TBA | ||||

Friday May 19 2017 | ||||

16:00-16:50 (MS 6627) | John Steel (UC Berkeley) | TBA | ||

Abstract. TBA | ||||

Friday May 05 2017 | ||||

16:00-16:50 (MS 6627) | Scott Cramer (CSUSB) | TBA | ||

Abstract. TBA |

Friday Mar 03 2017 | ||||

16:00-16:50 (MS 6221) | Isaac Goldbring (UCI) | The model-theoretic content of a result of Junge and Pisier | ||

Abstract. An operator space is a norm closed linear subspace of the Banach space B(H) of bounded linear operators on a Hilbert space. For reasons that will be explained in this talk, operator spaces are the noncommutative analogs of Banach spaces. A fundamental result of Junge and Pisier shows that there are many more operator spaces than there are Banach spaces in a way to be made precise in the talk. I will explain the model-theoretic content of their result. Most of my contributions mentioned in this talk represent joint work with Thomas Sinclair. | ||||

Friday Feb 24 2017 | ||||

16:00-16:50 (MS 6221) | Caroline Terry (University of Maryland, College Park) | VC_n-dimension and a jump in the speed of a hereditary property | ||

Abstract. A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends n to the number of distinct elements in H with underlying set 1,..., n. There are many wonderful results from combinatorics concerning what functions can occur as speeds of hereditary graph properties. These results show there are discrete "jumps" in the possible speeds of hereditary graph properties. In this talk we use VC_n-dimension, a generalization of VC-dimension, to extend one of these results to the setting of arbitrary finite relational languages. In particular, we show that bounded VC_n-dimension characterizes the gap between the fastest and penultimate speeds. | ||||

Friday Feb 10 2017 | ||||

16:00-16:50 (MS 6627) | Jack Lutz (Iowa State University) | Algorithmic Dimensions and Fractal Geometry | ||

Abstract. This talk will review the $\Sigma^0_1$ notions of algorithmic information and dimension and survey very recent applications of these to classical (non-algorithmic) questions in fractal geometry. These applications include N. Lutz and D. Stull's strengthened lower bounds on the dimensions of generalized Furstenberg sets and N. Lutz's extension of the fractal intersection formulas in Euclidean space from Borel sets to arbitrary sets. | ||||

Friday Jan 20 2017 | ||||

16:00-16:50 (MS 6627) | Nam Trang (UCI) | Compactness of $omega_1$. | ||

Abstract. We investigate various aspects of compactness of omega_1 under ZF + DC (the Axiom of Dependent Choice). We say that omega_1 is X-supercompact if there is a normal, fine, countably complete nonprincipal measure on powerset_{omega_1}(X) (in the sense of Solovay). We say omega_1 is X-strongly compact if there is a fine, countably complete nonprincipal measure on powerset_{omega_1}(X). A long-standing open question in set theory asks whether (under ZFC) "supercompactness" can be equiconsistent with "strong compactness. We ask the same question under ZF+DC. More specifically, we discuss whether the theories "omega_1 is X-supercompact" and "omega_1 is X-strongly compact" can be equiconsistent for various X. The global question is still open but we show that the local version of the question is false for various X. We also discuss various results in constructing and analyzing canonical models of AD^+ + omega_1 is X-supercompact. | ||||

Friday Nov 18 2016 | ||||

16:00-16:50 (MS 6627) | Martino Lupini (Caltech) | Borel complexity and C*-dynamics | ||

Abstract. I will present a logician-friendly overview of the classification problem for group actions on C*-algebras from the perspective of Borel complexity theory, including joint works with Gardella, Kerr, and Phillips. | ||||

Friday Nov 04 2016 | ||||

16:00-16:50 (MS 6627) | Nadja Hempel (UCLA) | Finding definable envelopes of subgroups | ||

Abstract. The core question of this talk is: Given a group G and an arbitrary subgroup H which is abelian, nilpotent or solvable, can one find a definable envelope of H, that is a definable subgroup of G containing H with the same or similar algebraic properties. In the past decades there has been remarkable progress on groups fulfilling model theoretic properties as well as on groups satisfying certain chain conditions on centralizers (Mc-groups) which will ensure the existence of definable envelopes. We briefly present the work in stable, simple, and NIP theories as well as Mc-groups. In the end of this talk we generalize these results to groups which merely satisfies the same chain condition on centralizers as groups definable in simple theories as well as NTP2 theories. | ||||

Friday Oct 28 2016 | ||||

16:00-16:50 (MS 6627) | Andre Nies (University of Auckland) | Randomness and K-triviality | ||

Abstract. Let K(x) denote the prefix-free Kolmogorov complexity of a finite bit string x. A string is incompressible (random) if the value of K(x) is at least its length minus a constant. An infinite bit sequence (real) is random in the sense of Martin-Löf (ML) iff each of its initial segments is incompressible (for the same constant). In the first part of the talk we characterise randomness of a real in terms of effective analysis and ergodic theory.
The K-trivial bit sequences are antirandom in the sense that the initial segment complexity in terms of K grows as slowly as possible. Since 2002, many alternative characterisations of this class have been found: properties such as low for ML-randomness, and basis for ML-randomness, which state in one way or the other that the sequence is close to computable. Initially the class looked quite amorphous. More recently, internal structure has been found. Bienvenu, Greenberg, Kucera, N., and Turetsky (JEMS 2016) showed that there is a ``smart" K-trivial set, in the sense that any ML-random computing it must compute all K-trivials. Greenberg, Miller and N. (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches using cost functions. | ||||

Friday Oct 07 2016 | ||||

16:00-16:50 (MS 6627) | Joel Nagloo (Bronx Community College, CUNY) | Model theory and Classical Differential equations | ||

Abstract. The study of differential fields using model theory has a long and rich history. The theory of differentially closed fields of characteristic 0, $DCF_0$, has been studied intensively and has played an important role in the development of geometric stability theory. Furthermore, many new results in number theory and differential Galois theory have been obtained using the model theoretic approach to differential algebra.
Nevertheless, only very recently has the techniques from geometric stability been used to study well-known differential equations. In this talk we highlight some of the contributions of logic, via model theory, to the classification and study of the classical Painlev\'e and Schwarzian equations. | ||||

Friday Jun 03 2016 | ||||

16:00-16:50 (MS 6627) | Slawomir Solecki (University of Illinois at Urbana-Champaign) | Projective Fra{\" i}ss{\' e} limits and homogeneity for tuples of points | ||

Abstract. The pseudoarc is the generic compact, connected, metric space. It can be represented as a canonical
quotient of the pre-pseudoarc, a projective Fra{\" i}ss{\' e} limit. I will present a homogeneity result for tuples of
points in the pre-pseudoarc. The proof of this result uses tools coming from combinatorics and logic. I will deduce
from it the topological homogeneity for tuples of points in the pseudoarc. I will finish with speculations on what
the ultimate homogeneity result for the pseudoarc may be and present results obtained in this direction.
The talk will continue the theme of my last year Logic Colloquium talk, but it will be self-contained. The talk will be based on joint work with Todor Tsankov. | ||||

Friday May 13 2016 | ||||

16:00-16:50 (MS 6627) | Asger Törnquist (University of Copenhagen) | Definable maximal discrete sets in forcing extensions. | ||

Abstract. Let R be a binary relation on a set X. A subset A of X is R-discrete if no two distinct elements of A are R-related.
Discrete sets arise in many context: If R is a graph, a discrete set is often called an independent set; or if R os the relation of having a mutual extension in some partial ordering, then a discrete set would be called an antichain. In this talk I will discuss the existence of maximal discrete sets for an analytic binary relations on a Polish spaces. If V=L we can always obtain a \Delta^1_2 maximal discrete set for a given \Sigma^1_1 relation, but there are easy examples that show that this is not the case if we add a Cohen or random real to L. In this talk, I will show that we _can_ add a Sacks or Miller real to L and there will still be a \Delta^1_2 maximal discrete set for any Sigma^1_1 relation. I will then discuss an application of this theorem to a question concerning the existence of definable sets of orthogonal Borel probability measures. The results discussed in the talk are joint with David Schrittesser. | ||||

Friday Apr 29 2016 | ||||

16:00-16:50 (MS 6627) | Pietro Carolino (UCLA) | Continuous approximate groups | ||

Abstract. Approximate groups are generalizations of groups where one relaxes the
condition of closure under the group operation to hold "an appreciable
fraction of the time" rather than always. Somewhat surprisingly, there
is a rich structure theory for approximate groups, starting in
additive combinatorics in the 50s. In this talk I will define
approximate groups, give some of the intuitions around them, and
describe how ideas from model theory led to a breakthrough in the case
of finite approximate groups. Then I will describe my own work
extending these results to continuous approximate groups, where a
couple new ideas are needed, especially from Lie theory. | ||||

Friday Apr 15 2016 | ||||

16:00-16:50 (MS 6627) | Silvain Rideau (UC Berkeley) | Imaginaries in valued fields with operators | ||

Abstract. The early 2000's saw the description by Haskell, Hrushovksi and Macpherson of the interpretable sets in algebraically closed valued fields as higher dimensional equivalents of balls --- more precisely, they proved elimination of imaginaries in the emph{geometric language}. These same years also saw a growing interest in the model theory of valued fields with operators. Most of the questions that were solved for these structure revolve around quantifier elimination and tameness results. But, in the light of Haskell, Hrushovksi and Macpherson's result, it is also tempting to try to classify interpretable sets in these structures.
In this talk, I will treat two of the most tractable examples: Scanlon's existentially closed valued fields with a contractive derivation and separably closed valued fields of finite imperfection degree. In particular, I will show how the elimination of imaginaries in these structures relates to computing the canonical basis of definable types and how the independence property (or rather its absence) can play a role in controlling those canonical bases. | ||||

Friday Apr 01 2016 | ||||

16:00-16:50 (MS 6627) | Andrés Villaveces (Universidad Nacional de Colombia) | Categoricity, between Model Theory and Set Theory? | ||

Abstract. The Categoricity Conjecture has been central in the development of Model Theory for Non-Elementary Classes. I will describe this role, and partial results and then will focus on the role of "abstract compactness properties" (tameness and type shortness being the most famous) and their connections to large cardinals (recent results of Boney and Unger). Finally, I will explore a couple of new directions stemming from these questions. | ||||

Friday Mar 11 2016 | ||||

16:00-16:50 (MS 6627) | Katrin Tent (University of Münster) | Describing finite groups by short sentences. | ||

Abstract. We say that a class of finite structures for a finite first- order signature is r-compressible for an unbounded function $r \colon \mathbb{N} \rightarrow \mathbb{N}^+$ if each structure G in the class has a first-order description of size at most O(r(|G|)). We show that the class of finite simple groups is log- compressible, and the class of all finite groups is log3 -compressible. The result relies on the classification of finite simple groups, the bi-interpretability of the twisted Ree groups with finite difference fields, the existence of profinite presentations with few relators for finite groups, and group cohomology.
This is joint work with A. Nies. | ||||

Friday Feb 19 2016 | ||||

16:00-16:50 (MS 6627) | Ali Enayat (University of Gothenburg) | Gödel-Bernays class theory: a familiar stranger | ||

Abstract. Most set theorists tend to think of Gödel-Bernays class theory, hereafter GB, as a minor variant of ZF-set theory, perhaps because of the perspicuity of the model-theoretic conservativity proof of GB over ZF. My talk will discuss the following old and new results about GB that seriously challenge this conception:
(1) [Mostowski 1950] The unprovability of the scheme of induction over natural numbers in GB. (2) [Pudlák, 1985] The superexponential speed-up of GB over ZF. (3) [E, 2004] The conservativity of GB + ``the class of ordinals is weakly compact'' over the extension of ZFC obtained by adding the scheme whose instances are statements of the form ``there is an n-reflective n-Mahlo cardinal'', where n ranges over natural numbers in the meta-theory. (4) [E and Hamkins, 2016] The veracity of the statements ``the class of ordinal is not weakly compact" and ``there is a global well-ordering of sets iff the class of ordinals carries a diamond sequence (in the sense of Jensen)" in canonical models of GB, i.e., models of GB whose classes are precisely the parametrically definable subsets of a model of ZFC. | ||||

Friday Jan 29 2016 | ||||

16:00-16:50 (MS 6627) | Benjamin Miller (Kurt Godel Research Center for Mathematical Logic) | Elementary consequences of the open graph dichotomy | ||

Friday Jan 22 2016 | ||||

16:00-16:50 (MS 6627) | Menachem Magidor (Hebrew University of Jerusalem) | Inner models constructed by generalized logics | ||

Abstract. The constructible universe L is built by series of stages where each stage is the set of (first order) definable subsets of the previous stage. L is a very nice inner model, but it misses many canonical objects, like $0^\sharp$.
One possible attempt to define rich class of inner models is by imitating the construction of L but replacing "first order definability" by definability by stronger logics. A classical theorem by Myhill and Scott claims that that if we use second order logic, we get HOD - the class of sets hereditarily ordinal definable. HOD is not very canonical, it depends very much on the universe of Set Theory from which we start. This talk will present some joint work with J. Kennedy and J. Vaananen, in which we study the inner models that are constructed by using logics that are stronger than first order logic, but weaker than full second order logic. One interesting case is the logic of the quantifier $Q x, y \Phi(x, y)$ which means: "The formula $\Phi(x, y)$ defines a linear order which has cofinality $\omega$. The model we get is rather canonical, in the presence of large cardinals, and contains many canonical definable objects. Another interesting case is the case of stationary logic studied by Barwise and Kaufmann and Makkai. | ||||

Friday Jan 08 2016 | ||||

16:00-16:50 (MS 6627) | Boban Velickovic (University of Paris 7) | Towards a structure theory of Maharam algebras | ||

Friday Nov 20 2015 | ||||

16:00-16:50 (MS 6627) | Omer Ben-Neria (UCLA) | The possible structure of the Mitchell Order | ||

Abstract. The Mitchell order is a partial ordering on normal ultrafilters which plays an important role in the theory of inner models. Let U, W be two normal ultrafilters in a transitive model of set theory V, U < W if U appears in the ultrapower of V by W.
How complicated can the Mitchell ordering be? Mitchell proved it is a well-founded poset and its possible structure was previously studied by Mitchell, Baldwin, Cummings, Witzany, Friedman and Magidor. We will discuss the possible structure of the Mitchell order and explain how to construct models with various Mitchell order structures using forcing methods, inner model theory, and some purely combinatorial ideas about a certain families of posets. | ||||

Friday Nov 06 2015 | ||||

16:00-16:50 (MS 6627) | Thomas Scanlon (UC Berkeley) | Towards the limit of Ax-Kochen-Ershov | ||

Abstract. In their celebrated approximate solution of Artin's conjecture on homogeneous forms over the $p$-adic numbers, Ax and Kochen showed that the first-order theory of a henselian valued field of residue characteristic zero is determined by the theories of its residue field and of its value group. Over the years, this principle (also identified by Ershov) has been greatly refined and extended to include much more complicated structures on valued fields (for example, by allowing analytic functions), to permit relative quantifier elimination theorems beyond the original relative completeness theorem, and even to permit a deep structural analysis of the types from the valued field sort in terms of the much simpler types in the residue field and value group.
We shall discuss limits of the Ax-Kochen-Ershov principle in two senses: in the original sense used in the 1960s of considering the situation as $p \to \infty$, but then also how for some natural structures on valued fields, we cannot expect this principle to hold in the form we have come to expect. | ||||

Friday Oct 23 2015 | ||||

16:00-16:50 (MS 6627) | Igor Pak (UCLA) | Complexity and Computability in Enumerative Combinatorics | ||

Abstract. Let {a_n} be a combinatorial sequence counting the number of certain
combinatorial objects, e.g. permutations, trees, graphs, etc. How
easy is it to compute this sequence? Are there sequences that are
hard to compute? More specifically, are the sequences P-recursive and
ADE? (these will be defined in the talk) I will try to answer these
questions and discuss how computability theory naturally arises in
this context. The main result is our recent disproof of the
Noonan-Zeilberger conjecture.
This talk is aimed at a general audience. Joint work with Scott Garrabrant. | ||||

Friday Oct 09 2015 | ||||

16:00-16:50 (MS 6627) | Jean-Yves Beziau (Federal University of Rio de Janeiro) | Lindenbaum Maximalization Theorem | ||

Abstract. Lindenbaum Maximalization Theorem (LMT) is a fundamental theorem of modern logic. It is also known as Lindenbaum lemma, since it is a fundamental step for the proof of the completeness theorem. The abstract version of LMT is equivalent to the axiom of choice, as proved by Dzik. In this talk I will explain the relations between LMT, compactness, the axiom of choice and the completeness theorem. I will also present another version of LMT, known as Lindenbaum-Asser theorem (LAT), which is stronger and more interesting in view of applications to many different systems of logic, in particular those with a weak negation or without negation. | ||||

Friday May 29 2015 | ||||

16:00-16:50 (MS 6627) | Martin Zeman (UC Irvine) | Arranging properties of the nonstationary ideal using the duality theorem | ||

Abstract. One of the commonly used constructions of ideals makes use of canonical extensions of elementary embeddings of the set theoretic universe to generic extensions. The properties of ideals constructed this way are typically studied using the duality theorem, which gives the forcing equivalence between the poset of positive sets on the one side and a quotient of the poset used to form the extension of the embedding on the other side. I will present a variant of the duality theorem that can be used to arrange various properties of interest, for instance presaturation, and explain the approach and ideas behind the method. The method seems to be quite flexible and is expected to have broader applications. This is a joint work with Sean Cox. | ||||

Friday May 22 2015 | ||||

16:00-16:50 (MS 6627) | Slawomir Solecki (University of Illinois) | Partial homogeneity of dual Fraisse limits and homogeneity of the pseudo-arc | ||

Abstract. The pseudo-arc is the generic compact connected subset of the plane (or the Hilbert cube). By a fundamental result of Bing, it is homogeneous as a topological space. By work of Irwin and myself, the pseudo-arc is represented as a quotient of a dual Fraisse limit, which makes it possible to discretize a continuous situation.
In this joint work with Tsankov, we determine the correct partial homogeneity of the dual Fraisse limit associated with the pseudo-arc, which involves combinatorial and basic "dual" model theoretic arguments (e.g., a notion of dual type). Further, we prove a transfer theorem, through which we recover Bing's homogeneity of the pseudo-arc from our partial homogeneity of the dual Fraisse limit. Time permitting, I will make comments on the possible generality of the method. | ||||

Friday May 15 2015 | ||||

16:00-16:50 (MS 6627) | Carol Wood (Wesleyan University) | Examples in the model theory of fields of positive characteristic | ||

Abstract. Fields (including enhanced fields) are a source both of examples and of applications of model theory. We consider here positive characteristic fields, including separably closed fields and differential fields. These examples have served to illustrate certain phenomena in model theory. We will indicate what is currently known, pointing to questions still unanswered in positive characteristic, some due to neglect or lack of interest, and at least one which appears to be difficult. | ||||

Friday May 01 2015 | ||||

16:00-16:50 (MS 6627) | Aleksandra Kwiatkowska (UCLA) | Universal minimal flows, Ramsey theory, and actions on spaces with chains | ||

Abstract. I will discuss a couple of aspects of a recent work, joint with Dana Bartosova, in which we describe the universal minimal flow of the homeomorphism group of the Lelek fan. I will present the Ramsey theorem we need, its proof uses in an interesting way the Graham-Rothschild Ramsey theorem about partitions, and also I will talk about actions of homeomorphism groups on spaces of maximal chains. | ||||

Friday Apr 17 2015 | ||||

16:00-16:50 (MS 6627) | Andrew Marks (Caltech) | One-ended subforests of Borel graphs | ||

Abstract. Given a measure preserving Borel graph G on a standard
probability space, we characterize when G has a Borel one-ended spanning subforest almost everywhere. We apply our characterization to prove results about measurable colorings of Borel graphs of bounded degree, strong treeability, and the cost of planar groups. This is joint work with Clinton Conley, Damien Gaboriau, and Robin Tucker-Drob. | ||||

Friday Mar 06 2015 | ||||

16:00-16:50 (MS 6627) | Phillip Wesolek (Catholic University of Louvain) | Elementary totally disconnected locally compact Polish groups | ||

Abstract. Locally compact Polish groups appear throughout mathematics. The connected groups are subject to a rich and deep theory which can be succinctly summarized by the celebrated solution to Hilbert's fifth problem: Every connected locally compact group is pro-Lie. On the other hand, until the work of G. Willis in 1994, an analogous rich and deep theory for the totally disconnected locally compact (t.d.l.c.) Polish groups was considered unlikely. Today, however, such a theory is rapidly developing! An important role is played in this theory by the class of elementary groups: The class of elementary groups is the smallest class of t.d.l.c. Polish groups so that the class contains the profinite groups and the discrete groups, the class is closed under group extensions, and the class is closed under countable increasing unions. In this talk, we will first discuss the permanence properties of the class of elementary groups and a characterization of elementary groups. We will then go on to show that all compactly generated t.d.l.c. Polish groups can be decomposed into finitely many elementary groups and topologically characteristically simple groups via group extension. We will conclude by considering a number of open questions related to elementary groups. | ||||

Friday Feb 13 2015 | ||||

16:00-16:50 (MS 6627) | Matthias Aschenbrenner (UCLA) | The model theory of transseries | ||

Abstract. Transseries were introduced in the 1980s by the analyst Écalle in his work on Hilbert's 16th Problem, and also, independently, by the model theorists Dahn and Göring in their work around Tarski's problem on real exponentiation. They naturally arise as asymptotic expansions for germs of functions definable in certain o-minimal structures. Since the late 1990s, van den Dries, van der Hoeven, and myself, have pursued a program to understand the algebraic and model-theoretic aspects of this intricate but fascinating mathematical object. Last year we were able to make a significant step forward, and established a quantifier elimination theorem for the differential field of transseries in a natural language. My goal for this talk is to introduce transseries and to explain our recent work. | ||||

Friday Jan 23 2015 | ||||

16:00-16:50 (MS 6627) | Maciej Malicki (Warsaw School of Economics) | Consequences of the existence of ample generics and automorphism groups of homogeneous metric structures | ||

Abstract. Inspired by a recent work of Marcin Sabok, we define a criterion for a homogeneous metric structure X that implies that its automorphism group Aut(X) satisfies all the main consequences of the existence of ample generics: it has the small index property, the automatic continuity property, and uncountable cofinality for non-open subgroups. Then we verify it for the Urysohn space, the Lebesgue probability measure algebra, and the Hilbert space, regarded as metric structures, thus proving that their automorphism groups share these properties. We also formulate a condition for X which implies that every homomorphism of Aut(X) into a separable group with a left-invariant, complete metric, is trivial, and we verify it for the Urysohn space, and the Hilbert space. | ||||

Friday Dec 12 2014 | ||||

16:00-16:50 (MS 6627) | Alexander Melnikov (UC Berkeley) | Recursion theory vs abelian group theory | ||

Abstract. We will discuss several recent results on infinitely generated abelian groups with solvable word problem. Most of the results can be interpreted classically. More specifically, they measure the complexity of classification problem for natural subclasses of countable abelian groups (up to isomorphism). | ||||

Friday Nov 21 2014 | ||||

16:00-16:50 (MS 6627) | Grigor Sargsyan (Rutgers University) | The core model induction up to the Largest Suslin Axiom. | ||

Abstract. We will introduce core model induction, a technique for proving determinacy from set theoretic hypothesis. We then will concentrate on some of the recent applications. One such applications gets the Largest Suslin Axiom from PFA augmented by a mild large cardinal axiom. The Largest Suslin Axiom is stated in the base theory AD^++DC and says that the largest Suslin cardinal is a member of the Solovay sequence. It is the strongest known extension of AD^+ (excluding long games and etc). | ||||

Friday Nov 07 2014 | ||||

16:00-16:50 (MS 6627) | Dana Bartosova (University of Sao Paulo.) | The group of linear isometries of the Gurarij space is extremely amenable | ||

Abstract. For abstract, go to http://www.logic.ucla.edu/LCabstracts/bartosova-11-7-2014.pdf. | ||||

Friday Oct 31 2014 | ||||

16:00-16:50 (MS 6627) | Jay Williams (Caltech) | Elementary amenable groups, chain conditions, and descriptive set theory | ||

Abstract. We will show that the set of elementary amenable groups is not Borel in the space of finitely generated groups. It is well-known that the set of amenable groups is Borel, and so this provides a new, non-constructive proof that there are amenable groups which are not elementary amenable, a result originally due to Grigorchuk. The proof involves constructing trees based on groups, an approach which can also be used to analyze sets of groups satisfying certain chain conditions. (Joint work with Philip Wesolek) | ||||

Friday Oct 17 2014 | ||||

16:00-16:50 (MS 6627) | Matthew Foreman (UC Irvine) | From Odometers to Circles, Classifying Diffeomorphisms of the Torus | ||

Abstract. We present an anti-classification result for diffeomorphisms under the equivalence relation of measure preserving conjugacy and discuss extending it to conjugation by homeomorphisms. An important ingredient is a functor from odometer based systems to circular systems. This is joint work with B Weiss. | ||||

Friday Jun 06 2014 | ||||

16:00-16:50 (MS 6627) | Ward Henson (University of Illinois at Urbana-Champaign) | Uncountably categorical Banach space structures | ||

Abstract. The recent progress discussed in this talk concerns new examples of uncountably categorical Banach spaces (of which there have been very few previously known). This is joint work with Yves Raynaud (Univ. of Paris 6).
Model theory is applied to (unit balls of) Banach spaces (and structures based on them, such as Banach algebras or Banach lattices) using the [0,1]-valued continuous version of first order logic. During the talk a sketchy and intuitive description of this logic will be given.
A theory T of such structures is said to be kappa-categorical} if $T$ has a unique model of density kappa. Work of Ben Yaacov and Shelah-Usvyatsov shows that Morley's Theorem holds in this context: if T has a countable signature and is kappa-categorical for some uncountable kappa, then T is \kappa-categorical for all uncountable kappa.
Known examples of uncountably categorical such structures (including the new ones) are closely related to Hilbert space. After the speaker called attention to this phenomenon, Shelah and Usvyatsov investigated it and proved a remarkable result: if M is a nonseparable Banach space structure (with countable signature) whose theory is uncountably categorical, then M is prime over a Morley sequence that is an orthonormal Hilbert basis of length equal to the density of M. There is a wide gap between this result and verified examples of uncountably categorical Banach spaces, which leads to the question: can a stronger such result be proved, in which the connection to Hilbert space structure is clearly expressed in the geometric language of functional analysis? Here the ultimate goal would be to prove analogues for Banach space structures (or even for general metric structures) of the Baldwin-Lachlan Theorems. | ||||

Friday May 23 2014 | ||||

16:00-16:50 (MS 6627) | Richard Shore (Cornell University) | The Strength of Determinacy and Turing Determinacy within Second Order Arithmetic | ||

Abstract. We analyze the strength of standard Determinacy principles as well as ones for Turing Determinacy that are provable in (subsystems of) second order arithmetic (equivalently ZFC^-). These are all at low levels of the arithmetic hierarchy. We consider three notions of strength. The first is in the sense of reverse mathematics, which asks what axioms (e.g. comprehension for Pi^1_n formulas) are needed to prove the principles. The second is more traditionally proof theoretic in that we compare principles in terms of consistency strength. The third is recursion or set theoretic in that we want to determine the existence of which ordinals (or better levels of the constructible universe L) are implied by these principles. Here the measure is in terms of levels of admissibility (in replacement) or nonprojectability (in comprehension axioms).
This is joint work with Antonio Montalbán.
The limits of determinacy in second order arithmetic, Proceedings of the London Mathematical Society 104 (3) (2012), 223-252. The Limits of Determinacy in Second Order Arithmetic: Consistency andComplexity Strength, Israel Journal of Mathematics, to appear. The Strength of Turing Determinacy within Second Order Arithmetic, to appear. All are available at http://www.math.cornell.edu/~shore/papers.html | ||||

Friday May 09 2014 | ||||

16:00-16:50 (MS 6627) | Rahim Moosa (University of Waterloo) | The Canonical Base Property and the Zilber Dichotomy Revisited | ||

Abstract. The truth of the Zilber dichotomy in several first-order theories of fields with additional operators was behind Hrushovski's dramatic application of model theory to diophantine geometry in the nineties. About ten years ago, abstracting from a theorem in complex-analytic geometry, Pillay introduced a new model-theoretic condition now called the canonical base property (CBP). This condition provides a direct proof of the Zilber dichotomy in various contexts, and has other strong geometric consequences. What seems to be required in establishing the CBP in any given situation is an appropriate notion of "jet space". This talk will be a largely expository introduction to, and overview of, the subject. | ||||

Friday Apr 25 2014 | ||||

16:00-16:50 (MS 6627) | James Cummings (Carnegie Mellon University) | Forcing at successors of singular cardinals | ||

Abstract. Many problems about structures on a regular cardinal become especially hard when that cardinal is the successor of a singular cardinal. We will discuss this phenomenon, with a particular focus on the question of how to prove consistency results. | ||||

Friday Apr 11 2014 | ||||

16:00-16:50 (MS 6627) | Boris Zilber (Oxford University) | Schemes - structures duality in geometry and logic | ||

Abstract. The well-known duality of classical algebraic geometry between affine varieties and their co-ordinate algebras has a perfect analogue in the theory of
commutative C^*-algebras, which can be seen by the Gel'fand-Naimark theorem as the algebras of continuous complex-valued functions on a compact Hausdorff space. In modern geometry and physics one deals with much more complex generalisations of co-ordinate algebras, such as schemes, stacks and non-commutative C^*-algebras, where a geometric counterpart is no longer readily available and in many cases is believed impossible.
We will discuss a model-theoretic project which challenges this point of view. | ||||

Friday Mar 07 2014 | ||||

16:00-16:50 (MS 6627) | Martin Hils (University of Paris 7) | Valued difference fields and NTP2 | ||

Abstract. There are interesting examples of algebraic structures with some
kind of`tame' model-theoretic behaviour whose theory is neither
simple nor NIP. The valued difference field given by the
non-standard Frobenius automorphism acting on an algebraically
closed valued field is such a structure.
Theories without the tree property of the second kind, i.e. NTP2 theories, generalise both simple and NIP theories, and, among other things, forking has been shown to behave well in this context. It turns out that certain valued difference fields are NTP2, in particular the non-standard Frobenius example mentioned above. (Joint work with Artem Chernikov.) | ||||

Friday Feb 21 2014 | ||||

16:00-16:50 (MS 6627) | Itay Neeman (UCLA) | Higher analogues of properness | ||

Abstract. Forcing axioms are strengthenings of the Baire category theorem
that allow meeting a prescribed number of dense sets with filters
in prescribed classes of partial orders. For example Martin's
Axiom (MA) for $\kappa$ involves meeting $\kappa$ dense sets in
the class of partial orders with no uncountable antichains.
Another example is the Proper Forcing Axiom (PFA) which involves
meeting $\aleph_1$ dense sets in the class of proper partial
orders. PFA was developed in the early 1980s and has been
incredibly useful, both as a starting point for consistency proofs
that would otherwise require forcing iterations, and as an axiom
leading to set theoretic structure theorems. In contrast with MA
where $\kappa$ can be arbitrary, PFA cannot be strengthened to
allow meeting more than $\aleph_1$ dense sets. However recent work
of Neeman shows that there are analogues of PFA which do involve
meeting more than $\aleph_1$ dense sets. The goal in developing
these analogues is to obtain generalizations to higher cardinals
of applications of PFA. We describe some of the analogues in the
talk, and some applications that have been obtained so far. | ||||

Friday Feb 07 2014 | ||||

16:00-16:50 (MS 6627) | Spencer Unger (UCLA) | Successive cardinals with the tree property | ||

Abstract. The tree property arises as the generalization of Konig's infinity lemma to an uncountable cardinal. The existence of an uncountable cardinal with the tree property has axiomatic strength beyond the axioms of ZFC. Indeed a theorem of Mitchell shows that the theory ZFC + ``omega_2 has the tree property" is consistent if and only if the theory ZFC + ``There is a weakly compact cardinal" is consistent. In the context of Mitchell's theorem, we can ask an old question in set theory: Is it consistent that every regular cardinal greater than aleph_1 has the tree property? In this talk we will survey the best known partial results towards a positive answer to this question. | ||||

Friday Jan 24 2014 | ||||

16:00-16:50 (MS 6627) | Philipp Hieronymi (University of Illinois at Urbana-Champaign) | Büchi, Cantor and Diophantus of Alexandria | ||

Abstract. I will give a progress report on the following two problems I have been
working on for a while now:
1) finding a Cantor set C such that the expansion of the real field by C is model theoretically tame, 2) understanding the expansion of the ordered additive group of real numbers by two predicates, one for Z and one for aZ, where Z is the set of integers and a is an irrational number. In particular, their connection to Büchi's theorem on the monadic second order theory of one successor will be discussed. | ||||

Friday Jan 10 2014 | ||||

16:00-16:50 (MS 6627) | Dima Sinapova (University of Illinois, Chicago) | Square properties for successors of singular cardinals | ||

Abstract. The square property was isolated by Jensen in his fine structure analysis of L. It is an "incompacness" property, that holds in canonical inner models. Square at $\kappa$ states that there is a coherent sequence of closed unbounded subsets singularizing points $\alpha<\kappa^+$. There are various weakenings of this principle by allowing multiple guesses for each club. How much a given model satisfies square principles serves as a measure how far this model is from a canonical inner model.
It is difficult to avoid the weaker square principles at successors of singulars. Doing so requires large cardinals. It is especially difficult to obtain these failures while also violating the Singular Cardinal Hypothesis (SCH). We will investigate the relationship between square properties and not SCH. Violating SCH is done via Prikry type forcing. We will discuss the impact of these type of forcings on square properties. Time permitting, we will focus on models where SCH fails at $\aleph_\omega$ and models when SCH fails at $\kappa$ while GCH holds below $\kappa$. | ||||

Friday Dec 06 2013 | ||||

16:00-17:00 (MS 6627) | Asger Tornquist (University of Copenhagen) | No mad families in Solovay's model | ||

Abstract. In a 1967 paper, Mathias showed that there are no
analytic infinite maximal almost disjoint (mad) families, and
asked if there are infinite mad families in Solovay's model.
Recently, I have found a completely elementary proof of Mathias'
theorem using an ordinal analysis/derivative argument. This
argument can be adapted to work under the following general
assumptions: (1) That all uncountable sets of reals contain a
perfect subset, and (2) that an apparent strengthening of the Open
Colouring Axiom, called $OCA_\infty$, which was proposed by Ilijas
Farah, holds. Since $OCA_\infty$ holds in Solovay's model, this then
answers Mathias' question. The talk will focus on this result, but
if time allows, I will also discuss a more general approach along
these lines that allow us to answer a number of related questions,
e.g., to show that there are no analytic maximal eventually
different families of functions from $\omega$ to $\omega$. | ||||

Friday Nov 22 2013 | ||||

16:00-17:00 (MS 6627) | John R. Steel (University of California, Berkeley) | Some recent results in inner model theory | ||

Abstract. We shall describe some recent work that extends our methods for constructing canonical inner models satisfying large cardinal hypotheses.
As applications, one obtains some new consistency strength lower bounds. | ||||

Friday Nov 08 2013 | ||||

16:00-17:00 (MS 6627) | Alexander S. Kechris (California Institute of Technology) | Topological dynamics and ergodic theory of automorphism groups of countable structures | ||

Abstract. I will discuss some aspects of the topological dynamics
and ergodic theory of automorphism groups of countable first-order
structures and their connections with logic, finite combinatorics
and probability theory. This is joint work with Omer Angel and
Russell Lyons. | ||||

Friday Oct 25 2013 | ||||

16:00-17:00 (MS 6627) | Damir Dzhafarov (University of Connecticut) | New directions in reverse mathematics | ||

Abstract. Mathematics today benefits from having "firm foundations", by which we usually mean a system of axioms sufficient to prove the theorems we care about. But given a particular theorem, can we specify precisely which axioms are needed to derive it? This is a natural question, and also an ancient one: over 2000 years ago, the Greek mathematicians were asking it about Euclid's geometry. Reverse mathematics provides a modern approach to this kind of question. A striking fact repeatedly demonstrated in this area is that the vast majority of mathematical propositions can be classified into just five main
types, according to which set-existence axioms are needed to carry
out their proofs. But more recently, a growing number of
principles falling outside this classification have emerged, whose
logical strength is more difficult to understand. These turn out
to include many important mathematical results, such as various
combinatorial problems related to Ramsey's theorem, and several
set-theoretic equivalents of the axiom of choice. I will discuss
some of these "irregular" principles, and some new approaches that
have arisen from trying to understand why their strength is so
different from that of most other theorems. In particular, this
investigation reveals new connections between different
mathematical areas, and exposes the rich and complex combinatorial
and algorithmic structure underlying mathematics as a whole. | ||||

Friday Oct 11 2013 | ||||

16:00-17:00 (MS 6627) | Theodore A. Slaman (University of California, Berkeley) | On normal numbers | ||

Abstract. A real number is simply normal in base b if in its base-b
expansion each digit appears with asymptotic frequency 1/b. It is normal in base b if it is simply normal in all powers of b, and absolutely normal if it is simply normal in every integer base. By a theorem of E. Borel, almost every real number is absolutely normal. We will present three main results. We will give an efficient algorithm, which runs in nearly quadratic time, to compute the binary expansion of an absolutely normal number. We will demonstrate the full logical independence between normality in one base and another. We will give a necessary and sufficient condition on a set of natural numbers M for there to exist a real
number X such that X is simply normal to base b if and only if b is an element of M. | ||||

Friday Sep 27 2013 | ||||

16:00-17:00 (MS 6627) | Isaac Goldbring (University of Illinois at Chicago) | A survey of the model theory of tracial von Neumann algebras | ||

Abstract. Von Neumann algebras are certain algebras of bounded operators on Hilbert spaces. In this talk I will survey some of the model theoretic results about (tracial) von Neumann algebras, focusing mainly on (in)stability, quantifier-complexity, and decidability. No prior knowledge of von Neumann algebras will
be necessary. Some of the work presented is joint with Ilijas
Farah, Bradd Hart, David Sherman, and Thomas Sinclair. | ||||

Friday May 17 2013 | ||||

16:00-17:00 (MS 6627) | Maryanthe Malliaris (University of Chicago) | Comparing the complexity of unstable theories | ||

Abstract. Keisler's order is a large scale program of understanding model-theoretic structure from asymptotic (ultrapower) points of view. The talk will explain some very recent progress on Keisler's order, consequences for the
classification of unstable theories, and related theorems on Szemeredi regularity and set theory/general topology: in particular, Malliaris and Shelah recently solved the oldest problem on cardinal invariants of the continuum, whether "p=t", using model-theoretic tools developed for the study of Keisler's order.
I will assume basic familiarity with ultraproducts, Los's theorem, and saturation, and plan to give most other relevant definitions. Papers mentioned in the talk are available at http://math.uchicago.edu/~mem. | ||||

Friday May 10 2013 | ||||

16:00-17:00 (MS 6627) | D.H.J. de Jongh (University of Amsterdam) | Heyting Arithmetic and Intermediate Logic | ||

Abstract. It is proved that all intermediate logics L(propositional logics between intuitionistic logic IPC and classical logic), that have the finite model property have the following maximality property: The logic of the propositional schemes valid in Heyting Arithmetic plus L is exactly L. This is generalization of the old theorem that the logic of Heyting Arithmetic is exactly intuitionistic logic. This work was in cooperation with Rineke Verbrugge and Albert Visser. | ||||

Friday Apr 26 2013 | ||||

16:00-17:00 (MS 6627) | R. Daniel Mauldin (University of North Texas) | Steinhaus' tiling problem | ||

Abstract. In the 1950's Steinhaus posed the following problem: Is there a set S in R^2 which meets each isometric copy of Z^2 in exactly one point? I will describe some aspects of the positive solution that Steve Jackson and myself gave and discuss a number of unsolved related problems. | ||||

Friday Apr 12 2013 | ||||

16:00-17:00 (MS 6627) | Mingzhong Cai (University of Wisconsin) | Recursive functions and provability degrees | ||

Abstract. Given a recursive function f (with a fixed algorithm), the totality of f is the Pi_2 sentence that this function f is total. Note that the totality of f depends on the algorithm for computing f. Given two recursive functions f and g with fixed algorithms, we say f is provably reducible to g if the totality of g proves the totality of f over some base theory T. Now we can consider the degree structure on recursive functions modulo provable equivalence, and investigate this proof-theoretic degree structure by recursion-theoretic methods and ideas. This is essentially Lindenbaum algebra restricted on true Pi_2 sentences, and there are two natural jump-like operators. I will present a few sample results, including density theorem, jump inversion theorem and high-low hierarchy. This is joint work with Andrews, Diamondstone, Lempp and Miller. | ||||

Friday Mar 15 2013 | ||||

16:00-17:00 (MS 6627) | Trevor Wilson (UC Irvine) | A Determinacy transfer principle | ||

Abstract. The Axiom of Determinacy, AD, asserts that infinitely long two-player games on the integers are determined. Although AD contradicts the Axiom of Choice, many strong hypotheses such as large cardinal axioms imply that AD holds in some realm of "nice" sets; for example, the projective sets or the sets of reals in the inner model L(R). In some cases showing that more games are determined requires a stronger hypotheses, whereas in other cases one can get extra determinacy "for free." The latter type of result, sometimes called a determinacy transfer principle, was used by Kechris and Woodin to prove that every set of reals in L(R) is determined from a seemingly lesser determinacy hypothesis. We introduce a general determinacy transfer principle and use it to give a new proof of Woodin's theorem that given two "divergent" models of AD, their intersection satisfies a strong form of AD (namely determinacy for games on the reals.) | ||||

Friday Feb 15 2013 | ||||

16:00-17:00 (MS 6627) | Sean Walsh (UC Irvine) | Basic Law V: Standard and Non-standard Models | ||

Abstract. Basic Law V was one of the crucial axioms of Frege's
ultimately inconsistent system in Grundgesetze. Roughly, Basic Law V postulates an injection from the second-order part of a structure to the first-order part. In recent decades, the work of Parsons, Ferreira, Wehmeier and others has shown Basic Law V is consistent with more limited amounts of comprehension. In this talk, we describe some new model constructions of Basic Law V. On the one hand, Basic Law V allows one to define a membership relation, and so here it's natural to look for models amongst small fragments of the constructible hierarchy. On the other hand, by modifying the Ferreira-Wehmeier construction, one can ascertain which kinds of fields are compatible with the structure of Basic Law V, and as some such fields are so
well-understood one is able to thus deduce that various natural statements about the induced membership relation are not provable from Basic Law V. | ||||

Friday Feb 08 2013 | ||||

16:00-17:00 (MS 6627) | Dana Bartosova (University of Toronto) | Ramsey property for Boolean algebras with ideals and the Katowice problem | ||

Abstract. I will give an introduction to the theory connecting topological dynamics, Ramsey theory and model theory of countable structures developed by Kechris, Pestov and Todorcevic. I will mention how their results can be extended to uncountable structures, in particular to the Boolean algebra of all subsets of an uncountable set modulo the ideal of finite sets. This requires a generalization of the Dual Ramsey Theorem to classes of finite Boolean algebras with distinguished ideals. Considering Fraisse limits of these classes provides results in dynamics of the group of homeomorphisms of the Cantor set. | ||||

Friday Jan 11 2013 | ||||

16:00-17:00 (MS 6627) | Edward Keenan (UCLA) | Boolean Type Theory for Natural Language (Eliminating the Universe) | ||

Abstract. We linguistically motivate an extensional type theory for natural language which replaces the unstructured universe of entities in which singular terms denote by a booleanly structured set P of properties in which common nouns (e.g. doctor) and one place predicates denote. Sentences denote in 2 = {0,1} as usual. Denotations of singular terms (e.g. John, individual constants) are booleanly defined in terms of properties and truth values. The full set of possible
denotation sets is the closure of {P,2} under the formation of function spaces and finite products. All denotation sets are provably complete atomic boolean lattices. This boolean streamlining is shown to be linguistically enlightening and to justify the same valid arguments as classical type theory.
Then we generalize our boolean type theory by relaxing the atomicity requirement on P in order to provide denotations for a class of intensional adjectives (skillful) and quantifiers (enough, too many). (If the surgeons and the lawyers happen to be the same individuals in some model it does not follow that the skillful surgeons and the skillful lawyers are the same; also it may be that not enough doctors attended some meeting even though enough (even too many) lawyers did). Our generalized boolean type theory makes extensive use of complete but non-atomic boolean lattices. We invoke no semantic novelties like "possible worlds" or structured meanings. Several open questions remain concerning generalizing boolean types to new categories of expressions (including sentences!) and the uniformity of intensions across categories. Do not modifier categories (adjectives, adverbs) behave differently from predicate-argument categories? Within a category different subclasses of adjectives seem to make different contributions to the intensions of the common noun phrases they build. | ||||

Friday Dec 07 2012 | ||||

16:00-17:00 (MS 6627) | Andrew Marks (Caltech) | Structure theorems for treeable countable Borel equivalence relations | ||

Abstract. We use Borel determinacy to prove some structure theorems
for treeable countable Borel equivalence relations. We show that a smooth disjoint union of continuum many non-universal treeable Borel equivalence relations is not universal treeable, that every universal treeable equivalence relation achieves its universality on a nullset,
and that universality for Borel reductions and universality for Borel embeddings coincide for the class of treeable equivalence relations.
Our results follow from the existence of a countably complete
ultrafilter on the invariant Borel sets of a universal treeable
equivalence relation for which every element of the ultrafilter is
universal. Our results also generalize to some other universal
K-structurable equivalence relations. | ||||

Friday Nov 30 2012 | ||||

16:00-17:00 (MS 6627) | Zlatan Damnjanovic (USC) | Concatenation as a basis for set theory | ||

Abstract. We describe a direct and natural interpretation of Adjunctive Set Theory with Extensionality (AST+EXT) in a weak elementary theory of concatenation. As a consequence we establish mutual interpretability of AST+EXT and Robinson arithmetic, Q. | ||||

Friday Nov 09 2012 | ||||

16:00-17:00 (MS 6627) | James Freitag (UC Berkeley) | Almost simple differential algebraic groups | ||

Abstract. We will begin by describing the setting and explaining what a differential algebraic group is and why they are of interest. After this, we will discuss a series of problems which were revealed when Cassidy and Singer proved a Jordan-Holder type theorem for differential algebraic groups. Subsequent work using model theoretic techniques and Steinberg groups has lead to a strong classification of noncommutative almost simple groups. If time allows, we will explain generalizations of this work to the superstable setting along with its relationship to Cherlin's main conjecture. | ||||

Friday Nov 02 2012 | ||||

16:00-17:00 (MS 6627) | Aleksandra Kwiatkowska (UCLA) | Boolean actions of groups of isometries | ||

Abstract. I will discuss the following result: every Boolean action of an isometry group of a separable locally compact space has a point realization. This generalizes both a classical result due to Mackey for separable locally compact groups and a recent result due to Glasner, Tsirelson, and Weiss for non-archimedean Polish groups, and it covers new interesting examples. The proof of this result relies on a new characterization of groups of isometries of separable locally compact spaces. The solution to the Hilbert's fifth problem plays a crucial role in our investigations. This is a joint work with Slawek Solecki. | ||||

Friday Oct 19 2012 | ||||

16:00-17:00 (MS 6627) | Jay Williams (Caltech) | Group embeddability and countable Borel quasi-orders | ||

Abstract. Descriptive set theory gives us a framework for analyzing the relative complexity of quasi-orders (i.e. reflexive transitive relations) arising in many areas of mathematics, such as Turing reducibility of sets of natural numbers or embeddability of countable groups, using the notion of a Borel reduction. I will discuss a special class of quasi-orders, the countable Borel quasi-orders, which include embeddability of finitely-generated groups. I will present a proof that embeddability of countable groups is a universal analytic quasi-order, and discuss how the ideas work in the finitely-generated case. |

Click here to see the announcements for older Logic Colloquia.