2017

date	speaker	title
2017-01-12	Riccardo Camerlo (Politecnico di Torino, Italy)	The density function: some remarks, results, and open problems
Given a Radon metric space $(X,d,\mu )$ and a measurable $A\subseteq X$, the density function associated with $A$ is the (partial) function on $X$ defined by \[ \mathcal D_A(x)=\lim_{\varepsilon\rightarrow 0^+} \frac{\mu (A\cap \mathcal B_{\varepsilon}(x))}{\mu ( \mathcal B_{\varepsilon }(x))} \] where $ \mathcal B_{\varepsilon }(x)$ is the open ball centered at $x$ of radius $\varepsilon $. I will discuss properties of this function relevant to descriptive set theory, especially for Cantor space and the real line, together with some open questions. Most results are joint work with A. Andretta and C. Costantini.
2017-01-19	Leandro Aurichi (University of São Paulo, Brazil)	A characterization for productively ccc spaces
We will discuss when a space $X$ is such that $X \times Y$ is ccc for every ccc space $Y$. We will present a characterization for this property and discuss some possible applications. This is a joint work with R. Mezabarba.
2017-01-26	Michal Garlík (Czech Academy of Sciences)	Bounded arithmetic and restricted reduced products
We present a construction of models of bounded arithmetic that yields nonelementary extensions but does not introduce new lengths. The construction has the form of a restricted reduced product. As an application we show that under the assumption of the existence of a one-way permutation $g$ hard against polynomial-size circuits, two similar-looking bounded arithmetic theories, $strict R^1_2(g)$ and $R^1_2(g)$, are in fact distinct. In particular, if such a permutation is definable by a term in the language of $R^1_2$, then $strict R^1_2$ is weaker than $R^1_2$. We discuss some strengthenings of this result.
2017-03-02	Brent M. Cody (Virginia Commonwealth University, Richmond, USA)	Rigid Ideals
An ideal $I$ on a cardinal $\kappa$ is called rigid if all automorphisms of $P(\kappa)/I$ are trivial. Woodin proved that if $MA_{\omega_1}$ holds, then every saturated ideal on $\omega_1$ is rigid. In all previously known models containing rigid saturated ideals, GCH fails. In this talk I will discuss recent joint work with Monroe Eskew in which we prove that the existence of a rigid saturated ideal on $\mu^+$, where $\mu$ is an uncountable regular cardinal, is consistent with GCH, relative to the existence of an almost huge cardinal. Our proof involves adapting the Friedman-Magidor coding forcing (from the number of normal measures paper) to code a generic for a universal collapsing poset which forces an almost huge cardinal $\kappa$ to become the successor of an uncountable regular $\mu$. Our forcing is ${<}\mu$-distributive and in the resulting forcing extension, GCH holds and there is a saturated ideal $I$ on $\mu^+$ such that in any forcing extension by $\mathbb{P}=P(\mu^+)/I$ there is a unique generic filter for $\mathbb{P}$, hence $I$ is rigid.
2017-03-09	Yizheng Zhu (Universität Münster, Germany)	Projective sets and inner models
The collection of projective sets of reals is the smallest one containing all the Borel sets and closed under complements and continuous images. The Axiom of Projective Determinacy (PD) is the correct axiom that settles the regularity properties of projective sets. Inner model theory provides a systematic way of studying the projective sets under PD. In this talk, we describe some recent progress in this direction. A key theorem is the following inner-model-theoretic characterization of the canonical model associated to $\Sigma^1_3$: Let $\mathcal{O}_{\Sigma^1_{3}}$ be the universal $\Sigma^1_3$ subset of $u_\omega$ in the sharp codes for ordinals in $u_\omega$. Let $M_{1,\infty}$ be the direct limit of iterates of $M_1$ via countable trees and let $\delta_{1,\infty}$ be the Woodin cardinal of $M_{1,\infty}$. Then $M_{1,\infty}\|\delta_{1,\infty} = L_{u_\omega}[\mathcal{O}_{\Sigma^1_{3}}]$. This theorem paves the way for further study of $\Sigma^1_3$ sets using inner model theory. It also generalizes to arbitrary $\Sigma^1_{2n+1}$ and $M_{2n-1,\infty}$.
2017-03-16	Vassilis Gregoriades (University of Turin, Italy)	The Dyck and Preiss Separation Uniformly
The typical example of a uniformity-type result in descriptive set theory is the Souslin-Kleene Theorem, which says that the separation property of the class of analytic sets can be witnessed by a recursive function in the codes. An important consequence of the latter is the extension of the result HYP is effectively bi-analytic, in all recursive Polish spaces. In this talk we present the uniform version of two more separation theorems about analytic sets by Dyck and Preiss. The former deals with the monotone analytic subsets of the Cantor space, and the latter with the convex analytic subsets of $\mathbb{R}^n$. (A subset of the powerset of the naturals is monotone if it is closed upwards under inclusion.) We show that the separation can be realized by a recursive and a HYP function in the codes respectively. As in the case of the Souslin-Kleene Theorem, these results have the analogous constructive consequence. It follows for example, that every HYP convex subset of $\mathbb{R}^n$ can be obtained from the class of HYP compact convex sets by taking HYP increasing unions and HYP intersections.
2017-03-23	Michał Tomasz Godziszewski (University of Warsaw, Poland)	Computable quotient presentations of models of arithmetic and set theory
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 discussed some questions and results in this area. Part of this 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 address 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.
2017-03-30	Luca Motto Ros (University of Turin, Italy)	Ultrametric spaces, isometry, and isometry groups
Gao and Kechris proposed in 2003 two somewhat related problems concerning ultrametric spaces, namely: 1) Determine the complexity of the isometry relation on locally compact Polish ultrametric spaces. 2) Characterize the Polish groups that are isomorphic (as topological groups) to the isometry group of some Polish ultrametric space. We will present a construction strictly relating ultrametric spaces and a special kind of trees which helps in tackling these two problems. This technique applies to both separable and non-separable complete ultrametric spaces, and allows us to e.g. show that they are unclassifyiable up to isometry even when considering only discrete spaces. (Joint work with R. Camerlo and A. Marcone.)
2017-04-06	Peter Holy (University of Bonn, Germany)	Small embedding characterizations for large cardinals, and internal large cardinals
Many notions of large cardinals are characterized in terms of the existence of certain elementary embeddings with the large cardinal in question as their critical point. A small embedding characterization of a large cardinal notion is one that requires the existence of certain elementary embeddings that map their critical point to the relevant large cardinal. One classic example of such a small embedding characterization is Magidor's small embedding characterization of supercompactness. We show that many other large cardinal notions have small embedding characterizations, in particular also large cardinal notions for which no embedding characterizations have been known to exist at all. In the second part of this talk, I will then sketch an application of small embedding characterizations, that yields what we call internal large cardinals, which essentially describe what is left of large cardinals after they have been destroyed or collapsed by sufficiently nice forcing. The basic idea is to lift the small embeddings that characterize the initial large cardinals. This is joint work with Philipp Lücke.
2017-04-26	Matteo Viale (Università di Torino, Italy)	Useful axioms

2017-04-27	Alberto Marcone (Università di Udine, Italy)	Some results about the higher levels of the Weihrauch lattice
In the last few years Weihrauch reducibility and the ensuing Weihrauch lattice have emerged as a useful tool for studying the complexity of mathematical statements viewed as "problems" or multi-valued functions. This approach complements nicely the reverse mathematics approach, and has been very successful for statements which are provable in ${\mathsf{ACA}_0}$. The study the Weihrauch lattice for functions arising from statements laying at higher levels, such as ${\mathsf{ATR}_0}$, of the reverse mathematics spectrum is instead in its infancy. We will present some results (work in progress with my graduate student Andrea Cettolo). In some cases we obtain the expected finer classification, but in other we observe a collapse of statements that are not equivalent with respect to provability in subsystems of second order arithmetic. This is in part due to the increased syntactic complexity of the statements. Our preliminary results deal with comparability of well‑orderings, $\Sigma^1_1$‑separation, and $\Delta^1_1$‑comprehension.
2017-05-04	Víctor Torres-Pérez (TU Wien)	Rado's Conjecture, an alternative to forcing axioms?
Rado's Conjecture (RC) in the formulation of Todorcevic is the statement that every tree $T$ that is not decomposable into countably many antichains contains a subtree of cardinality $\aleph_1$ with the same property. Todorcevic has shown the consistency of this statement relative to the consistency of the existence of a strongly compact cardinal. Todorcevic also showed that RC implies the Singular Cardinal Hypothesis, a strong form of Chang's Conjecture, the continuum is at most $\aleph_2$, the negation of $\Box(\theta)$ for every regular $\theta\geq\omega_2$, etc. These implications are very similar to the ones obtained from traditional forcing axioms such as MM or PFA. However, RC is incompatible even with $MA(\aleph_1)$. In this talk we will take the opportunity to give an overview of our results with different coauthors obtained in the last few years together with recent ones, involving RC, certain weak square principles and instances of tree properties. These new implications seem to continue suggesting that RC is a good alternative to forcing axioms. We will discuss to which extent this may hold true and where we can find some limitations. We will end the talk with some open problems and possible new directions.
2017-05-11	Stefan Hoffelner (KGRC)	$\text{NS}_{\omega_1}$ saturated and a $\Sigma^{1}_{4}$-definable wellorder on the reals
The investigation of the saturation of the nonstationary ideal $\text{NS}_{\omega_1}$ has a long tradition in set theory. In the early 1970's K. Kunen showed that, given a huge cardinal, there is a universe in which $\text{NS}_{\omega_1}$ is $\aleph_2$-saturated. The assumption of a huge cardinal has been improved in the following decades, using very different techniques, by many set theorists until S. Shelah around 1985 realized that already a Woodin cardinal is sufficient for the consistency of the statement “$\text{NS}_{\omega_1}$ is saturated”. Due to work of H. Woodin on the one hand and G. Hjorth on the other, there is a surprising and deep connection between definable wellorders of the reals and the saturation of $\text{NS}_{\omega_1}$: In a universe with a measurable cardinal and $\text{NS}_{\omega_1}$ saturated, it is impossible to have a $\Sigma^1_3$-wellorder. This leads naturally to the question whether there is a universe in which $\text{NS}_{\omega_1}$ is saturated and its reals have a $\Sigma^1_{4}$-wellorder. In my talk I will outline a proof that this is indeed the case; assuming the existence of $M_1^{\#}$ there is a model with a $\Sigma^1_{4}$-definable wellorder on the reals in which $\text{NS}_{\omega_1}$ is saturated. This is joint work with Sy-David Friedman.
2017-05-18	Victoria Gitman (CUNY Graduate Center, New York, USA)	A model of second-order arithmetic with the choice scheme in which $\Pi^1_2$-dependent choice fails
In second-order arithmetic, the choice scheme is the scheme of assertions, for every second-order formula $\varphi(n,X,A)$, that if for every $n$ there is a set $X$ such that $\varphi(n,X,A)$ holds, then there is a single set $Y$ whose $n$-th slice $Y_n$ witnesses $\varphi(n,Y_n,A)$. While full second-order arithmetic ${\textrm Z}_2$ implies the choice scheme for $\Sigma^1_2$-assertions, the reals of the Feferman-Lévy model form a model of ${\textrm Z}_2$ in which $\Pi^1_2$-choice fails. The dependent choice scheme is the analogue ${\textrm DC}$ for second-order arithmetic and it asserts, for every second-order formula $\varphi(X,Y,A)$, that if for every set $X$ there is another set $Y$ such that $\varphi(X,Y,A)$ holds, then there is a single set $Z$, viewed as an $\omega$-sequence of sets, such that for every $n$, $\varphi(Z\restrict n,Z_n,A)$ holds. The theory ${\textrm Z}_2$ implies $\Sigma^1_2$-dependent choice, and Simpson has conjectured that there is a model of ${\textrm Z}_2$ with the choice scheme in which $\Pi^1_2$-dependent choice fails. We prove Simpson's conjecture by constructing a symmetric submodel of a forcing extension in which ${\textrm AC}_\omega$ holds, but ${\textrm DC}$ fails for a $\Pi^1_2$-definable relation on the reals. We force over $L$ with a tree iteration of Jensen's forcing (a ccc subposet of Sacks forcing adding a unique generic real) along the tree ${}^{\lt\omega}\omega_1$, adding a tree, isomorphic to ${}^{\lt\omega}\omega_1$, of finite sequences of reals ordered by extension, such that that the sequences on level $n$ are $L$-generic for the $n$-length iteration of Jensen's forcing. We extend the uniqueness of generic reals properties of Jensen's forcing (obtained earlier by Jensen and later by Lyubetsky and Kanovei) by showing that in the tree iteration extension, the only sequences of reals $L$-generic for the $n$-length iteration of Jensen's forcing are those explicitly added on level $n$ of the generic tree. The uniqueness property implies that the generic tree is $\Pi^1_2$-definable. The theorem arose out of our attempts to separate the analogues of the choice scheme and the dependent choice scheme over Kelley-Morse set theory, and we conjecture that an appropriate generalization of our arguments will now achieve this result. This is joint work with Sy-David Friedman.
2017-06-08	Zoltán Vidnyánszky (York University, Toronto, Canada and Toronto University)	Borel chromatic numbers: finite vs infinite
One of the most interesting results of Borel graph combinatorics is the $G_0$ dichotomy, i. e., the fact that a Borel graph has uncountable Borel chromatic number if and only if it contains a Borel homomorphic image of a graph called $G_0$. It was conjectured that an analogous statement could be true for graphs with infinite Borel chromatic number. Using descriptive set theoretic methods we answer this question and a couple of similar questions negatively, showing that one cannot hope for the existence of a Borel graph whose embeddability would characterize Borel (or even closed) graphs with infinite Borel chromatic number. We will also discuss a positive result and its relation to Hedetniemi's conjecture.
2017-06-22	David Schrittesser (University of Copenhagen, Denmark)	News on mad families
This talk is about two results on mad families (dating from this year): Firstly, in joint work with Karen Bakke Haga and Asger Törnquist, we link madness of certain definable sets to forcing and use this to show that under the Axiom of Projective Determinacy there are no projective mad families. Moreover, the results generalize: we may replace "being almost disjoint" by "being J-disjoint", for certain ideals J on the natural numbers including, e.g., Fin x Fin. The other result is an improvement of Horowitz and Shelah's construction of a Borel maximal eventually different family of functions. We obtain a closed such family, and the result even generalizes to certain compact spaces.
2017-06-29	Peter Nyikos (University of South Carolina, Columbia, USA)	Cardinality restrictions on some kinds of locally compact spaces
In what follows, "space" means "Hausdorff ($T_2$) topological space." Some of the theorems and problems to be discussed include: Theorem 1. It is ZFC-independent whether every locally compact, $\omega_1$-compact space of cardinality $\aleph_1$ is the union of countably many countably compact spaces. [‘$\omega_1$-compact’ means that every closed discrete subspace is countable. This is obviously implied by being the union of countably many countably compact spaces, but the converse is not true.] Problem 1. Is it consistent that every locally compact, $\omega_1$-compact space of cardinality $\aleph_2$ is the union of countably many countably compact spaces? Problem 2. Is ZFC enough to imply that there is a normal, locally countable, countably compact space of cardinality greater than $\aleph_1$? Problem 3. Is it consistent that there exists a normal, locally countable, countably compact space of cardinality greater than $\aleph_2$? The spaces involved in Problem 2 and Problem 3 are automatically locally compact, because regularity is already enough to give every point a countable countably compact (hence compact) neighborhood. Problem 4 [Problem 5]. Is there an upper bound on the cardinalities of regular [resp. normal], locally countable, countably compact spaces? Theorem 2. The axiom $\square_{\aleph_1}$ implies that there is a normal, locally countable, countably compact space of cardinality $\aleph_2$. The statement in Theorem 1 was shown consistent by Lyubomyr Zdomskyy, assuming $\mathfrak p > \aleph_1$ plus P-Ideal Dichotomy (PID). Counterexamples have long been known to exist under $\mathfrak b = \aleph_1$, under $\clubsuit$, and under the existence of a Souslin tree. Theorem 2 may be the first application of $\square_{\aleph_1}$ to construct a topological space whose existence in ZFC is unknown.
2017-06-29	Witold Marciszewski (University of Warsaw, Poland)	On factorization properties of function spaces
For a Tychonoff space $X$, by $C_p(X)$ we denote the space of all continuous real-valued functions on $X$, equipped with the topology of pointwise convergence. One of the important questions (due to A.V. Arhangel'skii), stimulating the theory of $C_p$-spaces for almost 30 years and leading to interesting results in this theory, is the problem whether the space $C_p(X)$ is (linearly, uniformly) homeomorphic to its own square $C_p(X)\times C_p(X)$, provided $X$ is an infinite compact or metrizable space. In my talk I will present some recent developments concerning these type of questions. In particular, I will show a metrizable counterexample to this problem for homeomorphisms. I will also show that, for every infinite zero-dimensional Polish space $X$, spaces $C_p(X)$ and $C_p(X)\times C_p(X)$ are uniformly homeomorphic. This is a joint research with Rafal Gorak and Mikolaj Krupski.
2017-08-17	Yijia Chen (Fudan University, Shanghai, People's Republic of China)	Slicewise definability in first-order logic with bounded quantifier rank
For every $q\in \mathbb{N}$ let $\text{FO}_q$ denote the class of sentences of first-order logic $\text{FO}$ of quantifier rank at most $q$. If a graph property can be defined in $\text{FO}_q$, then it can be decided in time $O(n^q)$. Thus, minimizing $q$ has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size $k$. Usually this can only be expressed by a sentence of quantifier rank at least $k$. We use the color-coding method to demonstrate that some (hyper)graph problems can be defined in $\text{FO}_q$, where $q$ is independent of $k$. It is crucial for our results that the $\text{FO}$-sentences have access to built-in addition and multiplication. It is known that then $\text{FO}$ corresponds to the circuit complexity class uniform $\text{AC}^0$. We explore the connection between the quantifier rank of $\text{FO}$-sentences and the depth of $\text{AC}^0$-circuits, and prove that $\text{FO}_q \subsetneq \text{FO}_{q+1}$ for structures with built-in addition and multiplication.
2017-09-26	Kameryn Williams (Graduate Center, City University of New York (CUNY), USA)	The exact strength of the class forcing theorem
Gödel–Bernays set theory $\mathsf{GBC}$ proves that sufficiently nice (i.e. pretame) class forcings satisfy the forcing theorem—that is, these forcing notions $\mathbb P$ admit forcing relations $\Vdash_\mathbb{P}$ satisfying the recursive definition of the forcing relation. It follows that statements true in the corresponding forcing extensions are forced and forced statements are true. But there are class forcings for which having their forcing relation exceeds $\mathsf{GBC}$ in consistency strength. So $\mathsf{GBC}$ does not prove the forcing theorem for all class forcings. This is in contrast to the well-known case of set forcing, where $\mathsf{ZFC}$ proves the forcing theorem for all set forcings. On the other hand, stronger second-order set theories such as Kelley–Morse set theory $\mathsf{KM}$ prove the forcing theorem for all class forcings, providing an upper bound. What is the exact strength of the class forcing theorem? I will show that, over $\mathsf{GBC}$, the forcing theorem for all class forcings is equivalent to $\mathsf{ETR}_\mathrm{Ord}$ the principle of elementary transfinite recursion for recursions of height $\mathrm{Ord}$. This is equivalent to the existence of $\mathrm{Ord}$-iterated truth predicates for first-order truth relative to any class parameter; which is in turn equivalent to the existence of truth predicates for the infinitary languages $\mathcal L_{\mathrm{Ord}, \omega}(\in, A)$ allowing any class parameter $A$. This situates the class forcing theorem precisely in the hierarchy of theories between $\mathsf{GBC}$ and $\mathsf{KM}$. This is joint work with Victoria Gitman, Joel Hamkins, Peter Holy, and Philipp Schlicht.
2017-10-05	Mohammad Golshani (Institute for Research in Fundamental Sciences (IPM), Tehran, Iran)	Some properties of Cohen and random reals
We discuss some properties of Cohen and random reals. We prove a general combinatorial fact about them which in particular implies that they are large, they contain arbitrary large arithmetical or geometrical progressions, satisfy the Hindman's conclusion and so on. We also show that they are wild in the sense of o‑minimal theory. We also investigate how badly approximable are they by algebraic numbers. This is a work in progress with Will Brian.
2017-10-12	Yizheng Zhu (Universität Münster, Germany)	Iterates of $M_1$
Assume boldface $\boldsymbol{\Delta}^1_{3}$-determinacy. Let $L_{\kappa_3}[T_2]$ be the admissible closure of the Martin-Solovay tree and let $M_{1,\infty}$ be the direct limit of $M_1$ via countable trees. We show that $L_{\kappa_3}[T_2] \cap V_{u_{\omega}} = M_{1,\infty} \| u_{\omega}$. This is a continuation of my [/2017/Talk_03-09_a.html talk] on 9th, March.
2017-10-19	Monroe Eskew (KGRC)	Global Chang’s Conjecture
Instances of Chang’s Conjecture (CC) can be seen as a generalization of the Loweheim-Skolem Theorem to a logic in between those the first and second order. Foreman asked how far the analogy with Lowenheim-Skolem can go, specifically whether a global version of CC is consistent. In joint work with Yair Hayut, the speaker answered Foreman’s question affirmatively, and in the process lowered the known upper bounds on consistency strength for many instances of CC. We will discuss the results, as well as some barriers that singular cardinal combinatorics impose on the possibility of a stronger global CC.
2017-11-09	Zoltán Vidnyánszky (KGRC)	Random elements of large groups
The automorphism groups of countable homogeneous structures are usually interesting objects from group theoretic and set theoretic perspective. The description of typical (with respect to category) elements of such groups is a flourishing topic with a wide range of applications. A natural question is that whether there exist measure theoretic analogues of these results. An obvious obstacle in this direction is that such automorphism groups are often non-locally compact, hence there is no natural translation invariant measure on them. Christensen introduced the notion of Haar null sets in non-locally compact Polish groups which is a well-behaved generalisation of the null ideal to such groups. Using Christensen's Haar null ideal it makes sense to consider the properties of a random element of the group. We investigate these properties, giving a full description of random elements in the case of the automorphism group of the random graph and the rational numbers (as an ordered set).
2017-11-16	Paul Ellis (Manhattanville College, New York, USA)	Cycle Reversions and Dichromatic Number in (Infinite) Tournaments
The dichomatic number for a digraph is the least number of acyclic subgraphs needed to cover the graph. In 2005, Pierre Charbit showed that by iterating the operation $\{\{$select a directed cycle, and reverse the direction of each arc in it$\}\}$ that the dichromatic number in any finite digraph can be lowered to 2. This is optimal, as a single directed cycle will always have dichromatic number 2. Recently, Daniel Soukup and I showed that the same is true for infinite tournaments of any cardinality, and in fact, we proved this by induction. Along the way to proving this, we uncovered some nice structural facts about infinite digraphs that we think are of more general interest. While this talk will be mostly graph theoretic in flavor, we did need to put on our set theory glasses to distinguish between the singular and regular cases in the induction. I should note that the question remains open for arbitrary inifinite digraphs, even those of countable cardinality.
2017-11-23	Russell Miller (Queens College, City University of New York (CUNY), USA)	Isomorphism and Classification for Countable Structures
We describe methods of classifying the elements of certain classes of countable structures: algebraic fields, finite-branching trees, and torsion-free abelian groups of rank 1. The classifications are computable homeomorphisms onto known spaces of size continuum, such as Cantor space or Baire space, possibly modulo a standard equivalence relation. The classes involved have arithmetic isomorphism problems, making such classifications possible, and the results help suggest exactly which properties of their elements must be known in order to produce a nice classification. For algebraic fields, this homeomorphism makes it natural to transfer Lebesgue measure from Cantor space onto the class of these fields, although there is another probability measure on the same class which seems in some ways more natural than Lebesgue measure. We will discuss how certain properties of these fields — notably, relative computable categoricity — interact with these measures: the basic result is that only measure-0-many of these fields fail to be relatively computably categorical. (The work on computable categoricity is joint with Johanna Franklin.)
2017-11-30	Maxwell Levine (KGRC)	Forcing Square Sequences
In the 1970's, Jensen proved that Gödel's constructible universe $L$ satisfies a combinatorial principle called $\square_\kappa$ for every uncountable cardinal $\kappa$. Its significance is partially in that it clashes with the reflection properties of large cardinals—for example, if $\mu$ is supercompact and $\kappa \ge \mu$ then $\square_\kappa$ fails—and so it characterizes the minimality of $L$ in an indirect way. Schimmerling devised an intermediate hierarchy of principles $\square_{\kappa,\lambda}$ for $\lambda \le \kappa$ as a means of comparing a given model of set theory to $L$, the idea being that a smaller value of $\lambda$ yields a model that is more similar to $L$ at $\kappa$. Cummings, Foreman, and Magidor proved that for any $\lambda<\kappa$, $\square_{\kappa,\lambda}$ implies the existence of a PCF-theoretic object called a very good scale for $\kappa$, but that $\square_{\kappa,\kappa}$ (usually denoted $\square_\kappa^\ast$) does not. They asked whether $\square_{\kappa,<\kappa}$ implies the existence of a very good scale for $\kappa$, and we resolve this question in the negative. We will discuss the technical background of the problem, provide a complete solution, and discuss further avenues of research.
2017-12-07	Hubie Chen (Birkbeck, University of London, UK)	Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
QBF is the problem of deciding truth/falsity of a quantified propositional formula (assumed to be in prenex CNF form). Recent years have seen focused efforts to understand how QBF can be solved in practice, and to develop theoretical underpinnings for such solving. If one looks at typical proof systems for certifying QBF falsity, such as Q-resolution, a dilemma is encountered: lower bounds for Q-resolution are implied immediately by lower bounds for resolution, yet this says nothing about Q-resolution's ability to cope with quantifier alternation—and moreover clashes severely with the contemporary QBF view of SAT as “easy”. In this talk, we will discuss this dilemma and present a possible way to escape it. In particular, we present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified propositional formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res which is based on the established proof system QU-resolution. Our main technical results include an exponential separation of the tree-like and general versions of relaxing QU-res, and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity. This talk will focus on a conceptual discussion of the work's motivation, the framework and the main definitions.
2017-12-14	Moritz Müller (KGRC)	On the relative strength of finitary combinatorial principles
Define a finitary combinatorial principle to be a first-order sentence which is valid in the finite but falsifiable in the infinite. We aim to compare the strength of such principles over a weak arithmetic. We distinguish “weak” and “strong” principles based on their behaviour with respect to finite structures that are only partially defined. The talk sketches a forcing proof of a theorem stating that over relativized $T^1_2$ “weak” principles do not imply “strong” ones.