Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-18T14:56:14.209Z Has data issue: false hasContentIssue false
  • English
  • Français

SUSZKO’S PROBLEM: MIXED CONSEQUENCE AND COMPOSITIONALITY

Published online by Cambridge University Press:  15 February 2019

EMMANUEL CHEMLA  and
PAUL ÉGRÉ
EMMANUEL CHEMLA*
Affiliation:
École normale supérieure, PSL University, EHESS, CNRS
PAUL ÉGRÉ*
Affiliation:
École normale supérieure, PSL University, EHESS, CNRS
*
*LABORATOIRE DE SCIENCES COGNITIVES ET PSYCHOLINGUISTIQUE DÉPARTEMENT D’ÉTUDES COGNITIVES ENS, PSL UNIVERSITY, EHESS, CNRS 75005 PARIS, FRANCE E-mail: [email protected]
†INSTITUT JEAN NICOD DÉPARTEMENT D’ÉTUDES COGNITIVES & DÉPARTEMENT DE PHILOSOPHIE ENS, PSL UNIVERSITY, EHESS, CNRS 75005 PARIS, FRANCE E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Suszko’s problem is the problem of finding the minimal number of truth values needed to semantically characterize a syntactic consequence relation. Suszko proved that every Tarskian consequence relation can be characterized using only two truth values. Malinowski showed that this number can equal three if some of Tarski’s structural constraints are relaxed. By so doing, Malinowski introduced a case of so-called mixed consequence, allowing the notion of a designated value to vary between the premises and the conclusions of an argument. In this article we give a more systematic perspective on Suszko’s problem and on mixed consequence. First, we prove general representation theorems relating structural properties of a consequence relation to their semantic interpretation, uncovering the semantic counterpart of substitution-invariance, and establishing that (intersective) mixed consequence is fundamentally the semantic counterpart of the structural property of monotonicity. We use those theorems to derive maximum-rank results proved recently in a different setting by French and Ripley, as well as by Blasio, Marcos, and Wansing, for logics with various structural properties (reflexivity, transitivity, none, or both). We strengthen these results into exact rank results for nonpermeable logics (roughly, those which distinguish the role of premises and conclusions). We discuss the underlying notion of rank, and the associated reduction proposed independently by Scott and Suszko. As emphasized by Suszko, that reduction fails to preserve compositionality in general, meaning that the resulting semantics is no longer truth-functional. We propose a modification of that notion of reduction, allowing us to prove that over compact logics with what we call regular connectives, rank results are maintained even if we request the preservation of truth-functionality and additional semantic properties.

Keywords

03B4703B5003G27Suszko’s thesistruth valuelogical consequencemixed consequencecompositionalitytruth-functionalitymany-valued logicalgebraic logicsubstructural logicsregular connectives
Type
Research Article
Information
The Review of Symbolic Logic , Volume 12 , Issue 4 , December 2019 , pp. 736 - 767
Copyright
Copyright © Association for Symbolic Logic 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

Andréka, H., Németi, I., & Sain, I. (2001). Algebraic logic. In Gabbay, D. M., and Guenthner, F., editors. Handbook of Philosophical Logic, Vol. 2. Dordrecht: Springer, pp. 133–247.CrossRefGoogle Scholar
Béziau, J.-Y. (2001). Sequents and bivaluations. Logique et Analyse, 44(176), 373–394.Google Scholar
Blasio, C., Marcos, J., & Wansing, H. (2018). An inferentially many-valued two-dimensional notion of entailment. Bulletin of the Section of Logic, 46, 233–262.CrossRefGoogle Scholar
Blok, W. J. & Pigozzi, D. (1989). Algebraizable Logics, Vol. 77, Number 396. Providence, RI: American Mathematical Society.Google Scholar
Bloom, S. L., Brown, D. J., & Suszko, R. (1970). Some theorems on abstract logics. Algebra and Logic, 9(3), 165–168.CrossRefGoogle Scholar
Caleiro, C., Carnielli, W. A., Coniglio, M. E., & Marcos, J. (2003). Dyadic semantics for many-valued logics. Preprint. Available at: http://wslc.math.ist.utl.pt/ftp/pub/CaleiroC/03-CCCM-dyadic2.pdf.Google Scholar
Caleiro, C. & Marcos, J. (2012). Many-valuedness meets bivalence: Using logical values in an effective way. Multiple-Valued Logic and Soft Computing, 19(1–3), 51–70.Google Scholar
Caleiro, C., Marcos, J., & Volpe, M. (2015). Bivalent semantics, generalized compositionality and analytic classic-like tableaux for finite-valued logics. Theoretical Computer Science, 603, 84–110.CrossRefGoogle Scholar
Chemla, E. & Égré, P. (2019). From many-valued consequence to many-valued connectives. Synthese, to appear.CrossRefGoogle Scholar
Chemla, E., Égré, P., & Spector, B. (2017). Characterizing logical consequence in many-valued logic. Journal of Logic and Computation, 27(7), 2193–2226.Google Scholar
Cobreros, P., Égré, P., Ripley, D., & van Rooij, R. (2012a). Tolerance and mixed consequence in the s’valuationist setting. Studia Logica, 100(4), 855–877.CrossRefGoogle Scholar
Cobreros, P., Égré, P., Ripley, D., & van Rooij, R. (2012b). Tolerant, classical, strict. Journal of Philosophical Logic, 41(2), 347–385.CrossRefGoogle Scholar
Cobreros, P., Égré, P., Ripley, D., & van Rooij, R. (2018). Tolerance and degrees of truth. Manuscript.Google Scholar
Font, J. M. (1991). On the Leibniz congruences. Algebraic Methods in Logic and Computer Science, Vol. 28. Banach Center Publications, pp. 17–34.Google Scholar
Font, J. M. (2003). Generalized matrices in abstract algebraic logic. In Hendricks, V. and Malinowski, J., editors. Trends in Logic, Vol. 21. Dordrecht: Springer, pp. 57–86.CrossRefGoogle Scholar
Font, J. M. (2009). Taking degrees of truth seriously. Studia Logica, 91(3), 383–406.CrossRefGoogle Scholar
Frankowski, S. (2004). Formalization of a plausible inference. Bulletin of the Section of Logic, 33(1), 41–52.Google Scholar
French, R. & Ripley, D. (2018). Valuations: bi, tri, and tetra. Studia Logica, https://doi.org/10.1007/s11225-018-9837-1.Google Scholar
Gentzen, G. (1964 (1935)). Investigations into logical deduction. American Philosophical Quarterly, 1(4), 288–306. Original Publication in Mathematische Zeitschrift, 39(1), 176–210.Google Scholar
Gödel, K. (1932). On the intuitionistic propositional calculus. In Feferman, S., Dawson, J., Kleene, S., Moore, G., Solovay, R., and van Heijenoort, J., editors. Kurt Gödel, Collected Works, Vol. 1. Oxford: Clarendon Press, pp. 223–225.Google Scholar
Humberstone, L. (1988). Heterogeneous logic. Erkenntnis, 29(3), 395–435.CrossRefGoogle Scholar
Jansana, R. (2016). Algebraic propositional logic. In Zalta, E. N., editor. The Stanford Encyclopedia of Philosophy (Winter 2016 Edition). https://plato.stanford.edu/entries/logic-algebraic-propositional/.Google Scholar
Lahav, O. & Zohar, Y. (2018). From the subformula property to cut-admissibility in propositional sequent calculi. Journal of Logic and Computation, 28(6), 1341–1366.CrossRefGoogle Scholar
Malinowski, G. (1990). Q-consequence operation. Reports on Mathematical Logic, 24, 49–54.Google Scholar
Marcos, J. (2009). What is a nontruth-functional logic? Studia Logica, 92(2), 215.CrossRefGoogle Scholar
Ripley, D. (2017). On the ‘transitivity’ of consequence relations. Journal of Logic and Computation, 28(2), 433–450.CrossRefGoogle Scholar
Scott, D. (1974). Completeness and axiomatizability in many-valued logic. Proceedings of the Tarski Symposium, Vol. 25. Providence, RI: American Mathematical Society, pp. 411–436.CrossRefGoogle Scholar
Shoesmith, D. J. & Smiley, T. J. (1978). Multiple-Conclusion Logic. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Shramko, Y. & Wansing, H. (2011). Truth and Falsehood: An Inquiry into Generalized Logical Values, Trends in Logic, Vol. 36. Dordrecht: Springer.Google Scholar
Smith, N. J. J. (2008). Vagueness and Degrees of Truth. Oxford: Oxford University Press.CrossRefGoogle Scholar
Surma, S. J. (1982). On the origin and subsequent applications of the concept of the Lindenbaum algebra. Studies in Logic and the Foundations of Mathematics, 104, 719–734.CrossRefGoogle Scholar
Suszko, R. (1975). Remarks on Łukasiewicz’s three-valued logic. Bulletin of the Section of Logic, 3–4, 87–89.Google Scholar
Suszko, R. (1977). The Fregean axiom and Polish mathematical logic in the 1920s. Studia Logica, 36(4), 377–380.CrossRefGoogle Scholar
Tarski, A. (1930). On some fundamental concepts of metamathematics. In Corcoran, J., editor. Logic, Semantics, Metamathematics. Indianapolis, IN: Hackett Publishing, pp. 30–37.Google Scholar
Tsuji, M. (1998). Many-valued logics and Suszko’s thesis revisited. Studia Logica, 60(2), 299–309.CrossRefGoogle Scholar
Wansing, H. & Shramko, Y. (2008). Suszko’s thesis, inferential many-valuedness, and the notion of a logical system. Studia Logica, 88(3), 405–429.CrossRefGoogle Scholar
Wójcicki, R. (1973). Matrix approach in methodology of sentential calculi. Studia Logica, 32(1), 7–37.CrossRefGoogle Scholar
Wójcicki, R. (1988). Theory of Logical Calculi: Basic Theory of Consequence Operations, Synthese Library, Vol. 199. Dordrecht: Kluwer.CrossRefGoogle Scholar