Abstract
This paper is an investigation into what could be a goodexplication of ``theory S is reducible to theory T''. Ipresent an axiomatic approach to reducibility, which is developedmetamathematically and used to evaluate most of the definitionsof ``reducible'' found in the relevant literature. Among these,relative interpretability turns out to be most convincing as ageneral reducibility concept, proof-theoreticalreducibility being its only serious competitor left. Thisrelation is analyzed in some detail, both from the point of viewof the reducibility axioms and of modal logic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
Adams, E.: 1955, Axiomatic Foundations of Rigid Body Mechanics, Stanford University.
Adams, E.: 1959, ‘The Foundations of Rigid Body Mechanics and the Derivation of its Laws from Those of Particle Mechanics', in Henkin, Suppes, Tarski (eds), The Axiomatic Method, North-Holland, Amsterdam.
Balzer, W.: 1982, Empirische Theorien: Modelle, Strukturen,Beispiele, Vieweg, Braunschweig.
Balzer, W., D. Pearce, and H.-J. Schmidt: 1984, Reduction in Science, Reidel, Dordrecht.
Benthem van, J. and D. Pearce: 1984, ‘A Mathematical Characterization of Interpretation between Theories', Studia Logica 43, 295–303.
Berarducci, A.: 1990, ‘The Interpretability Logic of Peano Arithmetic', Journal of Symbolic Logic 55, 1059–1089.
Bonevac, D.: 1982, Reduction in the Abstract Sciences, Hackett, Indianapolis.
Boolos, G.: 1993, The Logic of Provability, Cambridge University Press, Cambridge.
Buchholz, W., S. Feferman, W. Pohlers, and W. Sieg: 1981, Iterated Inductive Definitions: Recent Proof-Theoretical Studies, Springer, Berlin.
Eberle, R.: 1971, ‘Replacing One Theory by Another under Preservation of a Given Feature', Philosophy of Science 38, 486–501.
Feferman, S.: 1960, ‘Arithmetization of Metamathematics in a General Setting', Fundamenta Mathematicae XLIX, 35–92.
Feferman, S.: 1988, ‘Hilbert's Program Relativized: Proof-Theoretical and Foundational Reductions', Journal of Symbolic Logic 53, 364–384.
Feferman, S.: 1993, ‘What Rests on What? The Proof-Theoretic Analysis of Mathematics', in J. Czermak (ed.), Philosophie der Mathematik, Akten des 15. Internationalen Wittgenstein-Symposiums, Hölder-Pichler-Tempsky, Wien, pp. 147–171.
Feferman, S., G. Kreisel, and S. Orey: 1962, ‘1–Consistency and Faithful Interpretations', Archiv für Mathematische Logik und Grundlagenforschung 6, 52–63.
Gajda, A., M. Krynicki, and L. Szczerba: 1987, ‘A Note on Syntactical and Semantical Functions', Studia Logica 46, 177–185.
Gajda, A.: 1988, ‘The Adequacy Condition as a Definition of Elementary Interpretation', Studia Logica 47, 57–69.
Gödel: 1931, ‘Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I', Monatshefte für Mathematik und Physik 38, 173–198.
Hájek, P. and M. Hájkova: 1972, ‘On Interpretability in Theories Containing Arithmetic', Fundamenta Mathematicae 76, 131–137.
Hájek, P. and P. Pudlák: 1993, Metamathematics of First-Order Arithmetic, Springer-Verlag, Berlin.
Hellman, G. and F. W. Thompson: 1975, ‘Physicalism: Ontology, Determination, and Reduction', Journal of Philosophy 72, 551–564.
Hooker, C.: 1981, ‘Towards a General Theory of Reduction', Dialogue XX, 1–3, 38–59, 201–236, 496–529.
Jongh de, D. and F. Veltman: 1990, ‘Provability Logics for Relative Interpretability', in P. P. Petkov (ed.), Mathematical Logic, Plenum Press, New York, pp. 31–42.
Kaye, R.: 1991, Models of Peano Arithmetic, Clarendon Press, Oxford.
Kreisel, G.: 1968, ‘A Survey of Proof Theory', Journal of Symbolic Logic 33, 321–388.
Kreisel, G. and A. Levy: 1968, ‘Reflection Principles and Their Use for Establishing the Complexity of Axiomatic Systems', Zeitschrift für mathematische Logik und Grundlagen der Mathematik 14, 97–142.
Kunen, K.: 1980, Set Theory, North-Holland, Amsterdam.
Lindström, P.: 1979, 'some Results on Interpretability', in Proceedings of the 5th Scandinavian Logic Symposium, 1979, Aalborg, pp. 329–361.
Lindström, P.: 1984a, ‘On Faithful Interpretability', in M. Richter et.al. (eds), '83, Springer, Berlin, pp. 279–288.
Lindström, P.: 1984b, ‘On Certain Lattices of Degrees of Interpretability', Notre Dame Journal of Formal Logic 25, 127–140.
Lindström, P.: 1997, Aspects of Incompleteness, Springer, Berlin.
Meseguer, J.: 1989, ‘General Logics', in H. D. Ebbinghaus et al. (eds), '87, Springer, Berlin, pp. 275–329.
Montague, R.: 1962, ‘Theories Incomparable with Respect to Relative Interpretability', Journal of Symbolic Logic 27, 195–211.
Montague, R.: 1965, ‘Interpretability in Terms ofModels', Indagationes Mathematicae 27, 467–476.
Mycielski, J.: 1977, ‘A Lattice of Interpretability Types of Theories', Journal of Symbolic Logic 42, 297–305.
Mycielski, J., P. Pudlák, and A. Stern: 1990, A Lattice of Chapters of Mathematics (Interpretations between Theorems), Memoirs of the American Mathematical Society, Vol. 84, No. 426, American Mathematical Society, Providence.
Orey, S.: 1961, ‘Relative Interpretations', Journal of Symbolic Logic 7, 146–153.
Pour-El, M. B. and S. Kripke: 1967, ‘Deduction-Preserving “Recursive Isomorphisms” between Theories', Fundamenta Mathematicae 61, 141–163.
Pudlák, P.: 1983, ‘Some Prime Elements in the Lattice of Interpretability Types', Transactions of the American Mathematical Society 280, 255–275.
Pudlák, P.: 1985, ‘Cuts, Consistency Statements and Interpretability', Journal of Symbolic Logic 50, 423–441.
Schaffner, K.: 1967, ‘Approaches to Reduction', Philosophy of Science 34, 137–147.
Schroeder-Heister, P. and F. Schaefer: 1989, ‘Reduction, Representation and Commensurability of Theories', Philosophy of Science 56, 130–157.
Smory´nski, C.: 1985a, Self-Reference and Modal Logic, Springer, Berlin.
Smory´nski, C.: 1985b, ‘Nonstandard Models and Related Developments', in L. Harrington et al. (eds), Harvey Friedman's Research on the Foundations of Mathematics, North-Holland, Amsterdam.
Solovay, R. M.: 1976, ‘Provability Interpretations of Modal Logic', Israel Journal of Mathematics 25, 287–304.
Suppes, P.: 1957, Introduction to Logic, Princeton.
Szczerba, L.: 1977, ‘Interpretability of Elementary Theories', in R. Butts and J. Hintikka (eds), Logic, Foundations of Mathematics and Computing Theory, Reidel, Dordrecht, pp. 129–145.
Szczerba, L.: 1980, ‘Interpretations with Parameters', Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 26, 35–39.
Tarski, A., A. Mostowski, and R. M. Robinson: 1953, Undecidable Theories, North-Holland, Amsterdam.
Tarski, A.: 1956, Logic, Semantics, Metamathematics, Clarendon Press, Oxford.
Visser, A.: 1990, ‘Interpretability Logic', in P. P. Petkov (ed.), Mathematical Logic, Plenum Press, New York, pp. 175–208.
Visser, A.: 1997, ‘An Overview of Interpretability Logic', Preprint, University of Utrecht.
Zambella, D.: ‘On the Proofs of Arithmetical Completeness for Interpretability Logic', Notre Dame Journal of Formal Logic 33, 542–551.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Niebergall, KG. On The Logic Of Reducibility: Axioms And Examples. Erkenntnis 53, 27–61 (2000). https://doi.org/10.1023/A:1005692729370
Issue Date:
DOI: https://doi.org/10.1023/A:1005692729370