Cross-Alps Logic Seminar

Tutti i seminari si terranno online via Webex. Per avere link e password dei meeting e per informazioni riguardo i seminari, per favore scrivere a luca.mottoros [at] unito.it.

Le registrazioni di alcuni video sono disponibili a questo indirizzo.

A venir:

  • 5 aprile 2024, 16.00-17.00 (Online on Webex)

    L. Motto Ros (Università degli studi di Torino) "Borel complexity of graph homomorphism".

    Abstract.

    We consider several classes of countable graphs naturally arising in the context of graph theory and combinatorics, and analyze the complexity with respect to Borel reducibility of the homomorphism relation on them. The outcome is a sort of empirical dichotomy asserting that for each of these classes, either there are few incomparable graphs, or else the homomorphism relation is invariantly universal (and hence complete for analytic quasi-orders). This considerably extends a result by Louveau and Rosendal and shows that many widely considered graph-theoretic constraints do not affect the complexity of graph homomorphism. (Joint work with Salvatore Scamperti)

    Nascondi abstract.

  • 3 maggio 2024, 16.00-17.00 (Online on Webex)

    S. Unger (University of Toronto) TBA.

    Abstract.

    TBA

    Nascondi abstract.

  • 31 maggio 2024, 16.00-17.00 (Online on Webex)

    M. Dzamonja (CNRS-Université de Paris / IHPST) TBA.

    Abstract.

    TBA

    Nascondi abstract.

  • 7 giugno 2024, 16.00-17.00 (Online on Webex)

    L. Halbeisen (ETH Zürich) TBA.

    Abstract.

    TBA

    Nascondi abstract.

Passé:

  • 1 marzo 2024, 16.00-17.00 (Online on Webex)

    S. Henry (University of Ottawa) "Higher categorical language" (Video).

    Abstract.

    It is a well-known result that first-order formulas in the language of categories that do not use equality between objects are automatically invariant under isomorphism and equivalence of categories. The aim of this talk is to explain how this can be generalized to any kind of "higher structures". More precisely, given any Quillen model category, we will attach to it a first-order language whose formulas are automatically invariant under homotopies and weak equivalences between the fibrant objects. This is already useful for direct practical applications by allowing us to automatically deduce in concrete situations that notions are invariant under "weak equivalences" without proof, but it also opens the door to a higher categorical version of model theory. Partly joint work with César Bardomiano-Martinez.

    Nascondi abstract.

  • 19 gennaio 2024, 16.00-17.00 (Online on Webex)

    C. Steinhorn (Vassar College) "O-minimality as a framework for tame mathematical economics".

    UNESCO World Logic Day Seminar


    Abstract.

    This talk would focus on preference and utility theory in the context of o-minimal expansions of the ordered field of real numbers. We give a complete description of all preferences that can be defined in such a structure. We also raise questions about incomplete preferences in this context.

    Nascondi abstract.

Espandi 2023
Nascondi 2023.
  • 1 dicembre 2023, 16.00-17.00 (Online on Webex)

    Z. Vidnyánszky (Eötvös Loránd University) "Homomorphisms in the choiceless world" (Video).

    Abstract.

    I will discuss an important recent result from computational complexity, the so called CSP Dichotomy Theorem and its connections to certain ZF models. The CSP Dichotomy states that a homomorphism problem is either easy (in P) or hard (NP-complete). It turns out that there is a rather natural ZF analogue of this statement, which I will sketch the proof of. The talk will be accessible without prior familiarity with choiceless models or computational complexity.

    Nascondi abstract.

  • 3 novembre 2023, 16.00-17.00 (Online on Webex)

    S. Lempp (University of Wisconsin) "The complexity of the class of models of arithmetic" (Slides,Video).

    Abstract.

    In joint work with Andrews and Rossegger, we investigate the descriptive complexity of the set of models of theories in the language of arithmetic. Using classical results of Solovay and Knight, we give sufficient conditions for complete theories to have a boldface-Pi^0_omega-complete set of models.

    Nascondi abstract.

  • 16 giugno 2023, 16.00-17.00 (Online on Webex)

    A. Nies (Università di Auckland) "Computably totally disconnected, locally compact groups" (Video).

    Abstract.

    In the first part of the talk I will introduce two notions of computable presentation of a totally disconnected, locally compact (t.d.l.c.) group, and show their equivalence. The first relies on standard notions of computability in the uncountable setting. The second restricts computation to a countable structure of approximations of the elements, the “meet groupoid” of compact open cosets. Based on this, I obtain various examples of computably t.d.l.c. groups, such as \(\operatorname{Aut}(T_d)\) and some algebraic groups over the field of \(p\)-adic numbers.
    In the second part I show that given a computable presentation of a t.d.l.c. group, the modular function and the Cayley-Abels graphs (in the compactly generated case) are computable. I give an example where the scale function fails to be computable.
    I explain why the class of computably t.d.l.c. groups is closed under most of the constructions studied by Wesolek.
    Time permitting, I will give a criterion when a computable presentation is unique up to computable isomorphism. Joint work with Alexander Melnikov.

    Nascondi abstract.

  • 9 giugno 2023, 16.00-17.00 (Online on Webex)

    U. Kohlenbach (Università Tecnica di Darmstadt) "Proof mining: Recent developments" (Video).

    Abstract.

    In this talk we survey some recent developments in the project of applying proof-theoretic transformations to obtain new quantitative and qualitative information from given proofs in areas of core mathematics such as nonsmooth optimization, geodesic geometry and ergodic theory. We will discuss some of the following items:
    (1) Proof mining in the context of set-valued monotone and accretive operators with applications in nonsmooth optimization such as inconsistent feasibility theorems (partly joint work with Nicholas Pischke).
    (2) Recent linear rates of asymptotic regularity as well as rates of metastability for Tikhonov-regularization methods (joint work with Horaţiu Cheval and Laurenţiu Leuştean).
    (3) The extraction of uniform rates of convergence for the \(\varepsilon\)-capture in the Lion-Man game in a general geodesic setting from a proof that made iterated use of sequential compactness arguments (i.e. arithmetical comprehension). The extraction also qualitatively generalizes previously known results (joint work with Genaro López-Acedo and Adriana Nicolae).
    (4) Recent applications to ergodic theory (joint work with Anton Freund).

    Nascondi abstract.

  • 19 maggio 2023, 16.00-17.00 (Online on Webex)

    J. Duparc (Università di Losanna) "The Wadge order on the Cantor Space and on the Scott Domain" (Video).

    Abstract.

    The Cantor space — \(2^\mathbb{N}\) — and the Scott domain — \(\mathcal{P}(\mathbb{N})\) — are two topological spaces whose points are sets of integers. But if the Cantor space is equipped with a topology of positive and negative information (conveyed through characteristic functions via the product topology of the discrete topology on \(\{0,1\}\)), the Scott domain drops that condition of negative information, and only keeps the one of positive information through the topology generated by the basis \(\{\mathcal{O}_F\mid F\subseteq \mathbb{N},\ F \text{ finite}\}\) where \(\mathcal{O}_F=\{A\subseteq \mathbb{N} \mid F\subseteq A\}\).
    As a consequence, the Scott domain is not anymore Hausdorff (\(T_2\)), not even Fréchet (\(T_1\)) but only Kolmogorov (\(T_0\)). So, on one hand, the Scott domain seems far away from the Cantor space: it is not even metrizable while the latter is Polish. But on the other hand, they share some similarities: the Cantor space is universal for 0-dimensional Polish spaces, the Scott domain is universal for quasi-Polish spaces (de Brecht).
    More results by de Brecht suggest that a reasonable descriptive set theory still holds in the quasi-Polish setting. However, despite works by Becher, Grigorieff, Motto Ros, Schlicht, Selivanov, and others, much less is known about the Wadge order in this context, rather than in the Polish one.
    We outline the main features of the Wadge order on Borel subsets of the Cantor space and on Borel subsets of the Scott domain and compare these two (a joint work with Louis Vuilleumier).

    Nascondi abstract.

  • 5 maggio 2023, 16.00-17.00 (Online on Webex)

    D. Sinapova (Rutgers University) "Mutual stationarity and the failure of SCH" (Video).

    Abstract.

    Mutual stationarity is a compactness type property for singular cardinals. Roughly, it asserts that given a singular cardinal \(\kappa\), stationary subsets of regular cardinals with limit \(\kappa\) have a “simultaneous witness” for their stationarity. This principle was first defined by Foreman and Magidor in 2001, who showed that it holds for every sequence of stationary sets of cofinality \(\omega\). They also showed that their ZFC result does not generalize to higher cofinality. Whether the principle can consistently hold for higher cofinalities remained open, until a few years ago Ben Neria showed that from large cardinals mutual stationarity at \(\langle\aleph_n\mid n<\omega\rangle\) can be forced for any fixed cofinality.
    We show that we can obtain mutual stationarity at \(\langle\aleph_n\mid n<\omega\rangle\) for any fixed cofinality together with the failure of SCH at \(\aleph_\omega\). This is joint work with Will Adkisson.

    Nascondi abstract.

  • 21 aprile 2023, 16.00-17.00 (Online on Webex)

    M. Elekes (Rényi Institute and Eötvös Loránd University) "On various notions of universally Baire sets" (Video).

    Abstract.

    Universally Baire sets play a crucial role in set theory, and they are also very interesting from the point of view of descriptive set theory. However, there are at least a dozen different definitions, and many of these are non-equivalent (at least consistently). The goal of this talk is to clarify this situation, and also to give applications in the theory of so called Haar meagre sets. Joint work with Máté Pálfy.

    Nascondi abstract.

  • 31 marzo 2023, 16.00-17.00 (Online on Webex)

    L. Patey (CNRS) "Canonical notions of forcing in Reverse Mathematics" (Video).

    Abstract.

    In Reverse Mathematics, a proof of non-implication from a statement P to a statement Q consists of creating a model of P which is not a model of Q. To this end, one usually create a complicated instance I of Q, and then, build iteratively a model of P containing I while avoiding every solution to I. The difficult part consists in building solutions to instances of P which will not compute any solution to I. This is usually done by forcing. Moreover, by some empirical observation, the notion of forcing used in a separation of P from Q usually does not depend on Q. For example, constructing models of WKL is usually done by forcing with Pi^0_1 classes. This tends to show that P admits a "canonical" notion of forcing. In this talk, we provide a formal framework to discuss this intuition, and study the canonical notions of forcing associated to some important statements in Reverse Mathematics. This is a joint work with Denis Hirschfeldt.

    Nascondi abstract.

  • 17 marzo 2023, 16.00-17.00 (Online on Webex)

    V. Selivanov (Institute of Informatics Systems, Novosibirsk) "Boole vs Wadge: comparing basic tools of descriptive set theory".

    Abstract.

    We systematically compare \(\omega\)-Boolean classes and Wadge classes, e.g. we complement the result of W. Wadge that the collection of non-self-dual levels of his hierarchy coincides with the collection of classes generated by Borel \(\omega\)-ary Boolean operations from the open sets in the Baire space. Namely, we characterize the operations, which generate any given level in this way, in terms of the Wadge hierarchy in the Scott domain. As a corollary, we deduce the non-collapse of the latter hierarchy. Also, the effective version of this topic and its extension to \(k\)-partitions are developed.

    Nascondi abstract.

  • 3 marzo 2023, 16.00-17.00 (Online on Webex)

    D. Macpherson (University of Leeds) "Asymptotics of definable sets in finite structures" (Video).

    Abstract.

    A 1992 theorem of Chatzidakis, van den Dries and Macintyre, stemming ultimately from the Lang-Weil estimates, asserts, roughly, that if \(\phi(x,y)\) is a formula in the language of rings (where \(x,y\) are tuples) then the size of the solution set of \(\phi(x,a)\) in any finite field \(F\) of size \(q\) (where \(a\) is a parameter tuple from \(F\)) takes one of finitely many dimension-measure pairs as \(F\) and a vary: for a finite set \(E\) of pairs \((\mu,d)\) (\(\mu\) rational, \(d\) integer) dependent on \(\phi\), any set \(\phi(F,a)\) has size roughly \(\mu q^d\) for some \((\mu,d) \in E\).
    This led in work of Elwes, Steinhorn and myself to the notion of ‘asymptotic class’ of finite structures (a class satisfying essentially the conclusion of Chatzidakis-van den Dries-Macintyre). As an example, by a theorem of Ryten, any family of finite simple groups of fixed Lie type forms an asymptotic class. There is a corresponding notion for infinite structures of ‘measurable structure’ (e.g. a pseudofinite field, by the Chatzidakis-van den Dries-Macintyre theorem). Any ultraproduct of an asymptotic class is measurable, and in particular has supersimple theory (in the sense of stability theory).
    I will discuss a body of work with Sylvy Anscombe, Charles Steinhorn and Daniel Wolf which generalises this, incorporating a richer range of examples with fewer model-theoretic constraints; for example, the corresponding infinite ‘generalised measurable’ structures, for which the definable sets are assigned values in some ordered semiring, need no longer have ‘simple’ theory. I will also discuss a variant in which sizes of definable sets in finite structures are given exactly rather than asymptotically.

    Nascondi abstract.

  • 27 gennaio 2023, 16.00-17.00 (Online on Webex)

    K. Kowalik (Università di Varsavia) "Reverse mathematics of some Ramsey-theoretic principles over a weak base theory" (Video).

    Abstract.

    The logical strength of Ramsey-theoretic principles has been one of the main areas of research in reverse mathematics. We study some of these combinatorial statements over a weak base theory RCA*_0, which is obtained from the usual RCA_0 by replacing Sigma^0_1 induction with Delta^0_1 induction. The weaker base theory allows for a finer analysis of the principles considered, but at the same time makes the notion of an infinite set unstable. Namely, it is consistent with RCA*_0 that there is an unbounded subset of natural numbers which is not in bijective correspondence with N. Thus, there are different ways of formalizing in RCA*_0 Ramsey-theoretic statements since they often assert the existence of some infinite sets (homogeneous sets for colourings, chains or antichains in partial orders etc.). For this reason, the reverse-mathematical zoo gets bigger over RCA*_0. However, there are certain general patterns of behaviour among our principles: some of them are Pi^0_3 conservative over RCA*_0 whereas some others imply I Sigma^0_1. In this talk I will present our main results on the topic and explain what it is like to work without assuming I Sigma^0_1. This is joint work with Marta Fiori Carones, Leszek Kolodziejczyk and Keita Yokoyama.

    Nascondi abstract.

  • 13 gennaio 2023, 16.00-17.00 (Online on Webex)

    V. Brattka (Universität der Bundeswehr München) "Some fascinating topics in logic around reducibilities" (Video).

    UNESCO World Logic Day Seminar


    Abstract.

    In mathematical logic and theoretical computer science a reducibility is a relation that allows one to describe the transformation of one problem A into another problem B. Such reducibilities can vary in terms of what kind of problems are eligible and they can also vary with respect to the way in which problem B can be used to solve problem A.
    Such reducibilities were first considered in computability theory, but they eventually conquered other areas related to logic, such as computational complexity theory, descriptive set theory, computable analysis, and reverse mathematics, where they turned out to be very powerful tools.
    Some particularly fascinating questions in mathematical logic are intrinsically tied to certain reducibilities. For instance, Post's problem and Martin's conjecture are related to Turing reducibility, the P-NP problem is based on polynomial-time reducibility.
    We will also discuss more recent types of reducibilities, such as the Wadge and the Weihrauch reducibilities and show how they might be helpful in addressing questions from descriptive set theory, such as the decomposability conjecture.

    Nascondi abstract.


Nascondi 2023.
Espandi 2022
Nascondi 2022.
  • 2 dicembre 2022, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    F. Parente (Università di Torino) "Good ultrafilters and universality properties of forcing".

    Abstract.

    In 1964, Keisler introduced $\kappa$-good ultrafilters, which can be characterized as those ultrafilters which produce $\kappa$-saturated ultrapowers. The problem of finding an analogous characterization for ultrafilters on Boolean algebras has been considered by Mansfield (1971), Benda (1974), and Balcar and Franek (1982), who proposed and compared different notions of “goodness” for such ultrafilters. In the first part of my talk, I shall outline the different definitions introduced in the literature and show that they are in fact all equivalent, thus providing a complete characterization of those ultrafilters which produce $\kappa$-saturated Boolean ultrapowers. In the second part of the talk, I shall present a joint work with Matteo Viale, which started in 2015 during my Master's thesis and was recently revived during the last few months in Torino. The aim of our project is to study the universality properties of forcing. More precisely, we shall prove that, for many interesting signatures, every model of the universal theory of an initial segment of the universe can be embedded into a model constructed by forcing. To achieve this goal, we build good ultrafilters on forcing notions such as the Lévy collapsing algebra and Woodin's stationary tower.

    Nascondi abstract.

  • 18 novembre 2022, 09.00-10.00 (Online on Webex)

    A. Conversano (Massey University) "Tools of o-minimality in the study of groups" (Video).

    Abstract.

    In this talk we will see how geometric invariants of definable sets in o-minimal structures can be used to understand the structure of groups in several categories.

    Nascondi abstract.

  • 4 novembre 2022, 16.00-17.00 (Online on Webex)

    J. Emmenegger (Università di Genova) "Quotients and equality, (co)algebraically" (Video).

    Abstract.

    Doctrines were introduced by Lawvere as an algebraic tool to work with logical theories and their extensions. In fact, this algebraic character makes the theory of doctrines a suitable context where to address the question: "What is the theory obtained by (co)freely adding logical structure?" or the closely related question: "How to express additional logical structure in terms of what is already available?". More precisely, in the first case we ask whether a certain forgetful functor is adjoint and, in the second case, whether the adjunction obtained in this way is (co)monadic. After an introduction to doctrines and their connection to logic and type theory, I shall discuss the above questions in the case of two forgetful functors: the one from theories with conjunctions, equality and quotients to theories with conjunctions and equality, and the one that further forgets equality. Not surprisingly, the answers revolve around the concept of equivalence relation. I shall discuss applications to useful constructions in categorical logic and type theory, as well as to the theory of imaginary elements in the sense of Poizat. If time allows, I shall also describe how to lift this setting to Grothendieck fibrations (of which doctrines are a particular case) using groupoids instead of equivalence relations.

    Nascondi abstract.

  • 21 ottobre 2022, 16.00-17.00 (Online on Webex)

    C. Rosendal (University of Maryland) "Amenability, optimal transport and complementation in Banach modules" (Video).

    Abstract.

    Using tools from the theory of optimal transport, I will discuss a new characterisation of general amenable topological groups. Specifically, let G be an amenable topological group with no non-trivial homomorphisms to R and let d be a left-invariant continuous metric on G. Then one may find finitely supported probability measures on G that are almost invariant, with respect to the Wasserstein distance for the cost function d, under any given finite sets of translations by elements of G. On the other hand, I will also show how this fails in the amenable par excellence group Z. Time permitting, I will also indicate how this can be used to average potentially unbounded Lipschitz functions defined on spaces on which G acts isometrically.

    Nascondi abstract.

  • 10 giugno 2022, 16.00-18.00 (Online on Webex)

    S. L'Innocente (Università di Camerino) "A factorisation theory for generalised power series".

    Abstract.

    A classical tool in the study of real closed fields are the fields K((G)) of generalised power series (i.e., formal sums with well-ordered support) with coefficients in a field K of characteristic 0 and exponents in an ordered abelian group G. A fundamental result of Berarducci ensures the existence of irreducible series in the subring of generalised power series with non-positive exponents. This report aims at describing a factorisation theory in this context: a joint work with Vincenzo Mantova proves that every series admits a factorisation into a bounded number of irreducibles and a unique product, up to multiplication by a unit, of factors whose supports are finite and generate rational linear spaces of dimension one. Analogous results are deduced for the ring of omnific integers within Conway's surreal numbers, using a suitable notion of infinite product. In turn, Gonshor's conjecture is solved: the omnific integer omega 2 + omega + 1 is prime. Other possible generalizations will also be sketched.

    Nascondi abstract.

  • 27 maggio 2022, 16.00-17.00 (Online on Webex)

    T. Nemoto (Hiroshima Institute of Technology) "Determinacy of infinite games and reverse mathematics" (Video).

    Abstract.

    Reverse mathematics is a program to classify mathematical theorems by set comprehension axioms in second order arithmetic [1]. In this program, it is presented that most of the theorems from undergraduate mathematics are equivalent to set comprehension axioms characterizing systems called "Big Five". Comparing to the systems of set theory, second order arithmetic is a rather weak system, which enables the classification of weak determinacy schemata for the classes in the very low level of the Wadge hierarchy. In this talk, we will see that determinacy of infinite games up to the defference hierarchy over \Sigma^0_3 makes a fine hierarchy in second order arithmetic. References [1] S. G. Simpson, Subsystems of second order arithmetic (2nd edition), Cambridge University Press, 2010 [2] T. Nemoto, Determinacy of Wadge classes and subsystems of second order arithmetic, Mathematical Logic Quarterly, Volume 55, Issue 2, February 2009, pp. 154 - 176. [3] A. Montalbán and R. A. Shore, The limits of determinacy in second order arithmetic: consistency and complexity strength, Israel J. Math., 204 (2014), 477--508.

    Nascondi abstract.

  • 20 maggio 2022, 16.00-18.00 (Online on Webex)

    A. Marcone (Università di Udine) "The transfinite Ramsey theorem" (Video).

    Abstract.

    In this talk I discuss generalizations of the classic finite Ramsey theorem that substitute "set of cardinality n" with the notion of alpha-large set, where alpha is a countable ordinal. The prototype of these results is the statement that Paris and Harrington showed unprovable in PA in 1977. Since then several extensions were proved, typically for ordinals up to epsilon_0. Our results extend this approach by dealing with ordinals (at least) up to Gamma_0 and using simultaneously alpha-large sets (almost) everywhere in the statements. Quite surprisingly, in many cases we obtain tight bounds on the generalized Ramsey numbers, in contrast with the classical finite case where tight bounds are known only for very few cases involving very small numbers. This is joint work with Antonio Montalbán.

    Nascondi abstract.

  • 13 maggio 2022, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    U. Darji (University of Louisville) "Descriptive complexity and local entropy" (Slides,Video).

    Abstract.

    Blanchard introduced the concepts of Uniform Positive Entropy (UPE) and Complete Positive Entropy (CPE) as topological analogues of K-automorphism. He showed that UPE implies CPE, and that the converse is false. A flurry of recent activity studies the relationship between these two notions. For example, one can assign a countable ordinal which measures how complicated a CPE system is. Recently, Barbieri and García-Ramos constructed Cantor CPE systems at every level of CPE. Westrick showed that natural rank associated to CPE systems is actually a \Pi^1_1-rank. More importantly, she showed that the collection of CPE Z2-SFT's is a \Pi^1_1-complete set. In this talk, we discuss some results, where UPE and CPE coincide and others where we show that the complexity of certain classes of CPE systems is \Pi^1_1-complete. This is joint work with García-Ramos.

    Nascondi abstract.

  • 8 aprile 2022, 16.00-17.00 (Online on Webex)

    A. Kechris (Caltech) "Countable sections for actions of locally compact groups" (Slides).

    Abstract.

    A Borel action of a Polish locally compact group on a standard Borel space admits a countable Borel section, i.e., a Borel set that meets every orbit in a countable nonempty set. It is a long standing open problem whether this property characterizes locally compact groups. I will discuss the history of this problem and some recent progress in joint work with M. Malicki, A. Panagiotopoulos and J. Zielinski.

    Nascondi abstract.

  • 1 aprile 2022, 16.00-18.00 (Online on Webex)

    D. Evans (Imperial College London) "Amalgamation properties in measured structures" (Video).

    Abstract.

    In a paper published in 2008, Macpherson and Steinhorn introduced and studied structures in which each every definable set carries a well behaved dimension and measure: we refer to these as MS-measurable structures. Examples include totally categorical structures, pseudofinite fields and the random graph. MS-measurable structures are supersimple of finite SU-rank and we discuss some amalgamation properties which hold in MS-measurable structures, but not in all supersimple finite rank structures. We are interested in the question of whether every omega-categorical, MS-measurable structure is one-based. A construction of Hrushovski can be used to produce omega-categorical structures which are supersimple of finite SU-rank and not one-based: indeed, this construction is essentially the only known way to produce such structures. It is still an open question whether any of these Hrushovski constructions can be MS-measurable. However, I will discuss some work of myself and of my PhD student Paolo Marimon which uses the amalgamation results and other methods to show that at least some of the Hrushovski constructions are not MS-measurable.

    Nascondi abstract.

  • 25 marzo 2022, 16.00-18.00 (Online on Webex)

    O. Ben-Neria (The Hebrew University of Jerusalem) "Mathias-type Criterion for the Magidor Iteration of Prikry forcings".

    Abstract.

    In his seminal work on the identity crisis of strongly compact cardinals, Magidor introduced a special iteration of Prikry forcings for a set of measurable cardinals known as the Magidor iteration. The purpose of this talk is to present a Mathias-type criterion which characterizes when a sequence of omega-sequences is generic for the Magidor iteration. The result extends a theorem of Fuchs who introduced a Mathias criterion for discrete products of Prikry forcings. We will present the new criterion, discuss several applications, and outline the main ideas of the proof

    Nascondi abstract.

  • 18 marzo 2022, 16.00-17.30 (Online on Webex)

    D. Dzhafarov (University of Connecticut) "The SRT22 vs. COH problem" (Video).

    Abstract.

    I will give a brief introduction to the program of reverse mathematics, which seeks to answer the ancient question of which mathematical axioms are necessary to prove theorems of ordinary mathematics. I will then discuss a special theorem of combinatorics, Ramsey’s theorem, which has played an important role in this endeavor, and led to a tantalizing problem known as the SRT22 vs. COH problem. I will focus on this problem, talk about its history, and then briefly discuss its recent solution by Monin and Patey. I hope for the talk to be accessible to a general mathematical audience.

    Nascondi abstract.

  • 11 marzo 2022, 16.00-18.00 (Sala Orsi, Palazzo Campana, Torino)

    A. Andretta (Università di Torino) "Sierpiński's partitions with Sigma^1_2 pieces" (Video).

    Abstract.

    There are several statements in elementary geometry that depend on the size of the continuum, and most of them are modelled on the proof of a theorem of Sierpiński's. In the first part of the talk I will survey a few of these geometric statements and show how these are related to each other. In the second part I will show how imposing a definability condition on the pieces of Sierpiński's theorem yields a better bound on the size of the continuum.

    Nascondi abstract.

  • 4 marzo 2022, 16.00-18.00 (Online on Webex)

    M. Skrzypczak (University of Warsaw) "The infinite tree - from Kolmogorov, Rabin, and Shelah to modern Theoretical Computer Science ".

    Abstract.

    The infinite binary tree (i.e. the free structure of two successors, aka S2S) seems to be a very simple and natural object. Nevertheless, due to its branching structure, it has rich abilities of modelling complex processes including e.g. nondeterminism, perfect information games, combinatorics of P(N), etc The fundamental result of Rabin from late 60's (sometimes called ""the mother of all decidability results"") proves that the Monadic Second-Order (MSO) theory of S2S is decidable. Since then, the structure of properties expressible in MSO over S2S has been intensively studied. Many of these studies were related to and/or motivated by descriptive set theory. During the talk I would like to make a broad overview of these relations, including issues of Wadge degrees, measurability (with relations to Kolmogorov), and uniformisability (Gurevich-Shelah). Although a lot of questions have been already answered, there still remain important and natural open problems in all three mentioned directions of research.

    Nascondi abstract.

  • 13 gennaio 2022, 17.00-18.00 (Online on Webex)

    M. Magidor (Università ebraica di Gerusalemme) "Sets of reals are not created equal: regularity properties of subsets of the reals and other Polish spaces.".

    Abstract.

    A “pathological set” can be a non measurable set, a set which does not have the property of Baire (namely it is not a Borel set modulo a first category set).
    A subset $A \subseteq P^{\omega}(\mathbb{N})$ (=the infinite subsets of natural numbers) can be considered to be ”pathological” if it is a counterexample to the infinitary Ramsey theorem. Namely there does not exist an infinite set of natural numbers such that all its infinite subsets are in our sets or all its infinite subsets are not in the set.
    A subset of the Baire space $A\subseteq \mathbb{N}^{\mathbb{N}}$ can be considered to be “pathological” if the infinite game $G_A$ is not determined. The game $G_A$ is an infinite game where two players alternate picking natural numbers, forming an infinite sequence, namely a member of $\mathbb{N}^{\mathbb{N}}$. The first player wins the round if the resulting sequence is in $A$. The game is determined if one of the players has a winning strategy.
    A prevailing paradigm in Descriptive Set Theory is that sets that have a “simple description” should not be pathological. Evidence for this maxim is the fact that Borel sets are not pathological in any of the senses above.In this talk we shall present a notion of “super regularity” for subsets of a Polish space, the family of universally Baire sets. This family of sets generalizes the family of Borel sets and forms a $\sigma$-algebra. We shall survey some regularity properties of universally Baire sets , such as their measurability with respect to any regular Borel measure, the fact that they have an infinitary Ramsey property etc. Some of these theorems will require assuming some strong axioms of infinity. Most of the talk should be accessible to a general Mathematical audience, but in the second part we shall survey some newer results.

    Nascondi abstract.


Nascondi 2022.
Espandi 2021
Nascondi 2021.
  • 17 dicembre 2021, 16.00-18.00 (Online on Webex)

    M. Rathjen (University of Leeds) "Well-ordering principles in Proof theory and Reverse Mathematics" (Video).

    Abstract.

    There are several familiar theories of reverse mathematics that can be characterized by well-ordering principles of the form (*) "if $X$ is well ordered then $f(X)$ is well ordered", where $f$ is a standard proof theoretic function from ordinals to ordinals (such $f$'s are always dilators). Some of these equivalences have been obtained by recursion-theoretic and combinatorial methods. They (and many more) can also be shown by proof-theoretic methods, employing search trees and cut elimination theorems in infinitary logic with ordinal bounds. One could perhaps generalize and say that every cut elimination theorem in ordinal-theoretic proof theory encapsulates a theorem of this type.

    Nascondi abstract.

  • 10 dicembre 2021, 16.00-17.00 (Online on Webex)

    J. Hirst (Appalachian State University) "Reverse mathematics and Banach's theorem" (Slides,Video).

    Abstract.

    The Schröder-Bernstein theorem asserts that if there are injections of two sets into each other, then there is a bijection between the sets. In his note "Un théorème sur les transformations biunivoques," Banach proved an extension of the Schröder-Bernstein theorem in which the values of the bijection between the sets depend directly on the injections. This talk will present some old theorems of reverse mathematics about restrictions of Banach's theorem. Also, we will look at preliminary results of work with Carl Mummert on restrictions of Banach's theorem in higher order reverse mathematics. The talk will not assume familiarity with reverse mathematics.

    Nascondi abstract.

  • 3 dicembre 2021, 16.00-18.00 (Online on Webex)

    G. Goldberg (University of California, Berkeley) "The optimality of Usuba's theorem" (Video).

    Abstract.

    The method of forcing was introduced by Cohen in his proof of the independence of the Continuum Hypothesis and has since been used to demonstrate that a diverse array of set theoretic problems are formally unsolvable from the standard ZFC axioms. The technique allows one to expand a model of ZFC by adjoining to it a generic set. The resulting forcing extension is again a model of ZFC that may have a very different first order theory from the original structure; for example, according to one's tastes, one can build forcing extensions in which the Continuum Hypothesis is either true or false, demonstrating that the ZFC axioms can neither prove nor refute the Continuum Hypothesis. But does the forcing technique really show that the Continuum Hypothesis has no truth value? This seems to hinge on whether one believes that the true universe of sets (which the ZFC axioms attempt to axiomatize) could itself be a forcing extension of a smaller model of ZFC. This talk concerns a theorem of Usuba that bears on this question. I'll discuss recent work proving the optimality of the large cardinal hypothesis of Usuba's theorem and some applications of the associated techniques to questions outside the theory of forcing.

    Nascondi abstract.

  • 26 novembre 2021, 16.00-17.00 (Online on Webex)

    A. Martin-Pizarro (Albert-Ludwigs-Universität Freiburg) "On abelian corners and squares" (Video).

    Abstract.

    Given an abelian group \(G\), a corner is a subset of pairs of the form \(\{ (x,y), (x+g, y), (x, y+g)\}\) with \(g\) non trivial. Ajtai and Szemerédi proved that, asymptotically for finite abelian groups, every dense subset \(S\) of \(G\times G\) contains a corner. Shkredov gave a quantitative lower bound on the density of the subset \(S\). In this talk, we will explain how model-theoretic conditions on the subset \(S\), such as local stability, will imply the existence of corners and of cubes for (pseudo-)finite abelian groups. This is joint work with D. Palacin (Madrid) and J. Wolf (Cambridge).

    Nascondi abstract.

  • 19 novembre 2021, 16.00-17.00 (Aula 4, Palazzo Campana, Torino)

    A. Törnquist (Københavns Universitet) "Set-theoretic aspects of a proposed model of the mind in psychology" (Slides).

    Abstract.

    Jens Mammen (Professor Emeritus of psychology at Aarhus and Aalborg University) has developed a theory in psychology, which aims to provide a model for the interface between a human being (and mind), and the real world.
    This theory is formalized in a very mathematical way: Indeed, it is described through a mathematical axiom system. Realizations ("models") of this axiom system consist of a non-empty set $U$ (the universe of objects), as well as a perfect Hausdorff topology $\mathcal{S}$ on $U$, and a family $\mathcal{C}$ of subsets of $U$ which must satisfy certain axioms in relation to $\mathcal{S}$. The topology $\mathcal{S}$ is used to model broad categories that we sense in the world (e.g., all the stones on a beach) and the $\mathcal{C}$ is used to model the process of selecting an object in a category that we sense (e.g., a specific stone on the beach that we pick up). The most desirable kind of model of Mammen's theory is one in which every subset of $U$ is the union of an open set in $\mathcal{S}$ and a set in $\mathcal{C}$. Such a model is called "complete".
    Coming from mathematics, models of Mammen's theory were first studied in detail by J. Hoffmann-Joergensen in the 1990s. Hoffmann-Joergensen used the Axiom of Choice (AC) to show that a complete model of Mammen's axiom system, in which the universe $U$ is infinite, does exist. Hoffmann-Joergensen conjectured at the time that the existence of a complete model of Mammen's axioms would imply the Axiom of Choice.
    In this talk, I will discuss various set-theoretic aspects related to complete Mammen models; firstly, the question of "how much" AC is needed to obtain a complete Mammen model; secondly, I will introduce some cardinal invariants related to complete Mammen models and establish elementary ZFC bounds for them, as well as some consistency results.
    This is joint work with Jens Mammen.

    Nascondi abstract.

  • 12 novembre 2021, 16.00-17.00 (Online on Webex)

    S. Müller (Technische Universität Wien) "Large Cardinals and Determinacy" (Video).

    Abstract.

    Determinacy assumptions, large cardinal axioms, and their consequences are widely used and have many fruitful implications in set theory and even in other areas of mathematics. Many applications, in particular, proofs of consistency strength lower bounds, exploit the interplay of determinacy axioms, large cardinals, and inner models. I will survey some recent results in this flourishing area. This, in particular, includes results on connecting the determinacy of longer games to canonical inner models with many Woodin cardinals, a new lower bound for a combinatorial statement about infinite trees, as well as an application of determinacy answering a question in general topology.

    Nascondi abstract.

  • 5 novembre 2021, 16.00-18.00 (Online on Webex)

    A. Zucker (University of California San Diego) "Big Ramsey degrees in binary free amalgamation classes" (Video).

    Abstract.

    In structural Ramsey theory, one considers a "small" structure A, a "medium" structure B, a "large" structure C and a number r, then considers the following combinatorial question: given a coloring of the copies of A inside C in r colors, can we find a copy of B inside C all of whose copies of A receive just one color? For example, when C is the rational linear order and A and B are finite linear orders, then this follows from the finite version of the classical Ramsey theorem. More generally, when C is the Fraisse limit of a free amalgamation class in a finite relational language, then for any finite A and B in the given class, this can be done by a celebrated theorem of Nesetril and Rodl. Things get much more interesting when both B and C are infinite. For example, when B and C are the rational linear order and A is the two-element linear order, a pathological coloring due to Sierpinski shows that this cannot be done. However, if we weaken our demands and only ask for a copy of B inside C whose copies of A receive "few" colors, rather than just one color, we can succeed. For the two-element linear order, we can get down to two colors. For the three-element order, 16 colors. This number of colors is called the big Ramsey degree of a finite structure in a Fraisse class. Recently, building on groundbreaking work of Dobrinen, I proved a generalization of the Nešetril-Rödl theorem to binary free amalgamation classes defined by a finite forbidden set of irreducible structures (for instance, the class of triangle-free graphs), showing that every structure in every such class has a finite big Ramsey degree. My work only bounded the big Ramsey degrees, and left open what the exact values were. In recent joint work with Balko, Chodounský, Dobrinen, Hubicka, Konecný, and Vena, we characterize the exact big Ramsey degree of every structure in every binary free amalgamation class defined by a finite forbidden set.

    Nascondi abstract.


Nascondi 2021.

Logic Working Group

A venir:

  • 19 aprile 2024, 15.00-17.00 (Sala Riunioni, DMIF, Udine)

    F. Barrera (Università di Udine) "The $\lambda$-PSP at $\lambda$-coanalytic sets".

    Abstract.

    I will show that if there is a strong limit cardinal $\lambda$ of countable cofinality such that all $\lambda$-coanalytic sets have the $\lambda$-PSP, then $0^\dagger$ exist. The proof is quite an accessible example of the technique of establishing consistency strength lower bounds using core models and their covering properties. Time permitting, I will mention the obstacles that arise when trying to increase the given lower bound. This is joint work with Sandra Müller and Vincenzo Dimonte.

    Nascondi abstract.

Passé:

  • 22 marzo 2024, 15.00-17.00 (Sala Riunioni, DMIF, Udine)

    F. Barrera (Università di Udine) "The $\lambda$-PSP at $\lambda$-coanalytic sets" (CANCELLATO).

    Abstract.

    I will show that if there is a strong limit cardinal $\lambda$ of countable cofinality such that all $\lambda$-coanalytic sets have the $\lambda$-PSP, then $0^\dagger$ exist. The proof is quite an accessible example of the technique of establishing consistency strength lower bounds using core models and their covering properties. Time permitting, I will mention the obstacles that arise when trying to increase the given lower bound. This is joint work with Sandra Müller and Vincenzo Dimonte.

    Nascondi abstract.

  • 15 marzo 2024, 15.00-17.00 (Aula S, Palazzo Campana)

    E. Pozzan (Università di Torino) "Boolean valued models and presheaves", parte 2.

    Abstract.

    In the talks, we will explore some aspects of the relationship between the theory of boolean valued models and sheaf theory. We will firstly introduce a topological description via étalé bundles of the sheafification process with respect to the dense Grothendieck topology. Next, we will use this result to show how it is possible to identify presheaves on (complete) boolean algebras with boolean valued models, and sheaves with respect to the dense Grothendieck topology, with boolean valued models satisfying the mixing property. We will also present a categorical characterization of presheaves corresponding to full boolean valued models in terms of the structure of global sections of their associated étalé space. The talks are based on the joint work of Matteo Viale and Moreno Pierobon.

    Nascondi abstract.

  • 8 marzo 2024, 15.00-17.00 (Aula S, Palazzo Campana)

    E. Pozzan (Università di Torino) "Boolean valued models and presheaves", parte 1.

    Abstract.

    In the talks, we will explore some aspects of the relationship between the theory of boolean valued models and sheaf theory. We will firstly introduce a topological description via étalé bundles of the sheafification process with respect to the dense Grothendieck topology. Next, we will use this result to show how it is possible to identify presheaves on (complete) boolean algebras with boolean valued models, and sheaves with respect to the dense Grothendieck topology, with boolean valued models satisfying the mixing property. We will also present a categorical characterization of presheaves corresponding to full boolean valued models in terms of the structure of global sections of their associated étalé space. The talks are based on the joint work of Matteo Viale and Moreno Pierobon.

    Nascondi abstract.

  • 26 gennaio 2024, 15.00-17.00 (Aula S, Palazzo Campana)

    L. Notaro (Università di Torino) "Does $\mathsf{DC}$ imply $\mathsf{AC_\omega}$, uniformly?".

    Abstract.

    The axiom of dependent choice $\mathsf{DC}$ and the axiom of countable choice $\mathsf{AC_\omega}$ are two weak forms of the axiom of choice that can be stated for a specific set: $\mathsf{DC}(X)$ assets that any total binary relation on $X$ has an infinite chain; $\mathsf{AC_\omega}(X)$ assets that any countable family of nonempty subsets of $X$ has a choice function. It is well-known that $\mathsf{DC}$ implies $\mathsf{AC_\omega}$. We discuss and sketch the proof of the following theorem: it is consistent with $\mathsf{ZF}$ that there is a set $A\subseteq \mathbb{R}$ such that $\mathsf{DC}(A)$ holds but $\mathsf{AC_\omega}(A)$ fails. This is joint work with Alessandro Andretta.

    Nascondi abstract.

Espandi 2023
Nascondi 2023.
  • 22 dicembre 2023, 15.00-17.00 (Online on Webex)

    B. Pitton (Université de Lausanne e Università di Torino) "Complexity Hierarchies in Classical and Generalized Descriptive Set Theory", parte 2.

    Abstract.

    The central problem of descriptive set theory is to find and study the characteristic properties of definable subsets of Polish spaces. In this theory, sets are classified into hierarchies based on the complexity of their definitions, and a systematic analysis is conducted on the structure of sets at each level of these hierarchies. While classical descriptive set theory primarily focuses on studying subsets of the space of all countable binary sequences, generalized descriptive set theory aims at developing an higher analogue in which \(\omega\) is replaced with an uncountable cardinal \(\kappa\) satisfying the condition \(\kappa^{<\kappa}=\kappa\). In this talks, we will navigate between Classical and Generalized descriptive set theory, discussing the Borel hierarchy, the Difference hierarchy, and the Wadge hierarchy for subsets of the Cantor space. We will discuss some old and new results, with a particular focus on some new phenomena specifically arising in the generalized context.

    Nascondi abstract.

  • 15 dicembre 2023, 15.00-17.00 (Online on Webex)

    B. Pitton (Université de Lausanne e Università di Torino) "Complexity Hierarchies in Classical and Generalized Descriptive Set Theory ", parte 1.

    Abstract.

    The central problem of descriptive set theory is to find and study the characteristic properties of definable subsets of Polish spaces. In this theory, sets are classified into hierarchies based on the complexity of their definitions, and a systematic analysis is conducted on the structure of sets at each level of these hierarchies. While classical descriptive set theory primarily focuses on studying subsets of the space of all countable binary sequences, generalized descriptive set theory aims at developing an higher analogue in which \(\omega\) is replaced with an uncountable cardinal \(\kappa\) satisfying the condition \(\kappa^{<\kappa}=\kappa\). In this talks, we will navigate between Classical and Generalized descriptive set theory, discussing the Borel hierarchy, the Difference hierarchy, and the Wadge hierarchy for subsets of the Cantor space. We will discuss some old and new results, with a particular focus on some new phenomena specifically arising in the generalized context.

    Nascondi abstract.

  • 24 novembre 2023, 15.00-17.00 (Sala Riunioni, DMIF, Udine)

    G. Osso (Università di Udine) "An introduction to Weihrauch reducibility with some classification results in the generalized setting", parte 2.

    Abstract.

    Weihrauch reducibility allows the study of the computational content of relations, viewed as instance-solution problems. In particular, by identifying each $\Pi_2$ theorem with an adequate instance-solution problem, Weihrauch reducibility can be used to classify such theorems based on how hard the corresponding problems are to compute. While the classical Weihrauch reducibility framework is concerned with problems on sets of size at most that of the continuum, recent work by Galeotti and Nobrega has expanded the scope of this method to sets of size $2^{\kappa}$ where $\kappa$ is an uncountable cardinal satisfying $\kappa^{<\kappa}=\kappa$. In the first talk, we will see a detailed introduction to Weihrauch reducibility, together with some examples of classifications of theorems in real analysis. We will conclude the talk with the introduction of the notion of generalized Weihrauch reducibility which we will use in the uncountable setting. In the second talk, we will see the generalized real numbers introduced by Galeotti and we will explore some of their properties, among which a normal form theorem which provides a computational link between subsets of $\kappa$ and generalized reals. We will then use these facts to show some classification results in the generalized context analogous to those of the first talk.

    Nascondi abstract.

  • 17 novembre 2023, 15.00-17.00 (Sala Riunioni, DMIF, Udine)

    G. Osso (Università di Udine) "An introduction to Weihrauch reducibility with some classification results in the generalized setting", parte 1.

    Abstract.

    Weihrauch reducibility allows the study of the computational content of relations, viewed as instance-solution problems. In particular, by identifying each $\Pi_2$ theorem with an adequate instance-solution problem, Weihrauch reducibility can be used to classify such theorems based on how hard the corresponding problems are to compute. While the classical Weihrauch reducibility framework is concerned with problems on sets of size at most that of the continuum, recent work by Galeotti and Nobrega has expanded the scope of this method to sets of size $2^{\kappa}$ where $\kappa$ is an uncountable cardinal satisfying $\kappa^{<\kappa}=\kappa$. In the first talk, we will see a detailed introduction to Weihrauch reducibility, together with some examples of classifications of theorems in real analysis. We will conclude the talk with the introduction of the notion of generalized Weihrauch reducibility which we will use in the uncountable setting. In the second talk, we will see the generalized real numbers introduced by Galeotti and we will explore some of their properties, among which a normal form theorem which provides a computational link between subsets of $\kappa$ and generalized reals. We will then use these facts to show some classification results in the generalized context analogous to those of the first talk.

    Nascondi abstract.

  • 10 novembre 2023, 15.00-17.00 (Sala Riunioni, DMIF, Udine)

    S. Thei (Università di Udine) "Elementary embeddings and cardinal correctness".

    Abstract.

    An elementary embedding from an inner model M into another inner model N is cardinal preserving if M and N correctly compute the class of cardinals. We look at the case N = V and show that there is no cardinal preserving elementary embedding from M into V, answering a question of Caicedo. Time permitting, we will discuss the case M = V. This is joint work with Gabriel Goldberg.

    Nascondi abstract.

  • 23 giugno 2023, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    M. Bailetti (Wesleyan University) "Dividing lines and notions of maximality in first-order theories".

    Abstract.

    In the classification of first-order theories, many “dividing lines” have been defined in order to understand the complexity and the behavior of some classes of theories. These classes are usually defined by forbidding some specific configurations of definable subsets. In this talk, we define the principal dividing lines and we introduce some notions of maximal complexity by requesting the presence of all the possible combinatorial patterns of definable sets.

    Nascondi abstract.

  • 26 maggio 2023, 16.00-17.00 (Online on Webex)

    S. Maschio (Università di Padova) "Implicative algebras, categories of assemblies and intuitionistic set theory".

    Abstract.

    Implicative algebras were introduced by A. Miquel to provide a common foundation for forcing and realizability interpretations of logical operators. Every implicative algebra gives rise to a tripos and Miquel proved that every tripos based on Set is in fact isomorphic to one coming from an implicative algebra. Thus, implicative algebras can be understood as elementary algebraic counterparts of triposes over Set. We will show how this fact can be used to analyze from a different perspective some categories of assemblies which can be defined from an arbitrary tripos over Set. Moreover, we will show how one can use implicative algebras to produce models of intuitionistic set theory in a wide class of elementary toposes.
    This is partially a joint work in progress with Davide Trotta.

    Nascondi abstract.

  • 12 maggio 2023, 16.00-17.00 (Sala Riunioni, DMIF, Udine)

    A. Volpi (Università di Udine) "Reverse mathematics and dimension of posets" (Slides).

    Abstract.

    There are many different parameters used in order theory to describe a poset. Perhaps one of the most interesting is the dimension which is the least number of linearizations that allow us to recover the poset itself. With such definition, linearly ordered sets have dimension 1 as one would expect. More surprisingly, antichains have dimension 2. In this talk I will introduce Order Theory and I will state bounding theorems about the dimension of posets with many examples. As we will see, typical bounding theorems state that if we remove a point from a poset the dimension can decrease at most by one, while if we remove a chain the dimension can decrease at most by two. We are interested mostly in studying from the point of view of Reverse Mathematics bounding theorems of this kind. Recently we were able to prove that the second bounding theorem mentioned above is equivalent to WKL. This is joint work with Alberto Marcone and Marta Fiori-Carones.

    Nascondi abstract.

  • 28 aprile 2023, 16.00-17.00 (Online on Webex)

    M. Ng (Queen Mary University of London) "Foundations in non-Archimedean & arithmetic geometry: topology vs. set theory" (Slides).

    Abstract.

    What is a space?
    In classical point-set topology, one defines a space by taking a set of elements before defining the topology on it in the usual way. By contrast, in locale theory, the basic unit for defining a space is not the underlying set of points but the opens. Topos theory extends this perspective, and says: a space is a universe whose points correspond to models of a geometric theory.
    The differences between these perspectives brings into focus two key foundational questions: (i) What is the role of set theory in topology? (ii) What are the consequences of working classically, rather than intuitionistically?
    This talk will discuss a couple of illustrating examples from recent work. The first example involves using point-free techniques to sharpen a foundational result in Berkovich geometry, showing that algebraic hypotheses imposed by the classical mathematician (e.g. requiring that the base field \(K\) be non-trivially valued) are sometimes in fact point-set hypotheses, and are thus inessential to the underlying mathematics. The second example, from joint work with Steve Vickers, involves classifying the places of \(\mathbb{Q}\) via geometric logic. The big surprise is that, working geometrically, one discovers that the Archimedean place corresponds to a blurred unit interval — by contrast, the Archimedean place has always been classically regarded as a singleton (by number theorists). Aside from raising urgent questions for the foundations of arithmetic geometry, this result also illustrates an interesting moral: sometimes, working classically results in a serious loss of information that is only visible when looked at from the intuitionistic perspective.

    Nascondi abstract.

  • 14 aprile 2023, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    S. Scamperti (Università di Torino) "Continuous injective reduction on a zero-dimensional Polish space".

    Abstract.

    We talk about the continuous injective reduction on a zero-dimensional Polish space and the continuous injective quasi-order between Polish spaces. This is a work in progress joint with Raphaël Carroy.

    Nascondi abstract.

  • 24 marzo 2023, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    M. Viale (Università di Torino) "Topological maximality vs algebraic maximality in set theory".

    Abstract.

    A topological approach to forcing axioms considers them as strong forms of the Baire category theorem; an algebraic approach to them describes certain properties of “algebraic closure” for the universe of sets that can be derived from them. Our goal is to connect the geometric and algebraic points of view.

    Nascondi abstract.

  • 10 marzo 2023, 16.00-17.00 (Online on Webex)

    D. Leonessi (Graduate Center of the City University of New York) "Strategy and determinacy in infinite Hex" (Slides).

    Abstract.

    The game of Hex can be extended to the infinite hexagonal lattice, defining a winning condition which formalises the idea of a chain of coloured stones stretching towards infinity. The descriptive-set-theoretic complexity of the set of winning positions is unknown, although it is at most \(\Sigma^1_1\), and it is conjectured to be Borel; this has implications on whether games of infinite Hex are determined from all initial positions as either first-player wins or draws.
    Unlike the finite game, infinite Hex with an initially empty board is a draw. But is the game still a draw when starting from a non-empty board? This open question can be partially answered in the positive by assuming the existence of certain local strategies, and in the negative by giving the advantage of placing an extra stone at each turn to one of the players. This is joint work with Joel David Hamkins.

    Nascondi abstract.

  • 20 gennaio 2023, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    C. Agostini (Università di Torino) "A characterization of metrizability through games" (Slides).

    Abstract.

    The quest for characterizing metrizability has always risen a lot of interest, leading to results such as Urysohn metrization theorem, Nagata-Smirnov metrization theorem, Arhangel'skij metrization theorem… Most of these theorems characterize metrizability in terms of the existence of a basis for the topology with particularly nice properties.
    Metrizability has a natural generalization that occurs when the usual range of the metric \(\langle \mathbb{R}, +, 0, \leq \rangle\) is replaced by another structure \(\mathbb{G}=\langle G, +_{\mathbb{G}}, 0_{\mathbb{G}}, \leq_{\mathbb{G}} \rangle\). \(\mathbb{G}\)-metrics have been widely studied as well (both in general topology and, more recently, for their applications in generalized descriptive set theory), and most characterizations of metric spaces extend nicely to \(\mathbb{G}\)-metrics as well.
    In this talk, I will present a (hopefully) new characterization of both metrizability and \(\mu\)-metrizability of a slightly different fashion: we characterize metrizability in terms of a topological game. These results are part of a joint work with Luca Motto Ros.

    Nascondi abstract.


Nascondi 2023.
Espandi 2022
Nascondi 2022.
  • 16 dicembre 2022, 16.00-17.00 (Sala Orsi, Palazzo Campana, Torino)

    J. Santiago (Université Paris Cité) "Boolean valued semantics for infinitary logics" (Slides).

    Abstract.

    This is joint work with Matteo Viale. It is well known that the completeness theorem for $L_{\omega_1\omega}$ fails with respect to Tarski semantics. Mansfield showed that it holds for $L_{\kappa\kappa}$ if one replaces Tarski semantics with boolean valued semantics. I'll talk about using forcing to improve his result in order to obtain a stronger form of boolean completeness (but only for $L_{\kappa\omega}$). Leveraging on this completeness result, one can establish the Craig interpolation property and a strong version of the omitting types theorem for $L_{\kappa\omega}$ with respect to boolean valued semantics. I'll also present a weak version of these results for the general case $L_{\kappa\lambda}$ (if one leverages instead on Mansfield's completeness theorem). All this work is based on the key notion of consistency property.

    Nascondi abstract.

  • 25 novembre 2022, 16.00-17.00 (Aula 715, DIMA, Genova)

    G. Coraglia (Università di Genova) "A theory of fuzzy types" (Slides).

    Abstract.

    We introduce a fuzzy type theory and its calculus in order to model opinions. We begin revisiting a classical correspondence between type theories and display map categories, then move to the enriched setting so that we can account for different degrees of belief in a given argument. Finally, we write new rules taking into account the fuzziness, and prove completeness and validity for such a calculus. This is a work in progress and the first part of a project for the Adjoint School of 2022, it is joint with S. Arya, P. North, S. O’Connor, H. Reiss, and A. L. Tenório.

    Nascondi abstract.

  • 11 novembre 2022, 17.00-18.00 (Aula 3, Palazzo Campana, Torino)

    B. Degasperi (Università di Torino) "Equational theories" (Slides).

    Abstract.

    The aim of this talk is to present equational theories. Definable sets are the main objects of study in model theory. In many theories, such as algebraically closed fields and vector spaces, there is a family of sets with tame properties such that all the definable sets of the theory are a finite Boolean combination of these sets. Equationality is a generalisation of this concept. We start defining the notion of equations. Then we show that it is stronger than stability and the connection with indiscernible closure. We conclude with some examples.

    Nascondi abstract.

  • 28 ottobre 2022, 16.00-17.00 (Aula 714, DIMA, Genova)

    F. Dagnino (Università di Genova) "Quantitative equality in substructural logic".

    Abstract.

    Equality in First Order Logic is fairly well understood: from a syntactic point of view it can be characterised as a binary predicate forced to be reflexive and substitutive, and from a categorical perspective, following Lawvere, it can be described in terms of left adjoints. This story can be easily rephrased in the context of predicate Linear Logic, however, this smooth approach has an unexpected consequence: equality can be used an arbitrary number of times. This fact is not desirable in a substructural setting where one aims at controlling the use of resources. Moreover, it does not allow a quantitative interpretation of equality, for instance, as a distance.
    In this talk, we explore a novel approach to equality in substructural logic based on graded modalities. These modalities allow us to explicitly model resources inside the language, describing how much a formula can be used. In this way, we manage to control the use of equality, thus enabling its quantitative interpretation. We develop this approach using the categorical language of Lawvere's doctrines and having as main example metric spaces with Lipschitz maps. We also present a deductive calculus for (fragments of) predicate Linear Logic with this quantitative equality and its sound and complete categorical semantics. Finally, we describe a universal construction producing models of quantitative equality starting from models of (fragments of) Linear Logic with graded modalities.
    This is joint work with Fabio Pasquali presented at LICS 2022.

    Nascondi abstract.

  • 17 giugno 2022, 11.00-13.00 (Online on Webex)

    R. Mennuni (Università di Pisa) "Model theory of ordered abelian groups" (Slides).

    Abstract.

    The first part of this talk will be a survey of the state of the art in the model theory of ordered abelian groups, with emphasis on quantifier elimination. In the second part, I will present current work in progress of myself and Jan Dobrowolski, focused on "generic" automorphisms of ordered abelian groups and of ordered real vector spaces.

    Nascondi abstract.

  • 29 aprile 2022, 16.00-17.00 (Sala Riunioni, DMIF, Udine)

    M. Iannella (Università di Udine) "Embeddings of countable linear orders".

    Abstract.

    In this talk we recall the relations of embeddability and convex embeddability on the set \(\mathsf{LO}\) of countable linear orders. We extend the notion of convex embeddability providing a family of quasi-orders on \(\mathsf{LO}\) of which embeddability is a particular case as well. We study these quasi-orders from a combinatorial point of view and analyse their complexity with respect to Borel reducibility, highlighting differences and analogies with embeddability and convex embeddability.

    Nascondi abstract.

  • 22 aprile 2022, 16.00-18.00 (Sala Riunioni, DMIF, Udine)

    S. Thei (Università di Udine) "The geology of pseudo-grounds" (Slides).

    Abstract.

    Four decades after the invention of forcing, Laver and independently Woodin answered one of the most natural questions regarding forcing. Is the ground model definable in its forcing extensions? Surprisingly, it turns out that the ground models of a given set-theoretic universe are uniformly definable. Fuchs, Hamkins and Reitz used this result to establish the formal foundations for set-theoretic geology that reverses the forcing construction by studying what remains from a model of set theory once the layers created by forcing are removed. Such a switch in perspective leads to another interesting question. Is the universe itself a nontrivial forcing extension of a smaller model? Reitz addressed the issue and introduced the Ground Axiom (the precursor to set-theoretic geology) which asserts that the universe is not obtained by forcing over any strictly smaller model.
    This talk is about some types of inner models which are defined following the paradigm of “undoing” forcing. For example, a bedrock is a ground satisfying the Ground Axiom and the mantle is the intersection of all grounds. Once the main geological notions are in place, we will introduce inner models with the cover and approximation properties called pseudo-grounds. In particular, we will consider some generalizations of classical results to the context of class forcing and pseudo-grounds.

    Nascondi abstract.

  • 25 febbraio 2022, 16.00-18.00 (Sala Riunioni, DMIF, Udine)

    V. Cipriani (Università di Udine) "The (induced) subgraph problem in the Weihrauch lattice" (Slides).

    Abstract.

    In this talk we study principles related to the (induced) subgraph problem using Weihrauch reducibility. Such problems are well studied in finite complexity theory, but they can be naturally generalized to the infinite case. After a brief introduction on computable analysis and Weihrauch reducibility, we solve some open questions in a recent article of BeMent, Hirst and Wallace. Here the authors studied the Weihrauch degrees of problems (that in this talk we denote by \(\mathsf{FindSG}_G\) and \(\mathsf{FindIndSG}_G\) respectively) that, given in input a computable graph \(H\), output \(1\) if \(G\) is an (induced) subgraph of \(H\). The authors proved that for a computable non-empty graph \(\mathsf{LPO}\leq_\mathrm{W}\mathsf{FindIndSG}_G\leq_\mathrm{W}\mathsf{WF}\), leaving open the question whether there is a graph \(G\) such that \(\mathsf{FindIndSG}_G\) lies strictly in between them. We will negatively answer this question and improve their results about the subgraph decision problems.
    We then introduce strictly related principles. Such principles, given in input a computable graph \(H\) having \(G\) as an (induced) subgraph, output an isomorphic copy of \(G\). We will show how these relates with well-studied principles in the Weihrauch lattice.
    This is a joint work with Arno Pauly (Swansea University).

    Nascondi abstract.

  • 18 febbraio 2022, 16.00-18.00 (Online on Webex)

    T. Marinov (Università di Torino) "Is forcing enough?".

    Abstract.

    Would set-theorists miss out on a lot if they didn't care about other methods for constructing models of Set Theory and only used forcing? In this talk I will sketch out a line of reasoning I follow in my thesis, under the supervision of Prof. Matteo Viale, in the pursuit of a more rigorous answer to a formalized aspect of the question of how powerful forcing is. The goal is to argue that a rich class of models of set theory are accessible through forcing from easily accessible standard structures — of the form \(H_\delta\).

    Nascondi abstract.

  • 11 febbraio 2022, 16.00-17.00 (Online on Webex)

    D. Castelnovo (Università di Udine) "Fuzzy algebraic theories" (Slides).

    Abstract.

    In this seminar I will present a join work with my supervisor Marino Miculan (see arXiv:2110.10970). I'll present a formal system for fuzzy algebraic reasoning: this sequent calculus is based on two kinds of propositions, capturing equality and existence of terms as members of a fuzzy set. I'll provide a sound semantics for this calculus and show that there is a notion of free model for any theory in this system, allowing us (with some restrictions) to recover models as Eilenberg-Moore algebras for some monad. I will also prove a completeness result: a formula is derivable from a given theory if and only if it is satisfied by all models of the theory. Finally, if possible, I'll show how to use some results by Milius and Urbat to give an HSP-like characterizations of subcategories of algebras which are categories of models of particular kinds of theories.

    Nascondi abstract.

  • 28 gennaio 2022, 16.00-18.00 (Aula 4, Palazzo Campana, Torino)

    D. Quadrellaro (Helsingin yliopisto) "Compactness and types in team semantics".

    Abstract.

    Team Semantics was introduced by Hodges as a generalisation of the standard Tarski's semantics of first order logic. While in the usual first-order model theory free variables are interpreted via assignments, in team semantics they are interpreted via teams, i.e. set of assignments. This framework was employed by Jouko Väänänen to introduce and develop dependence logic and related formalisms — inclusion logic, independence logic, etc. — which extend first order logic by suitable atoms. In this talk, I shall introduce the underlying ideas of team semantics and focus on some open problems in the model theory of (in)dependence logic. Firstly, I will present a novel proof of the compactness of (in)dependence logic, which strengthens previous results by Kontinen, Yang and Väänänen. Secondly, I will introduce types in team semantics and dependence logic and prove some preliminary results about the topological space of types of dependence logic. This is a joint work-in-progress with Joni Puljujärvi.

    Nascondi abstract.

  • 21 gennaio 2022, 16.00-17.00 (Aula 4, Palazzo Campana, Torino)

    L. Notaro (Università di Torino) "Tree representations for Borel functions" (Slides).

    Abstract.

    In 2009 Brian Semmes, in his PhD thesis, provided a characterization of Borel measurable functions from and into the Baire space using a reduction game called the Borel game. Around the same year, Alain Louveau wrote some (still unpublished) notes in which he provided a characterization of Baire class $\alpha$ functions (again from and into the Baire space), for all fixed $\alpha$ and, importantly, $\boldsymbol{\Sigma}_\lambda^0$-measurable functions for $\lambda$ countable limit, using tree-representations instead of games. In this talk, we present Louveau's characterization, comparing it with Semmes' one, and see that if we modify a bit the Borel game we end up characterizing functions having a $G_\delta$ graph. Then we notice that under $\mathrm{AC}$ there are functions for which the Borel game is undetermined, thus opening questions regarding the consistency strength of the general determinacy of this game.

    Nascondi abstract.


Nascondi 2022.
Espandi 2021
Nascondi 2021.
  • 29 ottobre 2021, 16.00-18.00 (Aula 4, Palazzo Campana, Torino)

    B. Pitton (Université de Lausanne) "Borel and Borel$^*$ sets in Generalized Descriptive Set Theory " (Slides).

    Abstract.

    Generalized descriptive set theory (GDST) aims at developing a higher analogue of classical descriptive set theory in which $\omega$ is replaced with an uncountable cardinal $\kappa$ in all definitions and relevant notions. In the literature on GDST it is often required that $\kappa^{<\kappa}=\kappa$, a condition equivalent to $\kappa$ regular and $2^{<\kappa}=\kappa$. In contrast, in this talk we use a more general approach and develop in a uniform way the basics of GDST for cardinals $\kappa$ still satisfying $2^{<\kappa}=\kappa$ but independently of whether they are regular or singular. This allows us to retrieve as a special case the known results for regular $\kappa$, but it also uncovers their analogues when $\kappa$ is singular. We also discuss some new phenomena specifically arising in the singular context (such as the existence of two distinct yet related Borel hierarchies), and obtain some results which are new also in the setup of regular cardinals, such as the existence of unfair Borel$^*$ codes for all Borel$^*$ sets.

    Nascondi abstract.

  • 22 ottobre 2021, 16.00-17.00 (Aula 4, Palazzo Campana, Torino)

    E. Colla (Università di Torino) "Words and other words" (Slides).

    Abstract.

    We gently review some definitions and theorems regarding the free semigroup of words, from two different areas: automata theory and Ramsey theory. Our recent results in Ramsey theory hint at a possible connection between two classes of monoids introduced by Solecki and "[the second] most important result of the algebraic theory of automata" (J. E. Pin). While this possibility is still vague, it seems exciting enough to be investigated. As far as prerequisites are concerned, most of this talk could be followed by anyone having a bachelor in mathematics. Based on a joint work with Claudio Agostini.

    Nascondi abstract.

  • 15 ottobre 2021, 16.00-18.00 (Aula 4, Palazzo Campana, Torino)

    S. Scamperti (Università di Torino) "A complete picture of the Wadge Hierarchy in 0-dimensional Polish space", parte 2.

    Abstract.

    Wadge reducibility is a very important tool in descriptive set theory. On 0-dimensional Polish spaces it yields a nice hierarchy and very studied by results of Wadge, Martin, Monk, Andretta, Louveau, Duparc, Carroy, Medini, Müller, Motto Ros, and others. On Cantor space and Baire space the Wadge hierarchy has some different behaviors, one of those on countable degree. Namely countable degree on Cantor space are non selfdual classes, while on Baire space they are selfdual classes. This phenomenon arise a question: what happens in general 0-dimensional Polish spaces? We will answer this question with the notion of compactness degree for a 0-dimensional Polish space and see that infinitely different many cases can be realized on 0-dimensional Polish spaces.

    Nascondi abstract.

  • 8 ottobre 2021, 16.00-17.00 (Aula 4, Palazzo Campana, Torino)

    S. Scamperti (Università di Torino) "A complete picture of the Wadge Hierarchy in 0-dimensional Polish space", parte 1 (Slides).

    Abstract.

    Wadge reducibility is a very important tool in descriptive set theory. On 0-dimensional Polish spaces it yields a nice hierarchy and very studied by results of Wadge, Martin, Monk, Andretta, Louveau, Duparc, Carroy, Medini, Müller, Motto Ros, and others. On Cantor space and Baire space the Wadge hierarchy has some different behaviors, one of those on countable degree. Namely countable degree on Cantor space are non selfdual classes, while on Baire space they are selfdual classes. This phenomenon arise a question: what happens in general 0-dimensional Polish spaces? We will answer this question with the notion of compactness degree for a 0-dimensional Polish space and see that infinitely different many cases can be realized on 0-dimensional Polish spaces.

    Nascondi abstract.


Nascondi 2021.
Espandi 2019
Nascondi 2019.
  • 16 gennaio 2019, 10.30-12.30 (Anthropole-3077)

    L. Vuilleumier (Unil - Paris 7) "The Wadge order via admissible representations on the Borel subsets of the Scott domain is isomorphic to the Wadge order on the non-self-dual Borel subsets of the Baire space".

    Abstract.

    The Wadge order on a topological space is the quasi order on the subsets of the topological space induced by continuous functions. It is well behaved on the Borel subsets of the Baire space. A represented space is a topological space that can be coded by the elements of the Baire space. If this coding is continuous, then the quasi order on the preimages of the subsets of the space is interesting. We show that this quasi order on the Borel subsets of the Scott domain is isomorphic to the Wadge order on the non-self-dual Borel subsets of the Baire space.

    Nascondi abstract.


Nascondi 2019.