In modal logic, Sahlqvist formulas are a certain kind of modal formula with remarkable properties. The Sahlqvist correspondence theorem states that every Sahlqvist formula is canonical, and corresponds to a class of Kripke frames definable by a first-order formula. Sahlqvist's definition characterizes a decidable set of modal formulas with first-order correspondents. Since it is undecidable, by Chagrova's theorem, whether an arbitrary modal formula has a first-order correspondent, there are formulas with first-order frame conditions that are not Sahlqvist [Chagrova 1991] (see the examples below). Hence Sahlqvist formulas define only a (decidable) subset of modal formulas with first-order correspondents.
Definition Sahlqvist formulas are built up from implications, where the consequent is positive and the antecedent is of a restricted form.
A boxed atom is a propositional atom preceded by a number (possibly 0) of boxes, i.e. a formula of the form ◻ ⋯ ◻ p {\displaystyle \Box \cdots \Box p} (often abbreviated as ◻ i p {\displaystyle \Box ^{i}p} for 0 ≤ i < ω {\displaystyle 0\leq i<\omega } ). A Sahlqvist antecedent is a formula constructed using ∧, ∨, and ◊ {\displaystyle \Diamond } from boxed atoms, and negative formulas (including the constants ⊥, ⊤). A Sahlqvist implication is a formula A → B, where A is a Sahlqvist antecedent, and B is a positive formula. A Sahlqvist formula is constructed from Sahlqvist implications using ∧ and ◻ {\displaystyle \Box } (unrestricted), and using ∨ on formulas with no common variables.
Examples of Sahlqvist formulas
p → ◊ p {\displaystyle p\rightarrow \Diamond p}
Its first-order corresponding formula is ∀ x R x x {\displaystyle \forall x\;Rxx} , and it defines all reflexive frames
p → ◻ ◊ p {\displaystyle p\rightarrow \Box \Diamond p}
Its first-order corresponding formula is ∀ x ∀ y [ R x y → R y x ] {\displaystyle \forall x\forall y[Rxy\rightarrow Ryx]} , and it defines all symmetric frames
◊ ◊ p → ◊ p {\displaystyle \Diamond \Diamond p\rightarrow \Diamond p} or ◻ p → ◻ ◻ p {\displaystyle \Box p\rightarrow \Box \Box p}
Its first-order corresponding formula is ∀ x ∀ y ∀ z [ ( R x y ∧ R y z ) → R x z ] {\displaystyle \forall x\forall y\forall z[(Rxy\land Ryz)\rightarrow Rxz]} , and it defines all transitive frames
◊ p → ◊ ◊ p {\displaystyle \Diamond p\rightarrow \Diamond \Diamond p} or ◻ ◻ p → ◻ p {\displaystyle \Box \Box p\rightarrow \Box p}
Its first-order corresponding formula is ∀ x ∀ y [ R x y → ∃ z ( R x z ∧ R z y ) ] {\displaystyle \forall x\forall y[Rxy\rightarrow \exists z(Rxz\land Rzy)]} , and it defines all dense frames
◻ p → ◊ p {\displaystyle \Box p\rightarrow \Diamond p}
Its first-order corresponding formula is ∀ x ∃ y R x y {\displaystyle \forall x\exists y\;Rxy} , and it defines all right-unbounded frames (also called serial)
◊ ◻ p → ◻ ◊ p {\displaystyle \Diamond \Box p\rightarrow \Box \Diamond p}
Its first-order corresponding formula is ∀ x ∀ x 1 ∀ z 0 [ R x x 1 ∧ R x z 0 → ∃ z 1 ( R x 1 z 1 ∧ R z 0 z 1 ) ] {\displaystyle \forall x\forall x_{1}\forall z_{0}[Rxx_{1}\land Rxz_{0}\rightarrow \exists z_{1}(Rx_{1}z_{1}\land Rz_{0}z_{1})]} , and it is the Church–Rosser property.
Examples of non-Sahlqvist formulas
◻ ◊ p → ◊ ◻ p {\displaystyle \Box \Diamond p\rightarrow \Diamond \Box p}
This is the McKinsey formula; it does not have a first-order frame condition.
◻ ( ◻ p → p ) → ◻ p {\displaystyle \Box (\Box p\rightarrow p)\rightarrow \Box p}
The Löb axiom is not Sahlqvist; again, it does not have a first-order frame condition.
( ◻ ◊ p → ◊ ◻ p ) ∧ ( ◊ ◊ q → ◊ q ) {\displaystyle (\Box \Diamond p\rightarrow \Diamond \Box p)\land (\Diamond \Diamond q\rightarrow \Diamond q)}
… excerpt ends here. Continue reading the full article.
