2014

date	speaker	title
2014-01-09	Peter Schuster (Pure Mathematics, University of Leeds, UK)	Folding Up (Disjunctions)
The characteristic axiom of many an ideal object in algebra and logic (prime ideal, ultrafilter, valuation ring, linear order, complete theory, etc.) can be put as a variant of the interpretation of disjunction in a model of classical logic: that is, "if $A\lor B$ holds, then either $A$ holds or $B$ holds". Typically the characteristic axiom can be reduced to the special case that corresponds to disjunction interpretation where $A = B$. Unlike the latter, however, the former is not always a tautology. The reduction is usually done by an appropriate form of the Axiom of Choice (Krull's Lemma, the Artin-Schreier Theorem, Lindenbaum's Lemma, etc.); whence it falls short of telling us why it works and why $A = B$ matters. In spite of the resulting transfinite flavour, we hope that the reduction can often be done by finite methods only, and that we thus gain reasons and routines on top of the facts. Towards a systematic approach we have singled out a universal Krull-Lindenbaum Theorem crossing algebra and logic. Partially joint work with F. Ciraulo, N. Gambino and D. Rinaldi.
2014-01-23	Victor Selivanov (A.P. Ershov Institute of Informatics Systems, Novosibirsk, Russia and Siberian Branch of the Russian Academy of Sciences)	More Hierarchies of $\mathsf{qcb_0}$-Spaces
In the first part of the talk I present a joint work with Matthias Schroeder where we extend the Luzin hierarchy of $\mathsf{qcb_0}$-spaces introduced in in our previous work to all countable ordinals, obtaining in this way the hyperprojective hierarchy of $\mathsf{qcb_0}$-spaces. We extend to this larger hierarchy all main results of the previous work. In particular, we extend the Kleene-Kreisel continuous functionals of finite types to the continuous functionals of countable types and relate them to the new hierarchy. We show that the category of hyperprojective $\mathsf{qcb_0}$-spaces has much better closure properties than the category of projective $\mathsf{qcb_0}$-space. As a result, there are natural examples of spaces that are hyperprojective but not projective. In the second part I present a work in progress (joint with Matthew de Brecht and Matthias Schroeder) where we define and study new hierarchies based on the idea to classify $\mathsf{qcb_0}$-spaces according to the complexity of their bases. The new hierarchies complement the previous ones and provide new tools to investigate non-countably based $\mathsf{qcb_0}$-spaces. We concentrate on the non-collapse properties of the new hierarchies and on their relationships with the older ones. As a bi-product, we show that there is no universal $\mathsf{qcb_0}$-space.
2014-01-30	Hiroshi Ando (Erwin Schrödinger Institute, Vienna, Austria)	On von Neumann's Theorem and Borel complexity of unitary equivalence modulo compact perturbations of self-adjoint operators
The celebrated Weyl-von Neumann perturbation theorem asserts that every self-adjoint operator can be turned into a diagonal operator by an arbitrarily small compact (in fact Hilbert-Schmidt) perturbations. As a corollary, von Neumann obtained the following result: for bounded self-adjoint operator $A$,$B$, the following conditions are equivalent: (1) $uAu^+K=B$, where $u$ is a unitary and $K$ is a compact opeartor. (2) $A$ and $B$ have the same essential spectrum. Here, the essential spectrum of $A$ is the set of all points in the spectrum of $A$ which is either an eigenvalue of infinite multiplicity or an accumulation point in the spectrum. Therefore, the essential spectrum is the complete invariant for the classification problem of bounded self-adjoint operators in the sense of (1). Since Weyl-von Neumann theorem works for general unbounded self-adjoint operators, it is interesting to consider whether von Neumann's theorem still holds for unbounded operators. However, many examples indicates us that there is very little hope to find a complete and invariant $I(A)$ (assigned in a computable way) for each self-adjoint $A$ such that for $A,B$ $uAu^+K=B$ holds for some $u$,$K$ iff $I(A)=I(B)$. The purpose of our work is to justify this feeling by showing: (a) It can be deduced from von Neumann's characteriztion that the classification of bounded self-adjoint opeartors up to unitary equivalence modulo compacts is smooth. (b) The same type of equivalence relation for unbounded self-adjoint operatorss does not admit classification by countable structure, although the associated orbit equivalence relation is not turbulent. This is a joint work with Yasumichi Matsuzawa (Shinshu University).
2014-03-06	Valentina Harizanov (George Washington University, Washington, D.C., USA)	Orders on groups, their spaces, and complexity
We investigate properties of orders on groups, which respect the algebraic structure. There is a natural topology on the (nonempty) set of such orders, and this space is compact even for a structure with a single binary operation (non necessarily a semigroup). We study the spaces as well as computability-theoretic complexity of orders on groups, both abelian and nonabelian. While not all computable orderable groups have computable orders, many familiar groups contain orders in every Turing degree above a specific degree.
2014-03-13	Wei Li (KGRC)	$\Delta_2$ Degrees without $\Sigma_1$ Induction
In this talk, we consider the structure of Turing degrees below $0’$ in the theory that is a fragment of Peano arithmetic without $\Sigma_1$ induction, with special focus on proper $d$-r.e. degrees and non-r.e. degrees. We prove (1) $P^-+ B\Sigma_1+ \mathrm{Exp}$ implies the existence of a proper $d$-r.e. degree. (2) Over $P^-+ B\Sigma_1+ \mathrm{Exp}$, the existence of a proper $d$-r.e. degree below $0’$ is equivalent with $I\Sigma_1$. (3) $P^-+ B\Sigma_1+ \mathrm{Exp}$ is not enough to show there is a non-r.e. degree below $0’$.
2014-03-20	Hubie Chen (Universidad del País Vasco, San Sebastian, Spain)	One Hierarchy Spawns Another: The Complexity Classification of Conjunctive Queries
We study the problem of conjunctive query evaluation over sets of queries; this problem is formulated here as the relational homomorphism problem over a class of structures $A$, wherein each instance must be a pair of structures such that the first structure is an element of $A$. We introduce a notion which we call graph deconstruction, which is a variant of the well-known notion of tree decomposition. Using this notion, we give a novel, modular, and conceptually clean presentation of the theorem describing the tractable homomorphism problems in the framework under study (assuming bounded arity). We then study a binary relation on graph classes that is naturally induced by the notion of graph deconstruction. We completely describe the hierarchy of graph classes that this binary relation yields, and discuss how this hierarchy of graph classes can be used to infer a complexity-theoretic hierarchy of homomorphism problems, which is extremely fine as it is exhaustive up to a computationally very weak notion of reduction (namely, a parameterized form of quantifier-free reduction). We also plan to present and develop a theory of Ehrenfeucht-Fraisse-style pebble games for solving cases of the homomorphism problem wherein the tree depth is bounded. A version of the article on which this talk is based is available at: [http://arxiv.org/abs/1307.1353 arxiv.org/abs/1307.1353]
2014-03-27	Dan Turetsky (KGRC)	Algorithmic Randomness and the Turing Degrees
Algorithmic randomness uses the tools of computability theory to analyze the question, "When is an infinite binary sequence random?". Several different definitions of a random sequence are studied, with the most common being Martin-Löf randomness. Randomness has a rich interaction with the Turing degrees of more classical computability theory, in particular with the c.e. degrees and the PA degrees. For example, if a random cannot compute $0'$ (or equivalently, cannot compute a PA degree), then every c.e. set which it can compute is $K$-trivial, which means that randomness considers it useless as an oracle; despite being non-computable, it has no derandomization power. The covering problem asks if this can be reversed; is every $K$-trivial computable from a random that does not compute $0'$? I will review the appropriate definitions and discuss the covering problem and similar questions. I will also discuss the proof of the covering problem, which touches on the interaction of algorithmic randomness and effective analysis.
2014-04-03	Vadim Kulikov (KGRC)	Definability of Pure Unrectifiability
We will look at various notions which arise in geometric measure theory such as "positive Hausdorff-measure" and "purely unrectifiable" (a subset of a Hilbert space is purely unrectifiable if its intersection with any smooth curve has 1-dimensional Hausdorff measure zero). Some open questions in geometric measure theory reside around characterizing these properties in various ways. Here I present a result which might contribute to that program, namely proving descriptive set theoretic complexities of these classes of sets.
2014-04-10	Yurii Khomskii (KGRC)	Full-splitting Miller trees and infinitely often equal reals
We investigate two closely related tree-like forcing notions for adding reals, and their corresponding ideals. Both forcing notions are non-ccc, yet have many properties similar to Cohen forcing (for example, they force the same values of the cardinal characteristics in Cichon's diagram). Also, the notions of regularity derived from these trees are closely related to the Baire Property, yet are subtly different, which makes this a very interesting case study. We also consider some cardinal characteristics related to these trees. Finally, we look at the connection to Fremlin's problem about `adding half a Cohen real without adding a Cohen real', which was recently solved by Zapletal. This is joint work with Giorgio Laguzzi.
2014-05-08	Diego Alejandro Mejía Guzmán (KGRC)	Matrix iterations of ccc posets
We present several examples of ccc forcing constructions, using matrix iterations, to obtain models where several classical cardinal invariants of the continuum assume pairwise different values (preferably arbitrary ones). The main application is to obtain constellations of Cichon's diagram where the cardinals at the right hand side assume three different values.
2014-05-15	Moritz Müller (KGRC)	Topological dynamics of unordered Ramsey structures
We study connections between Ramsey properties of Fraïssé classes $\mathcal{K}$ and the universal minimal flow $M(G_\mathcal{K})$ of the automorphism group $G_\mathcal{K}$ of their Fraïssé limits. For example, extending a result of Kechris, Pestov and Todorcevic, we show that if the class $\mathcal{K}$ has finite Ramsey degree for embeddings, then this degree equals the size of $M(G_\mathcal{K})$.
2014-05-22	Andrea Medini (KGRC)	Dropping Polishness
Classical descriptive set theory studies the subsets of complexity $\mathbf{\Gamma}$ of a Polish space $X$, where $\mathbf{\Gamma}$ is one of the (boldface) Borel or projective pointclasses. However, the definition of a $\mathbf{\Gamma}$ subset of $X$ extends in a natural way to spaces $X$ that are separable metrizable, but not necessarily Polish. When one “drops Polishness”, many classical results suggest new problems in this context. We will discuss some early examples, then focus on the perfect set property. More precisely, we will determine the status of the statement “For every separable metrizable $X$, if every $\mathbf{\Gamma}$ subset of $X$ has the perfect set property then every $\mathbf{\Gamma}'$ subset of $X$ has the perfect set property” as $\mathbf{\Gamma},\mathbf{\Gamma}'$ range over all pointclasses of complexity at most analytic.
2014-06-05	Miloš S. Kurilić (University of Novi Sad, Serbia)	Copies of structures and ultrahomogeneous digraphs
The equality, isomorphism and equimorphism are natural relations between relational structures expressing different degrees of their similarity. In addition, if $\mathbb P(\mathbb X)$ denotes the poset of domains of substructures of a structure $\mathbb X$ isomorphic to $\mathbb X$, then the conditions $\mathbb P(\mathbb X)=\mathbb P(\mathbb Y)$, $\mathbb P(\mathbb X)\cong\mathbb P(\mathbb Y)$, $\mathop{\rm sq}\nolimits\mathbb P(\mathbb X)\cong\mathop{\rm sq}\nolimits\mathbb P(\mathbb Y)$ and $\mathop{\rm ro}\nolimits\mathop{\rm sq}\nolimits\mathbb P(\mathbb X) \cong \mathop{\rm ro}\nolimits\mathop{\rm sq}\nolimits\mathbb P(\mathbb Y)$ extend the list of such similarities; the last one is the roughest and equivalent to the forcing equivalence of the posets $\mathbb P(\mathbb X)$ and $\mathbb P(\mathbb Y)$. We will review some results concerning the hierarchy between these similarities and the corresponding classifications of structures. Also we will present some recent results concerning the structures with strongly connected components and a classification of ultrahomogeneous binary structures.
2014-06-26	Victor Torres Perez (TU Wien)	The Tree Property for $\omega_2$ and Bounded Forcing Axioms
We prove that the Tree Property for $\omega_2$ together with $\mathrm{BPFA}(\omega_1)$ is equiconsistent with the existence of a weakly compact cardinal. Also, we prove that the tree property for $\omega_2$ together with $\mathrm{BPFA}$ is equiconsistent with the existence of a weakly compact cardinal which is also reflecting. Similarly, we show that the Special Tree Property for $\omega_2$ together with $\mathrm{BPFA}(\omega_1)$ is equiconsistent with the existence of a Mahlo cardinal and the special tree property for $\omega_2$ together with $\mathrm{BPFA}$ is equiconsistent with the existence of a Mahlo cardinal which is also reflecting. This is a joint work with Sy Friedman.
2014-10-09	Vladimir V. Tkachuk (Universidad Autónoma Metropolitana de México, Mexico City, Mexico)	Maximal pseudocompactness and maximal countable compactness in the class of Tychonoff spaces
This is a presentation of results obtained in 2013-2014 jointly with O.T. Alas and R.G. Wilson. Given a property $\mathcal P$, say that a space $X$ is maximal $\mathcal P$ in the class of Tychonoff spaces if $X$ has $\mathcal P$ but any stronger ''Tychonoff'' topology on $X$ does not have $\mathcal P$. It turns out that maximal pseudocompactness and maximal countable compactness in the class of Tychonoff spaces have more interesting properties than maximal pseudocompactness and maximal countable compactness in the class of all spaces so we will call the respective spaces maximal pseudocompact and maximal countably compact. Our presentation will include the following results (all spaces are assumed to be Tychonoff): 1) Any dyadic maximal pseudocompact space is metrizable. 2) Any Fréchet-Urysohn compact space is a retract of a Fréchet-Urysohn maximal pseudocompact space; since there are Fréchet-Urysohn compact spaces which are not maximal pseudocompact, maximal pseudocompactness is not preserved by continuous images even in compact spaces. 3) If $\kappa$ is strictly smaller than the first weakly inaccessible cardinal, then the Tychonoff cube $I^\kappa$ is maximal countably compact. 4) If $\lambda$ is the first measurable cardinal, then the Tychonoff cube $I^\lambda$ does not even embed in a maximal countably compact space. 5) If a space $X$ is maximal countably compact, then every $\omega$-continuous real-valued function on $X$ is continuous. 6) If $X$ is a countably compact space with the Mazur property, i.e., every sequentially continuous real-valued function on $X$ is continuous, then $X$ is maximal countably compact. 7) If $X$ is an $\omega$-monolithic compact space, then $C_p(X)$ has the Mazur property if and only if $C_p(X)$ is Fréchet-Urysohn.
2014-10-16	Andrew Brooke-Taylor (University of Bristol, UK)	An analogy between cardinal characteristics and highness properties of Turing oracles
An analogy may be drawn between cardinal characteristics of the continuum and highness properties of Turing oracles, with forcing constructions as a motivating consideration. In a joint paper with Joerg Brendle, Slewyn Ng and Andre Nies, we spell out this analogy, giving a complete survey of the computability-theoretic analogue of Cichon's diagram, and obtaining further results about other cardinal characteristics. In this talk I will explain the analogy and present some of our results.
2014-10-30	Vadim Kulikov (KGRC)	Complexity of Homeomorphism Relations up to Borel Reducibility
We will consider the program of determining the complexity of homeomorphism relations on various subclasses of Polish spaces such as compact, locally compact, sigma-compact, manifolds etc. We will review the known classification and non-classification results and present some new ones. In particular we show that the homeomorphism on locally compact Polish spaces is classifiable by an equivalence relation induced by a Polish group action while the one on sigma-compact Polish spaces is not. In the end we will look at some open problems.
2014-11-06	Wiesław Kubiś (Academy of Sciences of the Czech Republic)	Banach-Mazur games and Fraisse limits
We shall present an abstract version of the Banach-Mazur game which is played on a fixed category (typically, some structures with embeddings). In case where the category is a Fraisse class, there is a winning strategy leading to its Fraisse limit. We shall also discuss applications to more general categories, describing certain generic objects that are analogues of Fraisse limits in continuous model theory.
2014-11-13	Jonathan Verner (Charles University, Prague, Czech Republic)	Monotone metric spaces
A metric space is ($k$-)monotone, if there is a linear order on it such that for any three points $x < y < z$ the distance between $x$ and $y$ is at most $k$ times the distance between $x$ and $z$. A space is $\sigma$-monotone if it is the union of countably many monotone spaces. Hrušák and Zindulka asked, whether there is (in ZFC) a non $\sigma$-monotone space of size $\aleph_1$. We investigate this and related questions.
2014-11-20	Jan Starý (Czech Technical Univeristy in Prague)	Order-sequential compactness
A Boolean algebra which is compact in its order-sequential topology needs to be ccc, must not add an independent real as a forcing (hence must not embedd the Cantor algebra), and the only Hausdorff case is the powerset of omega. We look for examples of such algebras (non-Hausdorff, hence non-Maharam) and the corresponding forcing restrictions.
2014-11-27	David Chodounsky (Institute of Mathematics of the Czech Academy of Sciences)	Y-c.c. and Y-proper forcing notions
I will introduce a new type of properties of c.c.c. and proper forcing notions, of which the Y-c.c. and Y-proper are the two most prominent examples. The Y-c.c. is an intermediate property between σ-centered and c.c.c., and Y-proper is intermediate between strongly proper and proper. These properties have interesting consequences, let us mention some: adding an unbounded real, preserving uncountable chromatic number of open graphs, not adding random reals, and not adding uncountable branches into trees. Moreover, partial orders with these properties appear naturally and many classical forcing notions do poses them. These properties behave also reasonably with respect to forcing iteration, and it is possible to get corresponding forcing axioms using posets in respective classes. The talk will focus on introducing these properties and proving basic fact about them. This is a joint work with Jindra Zapletal.
2014-12-04	Serikzhan Badaev (Al-Farabi Kazakh National University, Kazakhstan)	Computably enumerable equivalence relations
I am going to remind (introduce) some classes of computably enumerable relations that are related to the idea of fixed point such as precomplete, weakly precomplete, uniformly finitely precomplete. These relations are considered with respect to m-reducibility. Some new joint results with Andrea Sorbi on interrelations of the mentioned above classes will be presented.
2014-12-11	Sergey Goncharov (Novosibirsk State University, Russia, and Russian Academy of Sciences)	Definability, complexity and index sets of classes of computable models
We will discuss some problem about definability and complexity of these descriptions for classes of computable modes. The main topic will connect with decidable models and characterizations of these classes. We will present the results about complexity of description of autostable relative to strong constructivizations computable models with finite signatures. We will discuss some related problems.
2014-12-18	Valentina Harizanov (The George Washington University, Washington, D.C., USA)	Maximal computably enumerable sets and vector spaces
A computably enumerable set is maximal if its complement is infinite but cannot be split by any computably enumerable set into two infinite parts. Maximal sets play an important role in computability theory, especially in the study of the lattice of computably enumerable sets. They are co-atoms in its quotient lattice modulo finite sets. Similarly, maximal vector spaces play an important role in the study of the lattice of computably enumerable vector spaces and its quotient lattice modulo finite dimension. We investigate principal filters determined by maximal spaces and how algebraic structure interacts with computability theoretic properties.