Date/Time : 31 Aug 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Yang Yue, National University of Singapore

Abstract: A pair (a,b) of nonzero r.e. Turing degrees is called a strong minimal pair iff the recursive Turing degree is the only common lower bound and if every nonzero Turing degree bounded by a has with b a join greater or equal a. We show that such strong minimal pairs do not exist.

Joint work with Cai Mingzhong, Liu Yiqun, Liu Yong and Peng Cheng

Add to calendar :

Date/Time : 24 Aug 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Goh Jun Le, National University of Singapore

Abstract: We present ongoing work with Steffen Lempp, Ng Keng Meng and Mariya Soskova on the algebraic structure of the Sigma^0_2 e-degrees, i.e., the quotient structure on the Sigma^0_2 subsets of the natural numbers induced by enumeration reducibility. The Sigma^0_2 e-degrees are analogous to the r.e. Turing degrees in some ways, but an elementary difference between them was exhibited by Ahmad (1998): In the former structure there are incomparable degrees a and b such that if x < a, then x < b. (Such a and b cannot exist in the r.e. Turing degrees by the Sacks splitting theorem.) Ahmad also showed that this phenomenon cannot occur symmetrically, i.e., there cannot be incomparable degrees a and b such that x < a if and only if x < b. In contrast, we show that there are incomparable degrees a, b and c such that x < a if and only if (x < b and x < c). In other words, the ideal {x: x < a} admits an exact pair (b,c). This result constitutes progress towards our ultimate goal of algorithmically deciding the truth of all two-quantifier sentences in the Sigma^0_2 e-degrees.

Add to calendar :

Date/Time : 17 Aug 2022 17:00
Venue : S17 #04-05 (SR2)
Speaker : Wong Tin Lok, National University of Singapore

Abstract: I will present another quantifier-elimination result in arithmetic under negated induction. This gives new information about pigeonhole principles and expansions to second-order models.

Joint work with: David Belanger, CT Chong, Wei Li and Yue Yang.

Add to calendar :

Date/Time : 10 Aug 2022 17:00
Venue : S17 #04-05 (Seminar Room 2)
Speaker : Tran Chieu-Minh, National University of Singapore

Abstract:  For a bivariate P(x,y) in R[x,y] – (R[x] union R[y]), we show that for all finite subsets A of R,|P(A,A)| is greater or equal alpha |A|^(5/4) with alpha = alpha(deg P) being a real number greater than 0, P(x,y)=f(gamma u(x)+delta u(y)) or P(x,y)=f(u^m(x)u^n(y)) for some univariate f, u R[t] – </b>, constants gamma, delta in R – {0}</b> and m, n in {1,2,3,…}.

This resolves the symmetric nonexpanders classification problem proposed by de Zeeuw and is a step towards the analog for polynomials of the Erdoes-Szemeredi sumproduct Conjecture. The proofs of our results use tools from semialgebraic / o-minimal geometry.

Add to calendar :

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 :