Complete Axiomatization of a Relative Modal Logic with Composition and Intersection

complete axiomatization fragment of propositional dynamic logic with intersection modal operators relational structure relative modal logic with composition and intersection

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70)

Review text

Considering the question of the complete axiomatization of a \(PDL\) with intersection, we have to face the fact that neither the transitive closure of one binary relation nor the intersection of two binary relations are modally definable. This problem leads to the present impossibility of carrying out the plan of a complete axiomatization of a \(PDL\) with intersection. Consequently, we do not claim to be able to realize this plan and we modestly focus our attention on a fragment of \(PDL\) with intersection. The linguistic basis of this fragment is the propositional calculus enlarged with a family of modal operators of the form \([\alpha]\) where \(\alpha\) is a program in \(\Pi_c\) composed in the following way, for every \(\alpha,\beta\in \Pi_c\): \(\alpha;\beta\in\Pi_c\), \(\alpha\wedge\beta\in \Pi_c\). Semantically, the program \(\alpha\) in \(\Pi_c\) still corresponds to the binary relation \(R(\alpha)\) between the states of some universe \(W\), seeing that \(R(\alpha;\beta)= R(\alpha)\circ R(\beta)\), \(R(\alpha\wedge\beta)= R(\alpha)\cap R(\beta)\). The axiomatization of this fragment of \(PDL\) with intersection is presented in section 4, whereas the proof of the completeness of this axiomatization is organized in sections 6 and 7. Section 6 shows that if a formula \(A\) is consistent with the considered axiomatical presentation of our relative modal logic with composition and intersection then there exists a universe \(W\) and, for every \(\alpha\in\Pi_e\), a binary relation \(R(\alpha)\) between the states of \(W\) such that \(R(\alpha;\beta)\supseteq R(\alpha)\circ R(\beta)\), \(R(\alpha\wedge \beta)= R(\alpha)\cap R(\beta)\) and there exists a state \(x\in W\) such that \(A\) is true in \(x\). However, it is quite possible that there exist \(\alpha,\beta\in \Pi_c\) and there exist \(x,z\in W\) such that \(x R(\alpha;\beta) z\) and, for every \(y\in W\), either \(x R(\alpha) y\) or \(y R(\beta) z\) and section 7 proves that the relational structure \((W,R)\) an be transformed into a relational structure \((W_\omega, R_\omega)\) such that \(R_\omega(\alpha; \beta)= R_\omega(\alpha)\circ R_\omega(\beta)\), \(R_\omega(\alpha\wedge \beta)= R_\omega(\alpha)\cap R_\omega(\beta)\) and there exists a state \(x\in W_\omega\) such that \(A\) is true in \(x\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Complete Axiomatization of a Relative Modal Logic with Composition and Intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4236070)