Skip to main content

Home

The Leeds Logic group

Mathematical logic, a young subject, has developed over the last 30 years into an amalgam of fast-moving disciplines, each with its own sophisticated techniques. These are linked by profound common concerns, around definability, decidability, effectiveness and computability, the nature of the continuum, and foundations. Some branches are highly multidisciplinary and force the researcher to be fully conversant with other fields (e.g. algebra, computer science).

The Logic Group at the University of Leeds is one of the largest and most active worldwide, with a long uninterrupted tradition dating back to 1951, when its founder Martin Löb moved to Leeds. It has an international reputation for research in most of the main areas of mathematical logic - computability theory, model theory, set theory, proof theory, and in applications to algebra, analysis, number theory and theoretical computer science.

More details about the current grants, PhD students, and research interests are on our Research page.

Upcoming events

Andrew Brooke-Taylor (University of Leeds)

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.

Dan Marsden (University of Nottingham)

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.

Aris Papadopoulos (University of Leeds)

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.

View all Events