The projective Beth property in well-composed logics

L. L. Maksimova

Algebra i logika, Tome 52 (2013) no. 2, pp. 172-202.

Résumé

The interpolation and Beth definability problems are proved decidable in well-composed logics, i.e., in extensions of Johansson's minimal logic $\mathrm J$ satisfying an axiom $(\perp\to A)\vee(A\to\perp)$. In previous studies, all $\mathrm J$-logics with the weak interpolation property (WIP) were described and WIP was proved decidable over $\mathrm J$. Also it was shown that only finitely many wellcomposed logics possess Craig's interpolation property (CIP) and the restricted interpolation property (IPR), and moreover, IPR is equivalent to the projective Beth property (PBP) on the class of logics in question. These results are applied to prove decidability of IPR and PBP in well-composed logics. The decidability of CIP in such logics was stated earlier. Thus all basic versions of the interpolation and Beth properties are decidable on the class of wellcomposed logics.

Détail

Keywords: projective Beth property, interpolation property, decidability, well-composed logic.

Bibliographie

[1] I. Johansson, “Der Minimalkalkül, ein reduzierter intuitionistischer Formalismus”, Compos. Math., 4 (1937), 119–136 | MR

[2] L. L. Maksimova, “Interpolyatsiya i proektivnoe svoistvo Beta v stroinykh logikakh”, Algebra i logika, 51:2 (2012), 244–275 | MR | Zbl

[3] L. L. Maksimova, “Teorema Kreiga v superintuitsionistskikh logikakh i amalgamiruemye mnogoobraziya psevdobulevykh algebr”, Algebra i logika, 16:6 (1977), 643–681 | MR | Zbl

[4] L. Maksimova, “Intuitionistic logic and implicit definability”, Ann. Pure Appl. Logic, 105:1–3 (2000), 83–102 | DOI | MR | Zbl

[5] L. L. Maksimova, “Razreshimost proektivnogo svoistva Beta v mnogoobraziyakh geitingovykh algebr”, Algebra i logika, 40:3 (2001), 290–301 | MR | Zbl

[6] L. L. Maksimova, “Neyavnaya opredelimost i pozitivnye logiki”, Algebra i logika, 42:1 (2003), 65–93 | MR | Zbl

[7] L. L. Maksimova, “Razreshimost slabogo interpolyatsionnogo svoistva nad minimalnoi logikoi”, Algebra i logika, 50:2 (2011), 152–188 | MR | Zbl

[8] L. Maksimova, “Interpolation and joint consistency”, We will show them!, Essays in honour of Dov Gabbay, v. 2, eds. S. Artemov et al., King's College Publ., London, 2005, 293–305

[9] L. L. Maksimova, “Sovmestnaya neprotivorechivost v rasshireniyakh minimalnoi logiki”, Sib. matem. zh., 51:3 (2010), 604–619 | MR | Zbl

[10] L. Maksimova, “Interpolation and definability over the logic Gl”, Stud. Log., 99:1–3 (2011), 249–267 | DOI | MR | Zbl

[11] L. L. Maksimova, “Interpolyatsiya i opredelimost v rasshireniyakh minimalnoi logiki”, Algebra i logika, 44:6 (2005), 726–750 | MR | Zbl

[12] L. L. Maksimova, “Razreshimost interpolyatsionnogo svoistva Kreiga v stroinykh J-logikakh”, Sib. matem. zh., 53:5 (2012), 1048–1064 | MR | Zbl

[13] L. L. Maksimova, “Proektivnye svoistva Beta v modalnykh i superintuitsionistskikh logikakh”, Algebra i logika, 38:3 (1999), 316–333 | MR | Zbl

[14] G. Kreisel, “Explicit definability in intuitionistic logic”, J. Symb. Log., 25 (1960), 389–390

[15] W. Craig, “Three uses of Herbrand–Gentzen theorem in relating model theory and proof theory”, J. Symb. Log., 22:3 (1957), 269–285 | DOI | MR | Zbl

[16] L. Maksimova, “Restricted interpolation in modal logics”, Advances in modal logic, v. 4, eds. Ph. Balbiani et al., King's College Publ., London, 2003, 297–311 | MR | Zbl

[17] A. I. Maltsev, Algebraicheskie sistemy, Nauka, M., 1970 | MR

[18] D. M. Gabbay, L. Maksimova, Interpolation and definability: modal and intuitionistic logics, Oxford Logic Guides, 46, Clarendon Press, Oxford Sci. Publ., Oxford, 2005 | MR | Zbl

[19] S. Odintsov, “Logic of classical refutability and class of extensions of minimal logic”, Log. Log. Philos., 9 (2001), 91–107 | MR | Zbl

[20] J. C. C. McKinsey, A. Tarski, “Some theorems about the sequential calculi of Lewis and Heyting”, J. Symb. Log., 13:1 (1948), 1–15 | DOI | MR | Zbl

[21] C. C. McKay, “The decidability of certain intermediate propositional logics”, J. Symb. Log., 33 (1968), 258–264 | DOI | MR | Zbl

[22] A. V. Kuznetsov, V. Ya. Gerchiu, “O superintuitsionistskikh logikakh i finitnoi approksimiruemosti”, DAN SSSR, 195:5 (1970), 1029–1032 | Zbl

[23] S. Miura, “A remark on the intersection of two logics”, Nagoya Math. J., 26 (1966), 167–171 | MR | Zbl

[24] L. L. Maksimova, “Proektivnoe svoistvo Beta i interpolyatsiya v pozitivnykh i blizkikh k nim logikakh”, Algebra i logika, 45:1 (2006), 85–113 | MR | Zbl

[25] L. L. Maksimova, “Slabaya forma interpolyatsii v ekvatsionalnoi logike”, Algebra i logika, 47:1 (2008), 94–107 | MR | Zbl