When Bi-interpretability implies Synonymy
Harvey M. Friedman †,‡, Albert Visser ‡ · 2025
Read When Bi-interpretability implies Synonymy by Harvey M. Friedman †,‡, Albert Visser ‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01028.txt.
Introduction
Harvey Friedman and Albert Visser ask when two formal theories that can interpret each other are really the same theory in a 2025 paper. Logic offers two grades of sameness: bi-interpretability, the looser one, and synonymy, also called definitional equivalence, the strictest. When the first implies the second was open for an important class of cases.
For sequential theories, they prove the implication holds when both interpretations are one-dimensional and preserve identity. The proof leans on a Schröder-Bernstein style result proved under very weak assumptions, which they note has interest of its own. A counterexample shows the identity condition cannot be dropped, so the theorem is exactly as strong as possible.
Catalog record
| CREATOR | Harvey M. Friedman †,‡, Albert Visser ‡ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01028
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Bi-interpretability implies Synonymy Thanks: † Harvey M. Friedman, Distinguished University Professor of Mathematics, Philosophy, and Computer Science, Emeritus, Ohio State University, Columbus, Ohio 43235. This research was partially supported by the John Templeton Foundation grant ID # 36297 \#36297 . The opinions expressed here are those of the author and do not necessarily reflect the views of the John Templeton Foundation. Thanks: ‡ We thank Tonny Hurkens who simplified our proof of the Schröder-Bernstein Theorem. We present his version here with his permission. We thank Allan van Hulst who verified our proof of the Schröder-Bernstein Theorem in Mizar. We are grateful to Peter Aczel, Ali Enayat and Wilfrid Hodges for stimulating conversations or e-mail correspondence. We are grateful to Tim Button and to Leszek Kołodziejczyk who independently spotted a mistake in an earlier version of this paper. Harvey M. Friedman †,‡, Albert Visser ‡ Abstract . Two salient notions of sameness of theories are synonymy , aka definitional equivalence , and bi-interpretability . Of these two definitional equivalence is the strictest notion. In which cases can we infer synonymy from bi-interpretability? We study this question for the case of sequential theories. Our result is as follows. Suppose that two sequential theories are bi-interpretable and that the interpretations involved in the bi-interpretation are one-dimensional and identity preserving. Then, the theories are synonymous. The crucial ingredient of our proof is a version of the Schröder-Bernstein theorem under very weak conditions. We think this last result has some independent interest. We provide an example to show that this result is optimal. There are two finitely axiomatized sequential theories that are bi-interpretable but not synonymous, where precisely one of the interpretations involved in the bi-interpretation is not identity preserving. 2010 Mathematics Subject Classification 03A05, 03B30, 03F25 1. Introduction When are two theories the same? Are there reasonable ways of abstracting away from the precise choice of the signature? The notions of synonymy (or: definitional equivalence ) and bi-interpretability provide two good answers to these questions. The notion of synonymy was introduced by de Bouvère in 1965. See [ dB65a ] and [ dB65b ] . It appears to be the strictest notion of sameness of theories except strict identity of signature and set of theorems. Two theories U and V are synonymous iff there is a theory W that is both a definitional extension of U and of V (where we allow the signatures of U and V to be made disjoint). Equivalently, U and V are synonymous iff there are interpretations K\mathop{:}U\to V and M\mathop{:}V\to U , such that V proves that the composition K\circ M is the identity interpretation on V and such that U proves that the composition M\circ K of is the identity interpretation on U . (Thus, synonymy is isomorphism in an appropriate category {\sf INT}_{0} of theories and interpretations.) There are many familiar examples of synonymy. First, a theory is synonymous with a definitional extension. For example, Peano Arithmetic with 0 , S , + and \times is synonymous with its extension with < and the additional axiom x<y\leftrightarrow\exists z\;x+{\sf S}z=y . Then, we have examples that are considered by mathematicians to be trivial alternative formulations like the theory of weak partial order and the theory of strong partial order. Finally, there are more substantial examples. E.g., Peano Arithmetic, PA , is synonymous with an appropriate theory of strings and concatenation. See [ CFM74 ] and, for a slightly weaker classical result, [ Qui46 ] . 1 1 1 In fact, it is simpler to prove that these theories are bi-interpretable via one-dimensional, identity preserving interpretations. Then, the results of the present paper immediately yield the synonymy. The notion of bi-interpretability was introduced by Alhbrandt and Ziegler in 1986. See [ AZ86 ] and, also, [ Hod93 ] . Two theories U and V are bi-interpretable iff there are interpretations K:U\to V and M:V\to U , such that there is a V -definable function F , such that V proves that F is an isomorphism between K\circ M and the identity interpretation on V and such that there is a U -definable function G , such that U proves that G is an isomorphism between M\circ K and the identity interpretation on U . (Thus, bi-interpretability is isomorphism in an appropriate category {\sf INT}_{1} of theories and interpretations.) In terms of models the notion of bi-interpretability takes the following form. We note that an interpretation K:U\to V gives us a uniform construction of an internal model \widetilde{K}(\mathcal{M}) of U in a model \mathcal{M} of V . We find that U and V are bi-interpretable iff, there are interpretations K:U\to V and M:V\to U and formulas F and G , such that, for all models \mathcal{M} of V , the formula F defines in \mathcal{M} an isomorphism between \mathcal{M} and \widetilde{M}\widetilde{K}(\mathcal{M}) , and, for all models \mathcal{N} of U , the formula G defines in \mathcal{N} an isomorphism between \mathcal{N} and \widetilde{K}\widetilde{M}(\mathcal{N}) . Bi-interpretability has a lot of good properties. E.g., it preserves automorphism groups, \kappa -categoricity, finite axiomatizability, etc. Still the stricter notion synonymy preserves more. For example, synonymy preserves the action of the automorphism group on the domain of the model. Bi-interpretability (without parameters) does preserve the automorphism group modulo isomorphism but does not necessarily preserve the action on the domain. See Section 7 for an example illustrating this difference. An example of a property of theories that is not preserved under bi-interpretability (not even under definitional equivalence) is having a computable model. See [ Pak22 ] . Surprisingly, it is not easy to provide natural examples of pairs of theories that are bi-interpretable but not synonymous. For example, Peano Arithmetic PA is prima facie bi-interpretable with an appropriate theory of the hereditarily finite sets. However, on closer inspection, these theories are also synonymous. See Subsection 6.3 . In Section 7 , we give a verified example of two finitely axiomatized sequential theories that are bi-interpretable but not synonymous. Our interest in this paper is in the relationship between synonymy and bi-interpretability for a special class of theories, the sequential theories . These are theories that have coding of sequences. Examples of sequential theories are Buss’s theory {\sf S}^{1}_{2} , Elementary Arithmetic EA or EFA , \mathrm{I}\Sigma_{1} , ZF , ZFC . We explain in detail what sequential theories are in Section 3 . We will show that, for identity-preserving interpretations between sequential theories, synonymy and bi-interpretability coincide (Section 5 ). In fact the proof works for a somewhat wider class: the conceptual theories . This last class was just defined here to pin down (more) precisely what is needed for the theorem. A central ingredient of our proof is the Schröder-Bernstein Theorem that turns out to hold under surprisingly weak conditions. We give the proof of the Schröder-Bernstein Theorem under these weak conditions in Section 4 . 1.1. Historical Remark The first preprint of this paper came out in the Logic Group Preprint Series of Utrecht University in 2014. On August 4, 2023, Albert Visser received an e-mail from Leszek Kołodziejczyk reporting that he found a counter-example to Theorem 5.4 of the preprint and, on September 6, 2023, Visser received an e-mail from Tim