Date/Time : 13 Apr 2022 16:00
Venue : via Zoom
Speaker : Wang Wei, Sun Yatsen University

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: Recently, Chong, Yang and I prove that a version of Pigeonholes Principle for trees (TT^1) is Pi^0_3-conservative over RCA_0. So, TT^1 does not imply the totality of Ackermann function over RCA_0, like the instance of Ramsey’s Theorem for 2-colorings of pairs. To fit the trend of logic talks, I am not going to present many details. Instead, I will try to recall some stories about the Ackermann function and its appearance in reverse mathematics.

Add to calendar :

Date/Time : 06 Apr 2022 16:00
Venue : via Zoom
Speaker : Frank Stephan, National University of Singapore

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: The talk investigates which versions of the pumping lemma are matching where matching means that exactly the regular languages satisfy it. In particular it will be shown that two-sided pumping lemmas where an automatic function computes the pump tend to be matching.

Add to calendar :

Date/Time : 30 Mar 2022 16:00
Venue : via Zoom
Speaker : Wu Liuzhen,

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: The continuum function is a key and long-studied object inside set theory. We will survey the study on the behavior of continuum function in presence of strongly compact cardinals. We will also introduce some major research problems in this area. Finally, We discuss our recent work on forcing continuum function of some special pattern.

Add to calendar :

Date/Time : 23 Mar 2022 16:00
Venue : via Zoom
Speaker : Wu Guohua, Nanyang Technological University

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract:  In this talk, I will review some existing work on splittings of c.e. sets, and then present an ongoing paper on nonsplitting, a joint work with Downey. The main result is the following.

Theorem: There are c.e. sets A and B such that B is strictly Turing reducible to A and for any c.e. sets U, V, if U and V form a set-splitting of A, then one of them is Turing reducible to B.

Add to calendar :

Date/Time : 16 Mar 2022 16:00
Venue : via Zoom
Speaker : Leszek Kolodziejczyk, University of Warsaw

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract:  The Chong-Slaman-Yang construction of a model of RT^2_2 not satisfying Sigma^0_2-induction makes crucial use of a principle known as BME_1. This principle was later shown by Kreuzer and Yokoyama to be equivalent to WO(omega^omega), the statement that omega^omega is well-ordered.

I will talk about the following result: if A is any set in a model of RCA_0 + Sigma^0_2-collection such that Sigma_2(A)-induction fails, then there + is a descending sequence in omega^omega that is low in A. As a consequence, the negation of WO(omega^omega) is Pi11-conservative over RCA_0 +BSigma^0_2 + not-ISigma^0_2.

This result has some potentially interesting corollaries:

– If RCA_0 + RT^2_2 is Pi^1_1-conservative over BSigma^0_2, then this can be proved by considering only models in which BME_1 fails.

– The formula “X is a well-order” is not provably equivalent to any Sigma^1_1 formula over COH + BSigma^0_2 + not-ISigma^0_2. (In contrast, by earlier work of Fiori Carones, Wong, Yokoyama, and myself, the theory
WKL*_0 + not-ISigma^0_1, which is to some extent analogous to COH + BSigma^0_2 + not-ISigma^0_2, proves a collapse of the analytic hierarchy to Delta^1_1.)

– There exist two models of RCA_0 + COH + BSigma^0_2 that share a first-order universe and a common counterexample to ISigma^0_2 but are not elementarily equivalent. (In contrast, by the work of Fiori Carones et al. mentioned above, the families of Delta^0_2-definable sets of any such two models have to be elementarily equivalent.)

The conservativity result is a side product of a larger project joint with Fiori Carones, Yokoyama, and others.

Add to calendar :

Date/Time : 02 Mar 2022 16:00
Venue : via Zoom
Speaker : Lavinia Picollo, National University of Singapore

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: Truth predicates are widely believed to be capable of serving a certain logical or quasi-logical function. There is little consensus, however, on the exact nature of this function. We offer a series of formal results in support of the thesis that disquotational truth is a device to simulate higher-order resources in a first-order setting. More specifically, we show that any theory formulated in a higher-order language can be naturally and conservatively interpreted in a first-order theory with a disquotational truth or truth-of predicate. In the first part of the talk we focus on the relation between truth and full impredicative sentential quantification. The second part is devoted to the relation between truth-of and full impredicative predicate quantification.

This is joint work with Thomas Schindler

Add to calendar :

Date/Time : 16 Feb 2022 16:30
Venue : via Zoom
Speaker : Rupert Hoelzl, Universitaet der Bundeswehr, Muenchen

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: A Martin-Loef test U is universal if it captures all sequences which are not Martin-Loef random. It is optimal if for every Martin-Loef test V there is a constant c such that, for all n, V_{n+c} subseteq U_n. We study the computational differences between universal and optimal Martin-Loef tests as well as the effects of these differences on both the notions of layerwise computability and the Weihrauch degree of LAY, the function that produces a bound on the randomness deficiency of a given Martin-Loef random sequence. We prove several robustness and idempotence results concerning the Weihrauch degree of LAY and we show that layerwise computability is more restrictive than Weihrauch reducibility to LAY. Along similar lines, we also study the principle RD, a variant of LAY outputting the precise randomness deficiency of sequences instead of only an upper bound as LAY.

This is joint work with Paul Shafer. The paper is available as in the Annals of Pure and Applied Logic, https://doi.org/10.1016/j.apal.2015.05.006

Add to calendar :

Date/Time : 09 Feb 2022 16:00
Venue : via Zoom
Speaker : Xie Ruofei,

oin Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: Consider the sum of the series (-1)^{x_n}a_n over n, where x_n is a binary sequence and a_n is a sequence of real numbers.
We say the sequence x_n has convergence property if the sum above converges for every computable sequence of real numbers whose sum \sum_n a_n^2 converges computably.

Downey, Greenberg, and Tanggara showed in their unpublished paper that every Schnorr random series x_n has convergence property.
In this talk, we will focus on convergence property and show its similarities and differences with randomness.

This is joint work with Noam Greenberg.

Add to calendar :

Date/Time : 03 Feb 2022 16:00
Venue : via Zoom
Speaker : Andre Nies, The University of Auckland

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Chaitin introduced this notion in about 1975, and showed that each K-trivial is Turing below the halting set. Shortly after, Solovay proved that a K-trivial set can be noncomputable.

In the past two decades, many alternative characterisations of this class have been found: properties such as being low for K, low for Martin-Loef (ML) randomness, and a basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially, the class of noncomputable K-trivials appeared to be amorphous. More recently, an internal structure has been found. Most of these results can be phrased in the language of a reducibility on the K-trivials which is weaker than Turing’s:

A is ML-below B if each ML-random computing B also computes A.

Bienvenu, Greenberg, Kucera, Nies and Turetsky (JEMS 2016) showed that there an ML complete K-trivial set. Greenberg, Miller and Nies (JML, 2019) established a dense hierarchy of subclasses of the K-trivials based on fragments of Omega computing the set, and each such subclass is an initial segment for ML. More recent results (see arxiv.org/abs/1707.00258, updated and submitted Dec 2020) generalise these approaches using cost functions. They also show that each K-trivial set is ML-equivalent to a c.e. K-trivial.

The extreme lowness of K-trivials, far from being an obstacle, allows for methods which don’t work in a wider setting. The talk provides an overview and discusses open questions. For instance, is ML-completeness an arithmetical property of K-trivials?

This is joint work with Noam Greenberg, Joseph Miller and Dan Turetsky.

Add to calendar :