2015

date	speaker	title
2015-01-08	Vera Fischer (TU Wien)	Measure, category and projective wellorders
We will see that every admissible assignment of $\aleph_1$ and $\aleph_2$ to the invariants of measure and category is consistent with the existence of a $\Delta^1_3$ definable wellorder on the reals.
2015-01-15	Daniel Soukup (University of Toronto, Canada)	Trees, ladders and graphs
The chromatic number of a graph $G$ is the least (cardinal) number $\kappa$ such that the vertices of $G$ can be covered by $\kappa$ many independent sets. A fundamental problem of graph theory asks how large chromatic number affects structural properties of a graph and in particular, is it true that a graph with large chromatic number has certain obligatory subgraphs? The aim of this talk is to introduce a new and rather flexible method to construct uncountably chromatic graphs from non special trees and ladder systems. Answering a question of P. Erdős and A. Hajnal, we construct graphs of chromatic number $\omega_1$ without uncountable infinitely connected subgraphs.
2015-01-22	Franqui Solis Cárdenas Poloche (Universidad Nacional de Colombia)	Unfoldable cardinals and some related problems
Unfoldable cardinals are between weakly compact cardinals and Ramsey cardinals but they still relativize to $L$. However unfoldable cardinals resemble in some aspects to large large cardinals like strongly compact cardinals. In this talk I would like to present two aspects of this. Weakly compact cardinals limit of unfoldable cardinals are unfoldable cardinals and if $K$ is an AEC with $LS(K) < \kappa$ for $\kappa$ a $\theta$ unfoldable cardinal then $K$ is $(\kappa,\theta)$ tame for $\kappa$ short types.
2015-01-29	Seçil Tokgöz (Hacettepe Üniversitesi, Ankara, Turkey)	Paracompactness and Remainders
A classical general problem in the theory of compactification is how properties of a space are related to properties of their remainders. The problem to characterize the class of topological spaces X such that every (some) remainder of X is paracompact remains open. In this talk, we present some partial results related to this question. This is a joint work with A.V. Arhangel'skii.
2015-02-20	Natasha Dobrinen (Denver University, Colorado, USA)	High and higher dimensional Ellentuck spaces and Tukey and Rudin-Keisler initial structures of non-p-points
(Sorry there are no abstracts for these talks in our database.)
2015-03-05	Sandra Uhlenbrock (Universität Münster, Germany)	Mice with finitely many Woodin cardinals from optimal determinacy hypotheses
Projective determinacy is the statement that for certain infinite games, where the winning condition is projective, there is always a winning strategy for one of the two players. It has many nice consequences which are not decided by ZFC alone, e.g. that every projective set of reals is Lebesgue measurable. An old so far unpublished result by W. Hugh Woodin is that one can derive specific countable iterable models with Woodin cardinals, $M^\#_n$, from this assumption. Work by Itay Neeman shows the converse direction, i.e. projective determinacy is in fact equivalent to the existence of such models. These results connect the areas of inner model theory and descriptive set theory. This talk will be an overview of the relevant topics in both fields and sketch a proof of the result that boldface $\Pi^1_{n+1}$ determinacy implies the existence of $M^\#_n(x)$ for all reals $x$. This is joint work with Ralf Schindler and W. Hugh Woodin.
2015-03-19	Vincenzo Dimonte (TU Wien)	Generic I0 at $\aleph_\omega$
An over-the-top attempt of proving the consistency of $\aleph_\omega$ Jónsson provided instead an interesting choiceless model, that produces drastically counterintuitive results about the combinatorics of $\aleph_\omega$, especially if compared to the pcf results in ZFC. There will be ample time to set these new results into the framework of Set Theory and to discuss their motivation. This research is a result of discussions with Hugh Woodin.
2015-03-26	Radek Honzik (KGRC)	Satisfaction in outer models
We will study a generalized notion of satisfaction in which the collection of test structures is restricted to outer models of a given transitive set model $M$ of ZFC. We will show that it is consistent from an inaccessible cardinal that there is $M$ which can define in a lightface way satisfaction in its outer models (we say that $M$ defines its outer model theory). The proof uses Barwise's results on infinitary logic $L_{\infty,\omega}$ and a non-monotonic Easton-type iteration which manipulates the continuum function on regular cardinals in $M$ and which is longer (in terms of ordinal type) than the number of ordinals in $M$. The result complements an unpublished result of Mac Stanley who showed that if $M$ contains many Ramsey cardinal then it defines its outer model theory. The work is joint with Sy Friedman.
2015-04-16	Wei Li (KGRC)	Fragments of Kripke-Platek Set Theory
Fragments of the Kripke–Platek set theory deal with structures of set theory without full foundation. This is a joint project with Sy Friedman and Tin Lok Wong from the Kurt Gödel Research Center. One motivation of this project is the connection between nonstandard arithmetic and $\alpha$-recursion theory. $\alpha$-recursion theory has its generalized arguments in $L_\alpha$'s, where $\alpha$ is a standard ordinal. And in nonstandard arithmetic, we work in models without full induction. Induction is the dual of foundation. In their developments, techniques and results have many overlaps. Yet, reasons for this phenomenon are yet to be found. In this project, our research is done in nonstandard models of set theory. These models are "between" those in nonstandard arithmetic and those in $\alpha$-recursion theory. It is one attempt to search for the reason for the mysterious connections between these two areas.
2015-04-23	Benjamin Miller (KGRC)	Definable perfect matchings
We will consider the problem of finding Baire, Borel, and Lebesgue measurable perfect matchings for acyclic, locally countable Borel graphs.
2015-04-30	Lyubomyr Zdomskyy (KGRC)	Remainders of topological groups and Grigorieff forcing
We will discuss what kind of constrains combinatorial covering properties of Menger, Scheepers, and Hurewicz impose on remainders of topological groups. For instance, we show that such a remainder is Hurewicz if and only it it is $\sigma$-compact. Also, the existence of a Scheepers non-$\sigma$-compact remainder of a topological group follows from CH and yields a $P$-point, and hence is independent of ZFC. We also make an attempt to prove a dichotomy for the Menger property of remainders of topological groups in the style of Arhangel'skii. This is a joint work with Angelo Bella and Secil Tokgoz.
2015-05-07	Ali Enayat (University of Gothenburg, Sweden)	Flexible Turing Machines
Suppose T is a consistent recursively enumerable extension of Q (Robinson arithmetic). A Turing Machine (hereafter TM) with program e is said to be T-flexible if for any prescribed natural number m, the theory T plus "on input 0, the output of the TM with program e is precisely the singleton {m}" is consistent. T-flexible TMs were first constructed by Kripke (1961). Note that here e is a concrete (standard) program. Recently Woodin (2011) introduced a new type of T-flexible TM for consistent r.e. extensions of PA (Peano arithmetic) such that: (1) T proves "on input 0, the output of the TM with program e is finite", and (2) for every countable model M of T, and any M-finite set s extending the M-output of the TM with program e (when the input is 0), there is an end extension N of M satisfying T plus "on input 0, the output of the TM with program e is precisely s". In this talk I will compare and contrast the aforementioned constructions of Kripke and Woodin, and will also present a refinement of Woodin's theorem, obtained in my collaborative work with Albert Visser, Volodya Shavrukov, and Rasmus Blanck.
2015-05-21	Piotr Borodulin-Nadzieja (Wrocław University, Poland)	Measure-theoretic Suslin Hypothesis
Many authors considered questions about existence of compact ccc non-separable spaces satisfying some additional properties and these questions often motivated quite important theorems. E.g. saying that there is no compact ccc non-separable ordered spaces is just refomulating Suslin's Hypothesis. We study spaces which are not only ccc but which carry strictly positive measures. In particular, we show that consistently each compact space of countable pi-character and supporting a measure is separable.
2015-05-27	Peter Holy (Universität Bonn, Germany)	Non-pretame Class Forcing and the Forcing Theorem, the axioms of ZFC and non-definable Class Forcing
Pretameness is a combinatorial condition on class forcings that was introduced by Sy Friedman and that is equivalent to the preservation of the axioms of ZF^-, that is ZF without the power set axiom. Moreover pretameness implies the forcing theorem to hold, that is, the definability of the forcing relation and the truth lemma (the latter states that everything true in a generic extension is forced by some condition in the generic). Building on an unpublished result of Sy Friedman, we show that there is always a (non-pretame) class forcing that fails to satisfy the forcing theorem, and that consistently, there is one that even fails to satisfy the truth lemma. We observe that all “simple” examples of non-pretame class forcings do not only destroy instances of the axiom of replacement, but also of the axiom of separation. We conjecture that this is actually the case for all (definable) class forcings, however we give an example of a non-definable class forcing, a class sized version of Prikry forcing, that destroys replacement, however preserves all instances of separation. This is joint work with Regula Krapf, Philipp Lücke, Ana Njegomir and Philipp Schlicht.
2015-05-28	Liang Yu (Nanjing University, Nanjing, PR of China)	CH and Cofinal maximal chains in the Turing degrees
Over ZFC, we prove that CH is equivalent to the existence of Cofinal maximal chains in the Turing degrees of order type $\omega_1$. However, it is consistent with ZF that they are not equivalent. We also present some applications of the result to the theory of equivalence relations.
2015-06-11	Clinton Conley (Cornell University, New York, USA)	Strong treeability of planar groups
An equivalence relation is called treeable if it can be realized as the connectedness relation of an acyclic Borel graph. We call a finitely generated group planar if there is some finite generating set such that the induced Cayley graph of the group is planar. Using techniques originally created to analyze measure-theoretic chromatic numbers of graphs, we show that any orbit equivalence relation of a free measure-preserving action of a planar group on a standard probability space is treeable on a conull set. This is joint work with Gaboriau, Marks, and Tucker-Drob.
2015-06-18	David Schrittesser (University of Copenhagen, Denmark)	Maximal discrete sets in arboreal forcing extensions
Given a graph (or just a binary relation) $G$ on a set $X$, we call $D \subseteq X$ $G$-discrete iff any two of its elements are $G$-unrelated. A maximal discrete set is one which has no proper discrete superset. If $X$ is an effectively presented Polish space and $G$ is say Borel, we can measure how hard it is to construct a maximal $G$-discrete set is in terms of the (effective) projective hierarchy. A good example is the space of Borel probability measures together with the relation of being orthogonal. It is known that there can be no analytic maximal orthogonal family of measures (m.o.f), but in the constructible universe, there is an (effectively) $\Pi^1_1$ m.o.f. It is also known that there can be no such m.o.f in the Cohen or Random extensions. In recent joint work with Asger Törnquist, we investigate the complexity of maximal discrete sets and in particular, of m.o.fs in forcing extensions by Sacks, Miller and Mathias forcing. We show that not only in the constructible universe is it possible to have a $\Pi^1_1$ m.o.f.
2015-06-25	Peter Schuster (University of Verona, Italy, currently Humboldt returning fellow at the Munich Center for Mathematical Philosophy, Germany)	Eliminating Disjunctions by Disjunction Elimination
Joint work with Davide Rinaldi (University of Leeds, England) If a Scott-style multi-conclusion entailment relation E extends a Tarskian single-conclusion consequence relation C, then E is conservative over C precisely when the appropriate rule of disjunction elimination can be proved for C. This readily follows from a sandwich criterion due to Scott, but can also be fleshed out into a proof-theoretical reduction. The principal application is to turn transfinite methods into admissible rules. For instance, contrapositive forms of Zorn's Lemma are often applied in concrete contexts in which–at least for definite Horn clauses–the corresponding conservation theorems would suffice. We now have at hand a syntactical, uniform approach to many of those conservation theorems, e.g. of the ones related to the theorems by Krull-Lindenbaum, Artin-Schreier, Szpilrajn and Hahn-Banach. Related work can be found e.g. in locale theory (Mulvey-Pelletier 1991), dynamical algebra (Coste-Lombardi-Roy 2001, Lombardi 1997-8), formal topology (Cederquist-Coquand-Negri 1998) and proof theory (Coquand-Negri-von Plato 2004, Negri-von Plato 2011).
2015-07-02	Dana S. Scott (Carnegie Mellon University, Pittsburgh, Pennsylvania, USA and UC Berkeley, California, USA)	Lambda-Calculus and Dependent Type Theory
The speaker has a favorite lambda-calculus model, as he will explain, but he could start with any model and graft on dependent types using partial equivalence relations. The scheme is very simple and leads to a number of good, but elementary exercises in logic. He wishes he had thought of it many years ago.
2015-07-09	David Chodounský (Academy of Sciences of the Czech Republic)	Properties intermediate between master and strong master
In our recent joint work J. Zapletal, we explored a portfolio of forcing properties, which are based on the notion of a Φ-master condition. Being Φ-master is in general a property intermediate between being a master and strongly master condition (in the sense of Mitchell). The main example is the so called Y-master condition, which gives rise to the Y-proper forcing notions. This approach enables us uncovers some new interesting techniques with useful applications.
2015-10-01	Tetsuo Ida (University of Tsukuba, Japan)	On Hestenes' geometric algebra: its formalization by the proof assistant and application to computational origami
We report the work of our on-going project on computational origami. The first is the formalization of a Hestenes' geometric algebra (GA) by the proof assistant Isabelle/HOL. We use the notion of Classes of Isabelle/HOL to build up GA from more fundamental algebras. We restrict our algebra to 3D case since our immediate concern is the application of the 3D origami. The formalization of GA produces a set of algebraic equalities that involves operators of multiplication and addition of multi-vectors as well as inner and outer products. Those equalities are turned into Mathematica programs for practical computations of origami geometry. The second is the integration of the obtained programs into our computation origami system Eos. Basing the geometric computation of Eos on GA requires significant changes of computing and proving engines of Eos. Our attempts so far are briefly explained.
2015-10-08	Rachid Atmai (KGRC)	The inner model problem and descriptive inner model theory
We will introduce one of the main problems in inner model theory (IMT). A solution to this problem is crucial for inner models of large cardinals to be canonical (in particular for their set of reals to be definable). Descriptive set theory (DST) meets IMT at multiple levels: first at the structural level of correspondence between inner models with Woodin cardinals and determinacy axioms then in the HOD analysis and the core model induction for example; second, it appears that DST is absolutely necessary to make progress on the inner model problem through the study of the universally Baire sets of reals and the strong determinacy models these sets live in. The goal of the talk is to introduce these notions and the ideas at play in this field.
2015-10-15	David Schrittesser (University of Copenhagen, Denmark)	Maximal independent sets in forcing extensions
In recent work with Asger Törnquist, we constructed a maximal orthogonal family of measures which has a very simple definition (i.e. it is effectively co-analytic) even in a situation where there are non-constructible reals (see my [/2015/Talk_06-18_a.html previous talk] at the KGRC). In this talk I will discuss the problem of obtaining a Hamel basis in the Sacks extension, at the same level of definability (effectively co-analytic). While the problem has a very similar flavour, it requires some new ideas.
2015-10-22	Hubie Chen (University of the Basque Country, Spain)	The Parameterized Complexity Classification of – and the Logic of – Counting Answers to Existential Positive Queries
We consider the computational complexity of the problem of counting the number of answers (satisfying assignments) to a logical formula on a finite structure. We present two contributions. First, in the setting of parameterized complexity, we present a classification theorem on classes of existential positive queries. In particular, we prove that (relative to the problem at hand) any class of existential positive formulas is interreducible with a class of primitive positive formulas. In the setting of bounded arity, this allows us to derive a trichotomy theorem indicating the complexity of any class of existential positive formulas, as we previously proved a trichotomy theorem on classes of primitive positive formulas (Chen and Mengel '15). This new trichotomy theorem generalizes and unifies a number of existing classification results in the literature, including the classifications on model checking primitive positive formulas (Grohe '07), model checking existential positive formulas (Chen '14), and counting homomorphisms (Dalmau and Jonsson '04). Our second contribution is to introduce and study an extension of first-order logic in which algorithms for the counting problem at hand can be naturally and conveniently expressed. In particular, we introduce a logic which we call #-logic where the evaluation of a so-called #-sentence on a structure yields an integer, as opposed to just a propositional value (true or false) as in usual first-order logic. We discuss the width of a formula as a natural complexity measure and show that this measure is meaningful in #-logic and that there is an algorithm that minimizes width in the "existential positive fragment" of #-logic. This is joint work with Stefan Mengel.
2015-10-29	Moritz Müller (KGRC)	Cobham recursive set functions and weak set theories
We introduce Cobham recursive set functions as a notion of polynomial time computation on arbitrary sets. We ask for characterizations of these functions as those definable in certain weak set theories.
2015-11-05	Diego Alejandro Mejía Guzmán (TU Wien)	Separating the left side of Cichon's diagram
It is well known that, with finite support iterations of ccc posets, we can obtain models where 3 or more cardinals of Cichon's diagram can be separated. For example, concerning the left side of Cichon's diagarm, it is consistent that $\aleph_1 < add(N) < cov(N) < b < non(M)=cov(M)=c$. Nevertheless, getting the additional strict inequality $non(M) < cov(M)$ is a challenge because subposets of $E$, the standard ccc poset that adds an eventually different real, may add dominating reals (by Pawlikowski, 1992). We construct a model of $\aleph_1 < add(N) < cov(N) < b < non(M) < cov(M)=c$ with the help of chains of ultrafilters that allows to preserve certain unbounded families. This is a joint work with M. Goldstern and S. Shelah.
2015-11-12	Victor Selivanov (A.P. Ershov Institute of Informatics Systems, Novosibirsk, Russia and Siberian Branch of the Russian Academy of Sciences)	On Weihrauch degrees of k-partitions of the Baire space
In the 1990s Peter Hertling found useful "combinatorial" characterizations of initial segments of the degree structures under Weihrauch reducibilities on k-partitions (for any integer k>1) of the Baire space whose components are finite boolean combinations of open sets. In this talk we discuss extensions of these characterizations to as large initial segments of the Weihrauch degree structures as possible.
2015-11-19	Barnabás Farkas (KGRC)	Towers in Borel filters
In a joint work with J. Brendle and J. Verner we studied which ultrafilters and which Borel filters can contain a tower, that is, a $\subseteq^$-decreasing sequence in the filter without a pseudointersection in $[\omega]^\omega$. First, I will give a short survey on the following result: The statement “every ultrafilter contains a tower” is independent from ZFC. Then my talk will be focused mainly on Borel filters and on some selected results concerning possible logical implications between (i) the existence of towers in certain classical Borel filters, (ii) inequalities between cardinal invariants of these filters, and (iii) the existence of a peculiar object, a large $\mathcal{F}$-Luzin set, that is, a family $\mathcal{X}\subseteq [\omega]^\omega$ of cardinality $\geq\omega_2$ such that $\{X\in\mathcal{X}: X\nsubseteq^ F\}$ is countable(!) for every $F\in\mathcal{F}$ (where $\mathcal{F}$ is a filter).
2015-11-26	Asger Törnquist (University of Copenhagen, Denmark)	Around the definability of maximal eventually different families
A while ago, I claimed that I could prove that no analytic eventually different family of functions from $\omega$ to $\omega$ can be maximal. Unfortunately, the proof contained a serious gap. In this talk, I will discuss a possible strategy for repairing the proof.
2015-12-03	Daniel Soukup (Hungarian Academy of Sciences, Budapest, Hungary)	Uniformization properties in connection to graph colourings
The aim of this talk is to review certain uniformization properties of ladder systems on $\omega_1$. In particular, we focus on a machinery (of iterating a family of simple non proper posets) developed by Shelah investigating the Whitehead problem under CH. Our main interest lies in using this technique to construct uncountably chromatic graphs with interesting/unexpected behavior.
2015-12-04	Sheila Miller (New York City College of Technology, CUNY, USA)	The nature of measurement in set theory
The goal of set theory, as articulated by Hugh Woodin, is develop a "convincing philosophy of truth." In his recent Rothschild address at the INI, he described the work of set theorists as falling into one of two categories: studying the universe of sets and studying models of set theory. We offer a new perspective on the nature of truth in set theory that may to some extent reconcile these two efforts into one. Joint work with Shoshana Friedman.
2015-12-10	Damian Sobota (Polish Academy of Sciences, Warsaw)	The Nikodym property and cardinal invariants of the continuum
A Boolean algebra $\mathcal{A}$ is said to have the Nikodym property if every sequence $(\mu_n)$ of measures on $\mathcal{A}$ which is elementwise bounded (i.e. $\sup_n\|\mu_n(a)\|<\infty$ for every $a\in\mathcal{A}$) is uniformly bounded (i.e. $\sup_n\\|\mu_n\\|<\infty$). The property is closely related to the classical Banach-Steinhaus theorem for Banach spaces. My recent study concerns the problem how (and whether at all) we can describe the structure of the class of Boolean algebras with the Nikodym property in terms of well-known objects occuring inside $\wp(\omega)$ or $\omega^\omega$, e.g. countable Boolean algebras, dominating families, Lebesgue null sets etc. During my talk I will present an attempt to obtain such a description via families of antichains in countable subalgebras of $\wp(\omega)$ having some special measure-theoretic properties. If time allows, I will present some consequences of my research for the Efimov problem and C*-algebra theory.
2015-12-11	Jonathan Verner (Charles University in Prague, Czech Republic)	Ramsey Partitions of Metric Spaces
We investigate the existence of metric spaces which, for any coloring with a fixed number of colors, contain monochromatic isomorphic copies of a fixed starting space $K$. I shall present a proof, due to Shelah, that for colorings with $\kappa$ colors and a $K$ of size $\kappa$ such a space can always be found of size $2^\kappa$. Time permitting I will also present a slightly weaker theorem for countable ultrametric $K$ where, however, the resulting space has size $\aleph_1$.
2015-12-17	Wei Li (KGRC)	Reverse mathematics in $\omega$ categoricity
In this talk, we consider classical characterizations of $\omega$ categorical theories from the view point of reverse mathematics. It is a joint work with Fokina and Turetsky.