2011-01-20Clinton Conley (KGRC)Measurable colorings of graphs, II
We continue the investigation of Borel and Lebesgue measurable graph colorings. This time we focus on "negative" results, i.e., situations in which these definable chromatic numbers differ substantially from the classical chromatic numbers. Additionally, we examine the possibility of a G0-like dichotomy occurring between graphs of finite Borel chromatic number and those of infinite Borel chromatic number.

This is joint work with Alexander S. Kechris and Benjamin D. Miller.

2011-01-27Achim Blumensath (TU Darmstadt, Darmstadt, Germany)The Monadic Second-Order Transduction Hierarchy
We study monadic second-order transductions between classes of finite structures. The main result is a complete description of the resulting hierarchy. It is linear of order type omega + 3. Each level has a combinatorial characterisation in terms of a suitable variant of tree-width. Canonical representatives of the various levels are: the class of (i) all trees of height n, for n < omega; (ii) all paths; (iii) all trees; and (iv) all grids.
2011-03-03Sy-David Friedman (KGRC)Absoluteness and Model Existence for Infinitary Logic
If a sentence of first-order logic has an infinite model then it has models of all infinite cardinalities. But this is not the case for infinitary logic, which for the purposes of this talk I take to be Lω1, ω, the extension of first-order logic which allows countably infinite conjunctions and disjunctions. In infinitary logic there are sentences which have only countably infinite models. Using Keisler's completeness theorem for the logic L(Q) (where Qx means "there exist uncountably many x") there is an absolute criterion for a sentence of infinitary logic to have a model of size 1. But without assuming CH, it is easy to show that there is no such absolute criterion for model existence in 2. In this talk I'll focus on model existence for infinitary logic under the assumption of GCH. Using Kurepa trees and Special Aronszajn trees, I'll show that model existence in α is not absolute for GCH models, for any countable alpha different from ω. The &omega case remains open, as is the question of whether large cardinals can be eliminated from these results. This is joint work with Tapani Hyttinen and Martin Koerwien.

2011-03-10Radek Honzik (Charles University, Prague)The Definable Failure of the Singular Cardinal Hypothesis (SCH)
We show first that it is consistent that Κ is a measurable cardinal where the GCH fails, while there is a lightface definable wellorder of H(Κ+). Then with further forcing we show that it is consistent that GCH fails at ω, ω strong limit, while there is a lightface definable wellorder of H(ℵω+1) ("definable failure" of the singular cardinal hypothesis at ω). The large cardinal hypothesis used is the existence of a Κ++-strong cardinal, where Κ is Κ++-strong if there is an embedding j:V → M with critical point Κ such that H(Κ++) is included in M (this is almost optimal). The fine structure of the canonical inner model L[E] for a Κ++-strong cardinal is used throughout. This is joint work with Sy D. Friedman.

2011-03-17Victor Torres (KGRC)Rado's Conjecture and the Tree Property for ω2
Rado's Conjecture is the following statement: A tree T of height ω1 is special (i.e. the union of countable many antichains) iff every subtree of T of size 1 is special. In the first part of the talk we will give a short introduction to this principle, and present some of its properties and consequences.

Recently, Rémi Strullu proved that the Map Reflection Principle plus MA imply the Tree Property for ω2. Similarly, Laura Fontanella showed recently that the Reflection Principle together with MA imply the Tree Property for ω2. In this talk we will present a joint work with Laura Fontanella and Lauri Tuomi, where we discuss whether Rado's Conjecture could also imply the Tree Property for ω2.

2011-03-31Juris Steprāns (York University, Canada)Reflecting non-meagreness
A great many results in analysis deal with the question of whether certain properties of sets in Rn can be determined by considering only subspaces of lower dimension. For example, Stein showed that a set of positive measure in Rn, where n≥3 must reflect this property to the surface of a sphere. This was shown later for n=2 by Bourgain and Marstrand. In a similar spirit, Fremlin asked the following: Letting λ be Haar measure on the classical Cantor set C and supposing that λ((A+x)∩C)=0 for all reals x, does it follow that A is Lebesgue null? I will discuss a result obtained with Marton Elekes on the category analogue of this question.
2011-04-07Shashi Srivastava (Indian Statistical Institute, Kolkata)Selection Theorems, Transition Probabilities and Stochastic Kripke models
We use measurable selection theorems to prove various results on transition probabilities over standard Borel spaces. We then show that logical equivalence, behavioral equivalence and bisimilarity are equivalent for stochastic Kripke models over standard Borel spaces.
2011-04-14Victor Torres (KGRC)Conjectures of Rado and Chang and Special $\aleph_2$-Aronszajn trees
We recall that Rado's Conjecture (RC) 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. Moreover he has shown that RC is consistent with CH as well as consistent with the negation of CH. Also, he has shown that RC has many interesting consequences, including the continuum is at most \(\aleph_2\), CC, SCH, the negation of \(\Box_\kappa\) for all \(\kappa > \omega\), etc. This result is the first in the series which will study the effect of RC or one of its consequences to weaker form of square sequences. We will show that Jensen's weak square principle \(\Box_{\omega_1}^*\) is equivalent to CH if we assume either Rado's conjecture or its consequence, the strong Chang's Conjecture.
2011-05-04Yi Zhang (Sun Yat-Sen University, Guangzhou, China)Maximal Cofinitary Groups
A subgroup G in Sym(N) is called cofinitary iff every element in G but identity has finitely many fix points. In my talk, I will talk about some results and questions concerning this group.

2011-05-19Mariya Soskova (Sofia University, Bulgaria)Definability in the enumeration degrees
I will talk about a joint project with H. Ganchev, whose aim is to study the definability properties, of the local structure of the enumeration degrees. We start by studying K-pairs of enumeration degrees, a notion introduced by Kalimullin. We show that the class of K-pairs are first order definable in the local structure. Using this result, we show that the local structure of the  Turing degrees (the Delta-two Turing degrees) has a first order definable isomorphic copy in the local structure of the enumeration degrees.
2011-05-26Asger Törnquist (KGRC)The cardinality of maximal cofinitary groups
2011-06-16Martin Goldstern (TU Wien, Austria)Ultralaver forcing and Janus forcing
First I will define and explain the "Borel conjecture" and the "Dual Borel conjecture", then I will present two forcing notions: Ultralaver forcing, a variant of Laver forcing which uses ultrafilters Janus forcing, which—depending on your point of view—can be seen as a variant of Cohen forcing or of random forcing. Ultralaver forcing can be used to show the consistency of the Borel conjecture (Laver's original proof used Laver forcing). Janus forcing can be used to show the consistency of the dual Borel conjecture (Carlson's original proof used Cohen forcing). The main point of these two new forcing notions is that they can be used to show the joint consistency of Borel plus dual Borel conjecture. (This is done using a strange kind of iteration; the iteration will be presented in a later talk next semester.)

This is joint work with J. Kellner, S. Shelah and W. Wohofsky.
2011-06-22Taras Banakh (Lviv State University, Ukraine)Topologically invariant \sigma-ideals on Polish spaces
We shall discuss the structure of topologically invariant \(\sigma\)-ideals with Borel base on homogeneous Polish spaces. An ideal \(\mathcal I\) of subsets of a topological space \(X\) is called topologically invariant if for each set \(A\in\mathcal I\) and each homeomorphism \(h:X\to X\) we get \(h(A)\in\mathcal I\).

During the lecture I plan to cover the following topics:

(1) classification of topologically invariant \(\sigma\)-ideals on topologically homogeneous zero-dimensional Polish spaces;

(2) extremal (i.e., maximal, largest, smallest) topologically invariant \(\sigma\)-ideals on some "nice" Polish spaces;

(3) cardinal characteristics of topologically invariant \(\sigma\)-ideals on some "nice" Polish spaces and their interplay with the cardinal characteristics of the ideal \(\mathcal M\) of meager sets.

2011-06-30Arthur Fischer (KGRC)On a method of Todorcevic
In their 2001 paper, P. Larson & S. Todorcevic introduced a method for constructing models of ZFC in which certain consequences of Martin's Axiom and the Axiom of Constructibility hold; consequences that were previously unknown to be jointly consistent.  We will examine an extension of this method to the Proper Forcing Axiom (due to S. Todorcevic), provide an indication of what is known to hold in these models, and by way of a novel example outline the machinery that has been used to generate many of the proofs to date.
2011-07-05CT Chong (National University of Singapore)$\Pi^1_1$ conservation of combinatorial principles weaker than Ramsey's Theorem for pairs
We discuss several combinatorial principles known to be weaker than Ramsey's Theorem for pairs from the point of view of reverse mathematics. This is joint work with Ted Slaman and Yue Yang.
2011-09-14Boaz Tsaban (Bar-Ilan University, Israel)The character of topological groups, via Pontryagin-van Kampen duality and pcf theory
The Birkhoff-Kakutani Theorem asserts that a topological group is metrizable if and only if it has countable character. We develop and apply tools for the estimation of the character for a wide class of nonmetrizable topological groups. Even in the special case of free abelian topological groups, our results extend a number of results of Nickolas and Tkachenko, which were proved using laborious elementary methods.

Our method use a novel combination of (classical) descriptive set theory, Pontryagin-van Kampen duality, and pcf theory.

I will not assume knowledge of topological groups or any of the topics mentioned in the abstract or used in the talk. Students are, in particular, welcome.

2011-09-19Jörg Brendle (Kobe University, Japan)aleph_1 perfect mad families
We investigate the complexity of maximal almost disjoint (mad) families of subsets of omega. A classical theorem of Mathias says that there are no analytic mad families. On the other hand, Miller proved that there are coanalytic mad families in the constructible universe \(L\). By forcing with a p.o. preserving such a family over \(L\), one sees that the existence of coanalytic mad families is consistent with non-CH. Friedman and Zdomskyy proved that the existence of a \(\Pi^1_2\) mad family is consistent with \(b > \aleph_1\), and asked whether the complexity could be improved to \(\Sigma^1_2\) in their result. In joint work with Yurii Khomskii, we prove that this is indeed the case. (We even conjecture that coanalytic mad families are consistent with \(b > \aleph_1\), though we still do not have a proof for that.) More explicitly, we show that, under CH, one can construct a sequence of \(\aleph_1\) many perfect almost disjoint sets whose union is almost disjoint as well and which survives after adding dominating reals. Under \(V = L\), this sequence, as well as the set defined from it, has a \(\Sigma^1_2\) definition.
2011-10-06Martin Koerwien (KGRC)Non-absoluteness of model existence for infinitary logic
We discuss how much the notion '\(\sigma\) has a model of size \(\aleph_\alpha\)' (where \(\sigma\) is a sentence of \(L_{\omega_1,\omega}\)) can depend on set theoretic properties. After some general remarks and examples, we will focus on the presentation of a complete sentence for which model-existence in \(\aleph_3\) is non-absolute modulo ZFC+GCH.
2011-10-13Vera Fischer (KGRC)Cardinal Characteristics, Projective Wellorders and Large Continuum
We present a method for controlling cardinal characteristics in the presence of a projective wellorder and \(2^\aleph_0>\aleph_2\). This also answers a question of Harrington by showing that the existence of a (lightface) \(\Delta^1_3\) wellorder of the reals is consistent with Martin's axiom and \(2^\aleph_0=\aleph_3\). This is joint work with Sy-David Friedman and Lyubomyr Zdomskyy.
2011-10-20Martin Koerwien (KGRC)Non-absoluteness of model existence for infinitary logic, Part 2
We discuss how much the notion '\(\sigma\) has a model of size \(\aleph_\alpha\)' (where \(\sigma\) is a sentence of \(L_{\omega_1,\omega}\)) can depend on set theoretic properties. After some general remarks and examples, we will focus on the presentation of a complete sentence for which model-existence in \(\aleph_3\) is non-absolute modulo ZFC+GCH.

2011-10-27Moritz Müller (KGRC)Positive Horn definability in \aleph_0-categorical structures
We show that in an \(\aleph_0\)-categorical structure \(A\) a relation is positive Horn definable if and only if it is preserved by the surjective periomorphisms of \(A\). These are homomorphisms from the periodic power of \(A\) into \(A\), and the periodic power of \(A\) is the structure induced on all periodic sequences in \(A^\omega\).<p/>

It follows that the complexity (up to polynomial time reducibility) of the problem to decide the positive Horn theory of some \(\aleph_0\)-categorical structure is determined by the structures set of surjective periomorphisms.<p/>

Such problems are known as quantified constraint satisfaction problems and have been studied in depth for finite structures - there a preservation theorem as above has been established via surjective polymorphisms.<p/>

The talk gives some background information concerning the so-called algebraic approach to constraint complexity which is based on such preservation theorems.<p/>

This is joint work with Hubie Chen.
2011-11-03Joel Hamkins (City University of New York, USA)Generalizations of the Kunen inconsistency
I shall present several generalizations of the well-known Kunen inconsistency that there is no nontrivial elementary embedding from the set-theoretic universe V to itself, including generalizations-of-generalizations previously established by Woodin and others.  For example, there is no nontrivial elementary embedding from the universe V to a set-forcing extension V[G], or conversely from V[G] to V, or more generally from one ground model of the universe to another, or between any two models that are eventually stationary correct, or from V to HOD, or conversely from HOD to V, or from V to the gHOD, or conversely from gHOD to V; indeed, there can be no nontrivial elementary embedding from any definable class to V.  Other results concern generic embeddings, definable embeddings and results not requiring the axiom of choice.  I will aim for a unified presentation that weaves together previously known unpublished or folklore results along with some new contributions.  This is joint work with Greg Kirmayer and Norman Perlmutter.

See [] for article, slides and discussion.
2011-11-10Jakob Kellner (KGRC)The joy of halving
We present a new \(\omega^\omega\)-bounding creature forcing construction resulting in large continuum, and use it to strengthen a previous result about "many cardinal characteristics" (with a considerably nicer proof). <p/> This is joint work with Saharon Shelah.
2011-11-17Victor Torres Perez (KGRC)Weak Reflection Principle, Saturation of the ideal NS and Diamonds in two cardinal version
We prove that the Weak Reflection Principle and the saturation of the ideal NS together imply \(\Diamond_{[\lambda]^{\omega_1}}\), for all regular \(\lambda\geq\aleph_2\). Even more, we get \(\Diamond_{[\lambda]^{\omega_1}}\) concentrated on \(x\in[\lambda]^{\omega_1}\) such that \(\sup(x)\) has uncountable cofinality.

2011-11-24Valentina Harizanov (George Washington University, Washington, D.C., USA)Computably enumerable and co-computably enumerable equivalence structures
We investigate computability theoretic properties of computably enumerable and co-computably enumerable equivalence structures and their isomorphisms. While every computably enumerable equivalence structure with infinitely many infinite classes is isomorphic to a computable structure, there are computably enumerable equivalence structures that are not isomorphic to computable ones. We show that if two isomorphic computably enumerable equivalence structures have only finitely many infinite classes or have finite upper bound on the size of their finite classes, then they are limit computably isomorphic. On the other hand, we prove that even simple co-computably enumerable equivalence structures do not have to be limit computably isomorphic to computable structures.

This is joint work with D. Cenzer and J. Remmel.

2011-12-01Sy-David Friedman (KGRC)The Essence of V
2011-12-15Tatiana Arrigoni (KGRC)The Hyperuniverse Program. An overview.
The "Hyperuniverse Program" is an approach due to Sy Friedman inspired by the search of solutions to questions undecidable in ZFC (see Friedman, Sy D., [ Internal consistency and the Inner Model Hypothesis], Bulletin of Symbolic Logic 12 (4), 2006, 591-600). The purpose of this talk is to illustrate and discuss this program in the broader context of the contemporary debate on the consequences of independence phenomena in set theory, with a particular focus on its underlying philosophical assumptions.