Logic Seminar in Semester II AY 2021/2022

• Wednesday 12/01/2022, 16:00 hrs, Week 1, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  
  Logic Day Special. Insights into Participant's Logic Research.
  This week's Logic Seminar on Wed 12 January 2022 at 16:00 hrs is an open session where, in light of the World Logic Day on Friday, everyone is encouraged to give about 10 minutes presentation about his favourate result or results of his own work.
  
  
  
• Wednesday 19/01/2022, 16:00 hrs, Week 2, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Ye Jinhe. Curve-exclusing fields.
  Consider the class of fields with Char(K)=0 and x⁴+y⁴=1 has only 4 solutions in K, we show that this class has a model companion, which we denote by curve-excluding fields. Curve-excluding fields provides (counter)examples to various questions. Model theoretically, they are model complete. Field theoretically, they are not large and unbounded. Time permitting, we will discuss other aspects such as decidability of such fields.
  This is joint work with Will Johnson and Erik Walsberg.
  
  
• Wednesday 26/01/2022, 16:00 hrs, Week 3, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Zhang Jing. Ramsey-type theorems on large structures.
  Structures like trees, linear orders, partial orders, graphs have been widely studied in different areas of mathematics. The Ramsey-type theorems we will discuss usually take the following form: for any given coloring of the structure, there exists a "large sub-structure" that intersects "very few" color classes. One example is a theorem of Laver that states for any finite coloring of Q x Q (ordered pairs of rationals), there exists X, Y order isomorphic to Q, such that X x Y intersects at most 2 color classes. We will discuss the uncountable analogues of these statements and their consistency. In particular, a diagonal version of the Halpern-Lauchli theorem plays a key role. The differences between countable combinatorics and uncountable combinatorics will be highlighted.
  
  
• Thursday 03/02/2022, 16:00 hrs, Week 4, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Andre Nies. The structure of the class of K-trivial sets.
  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.
  The slides are available.
  
  
• Wednesday 09/02/2022, 16:00 hrs, Week 5, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Xie Ruofei. Convergence property and randomness.
  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 ∑_n (a_n)² 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.
  
  
• Wednesday 16/02/2022, 16:30 hrs, Week 6, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Rupert Hölzl. Universality, optimality and randomness deficiency.
  A Martin-Löf test U is universal if it captures all sequences which are not Martin-Löf random. It is optimal if for every Martin-Löf test V there is a constant c such that, for all n, V_n+c ⊆ U_n. We study the computational differences between universal and optimal Martin-Löf 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-Löf 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.
  
  
• Wednesday 02/03/2022, 16:00 hrs, Week 7, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Lavinia Picollo. High-order logic and disquotational truth.
  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.
  
  
• Wednesday 09/03/2022, 16:00 hrs, Week 8, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  No Talk.
  
  
• Wednesday 16/03/2022, 16:00 hrs, Week 9, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Leszek Kolodziejczyk. A conservativity result for not-WO(ω^ω).
  The Chong-Slaman-Yang construction of a model of RT²₂ not satisfying Σ⁰₂-induction makes crucial use of a principle known as BME₁. This principle was later shown by Kreuzer and Yokoyama to be equivalent to WO(ω^ω), the statement that ω^ω is well-ordered.
  I will talk about the following result: if A is any set in a model of RCA₀ + Σ⁰₂-collection such that Σ₂(A)-induction fails, then there is a descending sequence in ω^ω that is low in A. As a consequence, the negation of WO(ω^ω) is Π¹₁-conservative over RCA₀ + BΣ⁰₂ + not-IΣ⁰₂.
  This result has some potentially interesting corollaries:
  • If RCA₀ + RT²₂ is Π¹₁-conservative over BΣ⁰₂, then this can be proved by considering only models in which BME₁ fails.
  • The formula >>X is a well-order<< is not provably equivalent to any Σ¹₁ formula over COH + BΣ⁰₂ + not-IΣ⁰₂. (In contrast, by earlier work of Fiori Carones, Wong, Yokoyama and myself, the theory WKL^*₀ + not-IΣ⁰₁, which is to some extent analogous to COH + BΣ⁰₂ + not-IΣ⁰₂, proves a collapse of the analytic hierarchy to Δ¹₁.)
  • There exist two models of RCA₀ + COH + BΣ⁰₂ that share a first-order universe and a common counterexample to IΣ⁰₂ but are not elementarily equivalent. (In contrast, by the work of Fiori Carones et al. mentioned above, the families of Δ⁰₂-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.
  
  
• Wednesday 23/03/2022, 16:00 hrs, Week 10, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Wu Guohua. Splittings and nonsplittings of computably enumerable sets.
  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.
  
  
• Wednesday 30/03/2022, 16:00 hrs, Week 11, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Wu Liuzhen. Continuum function and strongly compact cardinal.
  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.
  
  
• Wednesday 06/04/2022, 16:00 hrs, Week 12, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Frank Stephan. Matching regular pumping lemmas and automaticity. A pumping lemma for regular languages is matching iff it is satisfied exactly by the regular languages. Furthermore, one distinghises for pumping lemmas one-sided versions where only words in the language L are pumped and two-sided versions where all words of sufficiently long length are pumped.
  Jaffe as well as Ehrenfeucht, Parikh and Rozenberg gave examples of matching two-sided pumping lemmas. The goal of the present talk is to show that if one requires that an automatic function (equivalently a transducer) marks of the pump in the input word, then most two-sided pumping lemmas including the traditional pumping lemma are matching. Furthermore, it is shown that in contrast to this, most one-sided pumping lemmas with an automatic function to compute the pump are not matching. This is only left open for the case of the one-sided automatic block pumping lemma.
  This is joint work of Karen Celine, Ryan Chew, Sanjay Jain and the speaker. Slides are available as pdf-file and ps-file.
  
  
• Wednesday 13/04/2022, 16:00 hrs, Week 13, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Wang Wei. Ackermann, Ramsey and Trees.
  Recently, Chong, Yang and I prove that a version of Pigeonholes Principle for trees (TT¹) is Π⁰₃-conservative over RCA₀. So, TT¹ does not imply the totality of the Ackermann function over RCA₀, 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.