Talks and abstracts

  1. Bahareh Afshari
    • Reasoning About Time

    Temporal logic encompasses a family of logics equipped with unary and binary operators that express temporal properties such as ‘eventually’ and ‘always’. These logics play a central role in the theory of computation, where the succinct specification and tractable verification of state-based systems are essential for reliable and efficient system design. This course offers an introduction to temporal logic and the proof systems developed for reasoning about them. We demonstrate how formal proofs can be used to analyse fundamental computational properties, including decidability and interpolation. The second half of the course explores more advanced topics, including infinitary and cyclic proof systems.

  2. Manuel Bodirsky
    • Model-theoretic Challenges in Constraint Satisfaction

    Homogeneous structures and their reducts can be used to model many computational problems from finite model theory as constraint satisfaction problems (CSPs). In this talk I will give a survey on three open model-theoretic problems for such structures that are relevant for obtaining complexity classification results for the corresponding CSPs. In particular, I will discuss Thomas’ closed supergroup conjecture, a topological reconstruction conjecture, and the finite homogeneous Ramsey expansion conjecture.

    • Binary finitely homogeneous NIP structures, and taking model-complete cores

    Many important questions in model theory are open for finitely homogeneous structures, and often they even remain open if we additionally require that the structures are dependent (NIP). It might be possible to classify such structures explicitly, and such a classification might be useful to answer the open questions at least for these structures. In this tutorial I present the concept of model-complete cores, which I believe to be a useful tool (besides the concept of first-order interpretations) for such a classification task. Some results reported in the second talk are joint work with Bertalan Bodor and Paolo Marimon

  3. Juliette Kennedy
    • Gödel and the Entscheidungsproblem

    Formulated in its standard form in Hilbert and Ackermann’s 1928 text, the Entscheidingsproblem asks whether there is an algorithm for deciding validity for first order logic, i.e. if there is an algorithm which decides in a yes or no manner for any first order statement, whether it is valid or not. In this talk I will take up a question posed by Kripke in his 2013 paper, “The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem”: why didn’t Gödel publish a negative solution to the Entscheidungsproblem in 1931, given that it follows very naturally from theorem IX of Gödel’s 1931 paper on incompleteness? Given the fact that the Entscheidingsproblem was considered the major open problem in logic throughout the 1920s and 30s, Kripke’s question is a natural one to ask. Here I lay out a response to Kripke based on joint work with Walter Dean. After discussing the Entscheidingsproblem I will speak briefly about the machine metaphor, before turning to the continuation of this stream of thought around the Entscheidingsproblem in Gödel’s work going forward.

    • Set theory and first order logic

    In this talk I will point out the various ways in which set theory (in the form of the ZFC axioms) sheds light on the nature of first order logic. From some points of view, set theory underwrites the canonicity of first order logic; while from other points of view, set theory calls this very canonicity into question. We also take up the question whether set theory can be viewed in a natural way as a higher order logic.

  4. Corey Bacal Switzer
    • Uncountable Linear Orders and Dense Subsets of Polish Spaces 1

    A foundational theorem in logic is Cantor’s discovery that DLO is $\omega$ categorical or that every countable, dense linear without endpoints is isomorphic to the rationals with their standard ordering. A more topological phrasing of this result is that for each pair $A, B \subseteq \mathbb R$ which are countable and dense there is a linear order automorphism, and hence autohomeomorphism $h:\mathbb R \to \mathbb R$ so that $h``A = B$. Following Cantor, Brouwer proved this latter statement (for homeomorphisms) holds in fact for every finite dimensional Euclidean space $\mathbb R^n$ and even many locally compact, finite dimensional manifolds. A natural question is how to generalize these theorems to uncountable dense sets. In the context of linear suborders of the reals, the natural statement is denoted Baumgartner’s axiom or BA and was shown to be consistent (and independent) of the axioms of ZFC by Baumgartner in 1973. There are equally natural variations for various Polish spaces $X$ and many interesting questions (most of them open) about when a Baumgartner axiom for one space $X$ implies another for a space $Y$. For instance Steprans and Watson showed in 1987 that BA (\mathbb R^n) is consistent but does not imply BA for any $n >1$. It is open whether the reverse implication holds. In this talk we will introduce this topic including the above results and more and show how it naturally ties together set theory, real analysis, topology, order theory and model theory.

    • Uncountable Linear Orders and Dense Subsets of Polish Spaces 2

    In the second talk we continue to discuss Baumgartner’s axiom and its variants introduced in the first talk but focus more on applications of these statements including connections between BA and other set theoretic axioms. In particular we will look at the effect of BA and its relatives on the topology of the real line and cardinal characteristics of the continuum. Time permitting we will discuss some of the author’s recent work studying different models of set theory where BA and its relatives hold.

  5. Silvain Rideau-Kikuchi
    • Existentially closed fields with an automorphism and difference algebraic geometry

    In this talk, we will discuss the model theory of fields with automorphisms, in particular the existence of a model companion. We will also discuss the arithmetic flavour of this model companion: it is the asymptotic theory of algebraically closed fields in positive characteristic with the Frobenius automorphism, generalising a theorem of Ax on the model theory of finite fields. This follows from Hrushovski’s twisted Lang-Weil estimates. Time permitting we will discuss the finer model theoretic properties of this model companion: (super)simplicity, elimination of imaginaries…

    • Valued fields with an automorphism

    In this second talk we will explore the model theory of valued difference fields. Appearing in Hrushovski’s proof of the twisted Lang-Weil estimates, they went on to have a life of their own. We will first describe a class of (relatively) existentially closed difference valued fields in characteristic zero, as well as the recent breakthrough in positive characteristic by Dor and Hrurshovski. Finally we will discuss the question of the classification of imaginaries in valued difference fields.

  6. Tingxiang Zou
    • Pseudofinite counting dimension

    Pseudofinite structures are ultraproducts of finite structures. In such structures, one has access to a non-standard notion of counting cardinality. In this talk, I will discuss two dimensions on definable sets arising from this non-standard counting, namely the fine and coarse counting dimensions, introduced by Hrushovski. I will explain their basic properties, the associated independence relation, and their connections to other notions of dimension and independence arising in algebra and model theory more generally. Finally, I will discuss the Larsen–Pink inequality from the perspective of these counting dimensions.

    • The Elekes-Szabó Theorem

    The Elekes-Szabó Theorem can be stated informally as follows. Let $R \subseteq C^{3}$ be an algebraic surface defined over a field $K$ of characteristic $0$, where $C$ is an irreducible curve defined over $K$, such that any two coordinates are interalgebraic with the third (for example, the collinearity relation for three distinct points on a curve). Suppose that there exist arbitrarily large finite subsets $A \subseteq C(K)$ of size $n$ such that the intersection of $R$ with $A^3$ has size approximately $n^2$. Then $R$ is essentially the graph of the group operation of a one-dimensional algebraic group $G$.

    In this talk, I will explain how pseudofinite coarse dimension and model-theoretic techniques, for example, the group configuration theorem, together with combinatorial tools can be used to give a clean proof of the Elekes–Szabó theorem. I will also discuss higher-dimensional generalisations.

IMJ-PRG Université Paris Cité Sorbonne Université CNRS