One of the foundational results of voting theory is the Gibbard–Satterthwaite theorem: for finite societies, every function selecting a winner from a finite set of candidates that is immune to manipulation by the misrepresentation of preferences is either constant or dictatorial. In infinite societies, the Gibbard–Satterthwaite theorem can fail: Pazner and Wesley (1977) showed that when the set of voters is infinite, there exist social choice functions that are both non-manipulable ('strategyproof') and non-dictatorial. Their proof rests on the existence of non-principal ultrafilters, a consequence of the axiom of choice, and hence clearly has a nonconstructive aspect. In this talk I will examine the Pazner–Wesley possibility theorem in the context of reverse mathematics, and show that for countable societies it is equivalent over RCA0 to arithmetical comprehension. I will then formulate a seemingly weaker version of the Pazner–Wesley possibility theorem, using individual strategyproofness rather than coalitional strategyproofness, and raise some open questions regarding the relationship between these two statements.
The Ramsey theorem was the first example of a natural result escaping the Big Five phenomenon, which had so far identified every result to have equivalent strength to one of five classical axiomatic bases. It has since then been thoroughly studied, and we present a form of generalization of said theorem, as "Ramsey like" theorems. A Ramsey like theorem is of the form: "For every k-coloring of n-tuples of integers, there exists an infinite set avoiding a set of finite patterns P". Depending on the properties of the patterns in P, these results have vastly different strengths. In particular, we will use the notions of preservation of hyperimmunity (or hyperimmunities) and 2-dimensional hyperimmunity as strength quantifiers, and find necessary and sufficient conditions for the patterns in P for each to hold. We also study Ramsey-like theorems that don't ask to avoid every pattern in P, but at least one. We also see colorings as graphs and prove the existence of a computable infinite graph of which every computable subgraph contains every possible finite subgraph.
Many model-theoretic dividing lines, such as NIP, stability, and distality, are naturally defined in terms of binary formulas. One can nonetheless study higher-arity formulas under an NIP/stability/distality assumption, but this often turns out to be too strong. This has led to the development of higher-arity NIP, stability, and distality (which are strict weakenings of the binary versions). Of these, higher-arity distality has received the least treatment, and much more work remains before the theory can be applied. In particular, the theory of strong honest definitions for higher-arity distality is relatively undeveloped. I will survey what is known in the literature and discuss my ongoing work.
NOTES: unusual room.
In the last 20 years there has been a resurgence of interest in fixed points in both mathematical and computational logic. At the interface of both these traditions is the extension of type theories with (co)induction. Similar theories now underlie popular proof assistants such as Coq and Lean. However, until recently, little was known about the expressivity of theories with fixed points: what can they prove? what can they compute? In this talk I will talk about a recent line of work that classifies the expressivity of type theories with fixed points. This talk is based on joint work with Gianluca Curzi.
The representation type of a finite-dimensional k-algebra is an algebraic measure of how hard it is to classify its finite-dimensional indecomposable modules.
Intuitively, a finite-dimensional k-algebra is of tame representation type if we can classify its finite-dimensional modules and wild representation type if its module category contains a copy of the category of finite-dimensional modules of all other finite-dimensional k-algebras. An archetypical (although not finite-dimensional) tame algebra is k[x]. The structure theorem for finitely generated modules over a PID describes its finite-dimensional modules. Drozd’s famous dichotomy theorem states that all finite-dimensional algebras are either wild or tame.
The tame/wild dividing line is not seen by standard model theoretic invariants or even the more specialised invariants coming from Model Theory of Modules. A long-standing conjecture of Mike Prest claims that a finite-dimensional algebra has decidable theory of modules if and only if it is of tame representation type. More recently, I conjectured that a finite-dimensional algebra has decidable theory of (pseudo)finite dimensional modules if and only if it is of tame representation type. This talk will focus on recent work providing evidence for the second conjecture.
Partial combinatory algebras (pcas) are abstract models of computation. They are one of the earliest type of model that emerged in the 1930's when mathematicians were trying to define what it means to be computable. Notions such as recursive functions (used by Gödel in the proof of his incompleteness theorems), Turing machines, combinatory algebra and lambda calculus each turned out to be useful in the development of the theory of computation in their own way. Pcas are also used in the study of constructive mathematics. They play a key role in the connections between constructive mathematics, proof theory, and computability, and also serve as a basis for models of constructive mathematics.
In this talk we will give a quick review of the basics of combinatory algebra, and discuss some of the key examples, such as Kleene's models $\mathcal{K}_1$ (which describes the classical setting for computation on the natural numbers), $\mathcal{K}_2$ (which does the same for the real numbers), and Scott's graph model. We then discuss recent results about embeddings and completions of pcas, and in particular the complexity of various embeddings. Depending on time, we will also discus the complexity of the isomorphism problem, extensionality, and ordinal analysis of pcas.
Having outlined the problems, this seminar will be devoted to describing the tools which have been developed to help us solve them. First and foremost of these is the Ax-Schanuel theorem, the functional equivalent of Schanuel's conjecture. We will give a proof, and then discuss how this is applied to prove weak Zilber-Pink, another highly useful result. Given time, we will also explain how it was used by Bays-Kirby to remove Schanuel's conjecture from the list of requirements necessary for Zilber's Quasi-minimality conjecture.
Everyone loves a good decomposition. How can we break down a mathematical object — a graph, a group, or a function — efficiently into well-behaved (or regular) parts? And what conditions can we place on these objects to guarantee a higher degree of regularity, such as homogeneity? It turns out an excellent source of such conditions is model-theoretic dividing lines, that is, tameness properties of (first-order) structures. This is not a coincidence. In this talk, I will dive into the deep theory of these dividing lines in search of the source of homogeneity.
A graph has a countable chromatic number if the vertices can be labeled by natural numbers so that no edge has the same label on both ends. Verifying this property for a given graph can be somewhat difficult; consider e.g. the graph of points in the Euclidean space $ℝ^n$ connected with an edge iff their distance is a rational number. The countable chromatic number of this graph is an easy observation for $n=1$, but a nontrivial result for $n>1$ (Komjath, Schmerl). I will introduce an infinite determined game which provides a simple criterion for a definable (analytic on a Polish space) graph to be countably chromatic; it is sufficient to verify that the second player has a winning strategy. Using this criterion we can e.g. easily resolve the example of $ℝ^n$, as well as deduce interesting consequences on the structure of uncountably chromatic definable graphs.
The talk is based on the paper Chodounský, Zapletal: Two graph games (2024).
Given a topology on the natural numbers, how complicated is it to describe? To answer this question with tools from computability theory, we will restrict to the context of countable second-countable (CSC) topological spaces. One approach is to assign an index to each computable CSC space and determine the arithmetic complexity of the set of CSC spaces with some property. Another approach comes from computable structure theory; for example, given two computable copies of a CSC space, does there exist a computable homeomorphism between them? In this talk, we will explore these approaches and apply them in three running examples: the indiscrete, discrete, and initial segment topologies.
