×

New consecution calculi for \(R^{t}_{\to}\). (English) Zbl 1345.03046

Summary: The implicational fragment of the logic of relevant implication, \(R_{\to}\) is one of the oldest relevance logics and in 1959 was shown by Kripke to be decidable. The proof is based on \(LR_{\to}\), a Gentzen-style calculus. In this paper, we add the truth constant \(\mathbf{t} \text{ to } LR_{\to}\), but more importantly we show how to reshape the sequent calculus as a consecution calculus containing a binary structural connective, in which permutation is replaced by two structural rules that involve \(\mathbf{t}\). This calculus, \(LT^{\circ{\mathbf t}_{\to}}\), extends the consecution calculus \(LT_{\to}^{\mathbf{t}}\) formalizing the implicational fragment of ticket entailment. We introduce two other new calculi as alternative formulations of \(R_{\to}^{\mathbf{t}}\). For each new calculus, we prove the cut theorem as well as the equivalence to the original Hilbert-style axiomatization of \(R_{\to}^{\mathbf{t}}\). These results serve as a basis for our positive solution to the long open problem of the decidability of \(T_{\to}\), which we present in another paper.

MSC:

03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
03F05 Cut-elimination and normal-form theorems
03B25 Decidability of theories and sets of sentences
03F52 Proof-theoretic aspects of linear logic and other substructural logics

References:

[1] Ackermann, W., “Begründung einer strengen Implikation,” Journal of Symbolic Logic , vol. 21 (1956), pp. 113-28. · Zbl 0072.00106 · doi:10.2307/2268750
[2] Anderson, A. R., “Entailment shorn of modality” (abstract), Journal of Symbolic Logic , vol. 25 (1960), p. 388.
[3] Anderson, A. R., and N. D. Belnap, Entailment. The Logic of Relevance and Necessity , Vol. I, Princeton University Press, Princeton, 1975. · Zbl 0323.02030
[4] Anderson, A. R., N. D. Belnap, and J. M. Dunn, Entailment. The Logic of Relevance and Necessity , Vol. II, Princeton University Press, Princeton, 1992. · Zbl 0921.03025
[5] Belnap, N. D., and J. R. Wallace, “A decision procedure for the system \(E_{\overline{I}}\) of entailment with negation,” Technical Report 11, Contract No. SAR/609 (16), Office of Naval Research, New Haven, 1961. · Zbl 0143.24902
[6] Belnap, N. D., and J. R. Wallace, “A decision procedure for the system \(E_{\overline{I}}\) of entailment with negation,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik , vol. 11 (1965), pp. 277-89. · Zbl 0143.24902 · doi:10.1002/malq.19650110403
[7] Bimbó, K., “Admissibility of cut in \({LC}\) with fixed point combinator,” Studia Logica , vol. 81 (2005), pp. 399-423. · Zbl 1089.03012 · doi:10.1007/s11225-005-4651-y
[8] Bimbó, K., “Types of I-free hereditary right maximal terms,” Journal of Philosophical Logic , vol. 34 (2005), pp. 607-20. · Zbl 1089.03011 · doi:10.1007/s10992-005-2831-x
[9] Bimbó, K., “\(LE^{\,t}_{\to}\), \(LR^{^{_{\scriptstyle\circ}}}_{\overset{\scriptscriptstyle\land}{\scriptscriptstyle\sim}}\), \(LK\) and cutfree proofs,” Journal of Philosophical Logic , vol. 36 (2007), pp. 557-70. · Zbl 1129.03033 · doi:10.1007/s10992-007-9048-0
[10] Bimbó, K., “Relevance logics,” pp. 723-89 in Philosophy of Logic , edited by D. Jacquette, vol. 5 of Handbook of the Philosophy of Science , Elsevier (North-Holland), Amsterdam, 2007.
[11] Bimbó, K., and J. M. Dunn, Generalized Galois Logics: Relational Semantics of Nonclassical Logical Calculi , vol. 188 of CSLI Lecture Notes , CSLI Publications, Stanford, 2008. · Zbl 1222.03001
[12] Bimbó, K., and J. M. Dunn, “From relevant implication to ticket entailment” (abstract), Bulletin of Symbolic Logic , vol. 18 (2012), p. 288. · Zbl 1345.03046
[13] Bimbó, K., and J. M. Dunn, “The decision problem of \(T_{\to}\)” (abstract), to appear in Bulletin of Symbolic Logic . · Zbl 1344.03028
[14] Bimbó, K., and J. M. Dunn, “On the decision problem of \(T_{\to}\),” to appear in Journal of Symbolic Logic . · Zbl 1275.03159
[15] Church, A., “The weak theory of implication,” pp. 22-37 in Kontrolliertes Denken, Untersuchungen zum Logikkalkül und zur Logik der Einzelwissenschaften , edited by A. Menne, A. Wilhelmy, and H. Angsil, Verlag Karl Alber, Munich, 1951.
[16] Ciabattoni, A., and K. Terui, “Towards a semantic characterization of cut-elimination,” Studia Logica , vol. 82 (2006), pp. 95-119. · Zbl 1105.03057 · doi:10.1007/s11225-006-6607-2
[17] Curry, H. B., Foundations of Mathematical Logic , corrected reprint, Dover, New York, 1977. · Zbl 0396.03001
[18] Curry, H. B., J. R. Hindley, and J. P. Seldin, Combinatory Logic, vol. II , Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1972. · Zbl 0242.02029
[19] Došen, K., “The first axiomatization of relevant logic,” Journal of Philosophical Logic , vol. 21 (1992), pp. 339-56. · Zbl 0767.03009 · doi:10.1007/BF00260740
[20] Dunn, J. M., “The Algebra of Intensional Logics,” Ph.D. dissertation, University of Pittsburgh, 1966. · Zbl 0145.45104
[21] Dunn, J. M., “A ‘Gentzen system’ for positive relevant implication” (abstract), Journal of Symbolic Logic , vol. 38 (1973), pp. 356-57.
[22] Dunn, J. M., “Relevance logic and entailment,” pp. 117-224 in Handbook of Philosophical Logic , vol. III, edited by D. Gabbay and F. Guenthner, vol. 166 of Synthese Library , D. Reidel, Dordrecht, 1986. · Zbl 0875.03051
[23] Dunn, J. M., and R. K. Meyer, “Combinators and structurally free logic,” Logic Journal of the IGPL , vol. 5 (1997), pp. 505-37. · Zbl 0878.03008 · doi:10.1093/jigpal/5.4.505
[24] Dunn, J. M., and G. Restall, “Relevance logic,” pp. 1-128 in Handbook of Philosophical Logic , vol. 6, 2nd ed., edited by D. Gabbay and F. Guenthner, Kluwer, Dordrecht, 2002.
[25] Gentzen, G., “Untersuchungen über das logische Schließen, I” Mathematische Zeitschrift , vol. 39 (1935), pp. 176-210. · Zbl 0010.14501 · doi:10.1007/BF01201353
[26] Gentzen, G., “Investigations into logical deduction,” American Philosophical Quarterly , vol. 1 (1964), pp. 288-306.
[27] Kripke, S. A., “The problem of entailment” (abstract), Journal of Symbolic Logic , vol. 24 (1959), p. 324.
[28] Mares, E. D., and R. K. Meyer, “Relevant logics,” pp. 280-308 in The Blackwell Guide to Philosophical Logic , edited by L. Goble, Blackwell Philosophy Guides, Blackwell, Oxford, UK, 2001. · Zbl 0999.03021
[29] Meyer, R. K., “Intuitionism, entailment, negation,” pp. 168-98 in Truth, Syntax and Modality (Philadelphia, 1970) , edited by H. Leblanc, vol. 68 of Studies in Logic and the Foundations of Mathematics , North-Holland, Amsterdam, 1973. · Zbl 0317.02016
[30] Meyer, R. K., “Sentential constants in \(\mathrm{R}\) and \(\mathrm{R}_{\lnot}\),” Studia Logica , vol. 45 (1986), pp. 301-27. · Zbl 0624.03014 · doi:10.1007/BF00375901
[31] Meyer, R. K., “Improved decision procedures for pure relevant logic,” pp. 191-217 in Logic, Meaning and Computation. Essays in Memory of Alonzo Church , edited by C. A. Anderson and M. Zelëny, vol. 305 of Synthese Library , Kluwer Academic Publishers, Dordrecht, 2001. · Zbl 1023.03014 · doi:10.1007/978-94-010-0526-5_9
[32] Meyer, R. K., and M. A. McRobbie, “Multisets and relevant implication, I,” Australasian Journal of Philosophy , vol. 60 (1982), pp. 107-39.
[33] Meyer, R. K., and M. A. McRobbie, “Multisets and relevant implication, II,” Australasian Journal of Philosophy , vol. 60 (1982), pp. 265-81.
[34] Meyer, R. K., and R. Routley, “Algebraic analysis of entailment, I,” Logique et Analyse (New Series) , vol. 15 (1972), pp. 407-28. · Zbl 0336.02020
[35] Moh, S.-K., “The deduction theorems and two new logical systems,” Methodos , vol. 2 (1950), pp. 56-75.
[36] Orlov, I. E., “The calculus of compatibility of propositions” (in Russian), Matematicheskii Sbornik , vol. 35 (1928), pp. 263-86.
[37] Routley, R., R. K. Meyer, V. Plumwood, and R. T. Brady, Relevant Logics and Their Rivals, Part I , Ridgeview Publishing, Atascadero, Calif., 1982. · Zbl 0579.03011
[38] Schönfinkel, M., “On the building blocks of mathematical logic,” pp. 355-66 in From Frege to Gödel. A Source Book in Mathematical Logic , edited by J. van Heijenoort, Harvard University Press, Cambridge, MA, 1967 (1924).
[39] Urquhart, A., “The undecidability of entailment and relevant implication,” Journal of Symbolic Logic , vol. 49 (1984), pp. 1059-73. · Zbl 0581.03011 · doi:10.2307/2274261
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.