Date/Time : 08 May 2024 17:00
Venue : S17 #04-04 (SR3)
Speaker : Vittorio Cipriani, Vienna University of Technology

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, Kotzing, 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_0, the equivalence relation of eventual agreement on infinite binary sequences. Replacing E0 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.

Add to calendar :

Date/Time : 17 Apr 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Philipp Kunde, Universität Hamburg

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 {St}t ∈ R and {Tt}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.

Add to calendar :

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 :