# Logic

## Our research

Our members and their current research interests include:

### Dr Isolde Adler (School of Computing)

Both Graph Theory and Logic in Computer Science form the basis of her research interests. She is fascinated by the interplay between the combinatorial structure of graphs and discrete models on the one hand, and their algorithmic properties on the other hand. Furthermore, she likes the challenge of problems that are computationally hard but nevertheless have to be solved in practice. While based in Theory, she also enjoys bridging the gap to practical applications in different fields. Her research revolves around the structure of graphs and hypergraphs, logic and model theory, algorithms and (parameterised) complexity, algorithmic meta-theorems, database theory, model checking, combinatorial games, property testing.

### Dr Andrew Brooke-Taylor

Works in set theory, with an emphasis on applications to category theory, algebraic topology and other related areas. He is particularly interested in large cardinal axioms and forcing, with ongoing research interests in cardinal characteristics at large cardinals, connections between Borel reducibility and universal categories, relative consistency results around the level of Vopenka’s Principle, and applications of large cardinals in the theory of accessible categories.

### Dr Nicola Gambino

Works in categorical logic, type theory and constructive set theory. His current research focuses on Homotopy Type Theory (especially semantics and connections to homotopical algebra and higher-dimensional category theory) and on the 2-categorical calculus of operads and analytic functors, with a view towards models of linear logic and the differential λ-calculus. His research in constructive set theory revolves around the definition and application of sheaf models (which are counterparts of forcing) either directly or via algebraic set theory.

### Professor Dugald Macpherson

Works in model theory and its connections to algebra and combinatorics. Particular areas of current interest are: permutation groups (usually infinite), typically automorphism groups of countable first order structures; model theory of groups; model theory of families of finite structures (e.g. finite fields, finite simple groups, classes of finite graphs) and their infinite limits; model theory of fields (e.g. valued fields); abstract model theory around stability theory and its generalisations, and connections to combinatorics.

### Dr Vincenzo Mantova

Interests are around the model theory of exponentiation and of other analytic functions. His main focus is on taming complex exponentiation and other exponential functions on complex Lie groups, along the strategy set up by Zilber, and fast growing real functions, via surreal numbers and transseries. He also has an interest in Diophantine geometry, especially in connection with the aforementioned problems.

### Professor Michael Rathjen

Main interests are in proof theory (cut elimination for infinitary proof systems; ordinal analysis of classical and intuitionistic theories; witness extraction from proofs), intuitionism and constructive mathematics (frameworks for constructivism: constructive set theory, explicit mathematics, Martin-Löf type theory; realizability and forcing techniques), mostly non-classical set theory (proof theory and ordinal analysis of set theories; admissible set theory; constructive and intuitionistic set theory; set theory with anti-foundation axiom; 'large cardinals' axioms in constructive and intuitionistic set theories), reverse mathematics and combinatorial principles (Kruskal's Theorem, Graph Minor Theorem, …), philosophy of mathematics.

### Dr Paul Shafer

Works in computability theory, with an eye to describing the complexities of mathematical problems. He is particularly interested in reverse mathematics and in the Medvedev and Muchnik degrees. Reverse mathematics is an analysis of the logical strengths of mathematical theorems in the context of second-order arithmetic. Here Paul studies theorems from algebra, analysis, combinatorics, logic itself, and topology. The Medvedev and Muchnik degrees are higher-order analogues of the Turing degrees designed to model the “problem A is computationally harder than problem B” relation. Here Paul studies the algebraic properties of these degree structures, their complexities, and their uses as computational semantics for various logics.

### Professor John K Truss

Main interests are axiomatic set theory, specifically questions about the axiom of choice, infinite permutation groups, and their connections with model theory. Three recent pieces of work concern automatic homeomorphicity, Ehrenfeucht-Fraïssé games between linearly ordered sets, and constructions of rigid chains. A structure is said to have automatic homeomorphicity if any isomorphism from its endomorphism monoid to the full transformation monoid of a countable set is necessarily also a homeomorphism. This has been verified for monoids derived from the rationals and its reducts, and also associated clones. Ehrenfeucht-Fraïssé games between two structures provide a good way of analysing how similar the two structures are. This has been done for various classes of linear orders, sometimes with colours. A classical construction of Dushnik and Miller of a rigid dense subchain of the ordered set of real numbers, where ‘rigid’ means that there are no non- trivial automorphisms, has been generalized to give results also about rigidity for embeddings and epimorphisms. This is also extended to higher cardinalities.