Date/Time : 04 Sep 2024 16:45
Venue : S17 #04-04 (SR3)
Speaker : Chong Chi Tat, National University of Singapore

Let $\alpha$ be an admissible ordinal. A set $A\subset \alpha$ is of minimal $\alpha$-degree if it is non -recursive and every set of lower $\alpha$-degree is recursive. In 1956 Spector introduced the technique of forcing with perfect sets to prove the existence of a minimal $\omega$-degree. Sacks posed the problem of the existence of a minimal $\alpha$-degree for all admissible $\alpha$. This problem, poised in the early 1970’s, remains unsolved today. The best result to-date is that of Shore (1972) in which he showed that there is a positive solution if $\alpha$ is $\Sigma_2$-admissible. There has been no progress made on this problem since. In this talk we present a recent result on the minimal $\alpha$-degree problem for singular cardinals of uncountable cofinality which are not $\Sigma_2$-admissible.

Add to calendar :

Date/Time : 28 Aug 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Linus Richter, National University of Singapore

I will outline a few connections between various notions of definability (which vary in degree of logical formality), give examples, and describe some open questions at the intersection of logic and classical mathematics.

Add to calendar :

Date/Time : 21 Aug 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Vo Ngoc Thieu, National University of Singapore

The main aim of this talk is to introduce our recent results on computational problems related to DAEs, including the effective differential Nullstellensatz, effective differential elimination, and finding general solutions of low-order algebraic ODEs. The effective differential Nullstellensatz involves finding a positive integer N for a given DAE system, such that one can check the consistency of the system by performing N differentiations and polynomial eliminations. Differential elimination involves removing independent variables from a DAE system. Differential Nullstellensatz and elimination are two fundamental problems in differential algebra and differential algebraic geometry. Since the number N represents the computational complexity of the effective differential Nullstellensatz and elimination, finding an upper bound for N is crucial. We will present our recent investigations into the problem of determining an upper bound for N. In addition, our results on the problem of determining algebraic/rational general solutions of first-order algebraic ODEs, as well as their connection with the Poincaré problem, will also be presented.

Add to calendar :

Date/Time : 14 Aug 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Koh Heer Tern, Nanyang Technological University

We explore a recent program in comparing effective topological spaces up to (not necessarily computable) homeomorphism. We provide a survey of some earlier results separating some of the common notions of presentations for Polish spaces. By pushing existing definability techniques and effective versions of Stone duality, we also provide some new counterexamples. Most interestingly, that there exists a Polish space both left-c.e. and right-c.e. presentable but not computably presentable.

Add to calendar :

Date/Time : 07 Aug 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Zhang Jing, University of Toronto

We expose an organizing framework to study higher dimensional infinitary combinatorics based on \v{C}ech cohomology, originating from works by Barry Mitchell, Barbara Osofsky and others. Key combinatorial notions include n-coherence and n-triviality for sequences of functions. We will use some recent vanishing and non-vanishing results to demonstrate “aleph_n is incompact for (n+1)-dimensional combinatorics” and “aleph_{omega+1} can be compact for n-dimensional combinatorics for all n”. Time permitting, we will also discuss the possibility of generalizing classical 2-dimensional properties like being special or being Suslin to higher dimensions. The talk will be purely combinatorial. Joint work with Jeffrey Bergfalk and Chris Lambie-Hanson.

Add to calendar :

Date/Time : 31 Jul 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : George Barmpalias, Chinese Academy of Sciences

I will discuss current challenges and progress in algorithmic randomness, focusing on Chaitin’s halting probability, almost everywhere domination and measures of relative randomness. I will offer conjectures, partial results and benchmark problems toward solving the main questions.

Add to calendar :

Date/Time : 17 Jul 2024 17:00
Venue : LT33 (S17 Level 2)
Speaker : Wojciech Woloszyn, University of Oxford

Two features of the Ultimate L are that it is forcing invariant and compatible with large cardinals. The resurrection principle stabilizes forcing out albeit mildly. The latter can be refuted from the existence of a large cardinal way below I0. What is the bearing of this on the status of large cardinals and the axiom V=Ultimate L? An interesting picture unfolds.

Add to calendar :

Date/Time : 08 May 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Vittorio Cipriani, Vienna University of Technology

In this talk, we combine computable structure theory and inductive inference to study learning of families of structures. All the structures we consider are relational and countable and all the families of structures we consider are at most countable. The framework we use was defined in a series of papers by Bazhenov, Fokina, Kotzing, and San Mauro. In a nutshell, the framework models the scenario in which, given a family of structures K, a learner receives more and more information about the atomic diagram of a copy of some A ∈ K and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. In this context, a natural criterion to consider is Ex-learning in which we require the learner to stabilize to the correct conjecture after finitely many steps.

Together with Bazhenov and San Mauro we gave a descriptive set-theoretic characterization of Ex-learning. Namely, we showed that a family of structures is Ex-learnable if and only if the corresponding isomorphism problem continuously reduces to E_0, the equivalence relation of eventual agreement on infinite binary sequences. Replacing E0 with other equivalence relations, one obtains a hierarchy to rank such isomorphism problems. That is, a family of structures K is E-learnable, for an equivalence relation E, if there is a continuous reduction from the isomorphism problem associated with K to E.

We aim to obtain model-theoretic characterization of E-learning for different equivalence relations E. Some characterizations are already present in the literature: here we show that a family of structures K such that for any A_i, A_j ∈ K there is a Σ_n^{inf} formula satisfied by A_i but not by A_j is E-learnable if and only if E is the (iteration of the) Friedman-Stanely jump of the identity either on natural numbers or on Cantor space. We also show that other learning criteria coming from the classical setting of inductive inference of formal languages or recursive functions have a nice model-theoretic characterization.

This talk collects joint works with Bazhenov, Jain, Marcone, San Mauro and Stephan.

Add to calendar :

Date/Time : 17 Apr 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Philipp Kunde, Universität Hamburg

Dating back to the foundational paper by John von Neumann, a fundamental theme in ergodic theory is the isomorphism problem to classify invertible measure-preserving transformations (MPTs) up to isomorphism. In a series of papers, Matthew Foreman, Daniel Rudolph and Benjamin Weiss have shown that such a classification is impossible in terms of computable invariants, even with a very inclusive understanding of “computability”.  Besides isomorphism, Kakutani equivalence is the best known and most natural equivalence relation on ergodic MPTs for which the classification problem can be considered. For ergodic flows {St}t ∈ R and {Tt}t ∈ R Kakutani showed that the two flows have Kakutani equivalent transformations as cross-sections if and only if the flows are isomorphic up to a time change. Here, a time change of a flow is a reparametrization of the orbits of the flow such that each orbit is mapped to itself by an orientation-preserving homeomorphism of the parameter space. 

In joint work with Marlies Gerber we prove that the Kakutani equivalence relation of ergodic MPTs is not a Borel set. This shows in a precise way that the problem of classifying such transformations up to Kakutani equivalence is also intractable. In particular, our results imply the non-classifiability of ergodic flows up to isomorphism after a time change.

Add to calendar :