Logic Seminar in Semester I AY 2022/2023

• Wednesday 10/08/2022, 17:00 hrs, Week 1, Department of Mathematics, Room S17#04-05.
  Tran Chieu-Minh.
  O-minimal Methods and Generalized Sum-Product Phenomena.
  For a bivariate P(x,y) ∈ R[x,y] ∖ (R[x] ∪ R[y]), we show that for all finite A ⊆ R, |P(A,A)| ≥ α|A|^5/4 with α = α(deg P) ∈ R^>0 unless P(x,y)=f(γ u(x)+δ u(y)) or P(x,y)=f(u^m(x)uⁿ(y)) for some univariate f, u ∈ R[t] ∖ R, constants γ, δ ∈ R ∖ {0} and m, n ∈ {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 Erdös-Szemerédi sumproduct Conjecture.
  The proofs of our results use tools from semialgebraic / o-minimal geometry.
  
  
• Wednesday 17/08/2022, 17:00 hrs, Week 2, Department of Mathematics, Room S17#04-05.
  Wong Tin Lok. Another quantifier-elimination result in arithmetic under negated induction.
  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.
  This work is joint with David Belanger, CT Chong, Wei Li and Yue Yang.
  
  
• Wednesday 24/08/2022, 17:00 hrs, Week 3, Department of Mathematics, Room S17#04-05.
  Goh Jun Le. An exact pair in the Σ⁰₂ enumeration degrees.
  We present ongoing work with Steffen Lempp, Ng Keng Meng and Mariya Soskova on the algebraic structure of the Σ⁰₂ e-degrees, i.e., the quotient structure on the Σ⁰₂ subsets of the natural numbers induced by enumeration reducibility. The Σ⁰₂ 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 if x < a iff x < b. In contrast, we show that there are incomparable degrees a, b and c such that if x < a if and only if both 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 Σ⁰₂ e-degrees.
  
  
• Thursday 31/08/2022, 17:00 hrs, Week 4, Department of Mathematics, Room S17#04-05.
  Yang Yue. The Strong Minimal Pair Problem.
  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 equal a. We show that such strong minimal pairs do not exist.
  This is joint work with Cai Mingzhong, Liu Yiqun, Liu Yong and Peng Cheng.
  
  
• Wednesday 07/09/2022, 17:00 hrs, Week 5, Department of Mathematics, Room S17#04-05.
  Liao Yuke. A computable coloring without Π⁰₃ witness with apartness for Hindman theorem.
  We construct a computable coloring function such that any Π⁰₃ set with apartness can not be a witness of Hindman theorem for this coloring. And we can modify the coloring function and drop the condition "with apartness".
  
  
• Wednesday 14/09/2022, 17:00 hrs, Week 6, Department of Mathematics, Room S17#04-05.
  Ammar Fathin Sabili. Alternating automatic register machines.
  We introduce and study a new computation model called an Alternating Automatic Register Machine (AARM). An AARM possesses a basic features of a conventional register machine and an alternating Turing machine, but can carry out computations using bounded automatic relations in a single step. One particular finding is that an AARM can recognize some NP-complete problems, including CNF-SAT (using a particular encoding), in log^*n + O(1) steps. Furthermore, we also show that padding the input with a polynomial-size string allows to recognise exactly the sets in the polynomial hierarchy using log^*n + O(1) steps. These results illustrate the power of alternation when combined with computations involving automatic relations.
  This is joint work with Gao Ziyuan, Sanjay Jain, Li Zeyong and Frank Stephan. A technical report is available on https://arxiv.org/abs/2111.04254.
  
  
• Wednesday 28/09/2022, 17:00 hrs, Week 7, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  No talk.
  
  
• Wednesday 05/10/2022, 17:00 hrs, Week 8, Department of Mathematics, Room S17#04-05.
  Yang Yue. Between Σ₁ and Σ₂ Induction.
  Yang Yue will talk about his past and concurrent research in Reverse Mathematics and provide the background of other researchers on the same topic, please see the linked pdf-file for more details.
  
  
• Wednesday 12/10/2022, 17:00 hrs, Week 9, Department of Mathematics, Room S17#04-05.
  Frank Stephan. Initial segment complexity for measures.
  Based on a joint paper with Andre Nies, click here for its technical report version, the speaker will present the background and selected results of the paper. Furthermore, the slides are available as a ps-file or a pdf-file.
  
  
• Wednesday 19/10/2022, 17:00 hrs, Week 10, Department of Mathematics, Room S17#04-05.
  Abdul Basit. On the shatter function of semilinear families.
  The shatter function, a combinatorial function associated to a family of sets, is an important measure of its complexity. For example, it is related to the popular notions of VC dimension and VC density. We show that the shatter function of a semilinear family (i.e., a family definable in (R, + , <) is asymptotic to a polynomial. This implies, in particular, that any semilinear family has integer VC density, which confirms a conjecture by Artem Chernikov.
  This is joint work with Tran Chieu-Minh.
  
  
• Wednesday 26/10/2022, 17:00 hrs, Week 11, Department of Mathematics, Room S17#04-05.
  Sun Mengzhou. End extensions of weak arithmetic theories.
  Paris and Kirby showed that a countable model satisfies BΣ_n+2 if and only if it has an (n+2)-elementary proper end extension. Later Kaufman asked whether we can always end extend countable models of BΣ_n+2 to some model of BΣ_n+1. We briefly discuss what we have now related to this question and what is the difficulty here.
  
  
• Wednesday 02/11/2022, 17:00 hrs, Week 12, Department of Mathematics, Room S17#04-05.
  Wu Guohua. Ring constructions: axioms needed.
  Many constructions in rings involve applications of various axioms, which guarantee the existence of wanted objects. In this talk, I will present examples of such constructions, and show how these axioms are applied and really needed.
  The slides are available here as pdf-file.
  
  
• Wednesday 09/11/2022, 17:00 hrs, Week 13, Department of Mathematics, Room S17#04-05.
  Benjamin T Castle. Complex Polynomials up to Interdefinability.
  Motivated by recent progress toward Zilber's Restricted Trichotomy Conjecture, we study reducts of the complex field up to interdefinability over parameters. Precisely, we will consider structures of the form (C, P₁,...,P_n), where the P_i are polynomial maps of potentially different arities. Somewhat surprisingly, our main result states that almost all such structures (in a precise sense) are interdefinable. The proof uses a mix of tools from geometric stability theory, combinatorics, and algebraic geometry.
  This is joint work with Chieu-Minh Tran.