School "Definability, Decidability, and Computability"HIM/HSM Special Topic School

Sep 15, 2025, 9:00 AM → Sep 19, 2025, 4:00 PM Europe/Berlin

Poppelsdorfer Allee 45, 1. EG, Lecture room (HIM)

Emma Seggewiss (HCM), Kanami Ueda

This HIM School is a week-long event directed at PhD students and recent Postdocs, which will take place within the framework of the Trimester Program "Advances in Mechanism Design".

The online application platform to participate in the school will be accessible shortly after the due date to apply for participation in the trimester program has expired.

PhD students and early-career researchers (up to four years past their PhD), who were invited and have confirmed to be at HIM during the period of this School, are automatically admitted to this event. Beyond this, researchers from the HCM, in particular, early-career researchers, are welcome upon request.

Everyone will be notified in due time about whether participation and partial financial support is possible. After being selected as participant, you will be invited to register.

Lecture series by:

• Sylvy Anscombe (Université Paris Cité)

• Franziska Jahnke (Münster)

• Bjorn Poonen (MIT)

• Theodor Slaman (UC Berkeley)

Description: Definability has a far-reaching impact in mathematics, far beyond model theory. In this workshop, experts not only from definability, but in other areas of mathematics (number theory, computability theory, arithmetic geometry, etc.) will give an expository overview of the impact of definability in their fields, as well as the state of the current research in their fields. These talks are accessible to graduate students and experts from other fields, to facilitate the discussions that will follow during the trimester. 

Event Website

Trimester Program: "Definability, decidability, and computability"

Mon, September 15

1 Model Theory and Definability (1)

The aim of this course is to give a fast-track introduction to model-theoretic methods and their uses in number theory. In the first two to three sessions, I will introduce first-order logic and a range of model-theoretic tools, focusing in particular on compactness, quantifier elimination and definability. For each of the techniques introduced, I will discuss applications to number theory. Additionally, I will set reading tasks for researchers new to the area, enabling them to follow more model-theoretic talks throughout the programme.
In the second part of the course, I will discuss definability of henselian valuations, both explicitly and implicitly, and discuss questions of uniformity and complexity of such definitions.

Speaker: Prof. Franziska Jahnke (University of Münster)

2 Diophantine sets and Hilbert’s tenth problem

Hilbert’s tenth problem asked for an algorithm to decide, given a multivariable polynomial equation, whether it has a solution in integers. After Matiyasevich in 1970 completed the proof that no such algorithm exists, the same question has been asked for solutions in other rings and fields. Much has been learned also about what subsets are first-order definable in rings and fields that number theorists and algebraic geometers care about. I will survey these topics, including recent advances and prospects for future study.

Speaker: Prof. Bjorn Poonen (MIT)

3 The classical Ax-Kochen/Ershov principles

Sixty years ago Ax, Kochen, and (independently) Ershov showed that the first-order theory of a field complete with respect to a non-Archimedean absolute value of characteristic 0 (e.g. $\mathbb{Q}((t))$ or $\mathbb{C}((t))$) is determined by the theories of its residue field and value group. The method is indirect: First, in order to facilitate the use of model theoretic methods, we allow valuations rather than absolute values - the key difference is that the image of the valuation is not required to be Archimedean. Second, we replace the hypothesis of completeness by considering instead those valued fields that are henselian, i.e. that satisfy the conclusion of Hensel’s Lemma.
So, for the class of henselian valued fields of equal characteristic zero, one proves a suitable embedding lemma: any pair of embeddings between residue fields and value groups extends to an embedding of valued fields, subject to a natural saturation hypothesis. This embedding lemma in fact goes through allowing constants from certain common subfields, and it yields right away an AKE principle at the level of existential theories. Thus, by a back-and-forth argument, the same holds for any other classical fragment: existential-universal sentences, etc. Perhaps the “state of the art” setting for such AKE principles is the theory of (separably) tame valued fields: these principles and the underpinning algebraic results are due in the main to Kuhlmann and his collaborators, principally Knaf and Pal. In this short course of five talks I hope to give a rather uniform presentation of AKE principles, beginning in the classical setting of equal characteristic zero, then extending to include those valued fields that are finitely ramified (in mixed characteristic) and (separably) tame. I will describe three families of extensions and applications. The first is to discuss what is known around AKE principles for certain expansions of the language of valued fields, notably difference fields and differential fields. The second is the analysis of existential theories of henselian valued fields, in equal characteristic and to a lesser extent in mixed characteristic. The third is that we lay the ground for the “Taming Theorem” of Jahnke and Kartas, where they find AKE results for the first time that apply to certain valued fields that admit finite extensions with nontrivial defect.

Speaker: Dr Sylvy Anscombe (Université Paris Cité)

4 Computability and Definability: Theory and Application (1)

We will start with an overview of the mathematical study of definability. In the context of sets of integers, we will discuss computability, the Halting Problem and its associated operation the Turing jump, arithmetic and hyperarithmetic hierarchies. In the context of the real numbers, the objects are directly related to topological complexity, such as a function’s being continuous or a set’s being Borel. We will include proofs of several basic theorems chosen to illustrate the basic methods of the area. In the pure theory of definability, we will discuss Martin’s Conjecture, which gives a precise sense in which this analysis of definability is intrinsic and inevitable. We will outline two case studies in which the theory of definability is used to study phenomena whose origins are external to mathematical logic: normality to integer bases and Hausdorff dimension.

Speaker: Prof. Theodore Slaman (University of California Berkeley)

5 Model Theory and Definability (2)

The aim of this course is to give a fast-track introduction to model-theoretic methods and their uses in number theory. In the first two to three sessions, I will introduce first-order logic and a range of model-theoretic tools, focusing in particular on compactness, quantifier elimination and definability. For each of the techniques introduced, I will discuss applications to number theory. Additionally, I will set reading tasks for researchers new to the area, enabling them to follow more model-theoretic talks throughout the programme.
In the second part of the course, I will discuss definability of henselian valuations, both explicitly and implicitly, and discuss questions of uniformity and complexity of such definitions.

Speaker: Prof. Franziska Jahnke (University of Münster)

Tue, September 16

6 Positive residue characteristic: finite ramification and Kaplansky’s hypothesis

Sixty years ago Ax, Kochen, and (independently) Ershov showed that the first-order theory of a field complete with respect to a non-Archimedean absolute value of characteristic 0 (e.g. $\mathbb{Q}((t))$ or $\mathbb{C}((t))$) is determined by the theories of its residue field and value group. The method is indirect: First, in order to facilitate the use of model theoretic methods, we allow valuations rather than absolute values - the key difference is that the image of the valuation is not required to be Archimedean. Second, we replace the hypothesis of completeness by considering instead those valued fields that are henselian, i.e. that satisfy the conclusion of Hensel’s Lemma.
So, for the class of henselian valued fields of equal characteristic zero, one proves a suitable embedding lemma: any pair of embeddings between residue fields and value groups extends to an embedding of valued fields, subject to a natural saturation hypothesis. This embedding lemma in fact goes through allowing constants from certain common subfields, and it yields right away an AKE principle at the level of existential theories. Thus, by a back-and-forth argument, the same holds for any other classical fragment: existential-universal sentences, etc. Perhaps the “state of the art” setting for such AKE principles is the theory of (separably) tame valued fields: these principles and the underpinning algebraic results are due in the main to Kuhlmann and his collaborators, principally Knaf and Pal. In this short course of five talks I hope to give a rather uniform presentation of AKE principles, beginning in the classical setting of equal characteristic zero, then extending to include those valued fields that are finitely ramified (in mixed characteristic) and (separably) tame. I will describe three families of extensions and applications. The first is to discuss what is known around AKE principles for certain expansions of the language of valued fields, notably difference fields and differential fields. The second is the analysis of existential theories of henselian valued fields, in equal characteristic and to a lesser extent in mixed characteristic. The third is that we lay the ground for the “Taming Theorem” of Jahnke and Kartas, where they find AKE results for the first time that apply to certain valued fields that admit finite extensions with nontrivial defect.

Speaker: Dr Sylvy Anscombe (Université Paris Cité)

7 Computability and Definability: Theory and Application (2)

We will start with an overview of the mathematical study of definability. In the context of sets of integers, we will discuss computability, the Halting Problem and its associated operation the Turing jump, arithmetic and hyperarithmetic hierarchies. In the context of the real numbers, the objects are directly related to topological complexity, such as a function’s being continuous or a set’s being Borel. We will include proofs of several basic theorems chosen to illustrate the basic methods of the area. In the pure theory of definability, we will discuss Martin’s Conjecture, which gives a precise sense in which this analysis of definability is intrinsic and inevitable. We will outline two case studies in which the theory of definability is used to study phenomena whose origins are external to mathematical logic: normality to integer bases and Hausdorff dimension.

Speaker: Prof. Theodore Slaman (University of California Berkeley)

8 The first order theory of finitely generated rings and fields

Hilbert’s tenth problem asked for an algorithm to decide, given a multivariable polynomial equation, whether it has a solution in integers. After Matiyasevich in 1970 completed the proof that no such algorithm exists, the same question has been asked for solutions in other rings and fields. Much has been learned also about what subsets are first-order definable in rings and fields that number theorists and algebraic geometers care about. I will survey these topics, including recent advances and prospects for future study.

Speaker: Prof. Bjorn Poonen (MIT)

9 Model Theory and Definability (3)

The aim of this course is to give a fast-track introduction to model-theoretic methods and their uses in number theory. In the first two to three sessions, I will introduce first-order logic and a range of model-theoretic tools, focusing in particular on compactness, quantifier elimination and definability. For each of the techniques introduced, I will discuss applications to number theory. Additionally, I will set reading tasks for researchers new to the area, enabling them to follow more model-theoretic talks throughout the programme.
In the second part of the course, I will discuss definability of henselian valuations, both explicitly and implicitly, and discuss questions of uniformity and complexity of such definitions.

Speaker: Prof. Franziska Jahnke (University of Münster)

10 Tame fields and existential theories in equal characteristic

Sixty years ago Ax, Kochen, and (independently) Ershov showed that the first-order theory of a field complete with respect to a non-Archimedean absolute value of characteristic 0 (e.g. $\mathbb{Q}((t))$ or $\mathbb{C}((t))$) is determined by the theories of its residue field and value group. The method is indirect: First, in order to facilitate the use of model theoretic methods, we allow valuations rather than absolute values - the key difference is that the image of the valuation is not required to be Archimedean. Second, we replace the hypothesis of completeness by considering instead those valued fields that are henselian, i.e. that satisfy the conclusion of Hensel’s Lemma.
So, for the class of henselian valued fields of equal characteristic zero, one proves a suitable embedding lemma: any pair of embeddings between residue fields and value groups extends to an embedding of valued fields, subject to a natural saturation hypothesis. This embedding lemma in fact goes through allowing constants from certain common subfields, and it yields right away an AKE principle at the level of existential theories. Thus, by a back-and-forth argument, the same holds for any other classical fragment: existential-universal sentences, etc. Perhaps the “state of the art” setting for such AKE principles is the theory of (separably) tame valued fields: these principles and the underpinning algebraic results are due in the main to Kuhlmann and his collaborators, principally Knaf and Pal. In this short course of five talks I hope to give a rather uniform presentation of AKE principles, beginning in the classical setting of equal characteristic zero, then extending to include those valued fields that are finitely ramified (in mixed characteristic) and (separably) tame. I will describe three families of extensions and applications. The first is to discuss what is known around AKE principles for certain expansions of the language of valued fields, notably difference fields and differential fields. The second is the analysis of existential theories of henselian valued fields, in equal characteristic and to a lesser extent in mixed characteristic. The third is that we lay the ground for the “Taming Theorem” of Jahnke and Kartas, where they find AKE results for the first time that apply to certain valued fields that admit finite extensions with nontrivial defect.

Speaker: Dr Sylvy Anscombe (Université Paris Cité)

Wed, September 17

11 Hilbert’s tenth problem for rings of integers I

Hilbert’s tenth problem asked for an algorithm to decide, given a multivariable polynomial equation, whether it has a solution in integers. After Matiyasevich in 1970 completed the proof that no such algorithm exists, the same question has been asked for solutions in other rings and fields. Much has been learned also about what subsets are first-order definable in rings and fields that number theorists and algebraic geometers care about. I will survey these topics, including recent advances and prospects for future study.

Speaker: Prof. Bjorn Poonen (MIT)

12 Computability and Definability: Theory and Application (3)

We will start with an overview of the mathematical study of definability. In the context of sets of integers, we will discuss computability, the Halting Problem and its associated operation the Turing jump, arithmetic and hyperarithmetic hierarchies. In the context of the real numbers, the objects are directly related to topological complexity, such as a function’s being continuous or a set’s being Borel. We will include proofs of several basic theorems chosen to illustrate the basic methods of the area. In the pure theory of definability, we will discuss Martin’s Conjecture, which gives a precise sense in which this analysis of definability is intrinsic and inevitable. We will outline two case studies in which the theory of definability is used to study phenomena whose origins are external to mathematical logic: normality to integer bases and Hausdorff dimension.

Speaker: Prof. Theodore Slaman (University of California Berkeley)

Thu, September 18

13 Model Theory and Definability (4)

The aim of this course is to give a fast-track introduction to model-theoretic methods and their uses in number theory. In the first two to three sessions, I will introduce first-order logic and a range of model-theoretic tools, focusing in particular on compactness, quantifier elimination and definability. For each of the techniques introduced, I will discuss applications to number theory. Additionally, I will set reading tasks for researchers new to the area, enabling them to follow more model-theoretic talks throughout the programme.
In the second part of the course, I will discuss definability of henselian valuations, both explicitly and implicitly, and discuss questions of uniformity and complexity of such definitions.

Speaker: Prof. Franziska Jahnke (University of Münster)

14 Analytic, difference, and differential structures

Sixty years ago Ax, Kochen, and (independently) Ershov showed that the first-order theory of a field complete with respect to a non-Archimedean absolute value of characteristic 0 (e.g. $\mathbb{Q}((t))$ or $\mathbb{C}((t))$) is determined by the theories of its residue field and value group. The method is indirect: First, in order to facilitate the use of model theoretic methods, we allow valuations rather than absolute values - the key difference is that the image of the valuation is not required to be Archimedean. Second, we replace the hypothesis of completeness by considering instead those valued fields that are henselian, i.e. that satisfy the conclusion of Hensel’s Lemma.
So, for the class of henselian valued fields of equal characteristic zero, one proves a suitable embedding lemma: any pair of embeddings between residue fields and value groups extends to an embedding of valued fields, subject to a natural saturation hypothesis. This embedding lemma in fact goes through allowing constants from certain common subfields, and it yields right away an AKE principle at the level of existential theories. Thus, by a back-and-forth argument, the same holds for any other classical fragment: existential-universal sentences, etc. Perhaps the “state of the art” setting for such AKE principles is the theory of (separably) tame valued fields: these principles and the underpinning algebraic results are due in the main to Kuhlmann and his collaborators, principally Knaf and Pal. In this short course of five talks I hope to give a rather uniform presentation of AKE principles, beginning in the classical setting of equal characteristic zero, then extending to include those valued fields that are finitely ramified (in mixed characteristic) and (separably) tame. I will describe three families of extensions and applications. The first is to discuss what is known around AKE principles for certain expansions of the language of valued fields, notably difference fields and differential fields. The second is the analysis of existential theories of henselian valued fields, in equal characteristic and to a lesser extent in mixed characteristic. The third is that we lay the ground for the “Taming Theorem” of Jahnke and Kartas, where they find AKE results for the first time that apply to certain valued fields that admit finite extensions with nontrivial defect.

Speaker: Dr Sylvy Anscombe (Université Paris Cité)

15 Computability and Definability: Theory and Application (4)

We will start with an overview of the mathematical study of definability. In the context of sets of integers, we will discuss computability, the Halting Problem and its associated operation the Turing jump, arithmetic and hyperarithmetic hierarchies. In the context of the real numbers, the objects are directly related to topological complexity, such as a function’s being continuous or a set’s being Borel. We will include proofs of several basic theorems chosen to illustrate the basic methods of the area. In the pure theory of definability, we will discuss Martin’s Conjecture, which gives a precise sense in which this analysis of definability is intrinsic and inevitable. We will outline two case studies in which the theory of definability is used to study phenomena whose origins are external to mathematical logic: normality to integer bases and Hausdorff dimension.

Speaker: Prof. Theodore Slaman (University of California Berkeley)

16 Hilbert’s tenth problem for rings of integers II

Hilbert’s tenth problem asked for an algorithm to decide, given a multivariable polynomial equation, whether it has a solution in integers. After Matiyasevich in 1970 completed the proof that no such algorithm exists, the same question has been asked for solutions in other rings and fields. Much has been learned also about what subsets are first-order definable in rings and fields that number theorists and algebraic geometers care about. I will survey these topics, including recent advances and prospects for future study.

Speaker: Prof. Bjorn Poonen (MIT)

17 Model Theory and Definability (5)

The aim of this course is to give a fast-track introduction to model-theoretic methods and their uses in number theory. In the first two to three sessions, I will introduce first-order logic and a range of model-theoretic tools, focusing in particular on compactness, quantifier elimination and definability. For each of the techniques introduced, I will discuss applications to number theory. Additionally, I will set reading tasks for researchers new to the area, enabling them to follow more model-theoretic talks throughout the programme.
In the second part of the course, I will discuss definability of henselian valuations, both explicitly and implicitly, and discuss questions of uniformity and complexity of such definitions.

Speaker: Prof. Franziska Jahnke (University of Münster)

Fri, September 19

18 Computability and Definability: Theory and Application (5)

We will start with an overview of the mathematical study of definability. In the context of sets of integers, we will discuss computability, the Halting Problem and its associated operation the Turing jump, arithmetic and hyperarithmetic hierarchies. In the context of the real numbers, the objects are directly related to topological complexity, such as a function’s being continuous or a set’s being Borel. We will include proofs of several basic theorems chosen to illustrate the basic methods of the area. In the pure theory of definability, we will discuss Martin’s Conjecture, which gives a precise sense in which this analysis of definability is intrinsic and inevitable. We will outline two case studies in which the theory of definability is used to study phenomena whose origins are external to mathematical logic: normality to integer bases and Hausdorff dimension.

Speaker: Prof. Theodore Slaman (University of California Berkeley)

19 Failed approaches to Hilbert’s tenth problem for $\mathbb{Q}$

Hilbert’s tenth problem asked for an algorithm to decide, given a multivariable polynomial equation, whether it has a solution in integers. After Matiyasevich in 1970 completed the proof that no such algorithm exists, the same question has been asked for solutions in other rings and fields. Much has been learned also about what subsets are first-order definable in rings and fields that number theorists and algebraic geometers care about. I will survey these topics, including recent advances and prospects for future study.

Speaker: Prof. Bjorn Poonen (MIT)

20 Towards the Taming Theorem of Jahnke and Kartas which applies the AKE-theory of tame valued fields to perfectoid fields

Sixty years ago Ax, Kochen, and (independently) Ershov showed that the first-order theory of a field complete with respect to a non-Archimedean absolute value of characteristic 0 (e.g. $\mathbb{Q}((t))$ or $\mathbb{C}((t))$) is determined by the theories of its residue field and value group. The method is indirect: First, in order to facilitate the use of model theoretic methods, we allow valuations rather than absolute values - the key difference is that the image of the valuation is not required to be Archimedean. Second, we replace the hypothesis of completeness by considering instead those valued fields that are henselian, i.e. that satisfy the conclusion of Hensel’s Lemma.
So, for the class of henselian valued fields of equal characteristic zero, one proves a suitable embedding lemma: any pair of embeddings between residue fields and value groups extends to an embedding of valued fields, subject to a natural saturation hypothesis. This embedding lemma in fact goes through allowing constants from certain common subfields, and it yields right away an AKE principle at the level of existential theories. Thus, by a back-and-forth argument, the same holds for any other classical fragment: existential-universal sentences, etc. Perhaps the “state of the art” setting for such AKE principles is the theory of (separably) tame valued fields: these principles and the underpinning algebraic results are due in the main to Kuhlmann and his collaborators, principally Knaf and Pal. In this short course of five talks I hope to give a rather uniform presentation of AKE principles, beginning in the classical setting of equal characteristic zero, then extending to include those valued fields that are finitely ramified (in mixed characteristic) and (separably) tame. I will describe three families of extensions and applications. The first is to discuss what is known around AKE principles for certain expansions of the language of valued fields, notably difference fields and differential fields. The second is the analysis of existential theories of henselian valued fields, in equal characteristic and to a lesser extent in mixed characteristic. The third is that we lay the ground for the “Taming Theorem” of Jahnke and Kartas, where they find AKE results for the first time that apply to certain valued fields that admit finite extensions with nontrivial defect.

Speaker: Dr Sylvy Anscombe (Université Paris Cité)