Date/Time : 09 Apr 2024 17:00
Venue : S17 #05-11 (SR5)
Speaker : Piotr Kowalski, The University of Wrocław

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 group.

Add to calendar :

Date/Time : 27 Mar 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Kyle Gannon, Peking University

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.

Add to calendar :

Date/Time : 20 Mar 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Sun Mengzhou,

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.

Add to calendar :

Date/Time : 06 Mar 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Rupert Hoelzl, Universitaet der Bundeswehr, Munich

A left-computable number x is called regainingly approximable if there is a computable increasing sequence (x_n)_{n in N} of rational numbers converging to x such that x-x_n < 2^-n for infinitely many n in 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 in N} converges computably to 0.

In this talk 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-Loef 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 Philip Janicki.

Add to calendar :

Date/Time : 21 Feb 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Neil Barton, University of Oslo

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.

Add to calendar :

Date/Time : 07 Feb 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Alexander Rabinovich, Tel Aviv University

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. Buechi 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.

Add to calendar :

Date/Time : 31 Jan 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Yu Liang, Nanjing University

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.

Add to calendar :

Date/Time : 24 Jan 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Arturo Rodríguez Fanlo, Hebrew University of Jerusalem

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).

Add to calendar :

Date/Time : 17 Jan 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Makoto Tatsuta, National Institute of Informatics, Japan

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-Lof’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-Lof’s system, since a cyclic proof system does not have to choose fixed induction formulas in advance. The equivalence of the provability of Martin-Lof’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.

Add to calendar :