The classification of the countable homogeneous bipartite graphs is rather straightforward; they are empty or complete, perfect matching or its complement, and generic. Chernikov and Kruckmann asked what happens if a linear order is imposed on the structure. This is relevant (and required) in structural Ramsey theory: the Nesetril-Rodl Theorem requires the universe of the structure to be linearly ordered. I present a solution to this, which while not so very complicated, does require some tricks, and a rather longer list of structures. One would really like to address the same question for multipartite graphs. I shall briefly recall the classification of the countable homogeneous multipartite graphs (with a fixed finite number of parts), in joint work with Jenkinson and Seidel. The extension to linearly ordered multipartite graphs would require further work.
Location: MALL
Title: Baumgartner's Axiom and its Higher Dimensional Versions
Note: the speaker will be joining us online.
A set of reals $A \subseteq \mathbb{R}$ is called $\aleph_1$-dense if its intersection with every nonempty open interval has size $\aleph_1$. Baumgartner's axiom (BA) is the statement that every pair of $\aleph_1$-dense set of reals are isomorphic as linear orders. BA is the most straightforward generalization of Cantor's theorem about countable dense linear orders to the uncountable. This axiom, proved consistent by Baumgartner in 1973, while seemingly innocuous is actually both very finnicky and also seems to induce a lot of structure on the reals. For instance (on the finnicky side) it is implied by PFA, but not MA, even in the presence of strong reflection principles. On the '"induces a lot of structure" side, it implies the bounding number is greater than $\aleph_1$ (Todorčević). BA also has a natural generalization to higher dimensions i.e. $\mathbb{R}^n$ for $n > 1$ and these versions do follow from MA and in fact weaker cardinal characteristic assumptions (Steprāns-Watson). In this talk we will discuss these issues and show that the higher dimensional versions however also induce a lot of structure on the reals, in particular for every natural number $n$ BA for $\mathbb{R}^n$ implies the bounding number is bigger than $\aleph_1$.
Location: MALL
Title: Peano arithmetic, games, and descent recursion
I will discuss a game semantics for classical (first-order) arithmetic due to Coquand. The real content of this semantics is a proof of cut elimination for infinitary propositional logic. As the title suggests, I will say something about descent recursive functions and how it all comes together.
A dynamical ideal is a group action on a set together with an ideal on the set which is invariant under the action. There is a permutation choiceless model of ZFA associated with each dynamical ideal. I will isolate several natural properties of dynamical ideals which translate into fragments of the Axiom of Choice in the permutation model. Verification of these properties leads to interesting problems in model theory, topology, and other fields, depending on the group action considered.
Location: MALL
Title: Natural Deduction Proof for Substructural, Constructive and Classical Logics
Since the 1990s, we have seen how to understand a very wide range of logical systems (classical logic, intuitionistic logic, dual intuitionistic logic, relevant logics, linear logic, the Lambek calculus, affine logic, orthologic and more) by way of the distinction between operational and structural rules. We can have one set of rules for a connective (say, conjunction, negation, or the conditional) in a sequent calculus, and get different logical behaviour depending on the shape of the sequents allowed and the structural rules governing those sequents.
In this talk, I will consider the relationship between the “big four” traditional substructural logics—intuitionistic, relevant, affine and linear—corresponding to the four options for including or excluding the structural rules of weakening and contraction, in the setting of Gentzen/Prawitz-style natural deduction proofs for implication and the simply typed λ calculus. Such a natural deduction setting—in which proofs have any number of premises and a single conclusion—has a natural bias toward constructive, or intuitionistic logic.
I will show how the choice of whether to “go classical”, expanding the structural context to allow for more than one formula in positive position is orthogonal to the choice of the other structural rules, so that even in the context of natural deduction proofs, the familiar pair of traditional implication introduction and elimination rules gives rise to eight different propositional logics, four of which are “classical” and four of which are “constructive”. Furthermore, the familiar double-negation translation of classical logic inside intuitionistic logic generalises to the other three classical/constructive pairings.
I will explain these results, and, if there is time, I will end the talk with some reflections on what this might mean for the relationship between classical and constructive reasoning.
Location: MALL
Title: Parametrizations in valued fields
In the o-minimal setting, parametrizations of definable sets form a key component of the Pila-Wilkie counting theorem. A similar strategy based on parametrizations was developed by Cluckers-Comte-Loeser and Cluckers-Forey-Loeser to prove an analogue of the Pila-Wilkie theorem for subanalytic sets in $p$-adic fields. In ongoing work with R. Cluckers, P. Cubides-K. and I. Halupczok, we prove the existence of parametrizations for arbitrary definable sets in Hensel minimal fields, leading to a counting theorem in this general context.
Location: Roger Stevens LT 04 (8.04)
Title: "Categorifying" Borel reducibility
NOTE: this is a 2-hour seminar for both model and set theorists.
Please make note of the unusual venue!
Borel reducibility is a framework for comparing the complexities of different equivalence relations, and it has been used to great effect showing that various old classification programmes were impossible tasks. However, these days classification maps are generally expected to be functorial, which the classical Borel reducibility framework takes no account of. After going through preliminaries of the classical set-up, I will present a natural framework of Borel categories and functorial Borel reducibility that remedies this oversight. Notably, many examples of classes of structures that were known to be universal in a Borel reducibility sense - Borel complete - are not universal for our functorial version. I'll give many examples, including new ones for the old hands who've seen me talk about this stuff before. This is joint work with Filippo Calderoni.
Location: Roger Stevens LT 13 (10.13)
Title: Games, Comonads and Compositionality
NOTE location change: Roger Stevens LT 13 (10.13)
Recent work of Abramsky, Dawar and Wang, and subsequently Abramsky and Shah, provided a categorical abstraction of model comparison games such as the Ehrenfeucht-Fraïssé, pebble and bisimulation games, in the form of so-called game comonads. This work opened up new connections between disciplines associated with computational power and complexity such as finite model theory and combinatorics, and areas traditionally focussed upon the structural understanding of computation and logic, such as program semantics.
This talk will introduce the comonadic perspective upon model comparison games. I shall then describe more recent work, jointly with Tomáš Jakl and Nihil Shah, giving a categorical account of Feferman-Vaught-Mostowski type theorems with this categorical framework.
The talk will aim to be reasonably self-contained, assuming only a basic background in logic, and some understanding of the categorical notions of category, functor and natural transformation.
Location: MALL
Title: Zarankiewicz’s Problem and Model Theory
NOTE: this is a 2-hour seminar for both model and set theorists.
A shower thought that anyone interested in graph theory must have had at some point in their lives is the following: `How “sparse" must a given graph be, if I know that it has no “dense” subgraphs?’. This curiosity definitely crossed the mind of Polish mathematician K. Zarankiewicz, who asked a version of this question formally in 1951. In the years that followed, many central figures in the development of extremal combinatorics contemplated this problem, giving various kinds of answers. Some of these will be surveyed in the first part of my talk.
So far so good, but this is a model (and set) theory seminar and the title does include the words “Model Theory"… In the second part of my talk, I will discuss how the celebrated Szemerédi-Trotter theorem gave a starting point to the study of Zarankiewicz’s problem in “geometric” contexts, and how the language of model theory has been able to capture exactly what these contexts are. I will then ramble about improvements to the classical answers to Zarankiewicz’s problem when we restrict our attention to one of: (a) semilinear/semibounded o-minimal structures; (b) Presburger arithmetic, and (c) various kinds of Hrushovski constructions. The second hour of the talk will essentially be devoted to proofs. Which of (a),(b), or (c) will occupy the second hour will depend on input from the audience.
The new results appearing in the talk were obtained jointly with Pantelis Eleftheriou.
