Archives of: Kurt Godel Research Center

Benjamin Vejnar: Complexity of the homeomorphism relation between compact spaces

Talk held by Benjamin Vejnar (Charles University, Prague, Czech Republic) at the KGRC seminar on 2019-01-24.

Abstract: We study the complexity of the homeomorphism relation of compact metrizable spaces when restricted to some subclasses such as continua, regular continua or regular compacta. The complexity of an equivalence relation on a Polish space is compared with some others (e.g. with the universal orbit equivalence relation) using the notion of Borel reducibility.

Moritz Müller: Forcing against bounded arithmetic

Talk held by Moritz Müller (Universitat Politècnica de Catalunya, Barcelona, Spain) at the KGRC seminar on 2019-01-17.

Abstract: We study the following problem. Given a nonstandard model of arithmetic we
want to expand it by a binary relation that does something prohibitive,
e.g. violates the pigeonhole principle in the sense that it is the graph
of a bijection from $n+1$ onto $n$ for some (nonstandard) $n$ in the
model. The goal is to do so while preserving as much as possible of true
arithmetic. More precisely, we want the expansion to model the least
number principle for a class of formulas as large as possible. The problem
is of central importance in bounded arithmetic and propositional proof
complexity. It is not well understood. The talk describes a general method
of forcing to produce such expansions.

Natasha Dobrinen: Mini-course on Infinitary Ramsey theory

Time and Place: Tuesday, January 8 and Wednesday, January 9  at 10:30am in the KGRC lecture room (both parts) at the KGRC.

Part I.    Topological Ramsey spaces and applications to ultrafilters
Part II.   Ramsey theory on trees and applications to big Ramsey degrees

The Infinite Ramsey Theorem states that given $n,r\ge 1$ and a coloring of
all $n$-sized subsets of $\mathbb{N}$ into $r$ colors, there is an
infinite subset of $\mathbb{N}$ in which all $n$-sized subsets have the
same color.  There are several natural ways of extending Ramsey’s Theorem.
One extension is to color infinite sets rather than finite sets.  In this
case, the Axiom of Choice precludes a full-fledged generalization, but
upon restricting to definable colorings, much can still be said.  Another
way to extend Ramsey’s Theorem is to color finite sub-objects of an
infinite structure, requiring an infinite substructure isomorphic to the
original one.  While it is not possible in general to obtain substructures
on which the coloring is monochromatic, sometimes one can find bounds on
the number of colors, and this can have implications in topological
dynamics.

In Part I, we will trace the development of Ramsey theory on the Baire
space, from the Nash-Williams Theorem for colorings of clopen sets to the
Galvin-Prikry Theorem for Borel colorings, culminating in Ellentuck’s
Theorem correlating the Ramsey property with the property of Baire in a
topology refining the metric topology on the Baire space.  This refinement
is called the Ellentuck topology and is closely connected with Mathias
forcing.  Several classical spaces with similar properties will be
presented, including the Carlson-Simpson space and the Milliken space of
block sequences.  From these we shall derive the key properties of
topological Ramsey spaces, first abstracted by Carlson and Simpson and
more recently given a refined presentation by Todorcevic in his book {\em
Introduction to Ramsey spaces}.  As the Mathias forcing is closely
connected with Ramsey ultrafilters, via forcing mod finite initial
segments, so too any Ramsey space has a $\sigma$-closed version which
forces an ultrafilter with partition properties.  Part I will show how
Ramsey spaces can be used to find general schemata into which disparate
results on ultrafilters can be seen as special cases, as well as obtain
fine-tuned results for structures involving ultrafilters.

Part II will focus on Ramsey theory on trees and their applications to
Ramsey theory of homogeneous structures. An infinite structure is {\em
homogeneous} if each isomorphism between two finite substructures can be
extended to an automorphism of the infinite structure.  The rationals as a
linearly ordered structure and the Rado graph are prime examples of
homogeneous structures.  Given a coloring of singletons in the rationals,
one can find a subset isomorphic to the rationals in which all singletons
have the same color.  However, when one colors pairs of rationals, there
is a coloring due to Sierpinski for which any subset isomorphic to the
rationals has more than one color on its pairsets.  This is the origin of
the theory of {\em big Ramsey degrees}, a term coined by Kechris, Pestov
and Todorcevic, which investigates bounds on colorings of finite
structures inside infinite structures.  Somewhat surprisingly, a theorem
of Halpern and L\”{a}uchli involves colorings of products of trees,
discovered en route to a proof that the Boolean Prime Ideal Theorem is
strictly weaker than the Axiom of Choice, is the heart of most results on
big Ramsey degrees.  We will survey big Ramsey degree results on countable
and uncountable structures and related Ramsey theorems on trees, including
various results of Dobrinen, Devlin, D\v{z}amonja, Hathaway, Larson,
Laver, Mitchell, Shelah, and Zhang.

Natasha Dobrinen: Ramsey Theory of the Henson graphs

Abstract: A central question in the theory of ultrahomogeneous relational structures asks, How close of an analogue to the Infinite Ramsey Theorem does it carry? An infinite structure S is ultrahomogeneous if any isomorphism between two finitely generated substructures of S can be extended to an automorphism of S. We say that S has finite big Ramsey degrees if for each finite substructure A of S, there is a number n(A) such that any coloring of the copies of A in S can be reduced to no more than n(A) colors on some substructure S of S, which is isomorphic to the original S.

The two main obstacles to a fuller development of this area have been lack of representations and general Milliken-style theorems. We will present new work proving that the Henson graphs, the kk-clique free analogues of the Rado graph for k3, have finite big Ramsey degrees. We devise representations of Henson graphs via strong coding trees and prove Milliken-style theorems for these trees. Central to the proof is the method of forcing, building on Harrington’s proof of the Halpern-Läuchli Theorem.

Daniel T. Soukup – New aspects of ladder system uniformization II

Talk held by Daniel Soukup (KGRC) at the KGRC seminar on 2018-12-13.

Abstract: We continue the previous lecture and present proofs for some of the new results. We show that $\diamondsuit$ implies that for any Aronszajn-tree $T$, there is a ladder system with a 2-colouring with no $T$-uniformization. However, if $\diamondsuit^+$ holds then for any ladder system $C$ there is an Aronszajn tree $T$ so that any monochromatic colouring of $C$ has a $T$-uniformization (cf. https://arxiv.org/abs/1806.03867).

Stevo Todorcevic: Ramsey degrees of topological spaces

Talk held by Stevo Todorcevic (University of Toronto, Canada) at the KGRC seminar on 2018-12-04.

Abstract: This will be an overview of structural Ramsey theory when the objects are topological spaces. Open problems and directions for further research in this area will also be examined.

Daniel Soukup: New aspects of ladder system uniformization

Talk held by Daniel Soukup (KGRC) at the KGRC seminar on 2018-11-29.

Abstract: Given a tree $T$ of height $\omega_1$, we say that a ladder system colouring $(f_\alpha)_{\alpha\in \lim\omega_1}$ has a $T$-uniformization if there is a function $\varphi$ defined on a subtree $S$ of $T$ so that for any $s\in S_\alpha$ of limit height and almost all $\xi\in dom (f_\alpha)$, $\varphi(s\upharpoonright \xi)=f_\alpha(\xi)$.

In sharp contrast to the classical theory of uniformizations on $\omega_1$, J. Moore proved that CH is consistent with the statement that any ladder system colouring has a $T$-uniformization (for any Aronszajn tree $T$). Our goal is to present a fine analysis of ladder system uniformization on trees pointing out the analogies and differences between the classical and this new theory. We show that if $S$ is a Suslin tree then CH implies that there is a ladder system colouring without $S$-uniformization, but $MA(S)$ implies that any ladder system colouring has even an $\omega_1$-uniformization.

Furthermore, it is consistent that for any Aronszajn tree $T$ and ladder system $\mathbf C$ there is a colouring of $\mathbf C$ without a $T$-uniformization; however, and quite surprisingly, $\diamondsuit^+$ implies that for any ladder system $\mathbf C$ there is an Aronszajn tree $T$ so that any monochromatic colouring of $\mathbf C$ has a $T$-uniformization. We also prove positive uniformization results in ZFC for some well-studied trees of size continuum. (cf. https://arxiv.org/abs/1806.03867 and https://arxiv.org/abs/1803.03583)

Raphaël Carroy – A dichotomy for topological embeddability between continuous functions

Talk held by Raphaël Carroy (KGRC) at the KGRC seminar on 2018-11-22.

Abstract

We say a function $f$ embeds (topologically) in a function $g$
when there are two topological embeddings $\sigma$ and $\tau$
satisfying $\tau \circ f = g \circ \sigma$. I will prove the
following dichotomy: the quasi-order of topological embeddability
between continuous functions on compact zero-dimensional Polish spaces
is either an analytic complete quasi-order, or a well-quasi-order.

This is a joint work with Yann Pequignot and Zoltán Vidnyánszky.

Russell G. Miller: Hilbert’s Tenth Problem for Subrings of the Rational Numbers

Talk held by Russell Miller (Queens College, City University of New York (CUNY), USA) at the KGRC seminar on 2018-11-15.

 

Abstract: When considering subrings of the field $\mathbb{Q}$ of rational numbers, one can view Hilbert’s Tenth Problem as an operator, mapping each set $W$ of prime numbers to the set $HTP(R_W)$ of polynomials in $\mathbb {Z}[X_1,  X_2, \ldots]$ with solutions in the ring $R_W = \mathbb{Z}[W^{-1}]$. The set $HTP(R_{\emptyset})$ is the original Hilbert’s Tenth Problem, known since 1970 to be undecidable. If $W$ contains all primes, then one gets $HTP(\mathbb{Q})$, whose decidability status is open. In between lie the continuum-many other subrings of $\mathbb{Q}$.

We will begin by discussing topological and measure-theoretic results on the space of all subrings of $\mathbb{Q}$, which is homeomorphic to Cantor space. Then we will present a recent result by Ken Kramer and the speaker, showing that the HTP operator does not preserve Turing reducibility. Indeed, in some cases it reverses it: one can have $V <_T W$, yet $HTP(R_W) <_T HTP(R_V)$. Related techniques reveal that every Turing degree contains a set $W$ which is \emph{HTP-complete}, with $W’ \le_1 HTP(R_W)$. On the other hand, the earlier results imply that very few sets $W$ have this property: the collection of all HTP-complete sets is meager and has measure $0$ in Cantor space.

Thilo Weinert: On Order-Types in Polarised Partition Relations

Talk held by Thilo Weinert (KGRC) at the KGRC seminar on 2018-11-08.

Abstract: The history of the polarised partition relation goes back to the original seminal paper by Erdős and Rado from 1956. For the ordinary partition relation after some time one also investigated order-types. For the polarised partition relation however, I am only aware of three papers where order-type played a role and here nothing beyond well-orders ever seems to have been considered.

We are attempting to rectify this. We will present an analogue of a theorem of Jones and a potentially vacuous generalisation of a proposition of Garti and Shelah. Furthermore we will show limits to further generalisations and analogues and will exhibit some open problems.

This is joint work with Lukas Daniel Klausner.