We prove a completeness result for Multiplicative Exponential Linear Logic (MELL): we show that the relational model is injective for MELL proof-nets, i.e. the equality between MELL proof-nets in the relational model is exactly axiomatized by cut-elimination. In the seminal paper by Harvey Friedman [11] , it has been shown that equality between simply-typed lambda terms in the full typed structure M X over an infnite set X is completely axiomatized by β and η: A natural problem is to know whether a similar result could be obtained for Linear Logic. Such a result can be seen as a "separation" theorem. To obtain such separation theorems, it is a prerequesite to have a "canonical" syntax. When Jean-Yves Girard introduced Linear Logic (LL) [12] , he not only introduced a sequent calculus system but also "proof-nets". Indeed, as for LJ and LK (sequent calculus systems for intuitionnistic and classical logic, respectively), different proofs in LL sequent calculus can represent "morally" the same proof: proof-nets were introduced to find a unique representative for these proofs. The technology of proof-nets was completely satisfactory for the multiplicative fragment without units. For proof-nets having additives, contractions or weakenings, it was easy to exhibit different proof-nets that should be identified. Despite some flaws, the discovery of proof-nets was striking. In particular, Vincent Danos proved by syntactical means in [3] the confluence of these proof-nets for the Multiplicative Exponential Linear Logic fragment (MELL). For additives, the problem to have a satisfactory notion of proof-net has been addressed in [15] . For MELL, a "new syntax" was introduced in [4] . In the original syntax, the following properties of the weakening and of the contraction did not hold: • the associativity of the contraction; • the neutrality of the weakening for the contraction; • the contraction and the weakening as morphisms of coalgebras. But they hold in the new syntax; at least for MELL, we got a syntax that was a good candidate to deserve to be considered as being "canonical". Then trying to prove that any two (η-expanded) MELL proof-nets that are equal in some denotational semantics are β-joinable has become sensible and had at least the two following motivations: • to prove the canonicity of the "new syntax" (if we quotient more normal proof-nets, then we would identify proof-nets having different semantics); • to prove by semantics means the confluence (if a proof-net reduces to two cut-free proof-nets, then they have the same semantics, so they would be β-joinable, hence equal). 1 For the multiplicative fragment with units, it has been recently shown [14] that, in some sense, no satisfactory notion of proof-net can exist. Our proof-nets have no jump, so they identify too many sequent calculus proofs, but not more than the relational semantics.
De Carvalho showed that the relational model is injective for MELL REF .
The relational model is injective for Multiplicative Exponential Linear Logic
ArXiv
ArXiv
Computer Science Mathematics