Title：Features of (Un)decidable Logics

Speaker：Søren Knudstorp (ILLC, University of Amsterdam)

Time: 2024/04/09 15:10-18:00

Location: Room 313, Teaching Building No.2 (第二教学楼), Peking University

Abstract：

　　This talk will survey some of my recent results on (un)decidability within modal and temporal logic, truthmaker semantics, team semantics, and relevant logic. Motivated by the question of what makes a logic undecidable, the aim is to identify traits of undecidable logics. As a consequence, the presentation will offer more breadth than depth.

　　To begin, we show that the modal logic of any class of semilattices containing (P(N), ∪) is undecidable. This result carries substantial implications, including resolving the open problem concerning the decidability of hyperboolean modal logic, as raised by Goranko and Vakarelov (1999). Furthermore, it establishes (i) the undecidability of the modal (information) logic on semilattices, a problem posed by Bergman (2018) and Jipsen, Eyad Kurd-Misto, and Wimberley (2021) (and by the present author in Knudstorp 2023), and (ii) the undecidability of the temporal logic over lattices considered by X. Wang and Y. Wang (2022).

　　Next, we compare this result with the decidability of team and truthmaker logics, drawing heuristic insights into the factors contributing to the decidability or undecidability of logics.

　　Finally, we turn our attention to the semilattice relevant logic S, introduced by Urquhart (1972). While Urquhart (1984) showed that many relevant logics are undecidable, S eluded these techniques. Eventually, it led Urquhart (2016) to conjecture that S is decidable. Contrary to this conjecture, we show that S is undecidable.

References:

Bergman, Clifford (2018). “Introducing Boolean Semilattices”. In: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science. Outstanding Contributions to Logic. Ed. by Janusz Czelakowski. Springer, pp. 103–130.

Goranko, Valentin and Dimiter Vakarelov (1999). “Hyperboolean Algebras and Hyperboolean Modal Logic”. In: Journal of Applied Non-Classical Logics 9.2-3, pp. 345–368. doi: 10.1080/11663081.1999.10510971.

Jipsen, Peter, M. Eyad Kurd-Misto, and James Wimberley (2021). “On the Representation of Boolean Magmas and Boolean Semilattices”. In: Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic. Ed. by Judit Madarász and Gergely Székely. Cham: Springer International Publishing, pp. 289–312. doi: 10.1007/978-3-030-64187-0_12.

Knudstorp, Søren Brinck (2023). “Logics of truthmaker semantics: comparison, compactness and decidability”. In: Synthese 202. doi: 10.1007/s11229-023-04401-1.

Urquhart, Alasdair (1972). “Semantics for relevant logics”. In: Journal of Symbolic Logic 37, pp. 159–169.

— (1984). “The undecidability of entailment and relevant implication”. In: Journal of Symbolic Logic 49, pp. 1059–1073.

Urquhart, Alasdair (2016). “Relevance Logic: Problems Open and Closed”. In: The Australasian Journal of Logic 13.

Wang, Xiaoyang and Yanjing Wang (2022). “Tense Logics over Lattices”. In: Logic, Language, Information, and Computation. WoLLIC 2022. Ed. by Agata Ciabattoni, Elaine Pimentel, and Ruy J. G. B. de Queiroz. Springer, Cham.