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.
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.
NOTES: the speaker will be online.
I will give a talk on several recent results regarding ultrahomogeneous graphs. A relational structure R is ultrahomogeneous if every isomorphism of finite induced substructures of R extends to an automorphism of R. We classify the finite vertex-colored oriented ultrahomogeneous graphs and the finite vertex-colored undirected graphs. The classifications comprise new general methods which govern how graphs can be combined or extended to create new ultrahomogeneous graphs. Further, we extend a classic theorem of Cameron (every 5-tuple regular graph is already ultrahomogeneous) to the setting of colored graphs.
This is joint work with Sofia Brenner, Eda Kaja, Thomas Schneider, and Pascal Schweitzer.
Fix a sequence of countable structures $\mathcal{M}_n$, for $n$ in $ℕ$, in a given first-order language $\mathcal{L}$. The reduced product of $(\mathcal{M}_n)$, denoted $\prod_n\mathcal{M}_n/\mathrm{Fin}$ is the $\mathcal{L}$-structure obtained by quotienting the product of the $\mathcal{M}_n$ by the equivalence relation of 'eventual equality'. This is similar to the ultraproduct construction, yet its theory is fairly less understood.
We consider the following question: if two reduced products $\prod_n\mathcal{M}_n/\mathrm{Fin}$ and $\prod_n\mathcal{N}_n/\mathrm{Fin}$ are isomorphic, what can be said about relations between structures we started with? Of course, one can obtain isomorphisms by taking fiberwise isomorphisms, and/or shuffling the indexes, but is that all? We discuss how, in specific interesting cases (such as fields, or certain graphs), answers to this question depend on the set theoretic ambient.
The concept of a monster model in model theory is a helpful tool for avoiding cumbersome bookkeeping and notation. Instead of needing to repeatedly take elementary extensions to realise types, or find automorphisms, one can simply say that there is a model M of a theory such that any 'small' model of that theory embeds into M, and any 'small' partial isomorphism in M extends to an automorphism. While usually 'small' means 'cardinality less than M' (and M is then taken to be 'big enough'), sometimes there are special cases in which 'small' means 'set-sized'. In particular, the surreal numbers acts as a monster model for the theory of dense linear orders, real-closed fields, and more.
I will introduce the concept of a monster model and its uses, expand somewhat on the hidden set-theoretic baggage associated with these objects, and show off the monstrosity of the surreal numbers. I will then show how, without the axiom of choice, the surreal numbers may no longer be a monster, using a simple symmetric extension argument.
Fundamental to the practice of logic is the dogma regarding the first order/second order logic distinction, namely that it is ironclad. Was it always so? The emergence of the set theoretic paradigm is an interesting test case. Early workers in foundations generally used higher order systems in the form of type theory; but then higher order systems were gradually abandoned in favor of first order set theory—a transition that was completed, more or less, by the 1930s.
As for logic in general, the concept of a logic being first order is not only about whether the variables range over the elements of a given domain, or over sets of elements, or over sets of sets of elements, and so on; it is also, I suggest, about the context.
Of course, set theory is a theory and second order logic is a logic, at least that is the common understanding. However if one cares to view set theory as a logic—and if we do think of set theory as a logic, it is a logic with the cumulative hierarchy 𝑉 as its standard (class) model—then set theory turns out to be a stronger logic than second order logic. This is perhaps as it should be, given that the latter restricts the domain of quantifiable objects to those generated by (at most) a single iteration of the power set operation, while set theory allows for arbitrary iterations of the power set operation.
This talk is based on the forthcoming paper "How first order is first order logic?" by J. Kennedy and Jouko Väänänen for The Oxford Handbook of Philosophy of Logic. Editors: Elke Brendel, Massimiliano Carrara, Filippo Ferrari, Ole Hjortland, Gil Sagi, Gila Sher, Florian Steinberger, Oxford University Press.
One of the strongest known large cardinal axioms is I3, positing the existence of a non-trivial elementary embedding $j$ from $V_λ$ to $V_λ$ for some $λ$. Given two such embeddings $j$ and $k$ for the same lambda, there is a natural "application" operation to yield a third, $j*k$, and elementarity shows that this operation is left self-distributive: $j*(k*l)=(j*k)*(j*l)$. Structures with such an operation are called LD-algebras or shelves. Laver showed that the algebra of embeddings generated by a single such $j$ under $*$ is in fact the free LD-algebra on 1 generator; and the set-theoretic context around this concrete (once you've assumed I3) instantiation of the free LD-algebra gives rise to various theorems about LD-algebras that are only known under this very strong large cardinal assumption. Given I3, there will be many other embeddings from $V_λ$ to $V_λ$, and it is natural to ask if one can obtain from amongst them a free LD-algebra on more than one generator. In joint work with Scott Cramer and Sheila Miller, we show that the answer is positive if one assumes a little more: from I2 we get a free 2-generator LD-algebra of embeddings. This talk will focus on set-theoretic aspects of the proof; a week later I will be giving a talk in the ARTIN conference on the same topic, focusing more on the algebraic aspects.
The problem of integration in finite terms is the problem of finding exact closed forms for antiderivatives of functions, within a given class of functions. Liouville introduced his elementary functions (built from polynomials, exponentials, logarithms and trigonometric functions) and gave a solution to the problem for that class, nearly 200 years ago. The same problem was shown to be decidable and an algorithm given by Risch in 1969.
We introduce the class of exponentially algebraic functions, generalising the elementary functions and much more robust than them, and give characterisations of them both in terms of o-minimal local definability and in terms of definability in a reduct of the theory of differentially closed fields.
We then prove the analogue of Liouville's theorem for these exponentially-algebraic functions.
This is joint work with Rémi Jaoui.
