Equivalence in foundations

Hans Halvorson

I survey results — recent as well as historical — about the equivalence or inequivalence of systems that could serve as the foundation of mathematics. Throughout I focus on clarifying which notion of equivalence is operative in the various results, in the hope of arriving at a more clear sense of which notions are relevant in mathematical practice.

The known results that I discuss include:

• Type theory is not equivalent to ZF set theory (Kemeny [6])
• No two extensions of ZF are bi-interpretable (Enyat [4], Friedman, Friere and Hamkins [5], Pakhomov, Visser)
• (B)ZF is equivalent to the elementary theory of the category of sets (Cole [3], Mitchell [7], Shulman [8])

I consider precise definitions of equivalence including:

• Mutual interpretability
• Bi-interpretability: both strict, and generalized
• Morita equivalence [1]
• Categorical equivalence [1]

While bi-interpretability is, according to Hamkins, the “gold standard for equivalence”, there remains some unclarity in its definition — in particular, in the definition of “translation” on which bi-interpretability is built.

I show that two theories can be Morita equivalent without being bi-interpretable, even under the most liberal interpretation of the latter notion. This mismatch between Morita equivalence and bi-interpretability raises a puzzle about the classical result [2] that any theory formulated in many-sorted logic can be replaced by an unsorted theory. While the result is true for Morita equivalence for theories with finitely many sorts, it fails for infinitely many sorts, and even more severely for bi-interpretability. I attempt to bring order to this situation by considering various definitions of a translation between theories, and by comparing the resulting notion of equivalence with Morita equivalence.

Bibliography

1. Thomas Barrett and Hans Halvorson, Morita equivalence, Review of symbolic logic, vol. 9 (2016), no. 3, pp. 556–582.
2. Thomas Barrett and Hans Halvorson, Quine’s conjecture on many-sorted logic, Synthese, vol. 194 (2017), pp. 3563–3582.
3. J.C. Cole, Categories of sets and models of set theory, The Proceedings of the Bertrand Russell Memorial Conference, Uldum, 1971, Bertrand Russell Memorial Logic Conf., Leeds, 1973, pp. 351–399.
4. Ali Enayat, Variations on a Visserian theme, Liber Amicorum Alberti : a tribute to Albert Visser (Jan van Eijck, Rosalie Iemhoff and Joost J. Joosten, editors), College Publications, London, 2016, pp. 99-110.
5. Alfredo Roque Freire and Joel David Hamkins, Bi-interpretation in weak set theories, Journal of symbolic logic, vol. 86 (2021), no. 2, pp. 609–634.
6. John Kemeny, Type-theory vs. set-theory, PhD thesis, Princeton University, (1949).
7. William Mitchell, Boolean topoi and the theory of sets, Journal of pure and applied algebra, vol. 2 (1972), pp. 261–274.
8. Michael Shulman, Comparing material and structural set theories, Annals of pure and applied logic, vol. 170 (2019), no. 4, pp. 465–504.

 Overview  Program