TY - GEN
T1 - Classical and intuitionistic subexponential logics are equally expressive
AU - Chaudhuri, Kaustuv
PY - 2010/9/20
Y1 - 2010/9/20
N2 - It is standard to regard the intuitionistic restriction of a classical logic as increasing the expressivity of the logic because the classical logic can be adequately represented in the intuitionistic logic by double-negation, while the other direction has no truth-preserving propositional encodings. We show here that subexponential logic, which is a family of substructural refinements of classical logic, each parametric over a preorder over the subexponential connectives, does not suffer from this asymmetry if the preorder is systematically modified as part of the encoding. Precisely, we show a bijection between synthetic (i.e., focused) partial sequent derivations modulo a given encoding. Particular instances of our encoding for particular subexponential preorders give rise to both known and novel adequacy theorems for substructural logics.
AB - It is standard to regard the intuitionistic restriction of a classical logic as increasing the expressivity of the logic because the classical logic can be adequately represented in the intuitionistic logic by double-negation, while the other direction has no truth-preserving propositional encodings. We show here that subexponential logic, which is a family of substructural refinements of classical logic, each parametric over a preorder over the subexponential connectives, does not suffer from this asymmetry if the preorder is systematically modified as part of the encoding. Precisely, we show a bijection between synthetic (i.e., focused) partial sequent derivations modulo a given encoding. Particular instances of our encoding for particular subexponential preorders give rise to both known and novel adequacy theorems for substructural logics.
U2 - 10.1007/978-3-642-15205-4_17
DO - 10.1007/978-3-642-15205-4_17
M3 - Conference contribution
AN - SCOPUS:77956565107
SN - 364215204X
SN - 9783642152047
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 199
BT - Computer Science Logic - 24th International Workshop, CSL 2010, and 19th Annual Conference of the EACSL, Proceedings
T2 - 24th International Workshop on Computer Science Logic, CSL 2010, and 19th Annual Conference of the EACSL
Y2 - 23 August 2010 through 27 August 2010
ER -