New constants in two pretabular superintuitionistic logics.

*(English. Russian original)*Zbl 1271.03043
Algebra Logic 50, No. 2, 171-186 (2011); translation from Algebra Logika 50, No. 2, 246-267 (2011).

The paper deals with extensions of intermediate propositional logics, i.e., the logics lying between intuitionistic propositional logic and the classical one in terms of their deductive powers. The set \(\{\,\wedge, \vee, \to, \neg, 0, 1\,\}\) of standard propositional connectives and constants for these logics is extended with a number of new propositional constants \(\varphi_1,\dots, \varphi_n\) each denoting a cone (i.e., a set of worlds which is closed with respect to the accessibility relation) in a corresponding Kripke frame.

Assume that \(L\) is the basic propositional language and that \(\mathcal{L}\) is an intermediate logic over \(L\). Assume, further, that \(L'\) is an extension of \(L\) of the above-mentioned kind and that \(\mathcal{L}'\) is a logic over \(L'\) such that \(\mathcal{L} \subseteq \mathcal{L}'\). Then \(\mathcal{L}'\) might be conservative over \(\mathcal{L}\), but not ‘maximally conservative’ in the sense that there is a formula \(A \in L'\) which can be added to \(\mathcal{L}'\) as a new axiom to yield a still stronger conservative extension of \(\mathcal{L}\). However, if \(\mathcal{L}'\) is not only conservative over \(\mathcal{L}\) but also maximally conservative in this sense, it is called a Novikov-complete extension of \(\mathcal{L}\).

The paper under review deals with the task of enumerating all Novikov-complete extensions of a given intermediate propositional logic in a given variant of the extended language. Since there exists a continuum of different intermediate propositional logics and each of them can be extended in infinitely many ways, it is natural to address this task by taking up different logics one by one starting with the ones that are for some reason more important and visible in the existing literature. And of course, the most natural choice would be to start with some systems from the narrow group of intermediate logics that lie strictly between intuitionistic logic and classical logic and enjoy the Craig interpolation property. It is known [L. L. Maksimova, Algebra Logic 16, 427–455 (1978); translation from Algebra Logika 16, 643–681 (1977; Zbl 0403.03047)] that there are only five such systems and the author in fact takes up two of them: Dummett’s logic (aka the logic of linear frames) and the logic \(L2\), which is basically the logic of two-tiered rooted frames.

For Dummett’s logic the author considers the general case where the basic language is extended with an arbitrary finite number of constants; to arrive at his result, he uses the method of outgrowths and the notion of a universal frame (note that universality of a frame is relative to an extension of the basic language rather than to a given logic over this extension) both of which were introduced earlier in [V. V. Rybakov, Admissibility of logical inference rules. Amsterdam: Elsevier (1997; Zbl 0872.03002); A. D. Yashin, Fundam. Prikl. Mat. 5, No. 3, 903–926 (1999; Zbl 0982.03005)]. It turns out that the family of Novikov-complete extensions of Dummett’s logic in a given version of the extended language is in one-to-one correspondence with the set of root cones of the respective universal frame (which normally has several roots), or, to put it in a different way, this family is in one-to-one correspondence with all maximal distributions of the relations \(=\) (equality) and \(\subset\) (proper inclusion) among the given set of constants.

As for the extensions of \(L2\), the author only considers the language with one extra constant and the result is that there are just five Novikov-complete extensions for \(L2\) in this language. Roughly speaking, we may assume that the new constant is true either (1) in exactly one world, or (2) in every world except for the root, or (3) in every world except for the root and some other world. In addition, we have two degenerate cases where the new constant is equal to one of the basic ones, that is to say, to either \(1\) or \(0\).

Assume that \(L\) is the basic propositional language and that \(\mathcal{L}\) is an intermediate logic over \(L\). Assume, further, that \(L'\) is an extension of \(L\) of the above-mentioned kind and that \(\mathcal{L}'\) is a logic over \(L'\) such that \(\mathcal{L} \subseteq \mathcal{L}'\). Then \(\mathcal{L}'\) might be conservative over \(\mathcal{L}\), but not ‘maximally conservative’ in the sense that there is a formula \(A \in L'\) which can be added to \(\mathcal{L}'\) as a new axiom to yield a still stronger conservative extension of \(\mathcal{L}\). However, if \(\mathcal{L}'\) is not only conservative over \(\mathcal{L}\) but also maximally conservative in this sense, it is called a Novikov-complete extension of \(\mathcal{L}\).

The paper under review deals with the task of enumerating all Novikov-complete extensions of a given intermediate propositional logic in a given variant of the extended language. Since there exists a continuum of different intermediate propositional logics and each of them can be extended in infinitely many ways, it is natural to address this task by taking up different logics one by one starting with the ones that are for some reason more important and visible in the existing literature. And of course, the most natural choice would be to start with some systems from the narrow group of intermediate logics that lie strictly between intuitionistic logic and classical logic and enjoy the Craig interpolation property. It is known [L. L. Maksimova, Algebra Logic 16, 427–455 (1978); translation from Algebra Logika 16, 643–681 (1977; Zbl 0403.03047)] that there are only five such systems and the author in fact takes up two of them: Dummett’s logic (aka the logic of linear frames) and the logic \(L2\), which is basically the logic of two-tiered rooted frames.

For Dummett’s logic the author considers the general case where the basic language is extended with an arbitrary finite number of constants; to arrive at his result, he uses the method of outgrowths and the notion of a universal frame (note that universality of a frame is relative to an extension of the basic language rather than to a given logic over this extension) both of which were introduced earlier in [V. V. Rybakov, Admissibility of logical inference rules. Amsterdam: Elsevier (1997; Zbl 0872.03002); A. D. Yashin, Fundam. Prikl. Mat. 5, No. 3, 903–926 (1999; Zbl 0982.03005)]. It turns out that the family of Novikov-complete extensions of Dummett’s logic in a given version of the extended language is in one-to-one correspondence with the set of root cones of the respective universal frame (which normally has several roots), or, to put it in a different way, this family is in one-to-one correspondence with all maximal distributions of the relations \(=\) (equality) and \(\subset\) (proper inclusion) among the given set of constants.

As for the extensions of \(L2\), the author only considers the language with one extra constant and the result is that there are just five Novikov-complete extensions for \(L2\) in this language. Roughly speaking, we may assume that the new constant is true either (1) in exactly one world, or (2) in every world except for the root, or (3) in every world except for the root and some other world. In addition, we have two degenerate cases where the new constant is equal to one of the basic ones, that is to say, to either \(1\) or \(0\).

Reviewer: Grigory K. Olkhovikov (Ekaterinburg)

##### Keywords:

Dummett’s logic \(L2\); Novikov-complete extensions; method of outgrowths; universal frames; pretabular superintuitionistic logics; linear frames; two-tiered rooted frames
PDF
BibTeX
Cite

\textit{A. D. Yashin}, Algebra Logic 50, No. 2, 171--186 (2011; Zbl 1271.03043); translation from Algebra Logika 50, No. 2, 246--267 (2011)

Full Text:
DOI

##### References:

[1] | D. P. Skvortsov, ”Intuitionistic propositional calculus with extra logical connective,” in Contributions to Nonclassical Logics and Formal Systems [in Russian], Nauka, Moscow (1983), pp. 154–173. |

[2] | Ya. S. Smetanich, ”Completeness of propositional calculus with an extra operation of one variable,” Trudy Mosk. Mat. Obshch., 9, 357–371 (1960). |

[3] | Ya. S. Smetanich, ”Propositional calculi with extra operation,” Dokl. Akad. Nauk SSSR, 139, No. 2, 309–312 (1961). |

[4] | A. D. Yashin, ”A new constant in the intuitionistic propositional logic,” Fund. Prikl. Math., 5, No. 3, 903–926 (1999). · Zbl 0982.03005 |

[5] | A. D. Yashin, ”New intuitionistic logical constants and Novikov completeness,” Stud. Log., 63, No. 2, 151–180 (1999). · Zbl 0945.03010 |

[6] | A. D. Yashin, ”Classification of Novikov complete logics with extra logical constants,” Algebra Logika, 42, No. 3, 366–383 (2003). · Zbl 1034.03009 |

[7] | A. D. Yashin, ”A new regular constant in intuitionistic propositional logic,” Sib. Mat. Zh., 37, No. 6, 1413–1432 (1996). · Zbl 0876.03005 |

[8] | V. A. Yankov, ”Construction of sequences of strongly independent superintuitionistic propositional calculi,” Dokl. Akad. Nauk SSSR, 181, No. 1, 33–34 (1968). · Zbl 0198.31803 |

[9] | M. Dummett, ”A propositional calculus with denumerable matrix,” J. Symb. Log., 24, No. 1, 97–106 (1959). · Zbl 0089.24307 |

[10] | L. L. Maksimova, ”Pretable superintuitionistic logics,” Algebra Logika, 11, No. 5, 558–570 (1972). · Zbl 0275.02027 |

[11] | A. Chagrov and M. Zakharyaschev, Modal Logics, Oxford Logic Studies, 35, Clarendon, Oxford (1997). · Zbl 0871.03007 |

[12] | L. L. Esakia, Heyting Algebras [in Russian], Metsniereba, Tbilisi (1985). · Zbl 0601.06009 |

[13] | D. P. Dubashi, ”On decidable varieties of Heyting algebras,” J. Symb. Log., 57, No. 3, 988–991 (1992). · Zbl 0786.03007 |

[14] | N. Bezhanishvili and D. de Jongh, ”Intuitionistic logic,” http://www.illc.uva.nl/Publications/ResearchReports/PP-2006-25.text.pdf . · Zbl 1256.03019 |

[15] | A. D. Yashin, ”Novikov complete logics: Translation techniques,” Algebra Logika, 43, No. 3, 364–378 (2004). · Zbl 1061.03021 |

[16] | V. V. Rybakov, Admissibility of Logical Inference Rules, Stud. Log. Found. Math., 136, Elsevier, Amsterdam (1997). · Zbl 0872.03002 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.