×

Complete additivity and modal incompleteness. (English) Zbl 1532.03026

Summary: In this article, we tell a story about incompleteness in modal logic. The story weaves together an article of J. F. A. K. van Benthem [Theoria 45, 63–77 (1979; Zbl 0452.03013)], and a longstanding open question: whether every normal modal logic can be characterized by a class of completely additive modal algebras, or as we call them, \(\mathcal{V}\)-baos. Using a first-order reformulation of the property of complete additivity, we prove that the modal logic that starred in van Benthem’s article resolves the open question in the negative. In addition, for the case of bimodal logic, we show that there is a naturally occurring logic that is incomplete with respect to \(\mathcal{V}\)-baos, namely the provability logic \(GLB\) [G. K. Dzhaparidze, in: Proceedings of the 4th Soviet-Finnish symposium on logic, 1985. Tbilisi: Metsniereba. 16–48 (1988; Zbl 0725.03038); G. Boolos, The logic of provability. Cambridge: Cambridge University Press (1993; Zbl 0891.03004)]. We also show that even logics that are unsound with respect to such algebras do not have to be more complex than the classical propositional calculus. On the other hand, we observe that it is undecidable whether a syntactically defined logic is \(\mathcal{V}\)-complete. After these results, we generalize the Blok Dichotomy [W. J. Blok, On the degree of incompleteness of modal logic and the covering relation in the lattice of modal logics. Techn. Rep., University of Amsterdam (1978)] to degrees of \(\mathcal{V}\)-incompleteness. In the end, we return to van Benthem’s theme of syntactic aspects of modal incompleteness.

MSC:

03B45 Modal logic (including the logic of norms)
06E25 Boolean algebras with additional operations (diagonalizable algebras, etc.)
03F45 Provability logics and related algebras (e.g., diagonalizable algebras)
03B25 Decidability of theories and sets of sentences

Software:

SQEMA

References:

[1] AndrékaH., GyenisZ., & NémetiI. (2016). Ultraproducts of continuous posets. Algebra Universalis, 76(2), 231-235. · Zbl 1397.06007
[2] AndrékaH., NémetiI., & SainI. (2001). Algebraic logic. In GabbayD. M. and GuenthnerF., editors. Handbook of Philosophical Logic, second edition. Dordrecht: Kluwer, pp. 133-249. · Zbl 1003.03536
[3] BeklemishevL. (2011). Ordinal completeness of bimodal provability logic GLB. In BezhanishviliN., LöbnerS., SchwabeK., & SpadaL., editors. Logic, Language, and Computation: 8th International Tbilisi Symposium on Logic, Language, and Computation, TbiLLC 2009, Bakuriani, Georgia, September 21-25, 2009. Revised Selected Papers. Heidelberg: Springer, pp. 1-15. · Zbl 1341.03090
[4] BeklemishevL., BezhanishviliG., & IcardT. (2010). On topological models of GLP. In SchindlerR., editor. Ways of Proof Theory. Ontos Mathematical Logic, Vol. 2. Heusenstamm: Ontos Verlag, pp. 135-155. · Zbl 1223.03047
[5] BeklemishevL. & GabelaiaD. (2014). Topological interpretations of provability logic. In BezhanishviliG., editor. Leo Esakia on Duality in Modal and Intuitionistic Logics. Outstanding Contributions to Logic, Vol. 4. Dordrecht: Springer, pp. 257-290. · Zbl 1352.03070
[6] van BenthemJ. (1978). Two simple incomplete modal logics. Theoria, 44(1), 25-37. · Zbl 0405.03010
[7] van BenthemJ. (1979). Syntactic aspects of modal incompleteness theorems. Theoria, 45(2), 63-77. · Zbl 0452.03013
[8] van BenthemJ. (1983). Modal Logic and Classical Logic. Milan: Bibliopolis. · Zbl 0639.03014
[9] van BenthemJ. (2001). Correspondence theory. In GabbayD. and GuenthnerF., editors. Handbook of Philosophical Logic, second edition, Vol. 3. Dordrecht: Springer, pp. 325-408. · Zbl 1003.03518
[10] BezhanishviliG. & HollidayW. H. (2019). A semantic hierarchy for intuitionistic logic. Indagationes Mathematicae, 30(3), 403-469. · Zbl 1539.03032
[11] BezhanishviliN. & GhilardiS. (2014). The bounded proof property via step algebras and step frames. Annals of Pure Applied Logic, 165(12), 1832-1863. · Zbl 1361.03013
[12] BezhanishviliN., & KurzA. (2007). Free modal algebras: A coalgebraic perspective. In MossakowskiT., MontanariU., and HaveraaenM., editors. Algebra and Coalgebra in Computer Science. Lectures Notes in Computer Science, Vol. 4624. Berlin: Springer, pp. 143-157. · Zbl 1214.03052
[13] BlackburnP., de RijkeM., & VenemaY. (2001). Modal Logic. Cambridge Tracts in Theoretical Computer Science, Vol. 53. Cambridge: Cambridge University Press. · Zbl 0988.03006
[14] BlokW. J. (1978). On the degree of incompleteness of modal logic and the covering relation in the lattice of modal logics. Technical Report 78-07, University of Amsterdam. · Zbl 0418.03012
[15] BlokW. J. & KöhlerP. (1983). Algebraic semantics for quasi-classical modal logics. The Journal of Symbolic Logic, 48(4), 941-964. · Zbl 0562.03011
[16] BlokW. J. & PigozziD. (1989). Algebraizable Logics. Memoirs of the American Mathematical Society, no. 396. Providence, RI: American Mathematical Society. · Zbl 0664.03042
[17] BoolosG. (1993). The Logic of Provability. Cambridge: Cambridge University Press. · Zbl 0891.03004
[18] BoolosG. & SambinG. (1985). An incomplete systems of modal logic. Journal of Philosophical Logic, 14(4), 351-358. · Zbl 0589.03005
[19] BuszkowskiW. (1986). Embedding Boolean structures into atomic Boolean algebras. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 32, 227-228. · Zbl 0601.03025
[20] BuszkowskiW. (2004). A representation theorem for co-diagonalizable algebras. Reports on Mathematical Logic, 38, 13-22. · Zbl 1062.03063
[21] ten CateB. & LitakT. (2007). The importance of being discrete. Technical Report PP-2007-39, Institute for Logic, Language and Computation, University of Amsterdam.
[22] ChagrovA. V. (1990). Undecidable properties of extensions of a provability logic. II. Algebra and Logic, 29(5), 406-413. · Zbl 0729.03009
[23] ChagrovA. V. & RybakovM. N. (2003). How many variables does one need to prove PSPACE-hardness of modal logics? In BalbianiP., SuzukiN.-Y., WolterF., and ZakharyaschevM., editors. Advances in Modal Logic, Vol. 4. London: King’s College Publications, pp. 71-82. · Zbl 1076.03012
[24] ChagrovA. V. & ZakharyaschevM. (1993). The undecidability of the disjunction property of propositional logics and other related problems. The Journal of Symbolic Logic, 58(3), 967-1002. · Zbl 0799.03009
[25] ChagrovA. V. & ZakharyaschevM. (1997). Modal Logic. Oxford Logic Guides. Oxford: Clarendon Press. · Zbl 0871.03007
[26] ChagrovaL. A. (1998). On the degree of neighbourhood incompleteness of normal modal logics. In KrachtM., de RijkeM., WansingH., and ZakharyaschevM., editors. Advances in Modal Logic, Vol. 1. Stanford: CSLI Publications, pp. 63-72. · Zbl 0911.03008
[27] CirsteaC., KurzA., PattinsonD., SchröderL., & VenemaY. (2011). Modal logics are coalgebraic. The Computer Journal, 54(1), 31-41.
[28] ConradieW., GhilardiS., & PalmigianoA. (2014). Unified correspondence. In BaltagA. and SmetsS., editors. Johan van Benthem on Logic and Information Dynamics. Dordrecht: Springer, pp. 933-975. · Zbl 1344.03023
[29] ConradieW., GorankoV., & VakarelovD. (2006). Algorithmic correspondence and completeness in modal logic. I. The core algorithm SQEMA. Logical Methods in Computer Science, 2(1), 1-26. · Zbl 1126.03018
[30] CoumansD. C. S. & van GoolS. J. (2013). On generalizing free algebras for a functor. Journal of Logic and Computation, 23(3), 645-672. · Zbl 1325.08004
[31] CresswellM. J. (1984). An incomplete decidable modal logic. The Journal of Symbolic Logic, 49(2), 520-527. · Zbl 0591.03006
[32] CzelakowskiJ. (2001). Protoalgebraic Logics. Trends in Logic. Dordrecht: Springer. · Zbl 0984.03002
[33] DošenK. (1989). Duality between modal algebras and neighborhood frames. Studia Logica, 48(2), 219-234. · Zbl 0685.03013
[34] DziobiakW. (1978). A note on incompleteness of modal logics with respect to neighbourhood semantics. Bulletin of the Section of Logic, 7(4), 185-190. · Zbl 0415.03020
[35] FineK. (1974). An incomplete logic containing S4. Theoria, 40(1), 23-29. · Zbl 0287.02011
[36] FineK. (1975, 04). Normal forms in modal logic. Notre Dame Journal of Formal Logic, 16(2), 229-237. · Zbl 0245.02025
[37] FontJ. M. (2006). Beyond Rasiowa’s algebraic approach to non-classical logic. Studia Logica, 82(2), 179-209. · Zbl 1097.03062
[38] FontJ. M., JansanaR., & PigozziD. (2003). A survey of abstract algebraic logic. Studia Logica, 74(1), 13-97. · Zbl 1057.03058
[39] FontJ. M., JansanaR., & PigozziD. (2009). Update to “A survey of abstract algebraic logic”. Studia Logica, 91(1), 125-130. · Zbl 1162.03322
[40] GargovG. & GorankoV. (1993). Modal logic with names. Journal of Philosophical Logic, 22(6), 607-636. · Zbl 0793.03012
[41] GhilardiS. (1995). An algebraic theory of normal forms. Annals of Pure and Applied Logic, 71(3), 189-245. · Zbl 0815.03010
[42] GhilardiS. & MeloniG. (1997). Constructive canonicity in non-classical logic. Annals of Pure and Applied Logic, 86(1), 1-32. · Zbl 0949.03019
[43] GoldblattR. (2001). Persistence and atomic generation for varieties of Boolean algebras with operators. Studia Logica, 68(2), 155-171. · Zbl 0996.06008
[44] GoldblattR. (2003). Mathematical modal logic: A view of its evolution. Journal of Applied Logic, 1(5-6), 309-392. · Zbl 1041.03015
[45] HollidayW. H. (2014). Partiality and adjointness in modal logic. In GoréR., KooiB., and KuruczA., editors. Advances in Modal Logic, Vol. 10. London: College Publications, pp. 313-332. · Zbl 1385.03019
[46] HollidayW. H. (2015). Possibility frames and forcing for modal logic. UC Berkeley Working Paper in Logic and the Methodology of Science. February 2018 version. Available at: https://escholarship.org/uc/item/0tm6b30q.
[47] HollidayW. H. & LitakT. (2018). One modal logic to rule them all? In BezhanishviliG., D’AgostinoG., MetcalfeG., and StuderT., editors. Advances in Modal Logic, Vol. 12. London: College Publications, pp. 367-386. · Zbl 1418.03087
[48] HopcroftJ. E., MotwaniR., & UllmanJ. D. (2003). Introduction to Automata Theory, Languages, and Computation (second edition). Boston: Addison-Wesley.
[49] HumberstoneL. (2011). The Connectives. Cambridge, MA: MIT Press. · Zbl 1242.03002
[50] JansanaR. (2006). Willem Blok’s contribution to abstract algebraic logic. Studia Logica, 83(1), 31-48. · Zbl 1111.03058
[51] JaparidzeG. K. (1988). The polymodal logic of provability. In SmirnovV. A. and BezhanishviliM. N., editors. Intensional Logics and the Logical Structure of Theories: Proceedings of the Fourth Soviet-Finnish Symposium on Logic, Telavi, May 1985. Tbilisi: Metsniereba, pp. 16-48. · Zbl 0725.03038
[52] JipsenP. (1993). Discriminator varieties of Boolean algebras with residuated operators. In Algebraic Methods in Logic and in Computer Science. Banach Center Publications, Vol. 28. Warszawa: Institute of Mathematics, Polish Academy of Sciences, pp. 239-252. · Zbl 0794.06012
[53] JónssonB. & TarskiA. (1951). Boolean algebras with operators. Part I. American Journal of Mathematics, 73(4), 891-939. · Zbl 0045.31505
[54] JónssonB. & TarskiA. (1952). Boolean algebras with operators. Part II. American Journal of Mathematics, 74(1), 127-162. · Zbl 0045.31601
[55] KrachtM. (1999). Tools and Techniques in Modal Logic. Studies in Logic and the Foundations of Mathematics, Vol. 142. Amsterdam: Elsevier. · Zbl 0927.03002
[56] KrachtM. & WolterF. (1991). Properties of independently axiomatizable bimodal logics. The Journal of Symbolic Logic, 56(4), 1469-1485. · Zbl 0743.03013
[57] KrachtM. & WolterF. (1997). Simulation and transfer results in modal logic: A survey. Studia Logica, 59(2), 149-177. · Zbl 0960.03014
[58] KrachtM. & WolterF. (1999). Normal monomodal logics can simulate all others. The Journal of Symbolic Logic, 64(1), 99-138. · Zbl 0972.03019
[59] KurzA. & RosickýJ. (2012). Strongly complete logics for coalgebras. Logical Methods in Computer Science, 8(3:14), 1-32. · Zbl 1263.03063
[60] KuznetsovA. V. (1975). On superintuitionistic logics. In Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1. Montreal, Quebec: Canadian Mathematical Congress, pp. 243-249. · Zbl 0342.02015
[61] LemmonE. J. & ScottD. (1977). The “Lemmon Notes“: An Introduction to Modal Logic, ed. <name name-style=”western”>SegerbergK.. Number 11 in American Philosophical Quarterly Monograph Series. Oxford: Basil Blackwell. · Zbl 0388.03006
[62] LewisD. (1974). Intensional logics without iterative axioms. Journal of Philosophical Logic, 3(4), 457-466. · Zbl 0296.02014
[63] LitakT. (2004). Modal incompleteness revisited. Studia Logica, 76(3), 329-342. · Zbl 1045.03022
[64] LitakT. (2005a). An Algebraic Approach to Incompleteness in Modal Logic. Ph.D. Thesis, Japan Advanced Institute of Science and Technology.
[65] LitakT. (2005b). On notions of completeness weaker than Kripke completeness. In SchmidtR., Pratt-HartmannI., ReynoldsM., and WansingH., editors. Advances in Modal Logic, Vol. 5. London: College Publications, pp. 149-169. · Zbl 1102.03065
[66] LitakT. (2006). Isomorphism via translation. In GovernatoriG., HodkinsonI. M., and VenemaY., editors. Advances in Modal Logic, Vol. 6. London: College Publications, pp. 333-351. · Zbl 1144.03015
[67] LitakT. (2008). Stability of the Blok theorem. Algebra Universalis, 58(4), 385-411. · Zbl 1182.06005
[68] LitakT., PattinsonD., SanoK., & SchröderL. (2012). Coalgebraic predicate logic. In CzumajA., MehlhornK., PittsA., and WattenhoferR., editors. Automata, Languages, and Programming: 39th International Colloquium (ICALP). Lecture Notes in Computer Science, Vol. 7392. Heidelberg: Springer, pp. 299-311. · Zbl 1433.03163
[69] LitakT., PattinsonD., SanoK., & SchröderL. (2018). Model theory and proof theory of coalgebraic predicate logic. Logical Methods in Computer Science, 14(1:22), 1-52. · Zbl 1459.03104
[70] LitakT. & WolterF. (2005). All finitely axiomatizable tense logics of linear time flows are coNP-complete. Studia Logica, 81(2), 153-165. · Zbl 1096.03014
[71] ŁukasiewiczJ. & TarskiA. (1930). Untersuchungen über den Aussagenkalkül. Comptes Rendus des séances de la Societé des Sciences et des Lettres de Varsovie, 23, 30-50. English translation in Tarski 1956. · JFM 57.1319.01
[72] MakinsonD. (1971). Some embedding theorems for modal logic. Notre Dame Journal of Formal Logic, 12(2), 252-254. · Zbl 0193.29301
[73] MossL. S. (2007). Finite models constructed from canonical formulas. Journal of Philosophical Logic, 36(6), 605-640. · Zbl 1132.03007
[74] PittsA. M. (2013). Nominal Sets: Names and Symmetry in Computer Science. Cambridge Tracts in Theoretical Computer Science, Vol. 57. Cambridge: Cambridge University Press. · Zbl 1297.68008
[75] PittsA. M. (2016). Nominal techniques. ACM SIGLOG News, 3(1), 57-72.
[76] RabinM. O. (1969). Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141, 1-35. · Zbl 0221.02031
[77] RasiowaH. (1974). An Algebraic Approach to Non-classical Logics. Amsterdam: North-Holland. · Zbl 0299.02069
[78] RautenbergW., WolterF., & ZakharyaschevM. (2006). Willem Blok and modal logic. Studia Logica, 83(1-3), 15-30. Special issue in memory of Willem Johannes Blok. · Zbl 1105.03020
[79] RiceH. G. (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2), 358-366. · Zbl 0053.00301
[80] SchröderL. (2008). Expressivity of coalgebraic modal logic: The limits and beyond. Theoretical Computer Science, 390(2-3), 230-247. Special issue on Foundations of Software Science and Computational Structures. · Zbl 1132.03008
[81] SchröderL. & PattinsonD. (2010). Rank-1 modal logics are coalgebraic. Journal of Logic and Computation, 20(5), 1113-1147. · Zbl 1266.03032
[82] SegerbergK. (1971). An Essay in Classical Modal Logic. Filosofiska Studier, Vol. 13. Uppsala, Sweden: University of Uppsala. · Zbl 0311.02028
[83] ShapirovskyI. (2008). PSPACE-decidability of Japaridze’s polymodal logic. In ArecesC. and GoldblattR., editors. Advances in Modal Logic, Vol. 7. London: College Publications, pp. 289-304. · Zbl 1244.03073
[84] SimpsonS. G. (2009). Subsystems of Second Order Arithmetic. Perspectives in Logic. New York: Association for Symbolic Logic, Cambridge University Press. · Zbl 1181.03001
[85] SolovayR. M. (1976). Provability interpretations of modal logic. Israel Journal of Mathematics, 25(3), 287-304. · Zbl 0352.02019
[86] SurendonkT. J. (2001). Canonicity for intensional logics with even axioms. The Journal of Symbolic Logic, 66(3), 1141-1156. · Zbl 1049.03021
[87] SuzukiT. (2010, 009). Canonicity results of substructural and lattice-based logics. The Review of Symbolic Logic, 4(1), 1-42.
[88] TarskiA. (1956). Logic, Semantics, Metamathematics: Papers from 1923 to 1938. Oxford: Clarendon Press. Translated by J. H. Woodger. · Zbl 0075.00702
[89] ThomasonS. K. (1972). Semantic analysis of tense logics. The Journal of Symbolic Logic, 37(1), 150-158. · Zbl 0238.02027
[90] ThomasonS. K. (1974a). An incompleteness theorem in modal logic. Theoria, 40(1), 30-34. · Zbl 0287.02012
[91] ThomasonS. K. (1974b). Reduction of tense logic to modal logic. I. The Journal of Symbolic Logic, 39(3), 549-551. · Zbl 0317.02010
[92] ThomasonS. K. (1974c). Reduction of tense logic to modal logic II. Theoria, 40(3), 154-169. · Zbl 0365.02010
[93] ThomasonS. K. (1975a). Categories of frames for modal logic. The Journal of Symbolic Logic, 40(3), 439-442. · Zbl 0317.02012
[94] ThomasonS. K. (1975b). Reduction of second-order logic to modal logic. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 21(1), 107-114. · Zbl 0317.02011
[95] ThomasonS. K. (1982). Undecidability of the completeness problem of modal logic. Banach Center Publications, 9(1), 341-345. · Zbl 0522.03007
[96] VenemaY. (2003). Atomless varieties. The Journal of Symbolic Logic, 68(2), 607-614. · Zbl 1059.03078
[97] VenemaY. (2007). Algebras and coalgebras. In BlackburnP., van BenthemJ., and WolterF., editors. Handbook of Modal Logic. Amsterdam: Elsevier, pp. 331-426.
[98] ŠvejdarV. (2003). The decision problem of provability logic with only one atom. Archive for Mathematical Logic, 42(8), 763-768. · Zbl 1038.03011
[99] WolterF. (1993). Lattices of Modal Logics. Ph.D. Thesis, Fachbereich Mathematik, Freien Universität Berlin.
[100] WolterF. (1996a). Properties of tense logics. Mathematical Logic Quarterly, 42(1), 481-500. · Zbl 0871.03010
[101] WolterF. (1996b). Tense logic without tense operators. Mathematical Logic Quarterly, 42(1), 145-171. · Zbl 0858.03019
[102] WolterF. & ZakharyaschevM. (2006). Modal decision problems. In BlackburnP., van BenthemJ., and WolterF., editors. Handbook of Modal Logic. Amsterdam: Elsevier, pp. 427-489.
[103] ZakharyaschevM., WolterF., & ChagrovA. V. (2001). Advanced modal logic. In GabbayD. M. and GuenthnerF., editors. Handbook of Philosophical Logic, (second edition), Vol. 3. Dordrecht: Springer, pp. 83-266. · Zbl 1003.03516
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.