×

zbMATH — the first resource for mathematics

Admissible rules in the implication-negation fragment of intuitionistic logic. (English) Zbl 1225.03011
Summary: Uniform infinite bases are defined for the single-conclusion and multiple-conclusion admissible rules of the implication-negation fragments of intuitionistic logic IPC and its consistent axiomatic extensions (intermediate logics). A Kripke semantics characterization is given for the (hereditarily) structurally complete implication-negation fragments of intermediate logics, and it is shown that the admissible rules of this fragment of IPC form a PSPACE-complete set and have no finite basis.

MSC:
03B20 Subsystems of classical logic (including intuitionistic logic)
03B22 Abstract deductive systems
03B55 Intermediate logics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baader, F.; Snyder, W., Unification theory, (), 445-532 · Zbl 1011.68126
[2] Chagrov, A.; Zakharyaschev, M., Modal logic, (1996), Oxford University Press · Zbl 1003.03516
[3] Cintula, P., Weakly implicative (fuzzy) logics I: basic properties, Archive for mathematical logic, 45, 673-704, (2006) · Zbl 1101.03015
[4] Cintula, P.; Metcalfe, G., Structural completeness in fuzzy logics, Notre dame journal of formal logic, 50, 2, 153-183, (2009) · Zbl 1190.03027
[5] Citkin, A.I., On structurally complete superintuitionistic logics, Soviet mathematics doklady, 19, 816-819, (1978) · Zbl 0412.03009
[6] Friedman, H.M., One hundred and two problems in mathematical logic, Journal of symbolic logic, 40, 2, 113-129, (1975) · Zbl 0318.02002
[7] Ghilardi, S., Unification in intuitionistic logic, Journal of symbolic logic, 64, 2, 859-880, (1999) · Zbl 0930.03009
[8] Ghilardi, S., Best solving modal equations, Annals of pure and applied logic, 102, 3, 184-198, (2000) · Zbl 0949.03010
[9] Iemhoff, R., On the admissible rules of intuitionistic propositional logic, Journal of symbolic logic, 66, 1, 281-294, (2001) · Zbl 0986.03013
[10] Iemhoff, R., Intermediate logics and visser’s rules, Notre dame journal of formal logic, 46, 1, 65-81, (2005) · Zbl 1102.03032
[11] Iemhoff, R.; Metcalfe, G., Proof theory for admissible rules, Annals of pure and applied logic, 159, 1-2, 171-186, (2009) · Zbl 1174.03024
[12] Iemhoff, R.; Metcalfe, G., Hypersequent systems for the admissible rules of modal and intermediate logics, (), 230-245 · Zbl 1211.03037
[13] Jeřábek, E., Admissible rules of modal logics, Journal of logic and computation, 15, 4, 411-431, (2005) · Zbl 1077.03011
[14] Jeřábek, E., Admissible rules of łukasiewicz logic, Journal of logic and computation, 20, 2, 425-447, (2010) · Zbl 1216.03042
[15] E. Jeřábek, Bases of admissible rules of Łukasiewicz logic, Journal of Logic and Computation (in press). · Zbl 1216.03043
[16] Jeřábek, E., Complexity of admissible rules, Archive for mathematical logic, 46, 2, 73-92, (2007) · Zbl 1115.03010
[17] Lorenzen, P., ()
[18] McKay, C.G., The decidability of certain intermediate propositional logics, Journal of symbolic logic, 33, 258-264, (1968) · Zbl 0175.27103
[19] G. Metcalfe, Admissible rules of R-mingle (submitted for publication).
[20] Minari, P.; Wroński, A., The property (HD) in intermediate logics. A partial solution of a problem of H. ono, Reports on mathematical logic, 22, 21-25, (1988) · Zbl 0696.03009
[21] Mints, G., Derivability of admissible rules, (), 85-89 · Zbl 0358.02031
[22] Olson, J.S.; Raftery, J.G.; Alten, C.J.V., Structural completeness in substructural logics, Logic journal of the IGPL, 16, 5, 453-495, (2008) · Zbl 1168.03012
[23] Prucnal, T., On the structural completeness of some pure implicational propositional calculi, Studia logica, 32, 1, 45-50, (1973) · Zbl 0268.02013
[24] Prucnal, T., Structural completeness of medvedev’s propositional calculus, Reports on mathematical logic, 6, 103-105, (1976) · Zbl 0358.02024
[25] P. Rozière, Regles admissibles en calcul propositionnel intuitionniste, Ph.D. Thesis, Université Paris VII, 1992.
[26] Rybakov, V., Admissibility of logical inference rules, (1997), Elsevier · Zbl 0872.03002
[27] Statman, R., Intuitionistic propositional logic is polynomial-space complete, Theoretical computer science, 72, 67-72, (1979) · Zbl 0411.03049
[28] Wroński, A., On factoring by compact congruences in algebras of certain varieties related to the intuitionistic logic, Bulletin of the section of logic, 15, 2, 48-51, (1986) · Zbl 0624.03046
[29] Wroński, A., Transparent unification for equivalential algebras and some related varieties (abstract), Algebraic and topological methods in non-classical logics, II, (2005)
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.