Logic Seminar in AY 2023/2024

• Tuesday 15/08/2023, 17:00 hrs, Week 1.
  No Talk.
  
  
• Tuesday 22/08/2023, 17:00 hrs, Week 2.
  No Talk.
  
  
• Tuesday 29/09/2023, 17:00 hrs, Week 3, Department of Mathematics, Room S17#04-06.
  Tran Chieu Minh. Measure doubling of small sets in SO(3,R).
  In a recent work, we show that if A is an open subset of SO(3,R) with sufficiently small normalized Haar measure, then
  • μ(A²) > 3.99 μ(A).
  This was conjectured by Emmanuel Breuillard and Ben Green around 15 years ago in the context of getting optimal bounds and finding continuous counterparts of product theorems by Helfgott, Pyber-Szabo, and Breuillard-Green-Tao. The result is also related to the Brunn-Minkowski inequalities from convex geometry, the Kunze-Stein phenomenon from harmonic analysis, and the Pillay conjectures from model theory.
  In this talk, I will explain these connections and discuss some ideas from the proof, which uses nonstandard analysis and neostable group theory.
  The talk is based on joint work with Yifan Jing and Ruixiang Zhang.
  
  
• Tuesday 05/09/2023, 17:00 hrs, Week 4, Department of Mathematics, Room S17#04-06.
  Sun Mengzhou. On the (non)elementarity of cofinal extension.
  Compared with end extensions, much little is known about cofinal extensions for models of fragments of PA. In particular, it is not even known known whether the elementarity of cofinal extensions can fail at some specific level. In this talk, I will try to give a complete answer. I will present a systemetic way to `compress' the truth of M into the second-order structure of a definable cut, and as a consequence, a correspondence theorem between the first-order theory of M and the second-order theory of the cut. Through this method I will construct several models with special cofinal extension properties. I will also show that every countable model of arithmetic fail to satisfy PA admits a non-elementary cofinal extension. It provides a model-theoretic characterization for PA in terms of cofinal extensions.
  
  
• Tuesday 12/09/2023, 17:00 hrs, Week 5, Department of Mathematics, Room S17#04-06.
  Borisa Kuzeljevic. Lower bounds of sets of P-points.
  We will sketch the proof that MA(κ) implies that each collection of P_c-points of size at most κ which has a P_c-point as an RK upper bound also has a P_c-point as an RK lower bound.
  This is joint work with Dilip Raghavan and Jonathan Verner.
  
  
• Thursday 14/09/2023, 17:00 hrs, Week 5, Department of Mathematics, Room S17#04-06.
  Jan Dobrowolski. Kim-independence in positive logic.
  The class of NSOP1 theories, originally introduced by Džamonja and Shelah in 2004, has been studied very intensively in the last few years since the striking discovery of an independence relation called Kim-independence by Ramsey and Kaplan (based on earlier ideas of Kim and a work of Chernikov and Ramsey), which generalises forking independence in simple theories, and retains almost all its nice properties in the class of NSOP1 theories.
  I will start the talk with an overview of the notion of Kim-independence, and then I will present my joint work with Mark Kamsma on generalising Kim-independence to positive logic. In particular, I will discuss examples of positive NSOP1 theories falling into our framework such as the theory of existentially closed exponential fields (studied by Kirby and Haykazyan), the theory of fields with a generic submodule (studied by d'Elbée, Kaplan and Neuhauser) and the hyperimaginary extensions of NSOP1 theories.
  
  
• Tuesday 19/09/2023, 17:00 hrs, Week 6, Department of Mathematics, Room S17#04-06.
  Neoh Tzeh Yuan. The complexity of $3$-occur-SAT.. The Boolean satisfiabilty problem (SAT) is a problem with great theoretical and practical interest. While heuristic algorithms tend to work well in practice, the widely believed strong exponential time hypothesis (SETH) conjectures that there is no deterministic algorithm for SAT in time O(cⁿ) for some constant c < 2. On the other hand, better bounds of O(cⁿ) with c < 2 have been found for various restricted (but still NP-complete) instances of SAT. One such problem is 3-Occur-SAT, where every variable in the formula occurs at most 3 times. Wahlström presented in 2005 an algorithm which solves the problem in time O(1.1279ⁿ) and Peng and Xiao improved it (this year's IJCAI) to O(1.1238ⁿ). I will present an algorithm that gives a further improvement to O(1.1199ⁿ). I'll discuss the common bottleneck cases faced by previous efforts and introduce new reduction and branching rules that can circumvent these cases.
  The work I present is done in an internship at NUS / SOC supervised by Sanjay Jain and Frank Stephan from July to September 2023.
  
  
• Tuesday 03/10/2023, 17:00 hrs, Week 7.
  No Talk.
  
  
• Tuesday 10/10/2023, 17:00 hrs, Week 8.
  No Talk.
  
  
• Tuesday 17/10/2023, 17:00 hrs, Week 9, Department of Mathematics, Room S17#04-06.
  Frank Stephan Addition machines, automatic functions and the open problems of Floyd and Knuth.
  Floyd and Knuth studied in their 1990 paper addition machines which are machines which can add, subtract and compare integers (<,=,>) in unit time; also the reading or writing of an integer is in unit time. They showed that multiplying and dividing can be done in linear time with six registers and asked in their Open Problem (2) whether this bound can be broken; furthermore, they asked in Open Problem (5) of their paper whether there is a register machine which can output in subquadratic time the powers of two occurring in the binary representation of an integer. The talk answers both questions affirmatively and presents the key ideas and programs to witness this.
  This is joint work with Sanjay Jain, Xiaodong Jia and Ammar Fathin Sabili. The joint paper appeared in the Journal of Computer and System Sciences (volume 136, pages 135-156, year 2023) and is also available as technical report on https://arxiv.org/abs/2111.08969. The slides of the talk are available as ps-file and pdf-file.
  
  
• Tuesday 24/10/2023, 17:00 hrs, Week 10, Department of Mathematics, Room S17#04-06.
  Ho Meng-Che. Word problems of groups as ceers.
  Classically, the word problem of a group is the set of words equal to the identity of the group, and we analyze them using Turing reductions. In this talk, we consider the word problem of a group as a computably enumerable equivalence relation (ceer), namely, two words are equivalent if and only if they are equal in the group. We compare ceers using the computable reduction: E is reducible to F if there is a computable function f so that i E j if and only if f(i) F f(j).
  We will discuss some recent results and see that the landscape of word problems as ceers is very different from the classical theory. For instance, in the classical setting, any Turing degree can be realized as a word problem by first constructing a countable group and then embedding it into a finitely presented group via the Higman embedding theorem. However, we prove that in the ceer setting, there is a group G whose word problem is not universal, but for any nontrivial H, the free product of G and H has a universal word problem.
  This is a joint work with Uri Andrews and Luca San Mauro.
  
  
• Tuesday 31/10/2023, 17:00 hrs, Week 11, Department of Mathematics, Room S17#04-06.
  Samuel Alfaro Tanuwijaya. Generalisations of the Posner Robinson theorem.
  The talk will deal with relativised versions of the Posner Robinson theorem and explore how far one can go and how to prove these relatived versions.
  
  
• Tuesday 07/11/2023, 17:00 hrs, Week 12, Department of Mathematics, Room S17#04-06.
  Ye Jinhe. Lang-Weil type estimates in finite difference fields.
  A difference field is a field equipped with a given automorphism and a difference variety is the natural analogue of an algebraic varieties in this setting. Complex numbers with complex conjugation or finite fields with the Frobenius automorphism are natural examples of difference fields.
  For finite fields and varieties over them, the celebrated Lang-Weil estimate gives a universal estimate of number of rational points of varieties over finite fields in terms of several notions of the complexities of the given variety.
  In this talk, we will discuss an analogue to Lang-Weil estimate for difference varieties in finite difference fields. The proof uses pseudofinite difference fields, where the automorphism is the nonstandard Frobenius. This is joint work with Martin Hils, Ehud Hrushovski and Tingxiang Zou.
  
  
• Tuesday 14/11/2023, 17:00 hrs, Week 13, Department of Mathematics, Room S17#04-06.
  Liu Shixiao. Density forcings that collapse the continuum.
  Last semester I talked about the upper density Mathias forcing which we prove to be proper. This time we take a look at several similar forcings, each of which collapses the continuum to omega and thus fails to be proper.
  
  
• Tuesday 05/12/2023, 15:30 hrs. Department of Mathematics, Room S17#04-06.
  Lu Qi. Convexity of multiplicities of filtrations on local rings.
  In this talk, I will discuss some convexity properties of multiplicities of filtrations on a local ring. In particular, the multiplicity function is convex along geodesics. As a major application, this gives a new proof of a theorem due to Xu and Zhuang on the uniqueness of normalized volume minimizers. In order to characterize strict convexity, we introduce the notion of saturation of a filtration, which turns out to be useful in other settings. For example, it allows us to generalizes a theorem by Rees on characterization of when two filtrations have equal multiplicities. It also allows us to introduce a metric on the space of filtrations.
  This talk is based on joint work with Harold Blum and Yuchen Liu and some ongoing work.
  
  
• Tuesday 09/01/2024, 15:00 hrs, Department of Mathematics, Room S17#04-05.
  Manlio Valenti. The tree pigeonhole principle in the Weihrauch degrees.
  Ramsey's theorem for n-tuples and k colors can be generalized to colorings of binary trees. More precisely, TTⁿ_k states that given a k coloring of the n-subsets of finite binary strings, there is a monochromatic set of strings that is isomorphic to the full binary tree. In the literature, this is sometimes referred to as Chubb-Hirst-McNicholl tree theorem.
  In this talk, we will be focusing on the tree pigeonhole principle, namely the special case of the tree theorem for colorings of strings (i.e. n=1). We analyze its uniform computational content within the framework of Weihrauch reducibility. We show that different ways of phrasing the theorem yield different Weihrauch degrees. Our results provide new insights on the first-order part of the tree pigeonhole principle.
  This is joint work with Damir Dzhafarov and Reed Solomon.
  
  
• Wednesday 17/01/2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Tatsuta Makoto. Brotherston's Conjecture: Equivalence of Inductive Definitions and Cyclic Proofs.
  An inductive definition is a way to define a predicate by an expression which may contain the predicate itself. The predicate is interpreted by the least fixed point of the defining equation.
  Inductive definitions are important in computer science, since they can define useful recursive data structures such as lists and trees.
  Inductive definitions are important also in mathematical logic, since they increase the proof theoretic strength. Martin-Loef's system of inductive definitions given in 1971 is one of the most popular system of inductive definitions.
  In 2006 Brotherston proposed an alternative formalization of inductive definitions, called a cyclic proof system. In general, for proof search, a cyclic proof system can find an induction formula in a more efficient way than Martin-Loef's system, since a cyclic proof system does not have to choose fixed induction formulas in advance.
  The equivalence of the provability of Martin-Loef's system for inductive definitions and that of the cyclic proof system was conjectured in 2006. The speaker and Berardi solved it in 2017.
  This talk will explain this problem.
  
  
• Wednesday 24/01/2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Arturo Rodríguez Fanlo. Local Positive Logic.
  Abstract: In this talk I will present a new (first-order) logic that mixes positive logic (where negation is not allowed) and local logic (where quantifiers are bounded). We will discuss several basic notions of model theory for this logic such as compactness, positive closedness (existential closedness), completeness (irreducibility), type spaces and retractors (saturated models).
  
  
• Wednesday 31/01/2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Yu Liang. Some Applications of Recursion Theory to Geometric Measure Theory.
  Geometric measure theory relates effectivity notions to dimensions and measures like the Hausdorff dimension. The talk gives further links to the Axiom of Determinacy over ZF (it is not consistent with ZFC) and how these influence the geometry of the finite-dimensional Euclidian Space and its subsets. The talk explains the theorems of Besicovitch and Davis, of father and son Lutz and of Slaman; these theorems are related to recent results in the field including those by the speaker.
  The slides are available here.
  
  
• Wednesday 07/02/2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Alexander Rabinovich. The Church Synthesis Problem over Continuous Time.
  Church's Problem asks for the construction of a procedure which, given a logical specification S(I,O) between input -strings I and output-strings O, determines whether there exists an operator F that implements the specification in the sense that S(I,F(I)) holds for all inputs I. Büchi and Landweber gave a procedure to solve Church's problem for MSO specifications and operators computable by finite-state automata. We investigate a generalization of the Church synthesis problem to the continuous time of the non-negative reals. It turns out that in the continuous time there are phenomena which are very different from the canonical discrete time domain of the natural numbers.
  The slides of the talk can be found here.
  
  
• Wednesday 14/02/2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  No Talk.
  
  
• Wednesday 21/02/2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Neil Barton. Potentialist Sets, Intensions, and Non-Classicality.
  A popular view in the philosophy of set theory is that of potentialism: the position that the set-theoretic universe unfolds as more sets come into existence or become accessible to us. This often gets formalised using modal logic, but there is always a question of how to move to non-modal theories. In this latter regard, a difficult question for the potentialist is to explain how intensional entities (entities individuated by an application condition rather than an extension) behave, and in particular what logic governs them. This talk will discuss some work in progress on this issue. We'll see how to motivate acceptance of different propositional logics for different flavours of potentialism, and discuss the prospects for proving results about the kinds of first-order theories validated.
  
  
• Wednesday 06.03.2024, 17.00 hrs, Department of Mathematics, Room S17#04-05.
  Rupert Hölzl. Benign approximations and non-speedability.
  A left-computable number x is called regainingly approximable if there is a computable increasing sequence (x_n)_n of rational numbers converging to x such that x-x_n<2^-n for infinitely many n∈N; and it is called nearly computable if there is such an (x_n)_n such that for every computable increasing function s:N → N the sequence (x_s(n+1)-x_s(n))_n converges computably to 0. In this article we study the relationship between both concepts by constructing on the one hand a non-computable number that is both regainingly approximable and nearly computable, and on the other hand a left-computable number that is nearly computable but not regainingly approximable; it then easily follows that the two notions are incomparable with non-trivial intersection. With this relationship clarified, we then hold the keys to answering an open question of Merkle and Titov: they studied speedable numbers, that is, left-computable numbers whose approximations can be sped up in a certain sense, and asked whether, among the left-computable numbers, being Martin-Löf random is equivalent to being non-speedable. As we show that the concepts of speedable and regainingly approximable numbers are equivalent within the nearly computable numbers, our second construction provides a negative answer.
  This is joint work with Philipp Janicki.
  
  
• Wednesday 20.03.2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Sun Mengzhou. The Kaufmann-Clote question on end extensions of models of arithmetic.
  A general question in the model theory of arithmetic is: For each theories S, T and natural number n, is it true that every countable sufficiently saturated model of S has a proper n-elementary end extension to a model of a T? Efforts over the past four decades have revealed answers to this question for S and T in the induction-collection hierarchy IΣ_n, BΣ_n, except the following instance by Clote and Kaufmann: Is it true that, given any integer n, every countable model of BΣ_n+2 has a proper n-elementary end extension to a model of BΣ_n+1? We present a positive answer to the Kaufmann-Clote question. The proof consists of a second-order ultrapower construction based on a low basis theorem. We also include a survey on the results related to the general question above. This is a joint work with Tin Lok Wong and Yue Yang.
  
  
• Wednesday 27.03.2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Kyle Gannon. Model theoretic events.
  This talk is motivated by the following two soft questions: How do we sample an infinite sequence from a first order structure? What model theoretic properties might hold on almost all sampled sequences? We advance a plausible framework in an attempt to answer these kinds of questions. The central object of this talk is a proability space. The underlying set of our space is a standard model theoretic object, namely the space of types in countably many variables over a monster model. Our probability measure is an iterated Morley product of a fixed Borel-definable Keisler measure. Choosing a point randomly in this space with respect to our distribution yields a random generic type in infinitely many variables. We are interested in which model theoretic events hold for almost all random generic types. Two different kinds of events will be discussed:
  (1) The event that the induced structure on a random generic type is isomorphic to a fixed structure;
  (2) the event that a random generic type witnesses a dividing line.
  This work is joint with James Hanson.
  
  
• Wednesday 03.04.2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Frank Stephan. Fuzzy Logic and Completeness.
  Fuzzy Logic allows either finitely many truth values of the form 0,1/k,2/k,...,k/k or an infinite number of truth values which is dense in the real interval from 0 to 1 and which includes the two end-points 0 and 1. The specific properties depend on the formulas chosen for calculating logical connectives; in this talk, one uses the following conventions:

         NOT q        is  1-q;
         p OR q       is  max{p,q};
         p AND q      is  min{p,q};
         p EOR q      is  min{p+q,2-p-q};
         p IMPLIES q  is  min{1,1+q-p};
         p EQUIV q    is  min{1+p-q,1+q-p}.  

  An interesting question is when is the Fuzzy Logic with these truth-values complete in the following sense, for Propositional Logic: One says that S logically implies α iff for all truth-assignments for the atoms which make all formulas in S have the truth value 1 it also holds that α has the truth value 1. The question is now whether there is a set of axioms for the Propositional Fuzzy Logic which allows to prove α from S and these axioms.
  Vilém Novák has proven in 1980 that this is the case when there are only finitely many truth-values 0,1/k,2/k,...,k/k; furthermore, this talk will provide a countable set S of propositional formulas S which logically imply one atoms B such that, whenever there is an infinite set of truth-values, no finite subset T of S logically implies B. Hence one can for infinitely many truth-values not expect completeness, independently of what axioms one allows. Furthermore, the set of axioms must depend on the number of truth-values k+1 in the case of finitely many values.
  This is joint work with Neo Wei Qing and Wong Tin Lok.
  
  
• Tuesday 09.04.2024, 17:00 hrs, Department of Mathematics.
  Piotr Kowalski.Model completeness and matrix groups.
  I plan to discuss the notions of model companion and model completeness focusing on algebraic and geometric examples. For instance, I will mention recent joint work with Daniel Max Hoffmann, Chieu-Minh Tran and Jinhe Ye, where we consider model completeness of certain matrix groups.
  
  
• Wednesday 17.04.2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Philipp Kunde. Non-classifiability of ergodic flows up to time change.
  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 {S_t}_{t ∈ R} and {T_t}_{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.
  Note that there is a related talk in the Geometry and Topology seminar by Shilpak Banarjee at 15:30 hrs on the same day.
  
  
• Wednesday 08.05.2024, 17:00 hrs, Department of Mathematics, Room S17#04-04.
  Vittorio Cipriano. Characterizing different notions of learnability of structures.
  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, Kötzing 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₀, the equivalence relation of eventual agreement on infinite binary sequences. Replacing E₀ 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.
  
  
• Wednesday 17.07.2024, 17:00 hrs, Department of Mathematics, Room LT33.
  Wojciech Woloszyn. Ultimate L and the Resurrection Principle: A Tale of Forcing and Large Cardinals.
  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.
  
  
• Wednesday 31.07.2024, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  George Barmpalias. Questions and progress in Algorithmic Randomness.
  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.