NNIL and ONNILLI
Publication date
2013-06-20
Authors
Bezhanishvili, Nick
Jongh, Dick de
Editors
Advisors
Supervisors
DOI
Document Type
Preprint
Metadata
Show full item recordCollections
License
Abstract
NNIL formulas are propositional formulas that do not allow nesting of implication to the left. These formulas were introduced in [15], where it was shown that NNIL-formulas are (up to frame-equivalence) exactly the formulas that are closed under taking submodels of Kripke models. In this paper we show that NNIL-formulas are exactly those formulas that are closed under taking subframes of (descriptive and Kripke) frames. As a result we obtain that the set of NNIL-formulas coincides with the set of subframe formulas and that subframe logics can be axiomatized by NNIL formulas.
We also introduce ONNILLI formulas, only NNIL to the left of implications, and show that ONNILLI formulas are (up to frame-equivalence) the formulas that are closed under order-preserving images of (descriptive and Kripke) frames. As a result, we obtain that the set of ONNILLI-formulas coincides with the set of stable formulas, which was introduced in [4]. Thus, ONNILLI is a syntactically defined set of formulas that axiomatizes all stable logics. This resolves an open problem of [4].