# UCLA Logic Colloquium

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.

# Logic Colloquium: 09/15/2019 - 09/14/2020

 Wednesday Feb 19 2020 16:00-16:50 (MS 6221) Natasha Dobrinen (University of Denver) TBA Abstract. TBAHide Friday Nov 15 2019 16:00-16:50 (MS 6221) Isaac Goldbring (UC Irvine) TBA Abstract. TBAHide Friday Nov 01 2019 16:00-16:50 (MS 6221) Pieter Spaas (UCLA) TBA Abstract. TBAHide Friday Oct 18 2019 16:00-16:50 (MS 6221) Mate Szabo (Université Paris 1 - Panthéon-Sorbonne) Pepis' and Kalmár's Arguments Against Church's Thesis Abstract. In his famous paper, "An Unsolvable Problem of Elementary Number Theory," Alonzo Church (1936) identified the intuitive notion of effective calculability with the mathematically precise notion of recursiveness. This proposal, known as Church's Thesis, has been widely accepted. In this talk I consider two early arguments against it. Pepis criticized Church's Thesis already in 1937 in his dissertation and in a letter written to Church. I will display recently found documents showing Pepis's stance. The main focus of the talk will be László Kalmár's famous "An Argument Against the Plausibility of Church's Thesis" from 1959. As this paper is quite short, my aim will be to present Kalmár's argument and to fill in missing details based on his general philosophical thoughts on mathematics and his writings published on these issues in Hungarian.Hide Friday Oct 04 2019 16:00-16:50 (MS 6221) Erik Walsberg (UC Irvine) TBA Abstract. TBAHide

# Logic Colloquium: 09/1/2015 - 09/14/2019

 Friday May 31 2019 16:00-16:50 (MS 6221) Joshua Wiscons (Sacramento State) Status of the classification of finite Morley rank actions with a high degree of generic transitivity Abstract. It became clear through work of Borovik and Cherlin in 2008 that the classification theory for groups of finite Morley rank (fMr) is sufficiently developed that general questions about permutation groups of fMr can be settled even though the classification itself remains incomplete. This is a particularly salient direction since the study of uncountably categorical theories is intertwined with binding groups of fMr (acting on realizations of types). Borovik and Cherlin posed several motivating problems, many of which are centered around the notion of generic $n$-transitivity''. In this talk, we will discuss the status and implications of their conjecture that the only transitive and generically $(n+2)$-transitive group of fMr acting on a set of rank $n$ is $operatorname{PGL}_{n+1}$ acting naturally on projective $n$-space. Among other things, we will highlight a general approach to constructing a projective geometry in this context, and we will also illustrate how this conjecture is intertwined with minimal fMr representations of the finite symmetric groups. The talk will begin with a brief overview of the fMr landscape---knowledge of the advanced theory of groups of fMr will be not be required.Hide Friday May 17 2019 16:00-16:50 (MS 6221) Rachid Atmai (Mira Costa College, Oceanside) The search for definable counterexamples to the CH Abstract. We will talk about some partial results and methods which point in the direction of more definable counterexamples of the continuum hypothesis. The goal is to try to identify a canonical generic extension of L(R) in which Theta^L(R)>aleph_3, the axiom of choice holds and whose theory is set-forcing invariant in the presence of large cardinals. From the point of view of Woodin's Omega-logic, the idea behind this work is to identify axioms which mirror forcing axioms and which settle Sigma_2 truth of initial segments of V but under which there are definable counterexamples to CH. We will first review the context and motivation of this investigation and previous results.Hide Friday May 03 2019 16:00-16:50 (MS 6221) Aristotelis Panagiotopoulos (Caltech) Bernoulli shifts for Polish groups and a question of Kechris Abstract. The orbit equivalence relation of any continuous action of a Polish group $G$ has trivial Borel complexity if $G$ is compact. Similarly it is a theorem of A.S. Kechris that whenever a locally--compact Polish group acts continuously on a Polish space, the orbit equivalence relation of the action is essentially countable ---that is, Borel reducible to the orbit equivalence relation of an action of a countable group. A.S. Kechris asked for inverses'' to these results: (1) does every non--compact Polish group admit a continuous action that is not concretely classifiable? (2) does every non--locally--compact Polish group admit a continuous action that is not essentially countable? Question (1) was positively answered by S. Solecki in a paper where he also answered question (2) for the special case where $G$ is the additive group of a separable Banach space. It is also resolved for the case where $G$ is an Abelian pro--countable group, by results of M. Malicki. In this talk I will present recent work on this problem, including a new dynamical proof of question (1) and a positive solution of question (2) in the case of non--Archimedean Polish groups. This is in joint work with J. Zielinski.Hide 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.Hide 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.Hide 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.Hide 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.Hide 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.Hide 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.Hide 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).Hide 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.Hide 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.Hide 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.Hide 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