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 :

Date/Time : 09 Jan 2024 15:00
Venue : S17 #04-05 (SR2)
Speaker : Manlio Valenti, Swansea University

Ramsey’s theorem for n-tuples and k-colors can be generalized to colorings of binary trees. More precisely, TT^n_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.

Add to calendar :

Date/Time : 05 Dec 2023 15:30
Venue : S17 #04-04 (SR3)
Speaker : Lu Qi, Princeton University

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.

Add to calendar :

Date/Time : 14 Nov 2023 17:00
Venue : S17 #04-06 (SR1)
Speaker : Liu Shixiao,

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.

Add to calendar :