Month: January 2023

Quantified modal logics: One approach to rule them all!

Eugenio Orlandelli

We present a general approach to quantified modal logics (QML) that can simulate most other approaches. The language is based on operators indexed by terms which allow to express de re modalities and to control the interaction of modalities with the first-order machinery and with non-rigid designators. The semantics is based on a primitive counterpart relation holding between n-tuples of objects inhabiting possible worlds. This allows an object to be represented by one, many or no object in an accessible world. Moreover by taking as primitive a relation between n-tuples we avoid the shortcomings of standard individual counterparts. Finally, we use cut-free labelled sequent calculi to give a proof-theoretic characterisation of the quantified extensions of each first-order definable propositional modal logic. In this way we show how to complete many axiomatically incomplete QML.

Polynomial-time axioms of choice and polynomial-time cardinality

Josh Grochow

Many versions of the Axiom of Choice (AC), though equivalent in ZF set theory, are inequivalent from the computational point of view. When we consider polynomial-time analogues of AC, many of these different versions can be shown to be equivalent to other more standard questions about the relationship between complexity classes. We will use some of these formulations of AC to motivate several complexity questions that might otherwise seem a bit bespoke and unrelated from one another.

Next, as many versions of AC are about cardinals, in the second half of the talk we introduce a polynomial-time version of cardinality, in the spirit of polynomial-time model theory. As this is a new theory, we will discuss some of the foundational properties of polynomial-time cardinality, some of which may be surprising when contrasted with their set-theoretic counterparts. The talk will contain many open questions, and the paper contains even more! Based on arXiv:2301.07123 [cs.CC].