Skip to main content

Logic Seminar

The main logic seminar in Leeds.

Time and place: MALL 1 & Zoom, Wednesday 15.45 - 17.00.

Current organiser: Andrew Brooke-Taylor.

Search results for “”

Results 1 to 10 of 27

Zach McKenzie (University of Chester)

Date
, 4.00 PM
Category

Location: MALL
Title: Well-founded models of fragments of Collection

Let $\mathsf{M}$ be the weak set theory (with powersets) axiomatised by: $\textsf{Extensionality}$, $\textsf{Pair}$, $\textsf{Union}$, $\textsf{Infinity}$, $\textsf{Powerset}$, transitive containment ($\textsf{TCo}$), $\Delta_0\textsf{-Separation}$ and $\textsf{Set-Foundation}$. In this talk I will discuss the relationship between two alternative versions of the set-theoretic collection scheme: $\textsf{Collection}$ and $\textsf{Strong Collection}$. Both of these schemes yield $\mathsf{ZF}$ when added to $\mathsf{M}$, but when restricted the $\Pi_n$-formulae (denoted $\Pi_n\textsf{-Collection}$ and $\textsf{Strong } \Pi_n\textsf{-Collection}$) these alternative versions of set-theoretic collection differ. In particular, over the theory $\mathsf{M}$, $\textsf{Strong }\Pi_n\textsf{-Collecton}$ is equivalent to $\Pi_n\textsf{-Collection}+\Sigma_{n+1}\textsf{-Separation}$. And, $\mathsf{M}+\textsf{Strong }\Pi_n\textsf{-Collection}$ proves the consistency of $\mathsf{M}+\Pi_n\textsf{-Collection}$. In this talk I will show that, despite this difference in consistency strength, every countable well-founded model of $\mathsf{M}+\Pi_n\textsf{-Collection}$ satisfies $\textsf{Strong } \Pi_n\textsf{-Collection}$. If time permits I will outline how this argument can be refined to show that $\mathsf{M}+\Pi_n\textsf{-Collection}+\Pi_{n+1}\textsf{-Foundation}$ proves $\Sigma_{n+1}\textsf{-Separation}$.

Artem Chernikov (University of Maryland)

Date
, 4.00 PM
Category

Location: MALL
Title: Convolution semigroup on Keisler measures and revised Newelski's conjecture

We study the structure of the convolution semigroups of measures over definable groups. We isolate the property of generic transitivity and demonstrate that it is sufficient (and necessary) to develop stable group theory localizing on a generically stable type. We establish generic transitivity of generically stable idempotent types in important new cases, including abelian groups in arbitrary theories and arbitrary groups in rosy theories, and characterize them as generics of connected type-definable subgroups. Using tools from Keisler's randomization theory, we generalize some of these results from types to generically stable Keisler measures, and classify idempotent generically stable measures in abelian groups as (unique) translation-invariant measures on type-definable fsg subgroups. This provides a partial definable counterpart to the classical work of Rudin, Cohen and Pym for locally compact topological groups. Working over a countable NIP structure, we provide an explicit construction of a minimal left ideal in the convolution semigroup of measures from a minimal left ideal of types and the unique Haar measure on the ideal group. As a key ingredient, we prove the revised Ellis group conjecture of Newelski saying that under NIP, the so-called tau-topology on the ideal group is Hausdorff.

Joint work with Kyle Gannon and Krzysztof Krupiński.

Dianthe Basak (Paris)

Date
, 4.00 PM
Category

Location: MALL 1
Title: Continuous Actions of Monoids, a New Perspective on Large Cardinals

The standard "symmetric models" approach to building models of the failure of the axiom of choice relies on the action of non-discrete topological groups on a universe of sets (either sets-with-atoms or a boolean valued model of names). A new approach interprets large cardinal axioms as positing the action of non-discrete topological monoids on the universe of sets (a model of names, a model with atoms, or even $V$ itself). By understanding such actions, one can reinterpret (and reprove) the Kunen inconsistency theorem as a symmetric model theorem, as well as interpreting a version of the HOD conjecture in a natural way. The talk will attempt to place such techniques in their natural context and highlight some applications.

Jindrich Zapletal (University of Florida)

Date
, 4.00 PM
Category

Location: MALL
Title: Fraenkel-Mostowski models revisited

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.

Greg Restall (University of St Andrews)

Date
, 4.00 PM
Category

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.

Emanuele Frittaion (University of Leeds)

Date
, 4.00 PM
Category

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.

Dan Marsden (University of Nottingham)

Date
, 4.00 PM
Category

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.

Dugald Macpherson (Leeds)

Date
, 4.00 PM
Category

Location: MALL
Title: Definable groups in valued fields

I will discuss joint work with Gismatullin and Halupczok, giving the structure of definably (almost) simple groups definable in Henselian valued fields, possibly equipped with extra structure. I will also describe some other work on definable groups in valued fields.

Yong Cheng (Wuhan University)

Date
, 4.00 PM
Category

Location: MALL
Title: The limit of Gödel's first incompleteness theorem
NOTE date and time change: Fri 4pm

In this talk, we discuss the limit of the first incompleteness theorem (G1). It is well known G1 can be extended to both extensions and weak sub-systems of PA. We examine the question: are there minimal theories for which G1 holds. The answer of this question depends on how we define the notion of minimality. We discuss different answers of this question based on varied notions of minimality.

The notion of interpretation provides us a general method to compare different theories in distinct languages. We examine the question: are there minimal theories for which G1 holds with respect to interpretability. It is known that G1 holds for essentially undecidable theories, and there are no minimal essentially undecidable theories with respect to interpretability. G1 holds for effectively inseparable (EI) theories and the notion of effective inseparability is much stronger than essential undecidability. A natural question is: are there minimal EI theories with respect to interpretability? We negatively answer this question and prove that there are no minimal effectively inseparable theories with respect to interpretability: for any EI theory T, we can effectively find a theory which is EI and strictly weaker than T with respect to interpretability. Moreover, we prove that there are no minimal finitely axiomatizable EI theories with respect to interpretability.

Finally, we give a summary of the similarities and differences between logical incompleteness and mathematical incompleteness based on technical evidences and philosophical reflections.

Margaret Thomas (Purdue University)

Date
, 4.00 PM
Category

Location: Roger Stevens LT23 (8.23)
Title: Effective Pila–Wilkie bounds for Pfaffian sets with some diophantine applications
NOTE location change: Roger Stevens LT23 (8.23)

Following critical insights of Pila and Zannier, there are by now many applications of model theory to diophantine geometry arising from the celebrated counting theorem of Pila and Wilkie and its variants. The original Pila–Wilkie Theorem bounds the number of rational points of bounded numerator and denominator lying on (the transcendental parts of) sets definable in o-minimal expansions of the real field. However, the proof of this theorem (and that of its variants) does not provide an effective bound, which limits the precision of its applications. I will discuss some joint work with Gal Binyamini, Gareth O. Jones and Harry Schmidt in which we obtained effective forms of the Pila–Wilkie Theorem and its variants for sets definable in various structures described by Pfaffian functions (including an effective Yomdin–Gromov parameterization result for sets defined using restricted Pfaffian functions), and then used these effective estimates to derive several effective diophantine applications, including an effective, uniform Manin–Mumford statement for products of elliptic curves with complex multiplication.