Several areas of computer science (databases, knowledge representation, program verification, reasoning about knowledge and actions) feature logical languages in which one can construct complex binary relations from basic ones, through a certain set of operations (e.g., relational composition, union, inverse, …). Examples include propositional dynamic logics such as PDL and KAT (Kleene Algebra with Tests) as well as various query languages for graph databases. Underlying each of these is a “binary relation algebra” , i.e., an algebraic signature consisting of finitely many operations on binary relations. The specific set of operators, in each of the aforementioned languages, is typically chosen as a compromise between computational complexity and expressive power and/or may be based on a requirement to preserve certain natural structural properties such as functionality or bisimulation.

Preservation theorems link semantics properties of formulas to their syntactic shape. The most famous example is the Łoś-Tarski theorem, which states that a first-order formula is preserved under induced substructures (i.e., remains true if one passes from a structure to an induced substructure) if and only if it can be written without using any existential quantifiers (assuming negation normal form). In this talk, we will review some recent results (both positive and negative) about the existence of preservation theorems for algebras of binary relations. (Algebraically, the results I will present can be equivalently viewed as addressing the question whether certain clones admit a finite set of generators).

Specifically, I will discuss results about Tarski’s relation algebra from a joint paper with Bart Bogaerts, Brett McLean, and Jan van den Bussche (LMCS 2024) as well as results about Kleene Algebra with Tests (KAT) from a joint paper with Tobias Kappé (POPL 2025).

Disquotational truth can play a justificatory role for new mathematical knowledge. In particular, we focus on the known case of consistently extending a theory of first-order arithmetic (PA) with a truth predicate governed by disquotational principles for positive sentences. One philosophically interesting feature is that the addition of this truth predicate is conservative over the arithmetical theory, giving disquotational truth the same epistemic status of a mathematical definition. Following Feferman and McGee, we argue in favour of the open-ended nature of the induction schema: once a new mathematical concept is legitimately defined the schema should hold for the extended language. For truth, this results in more justificatory power as one can prove the consistency statement of the arithmetical theory. Moreover, the exact nature of the justificatory power of positive disquotational truth can be pinned down via an ordinal analysis of the theory, as done by Halbach.

We explore the possibility of extending this disquotational definition of truth via a principle of Generalised Induction introduced by Cantini. The principle is conservative over PA, meaning it preserves the epistemic status of a definition. Furthermore, we argue that the adoption of this principle is particularly motivated in the case of positive disquotational truth. Once this new truth predicate is allowed in the induction schema, we obtain significantly more justificatory power than the original disquotational theory. I conclude by sketching a possible strategy via a collapsing procedure to show that this result is sharp.

Non-classical logics have been proposed in a number of domains, including constructive mathematics and quantum mechanics. In this talk, I will identify a base logic beneath some of these non-classical logics that I suggest has a certain fundamental status. I will give an introduction to the proof theory and semantics of this “Fundamental Logic.”

An associated paper is available at https://arxiv.org/abs/2207.06993.

Previous works by Goré, Postniece and Tiu have provided sound and cut-free complete proof systems for modal logics extended with path axioms using the formalism of nested sequent. Our aim is to provide (i) a constructive cut-elimination procedure and (ii) alternative modular formulations for these systems. We present our methodology to achieve these two goals on a subclass of path axioms, namely quasi-transitivity axioms.

The axioms of quantum mechanics present the state of a quantum system as a unit vector in complex Hilbert space. However, when Dirac [1] presented his bra- and ket-vectors, he had a more general space in mind. Schwartz [4] later gave a rigorous account for Dirac’s “vectors” as distributions, but in elementary physics books one still encounters presentations where ket-vectors are presented just as elements of a Hilbert space, and treated with methods from finite-dimensional linear algebra.

During the last years Tapani Hyttinen and I [2,3] have been looking at various models justifying the finite dimensional approaches from such textbooks. Our approaches are based on various embeddings of a Hilbert space into metric ultraproducts of finite-dimensional Hilbert spaces. In this talk I will present the basic ideas, their benefits and limitations. Time permitting, I will also contrast our approach to Boris Zilber’s work on the same questions, that was the original inspiration for us.

1. P.A.M. Dirac. The principles of Quantum Mechanics, 3rd ed, Clarendon Press, Oxford, 1947.
2. Å. Hirvonen, T. Hyttinen, On eigenvectors, approximations and the Feynman propagator, Ann. Pure Appl. Logic 170 (2019).
3. Å. Hirvonen, T. Hyttinen, On Ultraproducts, the Spectral Theorem and Rigged Hilbert Spaces, to appear in J. Symb. Log.
4. L. Schwartz, Théory de Distributions, Hermann, Paris, 1950.

This dissertation concerns the properties of and relationship between positive truth and fixpoints over intuitionistic arithmetic in three respects: the strength of these theories relative to the arithmetic base theories, relationships between theories of strictly positive fixpoints and compositional and disquotational truth for strictly truth-positive sentences, and a comparison with the classical case.

Opponent: Gerhard Jäger, Professor Emiratus University of Bern

Natural languages vary in their quantity expressions, but the variation seems to be constrained by general properties, so-called universals. Explanations thereof have been sought among constraints of human cognition, communication, complexity, and pragmatics. In this work, we examine whether perceptual constraints and coordination dynamics contribute to the development of two universals: monotonicity and convexity. Using a state-of-the-art multi-agent language coordination model (originally applied to colour terms) we evolve communicatively usable quantity terminologies. We compare the degrees of convexity and monotonicity of languages evolving in populations of agents with and without approximate number sense (ANS). The results suggest that ANS supports the development of monotonicity and, to a lesser extent, convexity. We relate our results to some classical observations about generalised quantifiers in mathematical logic and to the research on conceptual spaces.

This is joint work with Dariusz Kalociński, Franek Rakowski and Jakub Uszyński.

Let M be the weak set theory obtained from ZF by removing the Collection Scheme, restricting the Separation Scheme to bounded formulae, and adding an axiom asserting that every set is contained transitive set. In this talk I will consider two formulations of the set-theoretic Collection Scheme restricted formulae that are Π_n in the Levy hierarchy: Π_n-Collection and Strong Π_n-Collection. It is known that, over M, Strong Π_n-Collection is equivalent to Π_n-Collection plus Σ_n+1-Separation, and Strong Π_n-Collection proves the consistency of M + Π_n-Collection. In this talk I will show that for all n > 0, every well-founded model of M + Π_n-Collection satisfies Strong Π_n-Collection. In particular, for n > 0, M + Strong Π_n-Collection does not prove the existence of a transitive model of M + Π_n-Collection. And, for n > 0, the minimum model of M + Strong Π_n-Collection and M + Π_n-Collection coincide. If time permits, I will indicate how the assumption that that the model is well-founded can be replaced with the assumption that the model instead satisfies a fragment of Foundation. This reveals new equivalences between subsystems of ZF that include the Powerset axiom.

We explain some of the connections between two research areas: cyclic proof theory and proof assistants. This talk is based on joint work-in-progress with Lide Grotenhuis.

In cyclic proof theory, we replace induction axioms with circular reasoning. By carefully placing restrictions on cycles, we can make sure that we do not prove more than with induction. Such cyclic proofs can be interpreted as programs using the Curry-Howard correspondence: cycles correspond to recursive calls, while the restrictions make sure that the program always terminates. Using this perspective, we show how the type theory implemented by proof assistants can be seen as a cyclic proof system: one where programs/proofs are defined using (co)pattern matching. We show some of the difficulties that come up specifically in dependent type theory: why unification becomes important, and how one can translate cyclic proofs to inductive proofs while preserving computational behavior. In addition, we show how some of the techniques from cyclic proof theory might be used to extend proof assistants.

Voting on two alternatives appears unproblematic compared to voting on three (or more). When faced with only two alternatives, many arguments show that Majority Rule distinguishes itself from all other ways of making a group decision. For three or more alternatives, one faces the so-called “Paradox of Voting”: there may be elections with a majority cycle in which a majority of voters prefer A to B, a majority of voters prefer B to C, and a majority of voters prefer C to A. In this talk, I will explain a series of results that axiomatically characterize rules for resolving majority cycles in elections. These rules avoid the “Strong No Show Paradox” by responding properly to the addition of new voters to an election and mitigate spoiler effects by responding properly to the addition of new candidates to an election.

This talk is based on joint work with Wes Holliday.

The 2024 Annual European Meeting of the Association for Symbolic Logic, also known as the Logic Colloquium, will be held in Gothenburg on 24-28 June, 2024 and hosted by the Faculty of Humanities at the University of Gothenburg. The colloquium comprises 3 tutorials, 7 plenary lectures and 6 special sessions as well as contributed talks. In addition, the 2024 Gödel Lecture was delivered at the meeting.

See lc2024.se for full information.

Inquisitive modal logic is a generalization of standard modal logic where the language also contains questions, and modal operators that can be applied to them. In this talk, I will provide an introductory overview of inquisitive modal logic. I will review some motivations for the approach, present some prominent examples of inquisitive modal logics, mention some results about them, and outline directions for future work.

The talk reports on an ongoing conversation with Graham Leigh on the topic of completeness theorem for modal logics, and more generally on the exploration of their semantics. The usual completeness theorem for modal logic is given over Kripke-style semantics. How necessary is this choice? In this talk we will see how such choice seems almost unavoidable. I will discuss how to tune this technology to handle more complex modal logics, and provide modular completeness theorems for them.

A classical result by Lovász asserts that two graphs G and H are isomorphic if and only if they have the same left profile, that is, for every graph F, the number of homomorphisms from F to G coincides with the number of homomorphisms from F to H. A similar result is also known to hold for right profiles, that is, two graphs G and H are isomorphic if and only if for every graph F, the number of homomorphisms from G to F coincides with the number of homomorphisms from H to F. During the past several years, there has been a study of equivalence relations that are relaxations of isomorphism obtained by restricting the left profile or the right profile to suitably restricted classes of graphs, instead of the class of all graphs. Furthermore, a notion of a query algorithm based on homomorphism counts was recently introduced and investigated. The aim of this talk is to present an overview of some of the main results in this area with emphasis on the differences between left homomorphism counts and right homomorphism counts.

There is a mature body of work in logic aiming to characterize logical formalisms in terms of their structural or model-theoretic properties. The origins of this work can be traced to Alfred Tarski’s program to characterize metamathematical notions in “purely mathematical terms” and to Per Lindström’s abstract characterizations of first-order logic. For the past forty years, rule-based logical languages have been widely used in databases and in related areas of computer science to express integrity constraints and to specify transformations in data management tasks, such as data exchange and ontology-based data access. The aim of this talk is to present an overview of more recent results that characterize various classes of rule-based logical languages in terms of their structural or model-theoretic properties.

Sequential theories form a fundamental class of theories in logic. They have full coding possibilities and allow us to build partial satisfaction predicates for formulas of bounded depth-of-quantifier-alernations. In many respects, they are the proper domain of Gödelian metamathematics. We explain the notion of sequential theory.

A theory is restricted if it can be axiomatised by axioms of bounded depth-of-quantifier-alernations. All finitely axiomatised theories are restriced, but, for example, also Primitive Recursive Arithmetic. We explain the small-is-very-small principle for restricted sequential theories which says that, whenever the given theory shows that a definable property has a small witness, i.e., a witness in a sufficiently small definable cut, then it shows that the property has a very small witness, i.e., a witness below a given standard number.

We sketch two proofs that restricted theories are incomplete (however complex the axiom set). One uses the small-is-very-small principle and the other a direct Rosser argument. (The second argument was developed in collaboration with Ali Enayat.)

There is a fundamental relation between the modal mu-calculus and infinite-duration two-player games, highlighted perhaps best by the well-known equivalence of mu-calculus formula evaluation and the solution of so-called parity games. Furthermore, parity games also feature prominently in tableau-based reasoning methods for the mu-calculus. Recent work has also shown that the close relation between extremal fixpoints in the mu-calculus and parity conditions can be generalized, lifting the connection to the level of fixpoint equation systems over arbitrary complete lattices.

In this talk, I will detail the above-mentioned connections, summing up recent research that shows how results from game theory can be used to improve and generalize existing algorithmic methods for the analysis of mu-calculus formulas. While this approach leads to improved worst-case runtime guarantees on one hand, it also enables the treatment of generalized mu-calculi that involve, e.g., quantitative or probabilistic modalities.

There is a classical result of Pitts that propositional intuitionistic logic eliminates second order propositional quantifiers. Later, Ghilardi and Zawadowski have worked out a semantic proof of this by developing a sheaf representation of finitely presented Heyting algebras. The basic idea is to represent a Heyting algebra via its collection of models on finite Kripke frames, expressed in a suitable categorical and sheaf-theoretic language. Their representation allows them to show, among other things, that the algebraic theory of Heyting algebras has a model companion, and the quantifier elimination result also follows as a consequence. In this talk, I will briefly recall these classical result and show the possibility of extending these developments to a suitable class of first-order intuitionistic theories. In particular, I will explain how to construct higher sheaf representation of first-order intuitionistic theories, and discuss some possible outcomes.

A game that characterizes definability of classes of structures by first-order sentences containing a given number of quantifiers was introduced by Immerman in 1981. In this talk I describe two other games that are equivalent with the Immerman game in the sense that they characterize definability by a given number of quantifiers.

In the Immerman game, Duplicator has a canonical optimal strategy, and hence Duplicator can be completely removed from the game by replacing her moves with default moves given by this optimal strategy. On the other hand, in the other two games there is no such optimal strategy for Duplicator. Thus, the Immerman game can be regarded as a one-player game, but the other two games are genuine two-player games.

The talk is based on joint work with Kerkko Luosto.

Switcher Semantics is a semantic framework that is basically characterised by allowing switching: when recursively applying a semantic function \(\mu\) to a complex term \(t\), the semantic function applying to an immediate subterm \(t'\) of \(t\) may be a function \(\mu'\), distinct from \(\mu\). An operator-argument-position pair is called a switcher if it induces such a switch. Switcher semantic systems do not satisfy the standard form of compositionality, but a generalized form, which allows greater flexibility. In earlier work (mostly published), some together with Kathrin Glüer, some with Dag Westerståhl, it has been applied to natural language constructions like proper names in modal contexts, general terms in modal contexts, indexicals in temporal contexts, quotation, and belief contexts. This talk will focus on quantifiers and quantification. First-order quantifiers can be regarded as switchers, switching from truth conditions to satisfaction conditions. The larger topic is quantification into switched contexts. I shall begin by giving an introduction to the framework.

The Logic Group at the University of Gothenburg hosts its annual World Logic Day Pub Quiz. For information of this and other World Logic Day events around the world, see http://wld.cipsh.international/wld2024.html.