| date | speaker | title |
|---|---|---|
| 2012-01-12 | Howard Becker (Universität Münster, Germany) | Isomorphism of Computable Structures and Vaught's Conjecture |
| The following question is open: Does there exist a hyperarithmetic class of computable structures with at least one, but only finitely many, properly \(\Sigma^1_1\) isomorphism classes? Given any oracle \(x\) in \(2^\omega\), we can ask the same question relativized to \(x\) (that is, replace hyperarithmetic, computable, and \(\Sigma^1_1\) by hyperarithmetic-in-\(x\), computable-in-\(x\), and \(\Sigma^1_1\)-in-\(x\)). A negative answer for all \(x\) implies Vaught's Conjecture for infinitary logic. | ||
| 2012-01-19 | André Nies (University of Auckland, New Zealand) | Borel structures and Borel theories |
| Continuum size structures occur naturally in analysis, algebra, and other areas. Examples are the additive group of real numbers, and the ring of continuous functions on the unit interval. How about effectiveness constraints on their presentations? A reasonable approach is to require that domain and relations are Borel. Structures from these areas usually have such Borel presentations. Borel structures were introduced by H. Friedman in 1978. He proved among other things that each countable theory has a Borel model of size the continuum. Hjorth and I considered the case where the language is uncountable but Borel (for instance, the language of a vector space over the reals). In a JSL paper (June 2011) we show that the completeness theorem fails for Borel structures of this kind: some complete Borel theory has no Borel model. I will also include open questions. For instance, does every Borel field Borel embed into a Borel algebraically closed field? If not, this would yield an alternative proof of my result with Hjorth. A further long-standing question is whether the Boolean algebra of subsets of natural numbers modulo finite sets has an injective Borel presentation. | ||
| 2012-03-01 | Michael Pinsker (Paris 7, France, TU Wien, Austria, and Hebrew University of Jerusalem, Israel) | Reducts of the random partial order |
| I will present a recent result which states that up to first-order interdefinability, there exist precisely 5 structures which are first-order definable in the universal homogeneous partial order. I will also outline the proof of this result, which is achieved by finding all closed permutation groups which contain the automorphism group of this order. The method for finding the groups relies on a Ramsey-theoretic analysis of permutations acting on the order, which makes it possible to find regular patterns in such permutations and make them accessible to finite combinatorial arguments. | ||
| 2012-03-08 | Yurii Khomskii (KGRC) | Regularity Idealized |
| I would like to talk about regularity properties of sets of reals and how these can be uniformly defined within the abstract framework of "idealized forcing" developed by Jindrich Zapletal. All the classical regularity properties, such as Lebesgue measurability, the Baire, Ramsey and perfect set properties, as well as more recent ones such as Sacks-, Miller- and Laver-measurability, fit naturally into this framework. Consequently, many results regarding such properties, particularly in relation to descriptive set theory, can now be given uniform proofs. This was one of the lines of research I pursued in my PhD thesis. Granted, many results presented here are strictly speaking not new but abstractions or generalizations of previously known results, such as those of Solovay, Judah-Shelah, Brendle, Loewe, Zapletal and Ikegami. However, the current framework seeks to explore and better explain the relationships between all these individual results. Moreover, many interesting open questions naturally arise along the way, and I would like to use this opportunity to present them to a larger audience. | ||
| 2012-03-15 | Giorgio Laguzzi (KGRC) | Separation of regularity properties |
| The talk centers around the separation of different regularity properties of sets of reals, topic which I deal with in my PhD thesis under the supervision of Sy Friedman. The notion of regularity will be presented in a rather general way; the approach will be slightly different (but practically equivalent) from Yurii Khomskii's one. Results of separation will include statements regarding the 2nd level of projective hierarchy and statements about the full family of all sets of reals. The main result of the talk will be the construction of a model where every set of reals is Silver-regular, but there exists a non-Miller-regular set, for which Shelah's amalgamation will be essential. | ||
| 2012-03-22 | Moritz Müller (KGRC) | Refutation complexity of relativized spectra |
| How difficult is it to prove that a given first-order sentence does not have a finite model of a given size? This can be understood in two natural, roughly equivalent ways. First, as a question for how strong a fragment of arithmetic needs to be to prove the statement. Second, as a question concerning proof lengths in certain propositional calculi. The talk gives a short introduction to proof complexity and presents some exponential lower bounds for the \(R(k)\) systems. This is joint work with Albert Atserias and Sergi Oliva. | ||
| 2012-03-29 | Sy-David Friedman (KGRC) | The complexity of isomorphism |
| If \(X\) is a set of reals then \(Iso(X)\) denotes the set of pairs \((x,y)\) from \(X\) such that \(x,y\) code isomorphic structures on \(\omega\). This is the restriction to \(X\) of a \(\Sigma_1^1\) equivalence relation. We say that \(Iso(X)\) is weakly complete if whenever \(E\) is a \(\Sigma_1^1\) equivalence relation there are functions \(f,g\) which are \(\Delta_1^1\) with parameters from \(X\) such that for \(x,y\) in \(X, E(x,y)\) iff \(Iso(f(x,y),g(x,y))\), and is complete if there is a function \(f\) which is \(\Delta_1^1\) with parameters from \(X\) such that for \(x,y\) in \(X, E(x,y)\) iff \(Iso(f(x),f(y))\). Let \(R\) denote the set of all reals and \(Comp\) the set of all computable reals. Then \(Iso(R)\) is weakly complete but not complete and \(Iso(Comp)\) is complete (the latter due to Fokina-F-Harizanov-Knight-McCoy-Montalban). I don't know if \(Iso(Hyp)\) is complete, where \(Hyp\) denotes the set of hyperarithmetic reals. One can also consider \(Iso\) on structures with universe \(\omega_1\), assuming \(V = L\). Then \(Iso(\omega_1\text{-}Comp)\) is again complete, but it is not known if \(Iso\) for arbitrary \(\omega_1\) structures is complete (it is weakly complete). | ||
| 2012-04-19 | Martin Bays (McMaster University, Ontario, Canada) | Abelian integrals and categoricity |
An integral of the form \(\int_{P_0}^P f(x,y)dx\), where \(f\) is a rational function and \(x\) and \(y\) satisfy a polynomial dependence \(p(x,y)=0\), is known as an Abelian integral. Fixing one endpoint \(P_0\) and allowing the other to vary on the Riemann surface \(p(x,y)=0\), we obtain a multifunction whose value depends on the (homology class of) the path along which we integrate. We consider the model-theoretic status of such multifunctions, and in particular the problem of giving categorical elementary descriptions of structures incorporating them and their interactions with the complex field. Following work by Zilber and Gavrilovich, we will find that the classical theory of Abelian varieties, along with Faltings' work and some model theoretic ideas due to Shelah, allow us to give partially satisfactory answers in some special cases. | ||
| 2012-04-26 | Diego Alejandro Mejía Guzmán (Universidad Nacional de Colombia) | Matrix iterations and Cichon's diagram |
| Using matrix iterations of ccc posets, we prove the consistency with ZFC of some cases where the cardinals on the right hand side of Cichon's diagram take two or three arbitrary values (two regular values, the third one with uncountable cofinality). Also, mixing this with Brendle's techniques in his paper [http://www.jstor.org/stable/10.2307/2275049 Larger cardinals in Cichon's diagram], we can prove that it is consistent with ZFC to assign, at the same time, several arbitrary regular values on the left hand side of Cichon's diagram. | ||
| 2012-05-03 | Hubie Chen (Universitat Pompeu Fabra, Barcelona, Spain) | Meditations on Quantified Constraint Satisfaction |
| <nowiki> The quantified constraint satisfaction problem (QCSP) is the computational problem of deciding, given a structure and a first-order prenex sentence whose quantifier-free part is the conjunction of atoms, whether or not the sentence holds on the structure. One obtains a family of problems by defining, for each structure B, the problem QCSP(B) to be the QCSP where the structure is fixed to be B. We will discuss the research program of trying to classify the complexity of QCSP(B) for each finite structure B. It is possible to associate an algebra to each finite structure in such a way that studying the algebra of a structure gives insight into the QCSP complexity of the structure. We will overview the use of universal-algebraic notions and techniques in this research program. In particular, there is a close connection between QCSP complexity and the growth rate of the number of elements needed to generate the powers A1, A2, ... of an algebra A: showing an at-most polynomial growth rate can (essentially) be translated to a complexity upper bound for a structure with algebra A. This research area gives (we believe) a fascinating interplay among computational complexity, universal algebra, and logic. This talk will partially be based on the overview article available at [http://arxiv.org/abs/1201.6306 arxiv.org/abs/1201.6306]. | ||
| 2012-05-10 | Alexander Osipov (Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Russia) | Set-open topology on the space of continuous functions |
For a Tychonoff space \(X\), we denote by \(C_{\lambda}(X)\) the space of all real-valued continuous functions on \(X\) with set-open topology. We investigate the topological-algebraic properties of \(C_{\lambda}(X)\) such as submetrizability, metrizability, separability and other. We also compare this topology with several well-known and lesser known topologies (for example, topology of uniform convergence). | ||
| 2012-05-16 | André Nies (University of Auckland, New Zealand) | Complexity of equivalence relations |
| We study the complexity of equivalence relations, and in particular isomorphism relations, in a variety of settings: from descriptive set theory via computability theory to computational complexity theory. | ||
| 2012-05-24 | Jindrich Zapletal (U of Florida, USA and Czech Academy of Sciences) | Canonical Ramsey Theory on Polish Spaces |
| This is an update on the joint canonization program with Marcin Sabok and Vladimir Kanovei. For many classes of sigma-ideals ''I'' and many classes of analytic equivalence relations ''E'' there is a Borel ''I''-positive set ''B'' such that ''E'' has a very simple form on ''B''—such as ''B'' consists of pairwise inequivalent elements, or ''B'' consists of pairwise equivalent elements. In particular, this holds if ''I'' is a calibrated sigma-ideal generated by closed sets and ''E'' is an analytic equivalence relation. | ||
| 2012-05-31 | Misha Gavrilovich (KGRC) | Shelah's revised power function as a homotopy invariant |
| In the talk we shall construct a family of partial orders (with extra structure) on <κ-directed families of sets, and express some set theoretic invariants and notions in terms of these partial orders; namely Shelah's revised power function—the cardinal function featuring in Shelah's revised GCH theorem—and the notion of a measurable cardinal. We shall also try to show that our construction introduces a homotopy-theoretic point of view on these notions: these partial orderings (with the extra structure) satisfy an axiomatization of homotopy theory making them what are known as "model categories", and Shelah's revised power function is what is known as a "homotopy-invariant" "derived functor". | ||
| 2012-06-14 | Miguel Angel Mota (KGRC) | A spectral approach to reflection principles |
| Gödel's response to the incompleteness of ZFC with respect to assertions like the Continuum Hypothesis was that one should add new natural and well justified axioms that decide these assertions. Furthermore, he suggested strong axioms of infinity, now more commonly known as large cardinal axioms, as the natural candidates to be added to ZFC. The first such new axiom of infinity is the Axiom of Inaccessibles, asserting the existence of uncountable regular, strong limit cardinals. But this axiom is only an instance of a more general class of axioms: the so called Reflection Principles. It is our aim to give a brief mathematical presentation of these principles and to suggest a philosophical justification for them. Our justification does not depend on the current idea that the universe of all sets is so complex that it can not be uniquely characterized; but rather on the intuitive fact that if a property makes a clear division between an initial segment and the global behaviour of its elements then this initial segment must be a set, since it is the obvious way to attain with the greatest certainty and obviousness ever newer number classes, and with them all the different, successive, ascending powers occurring in physical or mental nature. In this talk we will discuss (with more or less depth) the general problem of accepting new axioms, the mathematical status of set theory, the alleged paradoxes, and the philosophical standpoint of mathematical realism. We think that all these topics are related, and that they can help us to see why reflection principles must be natural axioms for set theory. | ||
| 2012-06-28 | Andrey Morozov (Novosibirsk State University, Russia) | On Sigma-definability of structures over the reals |
| We give a brief survey of the results on structures \(\Sigma\)-definable over \(HF(R)\) and present some further results on the number of non-\(\Sigma\)-isomorphic presentations of the ordered field R of reals and of its ordering. In particular, we will discuss a question, whether is it possible to use R to 'improve' itself by creating its new classically isomorphic \(\Sigma\)-copy. | ||
| 2012-07-04 | Frank Tall (University of Toronto, Canada) | Topological problems for set theorists, II |
| This is the second of a series of talks I give every 25 years. The aim is to acquaint set theorists with interesting and/or important topological problems that are likely set-theoretic in nature and don't require much topological knowledge in order to work on. | ||
| 2012-07-05 | Antonio Montalbán (University of Chicago, USA) | A computability-theoretic equivalent of Vaught's Conjecture |
| 2012-07-10 | Russell Miller (Queens College, City College of New York, USA) | Finitary reducibility on equivalence relations |
Numerous authors have considered the notion of computable reducibility (or FF-reducibility, or \(m\)-reducibility) on equivalence relations on the natural numbers. This holds of equivalence relations \(E\) and \(F\) (written \(E\leq F\)) if there exists a computable total function \(f\) on \(\omega\) such that \(x~E~y\) if and only if \(f(x)~F~f(y)\). Recent results include both the existence of such reductions and, for many pairs of equivalence relations, the impossibility of any such reduction. Considering several of the proofs of non-reducibility, we have defined a weaker notion, finitary reducibility, to help analyze these negative results. We say that \(E\) is \(n\)-arily reducible to \(F\), written \(E \leq_c^n F\), if there are computable total functions \(f_1,\ldots,f_n:\omega^n\to\omega\) such that, for all \(j,k\leq n\) and all \(i_1,\ldots,i_n\in\omega\), \(i_j~E~i_k\) if and only if \(f_j(i_1,\ldots,i_n)~F~f_k(i_1,\ldots,i_n)\). If the indices of such functions can be found uniformly for every \(n\), then \(E\) is finitarily reducible to \(F\), written \(E\leq_c^{\omega}F\). In this talk we will give examples of how these new notions can be used. | ||
| 2012-07-11 | Julia Knight (University of Notre Dame, USA) | An example illustrating a theorem of Gregory |
| John Gregory showed (in 1970) that for a countable admissible set \(A\), if \(T\) is set of \(L_A\) sentences that is \(\Sigma_1\) on \(A\) and \(T\) has models \(\mathcal{M}\) and \(\mathcal{N}\) such that \(\mathcal{N}\) is a proper \(L_A\)-elementary extension of \(\mathcal{M}\), then \(T\) has an uncountable model. I will describe an example showing that the result fails if we drop the assumption that \(T\) is \(\Sigma_1\) on \(A\). This is joint work with my three current students, Jesse Johnson, Victor Ocasio, and Steven VanDenDriessche. The construction involves iterated forcing. | ||
| 2012-10-04 | Vadim Kulikov (KGRC) | Analyzing the Complexity of Wild Knot Equivalence |
| A wild knot is an embedding of the unit circle into the three dimensional Euclidean space \(\mathbb{R}^3\), or more conventionally its one-point compactification \(S^3\). Two knots \(f\) and \(g\) are defined to be equivalent, if there exists an orientation preserving homoemorphism \(H\) of \(S^3\) onto itself that takes one knot to another: either \(H\circ f = g\) or just \(range(H\circ f)=range(g)\). We show that the isomorphism relation on all countable structures (in a finite vocabulary) is continuously reducible to this equivalence relation which provides a lower bound for the complexity of wild knot equivalence. | ||
| 2012-10-11 | Dan Turetsky (KGRC) | Racing Pawns, Internal Hyperarithmetic Comprehension, and the Law of the Excluded Middle |
| Galvin's "racing pawns" game involves two players using a tree as a chessboard and attempting to queen their pawn while interfering with their opponent's pawn. We show that the fact that the first player (“white”) wins every instance of this game (for countable trees) is equivalent to arithmetic transfinite recursion. Along the way we analyse the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas. | ||
| 2012-10-18 | Asger Törnquist (University of Copenhagen, Denmark) | The Poulsen simplex as a Fraisse limit |
| A Choquet simplex is an infinite dimensional generalization of the classical notion of a simplex (a polytope where every point is uniquely the convex combination of extremal points). Choquet asked in the 1950's if there is a metrizable Choquet simplex where the extremal boundary is dense in the simplex. This question was answered in the affirmative by Ebbe Thue Poulsen in a 1961 paper. Later, in 1978, it was shown that by Lindenstrauss, Olsen and Sternfeld that Poulsen's simplex is unique (with the prescribed properties) up to affine continuous isomorphism, and, moreover, that it is a highly homogeneous object. In this talk, I will discuss how the Poulsen simplex, P, can be constructed as a Fraisse limit. I will also discuss some vexing questions related to the automorphism group of P. This is joint work with Clinton Conley (formerly of the KGRC, now at Cornell). '''Please note:''' The talk has been rescheduled to Thursday, October 18, 10:30am. | ||
| 2012-10-18 | Laura Fontanella (KGRC) | Large Properties at Small Cardinals |
| One of the most intriguing research areas is the study of properties associated with large cardinals, that can be satisfied by small cardinals as well. The tree property is a notable example of such properties. Indeed, an inaccessible cardinal is weakly compact if and only if it satisfies the tree property. Strongly compact and supercompact cardinals admit a similar characterization in terms of combinatorial properties. An inaccessible cardinal is strongly compact if and only if it satisfies the strong tree property; it is supercompact if and only is it satisfies the super tree property. We discuss some consistency results concerning the strong and super tree properties at small cardinals. | ||
| 2012-11-08 | Shuguo Zhang (Sichuan University, People's Republic of China) | Relations between the I-ultrafilters |
\(I\)-ultrafilters were introduced by J. Baumgartner in 1995. In this talk, under the continuum hypothesis, we show the following results: * (1) There is a discrete ultrafilter which is not a \(Z_0\)-ultrafilter. * (2) There is a \(\sigma\)-compact ultrafilter which is not a \(Z_0\)-ultrafilter. * (3) There is a \(J_3^\omega\) ultrafilter which is not a \(Z_0\)-ultrafilter, where \(Z_0\) is the ideal of subsets of \(\omega\) with asymptotic density zero. This is joint work with Jianyong Hong. '''Please note:''' This announcement brings a change of program. Martin Goldstern will give his talk in the research seminar on a later day. | ||
| 2012-11-15 | Matthias Schröder (KGRC) | Computable Analysis and Topology |
| Computable Analysis investigates computability on the Euclidean space \(\mathbb{R}\) and on related spaces. One approach to Computable Analysis is the Type Two Model of Effectivity (TTE). TTE provides a computational framework for non-discrete topological spaces with cardinality of at most card\((\mathbb{R})\). We will give a short introduction to TTE. The basic tool of TTE are representations. A representation equips the objects of a given space with "names", which are infinite words. On these names the computation is performed. We discuss the property of admissibility as a well-behavedness criterion for representations. Then we characterise the class of topological spaces which can be equipped with an admissible representation. The ensuing category has a remarkably rich structure. | ||
| 2012-11-22 | Martin Goldstern (TU Wien, Austria) | Cardinal characteristics in Cichon's diagram |
Cichon's diagram describes the relationships between 12 infinite cardinal numbers, among them * \(\aleph_1\) and \(\mathfrak{c}\)=continuum (the smallest and largest of the 12) * \(\operatorname{cov(N)}\) and \(\operatorname{cov(M)}\), the covering numbers of the ideals of Lebesgue null and meager sets, respectively i.e., the answers to the questions "how many null/meager sets do we need to cover the reals?" * \(\mathfrak{b}\) and \(\mathfrak{d}\), the bounding and dominating numbers. (The dominating number \(\mathfrak{d}\) is the smallest size of a family of \(\sigma\)-compact sets covering the irrationals.) "ZFC + \(\mathfrak{c}=\aleph_1\)" implies of course that all 12 cardinals have the same value. All possible consequences for Cichon's diagram of the axioms "ZFC + \(\mathfrak{c}=\aleph_2\)" are known, or in other words: for every assignment of the values \(\aleph_1\) and \(\aleph_2\) to the cardinals in Cichon's diagram it is known whether there is a ZFC-universe in which this assignment is realized. It is notoriously difficult to construct universes with prescribed properties in which \(\mathfrak{c}\) is large (even just larger than \(\aleph_2\)). After discussing background and known results, I will highlight some features of a construction that will appear in a joint paper with Arthur Fischer, Jakob Kellner and Saharon Shelah. Our construction is a "creature iteration" (which is almost, but not quite, entirely unlike a product of creature forcings). All universes we construct will satisfy \(\mathfrak{d}=\aleph_1\) (which implies, among others, \(\operatorname{cov(M)}=\aleph_1\)), while the cardinals that are not obviously bounded by \(\mathfrak{d}\) can have (almost) arbitrary regular values. | ||
| 2012-11-29 | Peter Telec (KGRC) | The history of logic at the University of Vienna |
| ''Sorry, there is no abstract for this talk in our database.'' '''Please note''' the unusual times: tea at 4.30pm (instead of 3.30pm), talk at 5.00pm (instead of 4.00pm)! | ||
| 2012-12-06 | Dan Turetsky (KGRC) | Computable Categoricity |
This talk is in the area of computable model theory. A computable model is called "computably categorical" if for every two computable copies, there is a computable isomorphism between them. As defined, this is an external property of the model – the statement does not involve the internal structure of the model. A closely related property is being "relatively computably categorical" (which will be defined in the talk). Goncharov showed that being relatively computably categorical is equivalent to a nice internal property of the model; a model is relatively computably categorical if and only if the realized types of the model are all effectively isolated. We present a pathological collection of models which demonstrate that computable categoricity does not correspond to any internal property of this form. These models also allow us to show that the property of being computably categorical is \(\Pi^1_1\)-complete. | ||
| 2012-12-13 | Sam Sanders (Ghent University, Belgium and MCMP München, Germany) | Reuniting the antipodes: bringing together Nonstandard Analysis and Constructive Analysis |
Constructive Analysis (aka BISH) was introduced by Errett Bishop as a `computational' redevelopment of Mathematics in the spirit of the intuitionistic tradition. As such, BISH is based on the BHK (Brouwer-Heyting-Kolmogorov) interpretation of logic, where the notions of `proof' and `algorithm' are central. Constructive Reverse Mathematics (CRM) is a spin-off from Harvey Friedman's `Reverse Mathematics' program where the base theory is based on BISH. In this talk, we introduce an interpretation of BISH in classical Nonstandard Analysis. The role of `proof' in this interpretation is played by the Transfer Principle of Nonstandard Analysis. The role of `algorithm' is played by `\(\Omega\)-invariance'. Intuitively, an object is \(\Omega\)-invariant if it does not depend on the '''choice''' of infinitesimal used in its definition. Using this new interpretation, we obtain many of the well-known results form CRM. In particular, all non-constructive principles (like LPO, LLPO, MP, etc) are interpreted as Transfer Principles, which are not available in our (nonstandard) base theory. | ||
| 2012-12-20 | Leandro F. Aurichi (ICMC-USP, University of São Paulo, Brazil) | Some selective versions of separability-like properties |
We will present some selective versions of separability, as R-separability and M-separability. Then we will discuss about D-separability and its relations with d-separability (the first is a selective version of the second. The second is a generalization of separability). We also plan to present some results related to a selective version of the c.c.c. property. | ||
