The Logic seminar generally meets on Fridays, 2–3:30p.m., at Caltech or UCLA. Contact Alexander Kechris or Itay Neeman if you wish to give a talk.

Schedule of talks, going back to Fall
2016, in ** reverse chronological order**:

Friday Mar 16 2018 | ||||

14:00-15:30 (MS 6221) | Alex Kruckman (Indiana U.) | |||

Friday Mar 09 2018 | ||||

14:00-15:30 (MS 6221) | Philip Welch (Bristol U.) | 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 is recursively isomorphic (in the usual sense) to a complete $\Game$-$\Sigma^0_3 $ set. The subsystem of analysis needed for this work is $\Pi^1_3$-$\mathsf{CA_0}$, and there is something suggestive of what may be needed to give a proof theory for this latter theory. | ||||

Friday Mar 02 2018 | ||||

14:00-15:30 (MS 6221) | Vadim Kulikov (University of Helsinki) | Towards non-classifiability of open 3-manifolds | ||

Abstract. It has been shown by Goldman (1971) that the open 2-manifolds can be completely classified by algebraic structures. It is known that the open 3-manifolds are more complicated than the open 2-manifolds as witnessed e.g. by the Whitehead manifolds. This presents us with a question: do open 3-manifolds admit classification by countable structures? The conjecture is "no" and the attempt is to use the theory of turbulence developed by Hjorth, Kechris and others to attack this problem. In this talk I will present results surrounding this conjecture and put them in a broader context of descriptive set theory and Borel-reducibility. Finally I will present some new ideas on how to tackle the conjecture of non-classifiability of open 3-manifolds. |

Friday Feb 16 2018 | ||||

14:00-15:30 (MS 6221) | Matthew Foreman (UCI) | Classifying diffeomorphisms of the torus (part 2) | ||

Abstract. In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of compact manifolds. Notable progress was made by Halmos and von Neumann using spectral invariants. Later, Bernoulli shifts were classified by Ornstein using Kolmogorov's notion of entropy.
In these talks we show that the general von Neumann problem is intractable in a rigorous sense: the collection of pairs of diffeomorphisms of the torus that are isomorphic is complete analytic — in particular not Borel. It follows that there is no inherently countable procedure for determining whether a given pair (S,T) is isomorphic. A problem closely related to the isomorphism problem is the Realization Problem: which abstract measure preserving transformations can be realized as diffeomorphisms of a compact manifold. The only known restriction is that the transformations must have finite entropy. As a byproduct of the anti-classification result stated above, we show that a large class of previously unknown examples can be realized smoothly. For example there are measure distal diffeomorphisms of the 2-torus of arbitrary countable ordinal height, and diffeomorphisms of the torus whose simplex of invariant measures is affinely homeomorphic to an arbitrary compact Choquet simplex. This latter results are proved by establishing a Global Structure Theorem that says that there is a categorical isomorphism between the collection of ergodic transformations with odometer factors and diffeomorphisms realized by the Anosov-Katok method off conjugacy. | ||||

Friday Feb 09 2018 | ||||

14:00-15:30 (MS 6221) | Aristotelis Panagiotopoulos (Caltech) | A combinatorial model for the Menger curve | ||

Abstract. We will represent the universal Menger curve as a canonical quotient of a projective Fraisse limit
and we will illustrate how various homogeneity and universality properties of this space reduce to standard Fraisse theory and basic combinatorics. Finally we will discuss how our approach can be extended to higher dimensions, where it suggests the existence of homology versions of the $n$-dimensional Menger space, as well as a homology version of the Hilbert cube.
This is a joint work with Slawomir Solecki. | ||||

Friday Dec 08 2017 | ||||

14:00-15:30 (MS 6221) | Henry Towsner (U Penn) | Relatively Random First-Order Structures | ||

Abstract. The Aldous-Hoover Theorem gives a characterization of those random processes which generate "exchangeable" first-order structures. Exchangeable structures are precisely those where the "labels" of the points do not matter — they are random structures whose distribution remains the same when we permute the points. They therefore correspond to the structures we get when we sample countable substructures randomly from an ultraproduct; indeed, the original proof of the full Aldous-Hoover Theorem used ultraproducts, and the topic remains intimately tied to the way probability measures behave in ultraproducts.
For some purposes, full exchangeability is too strong: we should consider only those permutations respecting some existing structures. A full Aldous-Hoover theorem is not always possible in this setting, and how much we recover turns out to depend on the amalgamation properties of M. Our goal in this talk is to explain the connection between exchangeability and model theoretic notions, without assuming much prior expertise in either. | ||||

Friday Dec 01 2017 | ||||

14:00-15:30 (MS 6221) | Omer Ben-Neria (UCLA) | Singular stationarity | ||

Abstract. I will talk about Mutually Stationary sequences of sets.
The notion of Mutual Stationarity was introduced by Foreman and Magidor in the 90s, and has been developed as a notion of stationarity for subsets of singular cardinals and as means to address some classical problems in set theory.
We will discuss the basic concepts and describe several known and recent results. | ||||

Friday Nov 03 2017 | ||||

14:00-15:30 (MS 6221) | Matthew Foreman (UCI) | Classifying diffeomorphisms of the torus (part 1) | ||

Abstract. In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of compact manifolds. Notable progress was made by Halmos and von Neumann using spectral invariants. Later, Bernoulli shifts were classified by Ornstein using Kolmogorov's notion of entropy.
In these talks we show that the general von Neumann problem is intractable in a rigorous sense: the collection of pairs of diffeomorphisms of the torus that are isomorphic is complete analytic — in particular not Borel. It follows that there is no inherently countable procedure for determining whether a given pair (S,T) is isomorphic. A problem closely related to the isomorphism problem is the Realization Problem: which abstract measure preserving transformations can be realized as diffeomorphisms of a compact manifold. The only known restriction is that the transformations must have finite entropy. As a byproduct of the anti-classification result stated above, we show that a large class of previously unknown examples can be realized smoothly. For example there are measure distal diffeomorphisms of the 2-torus of arbitrary countable ordinal height, and diffeomorphisms of the torus whose simplex of invariant measures is affinely homeomorphic to an arbitrary compact Choquet simplex. This latter results are proved by establishing a Global Structure Theorem that says that there is a categorical isomorphism between the collection of ergodic transformations with odometer factors and diffeomorphisms realized by the Anosov-Katok method off conjugacy. | ||||

Friday Oct 20 2017 | ||||

14:00-15:30 (MS 6221) | Jeffrey Bergfalk (Cornell U.) | The first omega alephs | ||

Abstract. In the early seventies, several decisive relations were noticed between the homological dimension and the cardinality of a small category - particularly for the cardinalities $\aleph_n$ $(n\in\mathbb{N})$. Those relations, in the case of $n=1$, are best understood in terms of Todorcevic's method of minimal walks on the countable ordinals; the higher-$n$-cases point, similarly, to generalizations of that method, and to $n$-dimensional incompactness principles correlated, for each $n$, to $\aleph_n$. All these are ZFC phenomena. How these principles behave on other cardinals is a largely open question. We discuss these matters, and some of their implications both in set theory and in algebraic topology. | ||||

Friday Oct 13 2017 | ||||

14:00-15:30 (MS 6221) | Kota Takeuchi (University of Tsukuba) | Ramsey property and 2-Order Property | ||

Abstract. The notion of n-dependence was introduced by Shelah motivated to treat vector spaces with a bilinear form along NIP theories. One of the important tools analyzing the property is the Ramsey property of the class of ordered finite hyper graphs. Actually many of known results, preservation theorem under boolean combinations, finding a witness in a single variable and characterizing the property by generalized indiscernible can be implied from the Ramsey property. In this point of view we introduce the notion of 2-Order Property, which lies between Independent Property and 2-Independent Property, related a Ramsey class consisting of ladder-like graphs, and demonstrate that how the Ramsey property works well to prove similar results. The typical examples of 2-dependence are not 2-OP. So far, It is open if 2-OP is strictly weaker than 2-IP. | ||||

Wednesday Oct 04 2017 | ||||

16:00-17:30 (MS 6221) | Tobias Kaiser (Universitaet Passau) | Asymptotics of parameterized exponential integrals given by Brownian motion on globally subanalytic sets | ||

Abstract. (Joint work with Julia Ruppert) Understanding integration in the o-minimal setting is an important and difficult task. By the work of Comte, Lion and Rolin, succeeded by the work of Cluckers and Miller, parameterized integrals of globally subanalytic functions are very well analyzed. But very little is known when the exponential function comes into the game. We consider certain parameterized exponential integrals which come from considering the Brownian motion on globally subanalytic sets. We are able to show nice asymptotic expansions of these integrals.
(Note unusual day and time: Wednesday, 4pm.) | ||||

Friday Sep 29 2017 | ||||

14:00-15:30 (MS 6221) | Dana Bartosova (University of Sao Paulo) | Free actions via graphs | ||

Abstract. A topological group admits a free action if there is a
compact space on which it acts without fixed points. We translate this property into colorability of graphs, which leads us to questions of combinatorial nature. This is a joint work in progress with Vladimir Pestov. | ||||

Friday Jun 09 2017 | ||||

14:00-15:30 (MS 6221) | Danny Nguyen (UCLA) | Complexity of short Presburger arithmetic | ||

Abstract. We study complexity of short sentences in Presburger arithmetic. Here
by "short" we mean sentences with a bounded number of variables,
quantifiers, inequalities and Boolean operations; the input consists
only of the integers involved in the inequalities. The problem is
motivated by the earlier work on counting integer points in polytopes
and their projections in spaces of bounded dimension.
We completely resolve the problem. There were some surprises along the way which we also explain. Joint work with Igor Pak. | ||||

Friday Jun 02 2017 | ||||

14:00-15:30 (MS 6221) | Anush Tserunyan (UIUC) | Ergodic hyperfinite decomposition of countable Borel equivalence relations | ||

Abstract. A countable Borel equivalence relation $E$ on a probability space can always be generated in two ways: as the orbit equivalence relation of a Borel action of a countable group and as the connectedness relation of a locally countable Borel graph, called a graphing of $E$. When $E$ is measure-preserving, graphings provide a numerical invariant called cost, whose theory has been largely developed and used by Gaboriau and others in establishing rigidity results. A well-known theorem of Hjorth states that when $E$ is ergodic, treeable (admits an acyclic graphing), and has integer or infinite cost $n \le \infty$, then it is generated by an a.e. free measure-preserving action of the free group $\mathbf{F}_n$ on $n$ generators. We give a simpler proof of this theorem and a further development of our technique yields a strengthening of Hjorth's theorem: the action of $\mathbf{F}_n$ can be arranged so that each of the $n$ generators alone acts ergodically. This is joint work with Benjamin Miller. | ||||

Friday May 26 2017 | ||||

14:00-15:30 (MS 6221) | Igor Pak (UCLA) | Complexity of short generating functions | ||

Abstract. Short generating functions (GF) are power series defined as sums of terms
$ct^k/(1-t^a)(1-t^b)\dots$. One can think of each term as a GF of a
generalized arithmetic progression. The size of a short GF $A(t)$ is
defined as the total bit length of the parameters $a,b,c,k,\dots$. We study
the problem whether a given GF has a short GF presentation of
polynomial size.
This turn out to be a hard problem both mathematically and computationally. We resolve it modulo some complexity assumptions. Notably, we show that the truncated theta function $\sum_{k<N} t^{k^2}$ does NOT have a short GF presentation of polynomial size unless #P is in FP/poly. In the talk, I will spend much of the time giving a survey and motivating the problem. I will explain the connections to Presburger arithmetic, integer programming, number theory and discrete geometry. At the end, I will outline the proof. This is joint work with Danny Nguyen. No familiarity with the subject is assumed. | ||||

Friday May 19 2017 | ||||

14:00-15:30 (MS 6221) | Matthew Harrison-Trainor (UC Berkeley) | Describing Finitely Generated Structures | ||

Abstract. Every countable structure has an infinitary sentence which describes it up to isomorphism among countable structures. We can characterize the complexity of a structure by the complexity of the simplest description of that structure. A finitely generated structure always has a $\Sigma_3$ description. We will show that there is a finitely generated group which has no simpler description, and talk about a number of other results of this kind. | ||||

Friday May 12 2017 | ||||

14:00-15:30 (MS 6221) | Wai Yan Pong (CSUDH) | Independence of arithmetic functions | ||

Abstract. We examine various notions of dependence of arithmetic functions via Ax's theorem on differential Schanuel Conjecture. We will sample of several results in the literature and show how they can be generalized. | ||||

Friday Apr 28 2017 | ||||

14:00-15:30 (MS 6221) | Michał Tomasz Godziszewski (University of Warsaw) | Generalizations of Tennebaum phenomena for computable quotient presentations | ||

Abstract. A computable quotient presentation of a mathematical structure $\mathbb{A}$ consists of a computable structure on the natural numbers $(\mathbb{N}, \star, \ast, \ldots)$ (meaning that the operations and relations of the structure are computable) and an equivalence relation $E$ on $\mathbb{N}$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $(\mathbb{N}, \star, \ast, \ldots)_{/E}$ is isomorphic to the given structure
$\mathbb{A}$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure.
In 2016 Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. He outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation E or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo E. We engage with two conjectures that Khoussainov had made and prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+, \cdot, \leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. Concluding from that, we indicate how the program of computable quotient presentations has difficulties with purely relational structures (as opposed to algebras). This is joint work with Joel David Hamkins, GC CUNY. | ||||

Friday Feb 10 2017 | ||||

14:00-15:30 (MS 6221) | Vassilis Gregoriades (U. Turin) | The problem of HYP-isomorphism between recursive Polish spaces | ||

Abstract. It is a fundamental fact of descriptive set theory that every uncountable Polish space is Borel-isomorphic to the Baire space. The effective version of the latter is true as long as the given (recursive) Polish space has no isolated points. Given the importance of this fact in the development of effective descriptive set theory, it is natural to ask if this is also true in general. This however turns out to be false; in fact not only there are recursive uncountable Polish spaces, which are not effectively Borel-isomorphic to the Baire space, but the natural notion of effective Borel reduction carries a rich structure. In this talk we present some central results about these spaces and we describe the main techniques for proving them. | ||||

Friday Jan 27 2017 | ||||

14:00-15:30 (MS 6221) | Zoltán Vidnyánszky (York U. and U. Toronto) | Characterization of order types representable by Baire class 1 functions | ||

Abstract. Let $\mathcal{F}$ be a family of real valued functions on a Polish space $X$. A natural partial ordering on $\mathcal{F}$ is the pointwise ordering, $\leq_p$. The description of linearly ordered subsets of $(\mathcal{F},\leq_p)$ reveals a lot of information about the poset itself. It turns out that the first interesting family of functions to consider is the family of Baire class 1 functions, $\mathcal{B}_1(X)$. Answering a question of Laczkovich, we give a complete combinatorial characterization of the linearly ordered subsets of $(\mathcal{B}_1(X),\leq_p)$. | ||||

Friday Jan 20 2017 | ||||

14:00-15:30 (MS 6221) | Minh Tran (UIUC) | Tame structures via multiplicative character sums over constructible subsets of finite fields | ||

Abstract. We study the model theory of the structure $(\mathbb{F}; <)$ where $\mathbb{F}$ is the algebraic closure of the field of $p$ elements and $<$ is an ordering on $\mathbb{F}^\times$ induced by an injective group homomorphism $\chi: \mathbb{F}^\times \to \mathbb{C}^\times$. Various notions of model theoretic tameness of the structure turn out to be consequences of number theoretic behaviors of the character map $\chi$. The results obtained are attempts to bring number theoretic phenomena of this type into model theory, following a suggestion by van den Dries, Hrushovski and Kowalski. | ||||

Friday Jan 13 2017 | ||||

14:00-15:30 (MS 6221) | Spencer Unger (UCLA) | Borel circle squaring | ||

Abstract. We give a completely constructive solution to Tarski's circle squaring problem.
More generally, we prove a Borel version of a general equidecomposition theorem
due to Laczkovich. This answers a question of Wagon. Our proof
uses ideas from the study of flows in networks, and a recent result of Gao,
Jackson, Khrone, and Seward on special types of witnesses to the
hyperfiniteness of free Borel actions of $\mathbb{Z}^d$. This is joint work
with Andrew Marks. | ||||

Friday Nov 18 2016 | ||||

14:00-15:30 (MS 6221) | Anton Bernshteyn (UIUC) | Measurable graph colorings and the Lovasz Local Lemma | ||

Abstract. The Lovasz Local Lemma, or the LLL for short, is an immensely important tool in probabilistic combinatorics. It is typically used to demonstrate the existence of a function $f \colon X \to Y$ satisfying certain ``local'' combinatorial constraints, where $X$ is an underlying combinatorial structure (e.g. a graph) and $Y$ is a (usually finite) set (e.g. a set of colors). Since its first appearance in 1975, the LLL found numerous applications in combinatorics, some of them straightforward, and some highly technical and sophisticated. In this talk, we will consider the following question: Assume $X$ is equipped with a standard Borel structure and a probability Borel measure $\mu$. Can the function $f$, whose existence is asserted by the LLL, be $\mu$-measurable? Most of our attention will be focused on the situation when the combinatorial structure on $X$ is in some sense ``induced'' by a measure-preserving action of a countable group $\Gamma$. We will see that for some actions the answer is positive (which yields measurable analogs of various combinatorial consequences of the LLL for such actions). On the other hand, for some actions the measurable version of the LLL fails; in fact, if $\Gamma$ is amenable, then a probability measure-preserving action of $\Gamma$ satisfies a measurable analog of the LLL if and only if it has infinite entropy. | ||||

Friday Oct 28 2016 | ||||

15:00-15:50 (MS 6221) | Alessandro Achille (UCLA CS Dept.) | A Vietoris-Smale mapping theorem for the homotopy of hyperdefinable sets | ||

Abstract. Classical results of Vietoris (1927), Begle (1950), Smale (1950) and Dugundji (1969) allow to compare the homotopy of two topological spaces $X$ and $Y$ whenever a map $f : X \rightarrow Y$ with sufficiently trivial fibers is given (acyclic, contractible, etc.).
We apply similar techniques in o-minimal expansions of fields to compare the (o-minimal) homotopy of a definable set $X$ with the homotopy of some of its bounded hyperdefinable quotients $X/E$. As a special case we obtain some homotopy comparison results due to Delfs-Knebush (semialgebraic case) and Baro-Otero and we strengthen previous results on the higher homotopy groups of $G/G^{00}$, where $G$ is a definably compact group and $G^{00}$ is the infinitesimal subgroup. Under suitable assumptions on $E$ we show that $\dim(X) = \dim_R(X/E)$. In particular we obtain a new proof of Pillay's group conjecture $\dim(G) = \dim_R(G/G^{00})$ largely independent of the group structure of $G$. Joint work with Alessandro Berarducci. (Note unusual starting time, 3pm.) | ||||

Friday Oct 14 2016 | ||||

14:00-15:30 (MS 6221) | Ronnie Chen (Caltech) | Structurability by locally finite contractible simplicial complexes | ||

Abstract. By a result of Jackson, Kechris, and Louveau, every treeable compressible countable Borel equivalence relation (CBER) admits a treeing where each vertex has degree at most 3. We generalize this to show that every compressible CBER structurable by $n$-dimensional contractible simplicial complexes is structurable by $n$-dimensional contractible simplicial complexes in which each vertex is contained in at most $c_n$ simplices, where $c_n$ depends only on the dimension $n$. The proof is based on a classical result of Whitehead in algebraic topology. | ||||

Friday Sep 16 2016 | ||||

14:00-15:30 (MS 6221) | Haim Horowitz (Hebrew U) | On the non-existence and definability of mad families | ||

Abstract. By an old result of Mathias, there are no mad families in the Solovay model constructed by the Levy collapse of a Mahlo cardinal. By a recent result of Törnquist, the same is true in the classical model of Solovay as well. In a recent paper, we show that ZF+DC+"there are no mad families" is actually equiconsistent with ZFC. I'll present the ideas behind the proof in the first part of the talk.
In the second part of the talk, I'll discuss the definability of maximal eventually different families and maximal cofinitary groups. In sharp contrast with mad families, it turns out that Borel MED families and MCGs can be constructed in ZF. Finally, I'll present a general problem in Borel combinatorics whose solution should explain the above difference between mad and maximal eventually different families, and I'll show how large cardinals must be involved in such a solution. This is joint work with Saharon Shelah. |