In this talk, I’ll sketch a way of unifying a wide variety of set theoretic approaches for generating new models from old models. The underlying methodology will draw from techniques in Sheaf Theory and the theory of Boolean Ultrapowers.

We describe a number of related questions at the interface of set theory and homology theory, centering on (1) the additivity of strong homology, and (2) the cohomology of the ordinals. In the first, the question is, at heart: To how general a category of topological spaces may classical homology theory be continuously extended? And in the tension between various potential senses of continuity lie a number of delicate set-theoretic questions. These questions led to the consideration of the Cech cohomology of the ordinals; the surprise was that this is a meaningful thing to consider at all. It very much is, describing or suggesting at once (i) distinctive combinatorial principles associated to the nth infinite cardinal, for each n, holding in ZFC, (ii) rich connections between cofinality and dimension, and (iii) higher-dimensional extensions of the method of minimal walks.

One of the primary theoretical tools in machine learning is Vapnik-Chervonenkis dimension (VC dimension), which measures the maximum number of distinct data points a hypothesis set can distinguish. This concept is primarily used in assessing the effectiveness of training classification algorithms from data, and it is established that having finite VC dimension guarantees uniform versions of the various laws of large numbers, in the sense of e.g. Dudley (2014). An important result of Laskowski (1992) showed that finite VC dimension corresponds to a logical notion independently developed by Shelah, known as the non-independence property, and in subsequent decades much work has been done on finite VC dimension within model theory under the aegis of so-called NIP theories (cf. Simon, 2015).

However, despite this deep connection to logic, there has been little done on the computable model theory of VC dimension (one recent exception being Andrews and Guingona, 2016). The basic questions here are the following: (1) how computationally difficult is it to detect that one is in a setting with finite VC dimension?, and (2) if one is in this situation, how hard is it to compute what the precise VC dimension is? The current paper aims to answer these questions and discuss their implications.

Reference

Andrews, U. and Guingona, V. (2016). A local characterization of VC-minimality. Proceedings of the American Mathematical Society, 144(5):2241–2256.

Dudley, R. M. (2014). Uniform central limit theorems, volume 142 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, New York, second edition.

Laskowski, M. C. (1992). Vapnik-Chervonenkis classes of definable sets. Journal of the London Mathematical Society, 45(2):377–384.

Simon, P. (2015). A Guide to NIP Theories. Lecture Notes in Logic. Cambridge University Press, Cambridge.

Classification problems occur in all areas of mathematics. Descriptive set theory provides methods to assign complexity to such problems. Using a technique developed by Hjorth, Kechris and Sofronidis proved, for example, that the problem of classifying all unitary operators $\mathcal{U}(\mathcal{H})$ of an infinite dimensional Hilbert space up to unitary equivalence $\simeq_U$ is strictly more difficult than classifying graph structures with domain $\mathbb{N}$ up to isomorphism.

 
We present a game--theoretic approach to anti--classification results for orbit equivalence relations and use this development to reorganize conceptually the proof of Hjorth's turbulence theorem.  We also introduce a dynamical criterion for showing that an orbit equivalence relation is not Borel reducible to the orbit equivalence relation induced by a CLI group action; that is, a group which admits a complete left invariant metric (recall that, by a result of Hjorth and Solecki, solvable groups are CLI). We deduce that $\simeq_U$ is not classifiable by CLI group actions.

This is a joint work with Martino Lupini.  

We explore the applications of the pcf theory to cardinal estimates.