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.
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 19
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.
Title: Hilbert polynomials for finitary matroids
Eventual polynomial growth is a common theme in combinatorics and commutative algebra. The quintessential example of this phenomenon is the Hilbert polynomial, which eventually coincides with the linear dimension of the graded pieces of a finitely generated module over a polynomial ring. A later result of Kolchin shows that the transcendence degree of certain field extensions of a differential field is eventually polynomial. More recently, Khovanskii showed that for finite subsets $A$ and $B$ of a commutative semigroup, the size of the sumset $A+tB$ is eventually polynomial in $t$. I will present a common generalization of these three results in terms of finitary matroids (also called pregeometries). I’ll discuss other instances of eventual polynomial growth (like the Betti numbers of a simplicial complex) as well as some applications to bounding model-theoretic ranks. This is joint work with Antongiulio Fornasiero.
Location: Social Sciences SR (14.33)
Title: Generalised measurability and bilinear forms
NOTE location change: Social Sciences SR (14.33)
In this talk I will go over measurable and generalised measurable structures, giving examples and non-examples. I will then go on to consider the two sorted structure $(V,F,β)$ where $V$ is an infinite dimensional vector space over $F$ an infinite field, and $β$ a bilinear form on this vector space. In particular I will consider the interaction of different notions of independence when this structure is pseudo finite. I will finish with some questions around generalised measurable structures.
Title: Ordinal arithmetic and subgroups of Thompson's group
The class of finitely generated groups embeddable into Richard Thompson's group $F$ is both restrictive and rich at the same time. We show that there is a family of groups within this class which is pre-well-ordered in type $\epsilon_0$ by the embeddability relation. Moreover, the operations of addition and multiplication on the ordinals translate into natural group-theoretic operations—direct sum and a type of permutational wreath product. This talk will give a description of this correspondence. This is joint work with Collin Bleak and Matt Brin.
Title: Weihrauch degrees above arithmetical transfinite recursion
The studies of Weihrauch degrees and reverse mathematics share many ideas, and many similar results and close relations are known. The studies of Weihrauch degrees of the arithmetical transfinite recursion (ATR) and their relation to reverse mathematics are developed, e.g., in [1,2,3]. Typically, principles which are provable from $ATR_0$ (in the setting of reverse mathematics) by way of the pseudo-hierarchy method have various strengths. In this talk, we overview these situations and study the structure between ATR and the choice principle on the Baire space. This is joint work with Yudai Suzuki.
T. Kihara, A. Marcone and A. Pauly. Searching for an analogue of $ATR_0$ in the Weihrauch lattice. J. Symb. Log., 85(3):1006–1043, 2020.
Jun Le Goh. Some computability-theoretic reductions between principles around ATR0. arXiv preprint arXiv:1905.06868, 2019.
Paul-Elliot Anglès d'Auriac. Infinite Computations in Algorithmic Randomness and Reverse Mathematics. PhD thesis, Université Paris-Est, 2019.
Y. Suzuki and K. Yokoyama. Searching problems above arithmetical transfinite recursion. In preparation.
Title: Formalising Erdős and Larson: Ordinal Partition Theory
NOTE date and time change: Tue 11am
A number of results in infinitary combinatorics have been formalised in the proof assistant Isabelle/HOL. These include results on ordinal partition relations by Erdős–Milner, Specker, Larson and Nash-Williams, leading to Larson’s 1973 proof that for all $m$ in $ℕ$, $ω^ω → (ω^ω,m)$. This material is available online; here we discuss some of the most challenging aspects of the formalisation process, and wider issues in the formalisation of research-grade mathematics. See also the paper in Experimental Mathematics 31:2, 2022.
Title: To be announced
Title: Completeness: Turing, Schütte, Feferman
Title: Definable refinements of classical algebraic invariants
In this talk I will explain how methods from logic allow one to construct refinements of classical algebraic invariants that are endowed with additional topological and descriptive set-theoretic information. This approach brings to fruition initial insights due to Eilenberg, Mac Lane, and Moore (among others) with the additional ingredient of recent advanced tools from logic. I will then present applications of this viewpoint to invariants from a number of areas in mathematics, including operator algebras, group theory, algebraic topology, and homological algebra.