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

The Logic Colloquium Chair is
Artem Chernikov.

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 May 31 2019 | ||||

16:00-16:50 (MS 6221) | Joshua Wiscons (Sacramento State) | TBA | ||

Abstract. TBA | ||||

Friday May 17 2019 | ||||

16:00-16:50 (MS 6221) | Rachid Atmai (Mira Costa College, Oceanside) | TBA | ||

Abstract. TBA | ||||

Friday May 03 2019 | ||||

16:00-16:50 (MS 6221) | Aristotelis Panagiotopoulos (Caltech) | TBA | ||

Abstract. TBA | ||||

Friday Apr 19 2019 | ||||

16:00-16:50 (MS 6221) | Todor Tsankov (University Paris 7) | A model-theoretic approach to ergodic theory | ||

Abstract. The main object of study of ergodic theory are the measure-preserving
actions of (countable) groups on probability spaces. I will discuss a
formalization of this setup in the framework of continuous logic and
explain how some important notions studied in ergodic theory have a
natural model-theoretic interpretation. This allows for some quick
proofs of known results as well as a new rigidity theorem for strongly
ergodic, distal actions. This is joint work with Tomas Ibarlucia. |

Friday Mar 08 2019 | ||||

16:00-16:50 (MS 6221) | Nadja Hempel (UCLA) | N-dependent groups and fields | ||

Abstract. NIP theories are the first class of the hierarchy of n-dependent structures. The random n-hypergraph is the canonical object which is n-dependent but not (n-1)-dependent. Thus the hierarchy is strict. But one might ask if there are any algebraic objects (groups, rings, fields) which are strictly n-dependent for every n?
We will start by introducing the n-dependent hierarchy and present all known results on n-dependent groups and fields. | ||||

Friday Feb 22 2019 | ||||

16:00-16:50 (MS 6221) | Omer Mermelstein (University of Wisconsin - Madison) | Generic flat pregeometries | ||

Abstract. The property of "flatness" of a pregeometry (matroid) is best known in model theory as the device with which Hrushovski showed that his example refuting Zilber's conjecture does not interpret an infinite group. I will dedicate the first part of this talk to explaining what flatness is, how it should be thought of, and how closely it relates to hypergraphs and Hrushovski's construction method. In the second part, I will conjecture that the family of flat pregeometries associated to strongly minimal sets is model theoretically nice, and share some intermediate results. | ||||

Friday Feb 08 2019 | ||||

16:00-16:50 (MS 6221) | Adam Day (Victoria University of Wellington) | Computability Theoretic Hierarchies of Real-valued Functions | ||

Abstract. In this talk I will review some fundamental concepts in computability theory and show how they can be applied to analyze the relative complexity of real-valued functions. I will review some old results that come from this analysis, in particular, the continuous degrees of Miller. Then I will introduce some new hierarchies that results from joint work with Downey and Westrick. One of these new hierarchies refines the Bourgain rank for Baire class 1 functions and allows a new way to extend this rank to all Baire measurable functions. | ||||

Friday Jan 25 2019 | ||||

16:00-16:50 (MS 6221) | Lynn Scow (California State University, San Bernardino) | Transfer of the Ramsey property | ||

Abstract. For $L$-structures $B$, $C$ we use the notation ${C choose B}$ to denote the set of all substructures of $C$ isomorphic to $B$. We say that a countable, locally finite structure $I$ ordered
by a relation $<$ has RP (the Ramsey property) if for all $A_0, B_0 in textrm{age}(I)$ and integers $k geq 1$ there is some $C_0 in textrm{age}(I)$ such that
$C_0 rightarrow (B_0)^{A_0}_k$. In other words, for all functions $c: {C_0 choose A_0} rightarrow k$ there is some $B' subseteq C_0$, $B' cong B_0$ such that $c$ restricted to ${B' choose A_0}$ is a constant function. We will approach the question of when RP transfers from one countable structure to another, where these structures are in possibly different languages. We will look at universal algebraic and model theoretic criteria. | ||||

Friday Jan 11 2019 | ||||

16:00-16:50 (MS 6221) | Szymon Torunczyk (University of Warsaw) | Some applications of model theory in computer science | ||

Abstract. I will present a few basic applications of model theory in theoretical computer science, e.g. in verification, databases, and algorithms. I will also discuss some initial ideas employing (ideas from) stability theory to solve algorithmic problems concerning graphs. | ||||

Friday Nov 30 2018 | ||||

16:00-16:50 (MS 6221) | Nick Ramsey (UCLA) | Kim-independence and NSOP1 theories | ||

Abstract. Shelah's work on saturation spectra, Hrushovski on PAC structures, and Cherlin-Hrushovski on quasi-finite structures gave the initial impetus for the development of simple theories. A general theory, which unified and explained these different lines of research, was developed by Kim and Pillay using the notion of non-forking independence, which in turn spawned a remarkably rich line of model-theoretic research. In my talk, we will describe a parallel theory for the broader class of NSOP1 theories centered around the notion of Kim-independence and the applications that this theory made possible. We will survey results in a series of papers joint with Artem Chernikov, Itay Kaplan, Alex Kruckman, and Saharon Shelah (though not all at once). | ||||

Friday Nov 16 2018 | ||||

16:00-16:50 (MS 6221) | Lynn Scow (California State University, San Bernardino) | Transfer of the Ramsey property - CANCELLED | ||

Abstract. For $L$-structures $B$, $C$ we use the notation ${C choose B}$ to denote the set of all substructures of $C$ isomorphic to $B$. We say that a countable, locally finite structure $I$ ordered
by a relation $<$ has RP (the Ramsey property) if for all $A_0, B_0$ in age$(I)$ and integers $k geq 1$ there is some $C_0$ in age$(I)$ such that $C_0 rightarrow (B_0)^{A_0}_k$. In other words, for all functions $c: {C_0 choose A_0} rightarrow k$ there is some $B' subseteq C_0$, $B' cong B_0$ such that $c$ restricted to ${B' choose A_0}$ is a constant function.
We will approach the question of when RP transfers from one countable structure to another, where these structures are in possibly different languages. We will look at universal algebraic and model theoretic criteria. | ||||

Friday Nov 02 2018 | ||||

16:00-16:50 (MS 6221) | Douglas Ulrich (UC Irvine) | Generalized Amalgamation and Chromatic Numbers | ||

Abstract. Let $T_{k+1, k}$ denote the theory of the k-ary, k+1-clique
free random hypergraph, for k >= 3. Malliaris and Shelah have famously
proven that $T_{k+1, k}$ is not below $T_{k'+1, k'}$ in Keisler's order,
whenever k+1 < k'; hence, Keisler's order has infinitely many classes. I
have since improved the combinatorics to obtain the same result whenever k < k', and I obtain model-theoretic upper and lower bounds for the relevant dividing lines detected by Keisler's order. These bounds correspond to various kinds of k-dimensional amalgamation properties.
The combinatorics involved is rather technical; however, the model-theoretic upper and lower bounds are not. I aim to introduce and motivate them; in particular, we will explore a connection between generalized amalgamation properties and the chromatic numbers of hypergraphs of partial types. It is open if the various k-dimensional amalgamation properties we introduce are equivalent. | ||||

Friday Oct 19 2018 | ||||

16:00-16:50 (MS 6221) | Sam Buss (UC San Diego) | Bounded Arithmetic, Expanders, and Monotone Propositional Proofs | ||

Abstract. This talk discusses a new combinatorial proof of the existence of expander graphs, which can be carried out in the bounded arithmetic theory VNC$^1$ corresponding to alternating linear time. As an application, we prove that the monotone propositional sequent calculus polynomially simulates the full propositional sequent calculus. Prior to this, only a quasipolynomial simulation was known. Joint work with Valentine Kabanets, Antonina Kolokolova, and Michal Koucky. | ||||

Friday Oct 05 2018 | ||||

16:00-16:50 (MS 6221) | Byunghan Kim (Yonsei University, Seoul) | On the number of countable NSOP$_1$ theories without weight $omega$. | ||

Abstract. Lachlan's problem is asking whether any countable theory $T$ with $1<I(omega, T)$=the no. of countable models of $T<omega$ must have the strict order property. It is not fully answered yet, but Lachlan himself in 70s proved that such $T$ is non-superstable. The result is extended by me in 90s to non-supersimple $T$. Now I extend it further in NSOP$_1$ theory context.
Theorem: If $T$ is NSOP$_1$ with nonforking existence, then $1<I(omega, T)<omega$ implies that there must be a finite tuple whose own preweight is $omega$. The proof of the theorem relies on recent exciting developments on NSOP$_1$ theories initiated by I. Kaplan and N. Ramsey for models, and continued for sets in a joint work with J. Dobrowolski and N. Ramsey. | ||||

Friday Jun 08 2018 | ||||

16:00-16:50 (MS 6221) | Omer Ben-Neria (UCLA) | Ordinal Definable Sets and Singular Cardinals | ||

Abstract. The extent to which ordinal definable sets can capture essential information about the universe V has been extensively studied in the last few years.
One main line of study in this vein has been initiated by Shelah, who proved that for every singular strong limit cardinal k of uncountable cofinality, there exists a single subset x of k such that the ordinal definable class HOD(x) (consisting of sets which are hereditarily definable in ordinals and x) contains all other subsets of k. The theorem does not address cardinals k of countable cofinality and it is natural to ask whether Shelah's approximation result can be extended to all strong limit singular cardinals. In 2016, James Cummings, Sy Friedman, Menachem Magidor, Assaf Rinot, and Dima Sinapova, have established the failure of a version of Shelah's theorem for cardinals k of countable cofinality. The purpose of the talk is to discuss the consistency strength of this result and described new consistency bounds. This is a joint work with Moti Gitik, Itay Neeman, and Spencer Unger. | ||||

Friday May 25 2018 | ||||

16:00-16:50 (MS 6221) | Martin Zeman (UC Irvine) | TBA | ||

Abstract. TBA | ||||

Friday Apr 20 2018 | ||||

16:00-16:50 (MS 6221) | Martin Ziegler (University of Freiburg) | Equationality of pairs of algebraically closed sets. | ||

Abstract. (This is joint work with Martin Pizarro). We prove
the equationality of the theory of pairs of algbraically closed fields by exhibiting a nice set of equations. We do no know if these equations have the DCC outside characteristic 0. | ||||

Friday Mar 16 2018 | ||||

16:00-16:50 (MS 6221) | Asger Törnquist (University of Copenhagen) | What happened to mad families? | ||

Abstract. I will give an overview of the many developments in the
descriptive set theory of maximal almost disjoint ("mad") families
(and their cousins, maximal eventually different families and maximal
cofinitary groups) that have happened in the last 5 years. | ||||

Friday Mar 09 2018 | ||||

16:00-16:50 (MS 6221) | Philip Welch (University of Bristol) | Recursions of higher types and low levels of determinacy | ||

Abstract. We explore how generalisations of Kleene's theory of recursion in type 2 objects (which can be used to characterise complete $Pi^1_1$ sets and open determinacy) can be lifted to $Sigma^0_3$-Determinacy. The generalisation requires the use of so-called infinite time Turing machines, and the levels of the Gödel constructible hierarchy needed to see that such machines models produce an output are, perhaps surprisingly, intimately connected with those needed to prove the existence of such strategies: the generalised halting problem has the same informational content as a listing of the $Sigma^0_3 $-games won by Player I. The subsystem of analysis needed for this work is $Pi^1_3$-$mathsf{CA_0}$. | ||||

Friday Feb 16 2018 | ||||

16:00-16:50 (MS 6221) | Matthew Foreman (UCI) | Goedel's Diffeomorphisms | ||

Abstract. In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of compact manifolds. In modern language this means classifying up to conjugacy by measure preserving transformations. Von Neumann's question resulted in an enormous literature, with partial solutions involving invariants such as entropy, spectrum and several other properties.
In this talk we show that the general problem is impossible in the sense that no countable protocol, using arbitrary countable resources can solve it. Thus concrete methods such as spectral theory or entropy have no chance of succeeding-any classification must involve a some tool such as the uncountable axiom of choice. Precisely, we show: {(S,T): S and T are conjugate ergodic diffeomorphisms of the 2-torus} is NOT a Borel set in the C-infinity topology on pairs of diffeomorphism. For dessert, we give an example of a recursive diffeomorphism T such that the statement "T is isomorphic to its inverse" is independent of ZFC (and an S such that S being isomorphic to its inverse is independent of "ZFC + there is a supercompact cardinal" and so forth). This is joint work with Benjy Weiss and Hans Gaebler. | ||||

Friday Feb 02 2018 | ||||

16:00-16:50 (MS 6221) | Raphaël Carroy (University of Vienna) | Projective homogeneous spaces and Wadge theory | ||

Abstract. Fons van Engelen used the description of Wadge degrees of Borel sets to analyze Borel homogeneous spaces. I will explain the first steps we have made with Andrea Medini and Sandra Müller towards the generalization of van Engelen's results in the projective hierarchy. | ||||

Friday Jan 19 2018 | ||||

16:00-16:50 (MS 6221) | Sean Walsh (UCLA) | The Constructible Universe, the Naive Conception, and Intensional Logic | ||

Abstract. This talk looks at the relationship between three foundational systems: Goedel's Constructible Universe of Sets, the naive conception of set found in consistent fragments of Frege's Grundgesetze, and the intensional logic of Church's Logic of Sense and Denotation. One basic result shows how to use the constructible sets to build models of fragments of Frege's Grundgesetze from which one can recover these very constructible sets using Frege's definition of membership. This result also allows us to solve the related consistency problem and joint consistency problems for abstraction principles with limited amounts of comprehension. Another basic aim of this talk is to show how to "factor" this result via a consistent fragment of Church's Logic of Sense and Denotation: so one may use the constructible sets to build models of Church's Logic of Sense and Denotation, from which one may then define models of the consistent fragments of Frege's Grundgesetze. This talk is based on [1]-[3].
[1] S. Walsh. Fragments of Frege's Grundgesetze and Goedel's constructible universe. The Journal of Symbolic Logic, 81(2):605-628, 2016. [2] S. Walsh. Predicativity, the Russell-Myhill paradox, and Church's intensional logic. The Journal of Philosophical Logic, 45(3):277-326, 2016. [3] S. Walsh. The strength of abstraction with predicative comprehension. The Bulletin of Symbolic Logic, 22(1):105-120, 2016. | ||||

Friday Dec 08 2017 | ||||

16:00-16:50 (MS 6221) | Jindrich Zapletal (University of Florida) | Hypergraphs and proper forcing | ||

Abstract. Given a countable family G of analytic hypergraphs on a Polish space X, one can form the sigma-ideal generated by Borel sets which are anticliques in at least one hypergraph in the family G. One can also form the quotient forcing P(G) of Borel sets modulo the sigma ideal. It turns out that in large classes of cases, the quotient forcing is proper, and simple combinatorial properties of the hypergraph family G translate into forcing properties of the quotient poset P(G). Various dichotomies lead to partial classification of posets obtained from restrictive classes of hypergraphs. The machinery allows for simple computation of the iteration and product ideal in terms of the hypergraphs, which in turn leads to overwhelmingly simple proofs of various preservation theorems. | ||||

Friday Nov 17 2017 | ||||

16:00-16:50 (MS 6221) | Allen Gehret (UCLA) | A tale of two Liouville closures... | ||

Abstract. $H$-fields are ordered differential fields which serve as an abstract generalization of both Hardy fields (ordered differential fields of germs of real-valued functions at $+\infty$) and transseries (ordered valued differential fields such as $\mathbb{T}$ and $\mathbb{T}_{\log}$). A Liouville closure of an $H$-field $K$ is a minimal real-closed $H$-field extension of $K$ that is closed under integration and exponential integration. In 2002, Lou van den Dries and Matthias Aschenbrenner proved that every $H$-field $K$ has exactly one, or exactly two, Liouville closures, up to isomorphism over $K$. Recently (in arxiv.org/abs/1608.00997), I was able to determine the precise dividing line of this dichotomy. It involves a technical property of $H$-fields called $\lambda$-freeness. In this talk, I will review the 2002 result of van den Dries and Aschenbrenner and discuss my recent contribution. | ||||

Friday Nov 03 2017 | ||||

16:00-16:50 (MS 6221) | Howard Becker (Caltech) | Ancient Set Theory | ||

Abstract. We consider a 1903 theorem of G. H. Hardy and a more recent question of Peter Nyikos regarding its converse. We answer that question by producing a forcing model of (ZF + there exists an uncountable wellorderable set of reals + omega_1 is regular + there does not exist a ladder system). | ||||

Friday Oct 20 2017 | ||||

16:00-16:50 (MS 6221) | Aristotelis Panagiotopoulos (Caltech) | Games orbits play | ||

Abstract. Classification problems occur in all areas of mathematics. Descriptive set theory provides methods to assign complexity to such problems. Using a technique developed by Hjorth, Kechris and Sofronidis proved, for example, that the problem of classifying all unitary operators $\mathcal{U}(\mathcal{H})$ of an infinite dimensional Hilbert space up to unitary equivalence $\simeq_U$ is strictly more difficult than classifying graph structures with domain $\mathbb{N}$ up to isomorphism.
We present a game--theoretic approach to anti--classification results
for orbit equivalence relations and use this development to reorganize conceptually the proof of Hjorth's turbulence theorem. We also introduce a dynamical criterion for showing that an orbit equivalence relation is not Borel reducible to the orbit equivalence relation induced by a CLI group action; that is, a group which admits a complete left invariant metric (recall that, by a result of Hjorth and Solecki, solvable groups are CLI). We deduce that $\simeq_U$ is not classifiable by CLI group actions.
This is a joint work with Martino Lupini. | ||||

Friday Oct 06 2017 | ||||

16:00-16:50 (MS 6221) | Gabriel Conant (Notre Dame) | On tame expansions of the group of integers | ||

Abstract. I will present results on expansions of the additive group of integers which satisfy certain model theoretic notions of tameness, including stability, simplicity, and dp-minimality. The focus will be on how these model theoretic notions control the combinatorial and number theoretic properties of definable sets. | ||||

Friday Jun 02 2017 | ||||

16:00-16:50 (MS 6221) | Jana Marikova (WIU) | Residue field domination and independence in real closed valued fields | ||

Abstract. Valuations yield a way of understanding (an expansion of) a field in terms of two, often simpler, associated structures, namely its residue field and value group. Here, we consider real closed valued fields, i.e. real closed fields with a valuation determined by a convex subring. We discuss how the types in such a structure are determined by the residue field and value group, and what this implies for notions of independence in this structure.
This is joint work with C. F. Ealy and D. Haskell. | ||||

Friday May 19 2017 | ||||

16:00-16:50 (MS 6221) | John Steel (UC Berkeley) | Absolutely ordinal definable sets | ||

Abstract. We describe some recent work
concerning the hereditarily ordinal definable sets
in models M of the Axiom of Determinacy. Under a
natural iterability hypothesis, HOD^M admits a fine
structural analysis, and hence, for example, satisfies
the GCH. Underlying this fine structural analysis
is a general
comparison theorem for iteration strategies. | ||||

Friday May 05 2017 | ||||

16:00-16:50 (MS 6221) | Scott Cramer (CSUSB) | Woodin's AD-conjecture for I0 | ||

Abstract. We will discuss Woodin's AD-conjecture, which gives a deep
relationship between very large cardinals and determined sets of reals. In particular we will show that the AD-conjecture holds for the axiom I0 and that there are many interesting consequences of this fact. We will also discuss variations of the AD-conjecture and their consequences, including generic absoluteness properties for I0. | ||||

Friday Apr 21 2017 | ||||

16:00-16:50 (MS 6627) | Yann Pequignot (UCLA) | Pi^1_2 sets and countable Borel chromatic numbers | ||

Abstract. Analytic sets enjoy a classical representation theorem based on wellfounded relations. I will explain a similar representation theorem for Pi^1_2 sets due to Marcone. This can be used to answer negatively the primary outstanding question from (Kechris, Solecki and Todorcevic; 1999): the shift graph is not minimal among the graphs of Borel functions which have infinite Borel chromatic number. | ||||

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. |

Click here to see the announcements for older Logic Colloquia.