betaFeedback

WorksMathematics

Piecewise Interpretations in Many-Sorted Logic

Abstract

Piecewise interpretations, introduced by Visser, generalize ordinary interpretations between first-order theories by allowing formulae to be interpreted using disjoint unions of definable sets. This makes it possible to capture natural constructions, such as the projective completion of an affine plane, but also leads to a notion of equivalence of theories, namely piecewise bi-interpretability. We develop the theory of piecewise interpretations systematically in the many-sorted setting. Each piecewise interpretation induces a semantic dual, a functor between categories of models. In addition, we introduce a syntactic notion of morphism between piecewise interpretations, which likewise has a semantic dual. Using these semantic duals, we collect theories, piecewise interpretations, and morphisms between them into a bicategory, in particular defining a well-behaved notion of composition of interpretations, associative up to coherent isomorphism. As an application, we consider a familiar idea, championed by Quine, namely that one can replace any many-sorted theory with a corresponding single-sorted one by replacing sorts with sortal predicates. We show that this leads to a biequivalence between the developed bicategories of theories with finitely many sorts and single-sorted theories, thereby providing an argument for the dispensability of sorts.

Introduction

Interpretations between first-order theories provide a fundamental tool for understanding relationships between mathematical structures and theories. In the time since Tarski’s introduction of his relative interpretations in Undecidable Theories (1953), various generalizations of the classical notion have arisen [1]. These notions, and their philosophical applications, have received significant attention and are relatively well understood.1 The goal of this paper is to systematically study the far less thoroughly investigated piecewise interpretations, introduced by Visser (2004, 2021) in a single-sorted setting. As opposed to ordinary interpretations, these allow one to interpret formulae using disjoint unions of definable sets. The theory developed in the paper is quite general, encompassing ordinary interpretations. It also introduces a natural notion of equivalence of theories, namely piecewise bi-interpretability, and remedies certain defects of the ordinary notion of interpretation, to do with the reduction of many-sorted to single-sorted logic.

The main focus will be the development of the mathematical theory of piecewise interpretations in the many-sorted setting. In Section 2, we define many-sorted piecewise translations and interpretations, discuss the projective completion of an affine plane as an example, develop semantic duals of translations, and introduce morphisms between piecewise translations (ii-morphisms) and their semantics. In Section 3, we show that theories, piecewise interpretations, and ii-morphisms form a bicategory Thpw\mathrm{Th}^{\mathrm{pw}} by semantic means, using the induced semantic duals of interpretations. In particular, we show that the developed notion of composition of piecewise interpretations is associative (up to coherent ii-isomorphism), thereby answering a small question due to Visser [24]. In Section 4, we present a (pseudo)functorial reduction of many-sorted to single-sorted logic, based on the familiar idea that one can replace sorts with sortal predicates. This reduction will take the form of a biequivalence between the developed bicategory of theories (with finitely many sorts) and piecewise interpretations and the single-sorted analogue of that bicategory.

Our decision to place the study of interpretations against the background of category theory follows Visser [24], while our approach to interpretations in many-sorted logic is inspired by Halvorson [8]. Meadows [15] pursues a structurally similar but more general and semantic project, studying functorial comparisons between theories mediated through their categories of models, organized through 2-category theory. Taking a mostly syntactic route, D’Arienzo et al. [5] systematically develop a bicategory of interpretations in coherent logic, establishing a tight relationship to categorical logic. Beyond Visser, piecewise interpretations have been studied independently by Li [13] in his master’s thesis: he presents a definition extending Visser’s against a many-sorted background, connecting piecewise interpretations to Meadows’ Morita interpretations and providing a notion of composition. The definition we have chosen differs in presentation from his and Visser’s, taking a cue from categorical logic, and we develop the theory further by placing our notion of composition into a bicategorical framework.

Notation and Preliminaries

Given a set XX, we denote by X∗X^{*} the set of finite sequences of elements of that set. Elements of X∗X^{*} will be denoted by xˉ=(x1,…,xn)\bar{x}=(x_{1},\ldots,x_{n}). We also write xˉ=x1×x2×⋯×xn\bar{x}=x_{1}\times x_{2}\times\cdots\times x_{n}, identifying x∈Xx\in X with the sequence (x)(x), where ×\times denotes concatenation of sequences. Concatenation with the empty sequence ε\varepsilon is the identity. For a sequence xˉ\bar{x}, we denote by ∣xˉ∣∈N|\bar{x}|\in\mathbb{N} its length and by xix_{i} its ii-th component. For n∈Nn\in\mathbb{N} we write [n]:={1,…,n}[n]:=\{1,\ldots,n\}, with [0]:=∅[0]:=\varnothing. Identifying a sequence xˉ=(x1,…,xn)\bar{x}=(x_{1},\ldots,x_{n}) over a set XX with the function [n]→X[n]\to X sending jj to xjx_{j} and given a function s:[m]→[n]s:[m]\to[n], we write xˉs\bar{x}^{s} for the composite xˉ∘s\bar{x}\circ s, componentwise described as xˉs:=(xs(1),…,xs(m))\bar{x}^{s}:=(x_{s(1)},\ldots,x_{s(m)}). This is functorial: xˉid=xˉ\bar{x}^{\mathrm{id}}=\bar{x}, and (xˉs)t=xˉs∘t(\bar{x}^{s})^{t}=\bar{x}^{s\circ t} for t:[l]→[m]t:[l]\to[m], by associativity of composition.

A finite family over a set XX is a function p:Ip→Xp:I_{p}\to X where IpI_{p} is a finite, non-empty set, called the index set of the family. We denote by F(X):={p:Ip→X∣Ip is finite and non-empty}\mathcal{F}(X):=\{p:I_{p}\to X\mid I_{p}\text{ is finite and non-empty}\} the collection of all finite families over XX. We will frequently need to consider F(X∗)\mathcal{F}(X^{*}), the collection of finite families of finite sequences over XX. Given a finite family of sets p:Ip→Xp:I_{p}\to X, we denote by ⨆k∈Ipp(k)\bigsqcup_{k\in I_{p}}p(k) its disjoint union, set-theoretically constructed as the set of ordered pairs (k,a)(k,a) such that a∈p(k)a\in p(k).

Next, we fix our logical vocabulary. A relational many-sorted first-order signature Σ=(S,R,V)\Sigma= (S,\mathcal{R},\mathcal{V}) consists of a non-empty set SS of sort symbols, a set R\mathcal{R} of sorted relation symbols, and a family V=(Vσ)σ∈S\mathcal{V} = (\mathcal{V}_{\sigma})_{\sigma\in S} of sets of sorted variables.3 To ensure we have enough variables available, we fix an infinite cardinal κ\kappa and restrict attention to signatures with ∣R∪S∣≤κ|\mathcal{R} \cup S| \le\kappa and ∣Vσ∣=κ|\mathcal{V}_{\sigma}| = \kappa for all σ∈S\sigma\in S. Each relation symbol R∈RR \in\mathcal{R} has an arity σˉ∈S∗\bar{\sigma} \in S^*, written R:σˉR : \bar{\sigma}. Among the logical vocabulary, we count verum ⊤\top and falsum ⊥\bot, taking their arity to be the empty sequence ε\varepsilon. For sentential operators, we have {¬,∧,∨,→}\{\neg, \wedge, \vee, \to\}. Moreover, each variable x∈Vx \in\mathcal{V} (resp. sequence xˉ∈V∗\bar{x} \in\mathcal{V}^* of variables) comes with an arity σ∈S\sigma\in S (resp. sequence of sorts σˉ\bar{\sigma} of the same length), expressed by x:σx : \sigma (resp. xˉ:σˉ\bar{x} : \bar{\sigma}). Quantifiers are sorted as well, with one quantifier ∀σ\forall_{\sigma} for each sort σ∈S\sigma\in S, although we will only explicitly represent this sorting with a subscript where helpful. For a sequence of variables yˉ=(y1,…,yn):σˉ\bar{y} = (y_1,\ldots,y_n) : \bar{\sigma} we define ∀yˉ ψ:=∀σ1y1⋯∀σnynψ\forall\bar{y}\,\psi:= \forall_{\sigma_1}y_1 \cdots\forall_{\sigma_n}y_n\psi. In particular, ∀εψ=ψ\forall\varepsilon\psi= \psi. Officially, we will treat the existential quantifier ∃\exists as the dual of the universal quantifier. The signature Σ\Sigma generates a sorted first-order language LΣ\mathcal{L}_{\Sigma} in the standard inductive fashion: given a relation symbol R:σˉR : \bar{\sigma} and a sequence of variables xˉ:σˉ\bar{x} : \bar{\sigma}, one can form an atomic formula R(xˉ)R(\bar{x}), and general formulae are generated from these via the connectives and the quantifiers, taking sorting into account.4

For a syntactic calculus for many-sorted logic, we direct the reader to Halvorson [8]; starting from a syntactic calculus for single-sorted logic, one only needs to modify the rules for the quantifiers so as to take the sorting into account. We will denote the resulting consequence relation by ⊢\vdash. A theory TT in a signature Σ\Sigma is a deductively closed set of sentences in the language LΣ\mathcal{L}_{\Sigma}.

We will also work with formulae-in-context, that is, pairs of a formula φ∈LΣ\varphi\in\mathcal{L}_{\Sigma} and a context xˉ\bar{x} for φ\varphi. A context for a formula is a duplicate-free list xˉ\bar{x} of variables which contains all the free variables of φ\varphi. The notation (xˉ∣φ)(\bar{x} \mid\varphi) denotes the formula-in-context consisting of φ\varphi and the context xˉ\bar{x} for φ\varphi. Of particular importance will be the canonical context5 xˉ(φ)\bar{x}(\varphi) of a formula φ\varphi, which contains exactly the free variables of φ\varphi in order of first occurrence. The sort sequence σˉ(φ)\bar{\sigma}(\varphi) of xˉ(φ)\bar{x}(\varphi) is called the arity of φ\varphi; we write φ:σˉ\varphi: \bar{\sigma}.

Given a context yˉ=(y1,…,ym):τˉ\bar{y} = (y_1,\ldots,y_m) : \bar{\tau} for a formula φ\varphi with canonical context xˉ(φ)=(x1,…,xn):σˉ\bar{x}(\varphi) = (x_1,\ldots,x_n) : \bar{\sigma}, there is a unique injection c:[n]→[m]c : [n] \to[m] such that xj=yc(j)x_j = y_{c(j)} for 1≤j≤n1 \le j \le n. We call cc the context injection for yˉ\bar{y} relative to φ\varphi. Given a formula φ\varphi and a sequence of variables yˉ:σˉ(φ)\bar{y} : \bar{\sigma}(\varphi), we write φ(yˉ)\varphi(\bar{y}) for the result of the capture-avoiding simultaneous substitution of yˉ\bar{y} for xˉ(φ)\bar{x}(\varphi) in φ\varphi.6

Lemma 1.1.1 (Canonical Context under Substitution). Let φ\varphi be a formula with canonical context xˉ=(x1,…,xn):σˉ\bar{x} = (x_1,\ldots,x_n) : \bar{\sigma}, and let yˉ=(y1,…,yn):σˉ\bar{y} = (y_1,\ldots,y_n) : \bar{\sigma}. Then the canonical context of φ(yˉ)\varphi(\bar{y}) is yˉ\bar{y}, the sequence resulting from yˉ\bar{y} by deleting repeated members from right to left.

Proof. See Appendix A.

Let us record some other useful abbreviations: given a sequence of variables xˉ:σˉ\bar{x} : \bar{\sigma}, we write ⊤‾xˉ:=⋀i=1∣xˉ∣(xi=σixi)\overline{\top}_{\bar{x}} := \bigwedge_{i=1}^{|\bar{x}|}(x_i =_{\sigma_i} x_i) and ⊥‾xˉ:=¬⊤‾xˉ\overline{\bot}_{\bar{x}} := \neg\overline{\top}_{\bar{x}}, where the empty conjunction is the nullary ⊤\top. We write ⊤σˉ\top_{\bar{\sigma}} and ⊥σˉ\bot_{\bar{\sigma}} if the choice of duplicate-free variable sequence does not matter. Moreover, given another sequence yˉ:σˉ\bar{y}:\bar{\sigma}, we define identity for sequences of the same arity as xˉ=σˉyˉ:=⊤xˉ×yˉ∧⋀i=1∣xˉ∣(xi=σiyi)\bar{x} =_{\bar{\sigma}} \bar{y} := \top_{\bar{x}\times\bar{y}} \land\bigwedge_{i=1}^{|\bar{x}|}(x_i =_{\sigma_i} y_i), with the first conjunct serving as padding to get the arities right.

References

  1. [1]Daniel Alscher. Theorien der reellen Zahlen und Interpretierbarkeit, volume 25 of Logos – Studien zur Logik, Sprachphilosophie und Metaphysik. De Gruyter, Berlin, 2016.DOI
  2. [2]Thomas William Barrett and Hans Halvorson. Morita equivalence. The Review of Symbolic Logic, 9(3):556–582, 2016.
  3. [3]Thomas William Barrett and Hans Halvorson. Quine’s conjecture on many-sorted logic. Synthese, 194(9):3563–3582, 2017.DOI
  4. [5]Anthony D’Arienzo, Vinny Pagano, and Ian M. J. McInnis. Bicategories, biequivalence, and bi-interpretability, 2023. arXiv:2011.14056v2.arxiv.org/abs/2011.14056
  5. [7]Nick Gurski. Biequivalences in tricategories. Theory and Applications of Categories, 26(14):349–384, 2012.arxiv.org/abs/1102.0979
  6. [8]Hans Halvorson. The Logic in Philosophy of Science. Cambridge University Press, Cambridge, 2019.DOI
  7. [9]Hans Halvorson. Against eliminating sorts. Unpublished manuscript, 2024.
  8. [10]Robin Hartshorne. Foundations of Projective Geometry. W. A. Benjamin, New York, 1967.
  9. [11]Julian L. Hook. A note on interpretations of many-sorted theories. The Journal of Symbolic Logic, 50(2):372–374, 1985.
  10. [12]Tom Leinster. Basic bicategories, 1998. arXiv:math/9810017.DOI
  11. [13]Minzhe Li. Theoretical equivalence as representational equivalence. MSc thesis, Universiteit van Amsterdam, Amsterdam, June 2025.
  12. [14]Paul Anh McEldowney. On Morita equivalence and interpretability. The Review of Symbolic Logic, 13(2):388–415, 2020.
  13. [15]Toby Meadows. Beyond linguistic interpretation in theory comparison. The Review of Symbolic Logic, 17(3):819–859, 2024.
  14. [16]Toby Meadows. The Halvorson example. Erkenntnis, 91:3129–3148, 2026. doi: 10.1007/s10670-025-01031-6.DOI
  15. [18]Arnold Oberschelp. Untersuchungen zur mehrsortigen Quantorenlogik. Mathematische Annalen, 145(4):297–333, 1962.DOI
  16. [19]Hrafn Valtýr Oddsson. Constructive proofs for the standard translation of many-sorted to unsorted predicate logic, 2026. arXiv:2603.18216.
  17. [20]Willard Van Orman Quine. Unification of universes in set theory. The Journal of Symbolic Logic, 21(3):267–279, 1956.DOI
  18. [21]Arnold Schmidt. Über deduktive Theorien mit mehreren Sorten von Grunddingen. Mathematische Annalen, 115(1):485–506, 1938.
  19. [22]Arnold Schmidt. Die Zulässigkeit der Behandlung mehrsortiger Theorien mittels der üblichen einsortigen Prädikatenlogik. Mathematische Annalen, 123(1):187–200, 1951.
  20. [24]Albert Visser. Categories of theories and interpretations. Logic Group Preprint Series 228, Department of Philosophy, Utrecht University, 2004.
  21. [26]Hao Wang. Logic of many-sorted theories. The Journal of Symbolic Logic, 17(2):105–116, 1952.DOI

Paper details

vlnc:W_yw2qtm4j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents