We show that for a suitable fragment of linear logic the syntactical equivalence relation on proofs induced by cut-elimination coincide with the semantic equivalence relation on proofs induced by the multiset based relational model: one says that the interpretation in the model (or the semantics) is injective. More precisely, we prove that two cut-free proofs of the multiplicative and exponential fragment of linear logic with the same interpretation in the multiset based relational model are the same ``up to the connections between the doors of exponential boxes''. This result is proven in an untyped framework: two cut-free untyped Proof-Structures (PS) have the same Linear Proof-Structure (LPS). An immediate consequence is that two cut-free PS without weakenings with the same relational interpretation are the same; hence relational semantics is injective.
DE CARVALHO, D., TORTORA DE FALCO, L. (2012). The relational model is injective for Multiplicative Exponential Linear Logic (without weakenings). ANNALS OF PURE AND APPLIED LOGIC, 163 (issue 9), 1210-1236.
The relational model is injective for Multiplicative Exponential Linear Logic (without weakenings)
TORTORA DE FALCO, LORENZO
2012-01-01
Abstract
We show that for a suitable fragment of linear logic the syntactical equivalence relation on proofs induced by cut-elimination coincide with the semantic equivalence relation on proofs induced by the multiset based relational model: one says that the interpretation in the model (or the semantics) is injective. More precisely, we prove that two cut-free proofs of the multiplicative and exponential fragment of linear logic with the same interpretation in the multiset based relational model are the same ``up to the connections between the doors of exponential boxes''. This result is proven in an untyped framework: two cut-free untyped Proof-Structures (PS) have the same Linear Proof-Structure (LPS). An immediate consequence is that two cut-free PS without weakenings with the same relational interpretation are the same; hence relational semantics is injective.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.