Tag - Logic

Calum Hughes: An elementary theory of the 2-category of small categories

5th June, 2024

Lawvere’s Elementary Theory of the Category of Sets (ETCS) posits that the category Set is a well-pointed elementary topos with natural numbers object satisfying the axiom of choice. This provides a category theoretic foundation for mathematics which axiomatises the properties of function composition in contrast to Zermelo-Fraenkel set theory with the axiom of choice (ZFC), which axiomatises sets and their membership relation. Furthermore, ETCS augmented with the axiom schema of replacement can be shown to be equiconsistent with ZFC.

In this talk, I will present a categorification of ETCS which axiomatises the 2-category of small categories, functors and natural transformations; this is the elementary theory of the 2-category of small categories (ET2CSC) of the title. This extends Bourke’s characterisation of categories internal to a category E with pullbacks to the setting where E satisfies the extra properties of ETCS. Important 2-categorical definitions I will introduce are 2-well-pointedness, the full subobject classifier and the categorified axiom of choice. The main conclusion is that ET2CSC is 'Morita biequivalent’ with ETCS, meaning that the two theories have biequivalent 2-categories of models.

I will also describe how Shulman and Weber’s ideas on discrete opfibration classifiers can be used to incorporate replacement, in a way reminiscent of algebraic set theory.

Carles Casacuberta: Homotopy reflectivity is equivalent to the weak Vopenka principle

21st March, 2024

We discuss reflectivity of colocalizing subcategories of triangulated categories under suitable set-theoretical assumptions. In earlier joint work with Gutierrez and Rosicky, we proved that if K is any locally presentable category with a stable model category structure, then Vopenka's principle implies that every full subcategory L of the homotopy category of K closed under products and fibres is reflective. Moreover, if L is colocalizing, then the reflection is exact. Using recent progress in large-cardinal theory, we show that the statement that every full subcategory closed under products and fibres is reflective is, in fact, equivalent to the so-called weak Vopenka principle. Hence this statement cannot be proved using only the ZFC axioms.

Artem Chernikov: Recognizing groups in Erdős geometry and model theory

15th March, 2024

Erdős-style geometry is concerned with difficult questions about simple geometric objects, such as counting incidences between finite sets of points, lines, etc. These questions can be viewed as asking for the possible number of intersections of a given algebraic variety with large finite grids of points. An influential theorem of Elekes and Szabó indicates that such intersections have maximal size only for varieties that are closely connected to algebraic groups. Techniques from model theory - variants of Hrushovski’s group configuration and of Zilber’s trichotomy principle - are very useful in recognizing these groups, and led to far reaching generalizations of Elekes-Szabó in the last decade. I will overview some of the recent developments in this area, in particular explaining how all of this is not just about polynomials and works for definable sets in o-minimal structures.

Laura Ciobanu: Group equations, constraints and decidability

8th March, 2024

In this talk I will discuss group equations with non-rational constraints, a topic inspired by the long line of work on word equations with length constraints. Deciding algorithmically whether a word equation has solutions satisfying linear length constraints is a major open question, with deep theoretical and practical implications. I will introduce equations in groups and several kinds of constraints, and show that equations with length, abelian or context-free constraints are decidable in virtually abelian groups (joint with Alex Evetts and Alex Levine). This contrasts the fact that solving equations with abelian constraints is undecidable for non-abelian right-angled Artin groups and hyperbolic groups with ‘large’ abelianisation (joint work with Albert Garreta).

Andrei Yafaev: o-minimality and Diophantine geometry

4th December, 2023

In the recent years there have been some spectacular applications of the theory of o-minimality (a branch of Model Theory) to some problems in Diophantine Geometry. It culminated in the unconditional proof of the Andre-Oort conjecture on the Zariski closure of sets of special points on Shimura varieties. We will present ideas and methods surrounding this proof.

Andrey Nikolaev: Non-standard polynomials and non-standard free group

20th October, 2023

Interpretation and bi-interpretation offer a novel approach to studying all structures elementarily equivalent to a given one. We use this approach to describe and study non-standard models of the ring of polynomials, Laurent polynomials, and the group ring of a free group.

In the presence of interpretation but not bi-interpretation, this approach produces a family of structures elementarily equivalent to a given one. We exploit this to introduce non-standard models of a free group. As time permits, we discuss their main properties.

Mika Göös: Top-Down Lower Bounds for Depth-Four Circuits

24th July, 2023

We present a top-down lower-bound method for depth-4 boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-4 circuits of size exponential in n1/3. Our proof is an application of robust sunflowers and block unpredictability.

Yufei Zhao: Nearly all k-SAT Functions are Unate

24th July, 2023

We prove that 1-o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.

Jan Trlifaj: Deconstructible classes, approximations, and AECs of modules

4th July, 2023

Deconstructible classes of modules are among the main sources of approximations in relative homological algebra. They also occur in connection with abstract elementary classes (AECs). The latter were introduced by Shelah as far-reaching generalizations of classic first-order structures. A direct connection is provided by the 'AECs of roots of Ext': these are the AECs of the form P = (𝒜,≼) where 𝒜 = { M in Mod-R such that ExtiR(M,N) = 0 for all i > 0 and all N in 𝒞 } for a class of modules 𝒞, and ≼ is a partial order on 𝒜 satisfying X ≼ Y iff Y/X is in 𝒜. P is an AEC iff 𝒜 is a deconstructible class closed under arbitrary direct limits. A major open problem concerning AECs is Shelah's Categoricity Conjecture (SCC). It claims that categoricity of an AEC is a large enough cardinal λ (= existence of a unique structure in 𝒜 of cardinality λ up to isomorphism) is equivalent to its categoricity in a tail of cardinals. After recalling the role of deconstructible classes of modules, we will prove SCC for the AECs of roots of Ext, and more in general, for all 'deconstructible' AECs (𝒟,≤), i.e., such that 𝒟 is a deconstructible class of modules. We will also consider the open problem of whether for all deconstructible AECs, the class 𝒟 is necessarily closed under direct limits. We will show that it is consistent with ZFC that 𝒟 is closed under countable direct limits provided that 𝒟 is closed under direct summands and ≤ refines direct summands.

Joel David Hamkins: Infinite Games – Strategies, Logic, Theory, and Computation

16th June, 2023

Many familiar finite games admit natural infinitary analogues, which may captivate and challenge us with sublime complexity. Shall we have a game of infinite chess? Or how about infinite draughts, infinite Hex, infinite Wordle, or infinite Sudoku? In the Chocolatier’s game, the Chocolatier serves up an infinite stream of delicious morsels, while the Glutton aims to eat every one. These games and others illustrate the often subtle strategic aspects of infinite games, and sometimes their downright logical peculiarity. Does every infinite game admit of a winning strategy? Must optimal play be in principle computable? Let us discover the fascinating nature of infinitary strategic thinking.