SN and {CR} for free-style {${\bf LK}\sp {tq}$}: linear decorations and simulation of normalization
Joinet, Jean-Baptiste ; Schellinx, Harold ; Tortora de Falco, Lorenzo
J. Symbolic Logic, Tome 67 (2002) no. 1, p. 162-196 / Harvested from Project Euclid
The present report is a, somewhat lengthy, addendum to "A new deconstructive logic: linear logic," where the elimination of cuts from derivations in sequent calculus for classical logic was studied ‘from the point of view of linear logic’. To that purpose a formulation of classical logic was used, that - as in linear logic - distinguishes between multiplicative and additive versions of the binary connectives. ¶ The main novelty here is the observation that this type-distinction is not essential: we can allow classical sequent derivations to use any combination of additive and multiplicative introduction rules for each of the connectives, and still have strong normalization and confluence of tq-reductions. ¶ We give a detailed description of the simulation of tq-reductions by means of reductions of the interpre- tation of any given classical proof as a proof net of PN2 (the system of second order proof nets for linear logic), in which moreover all connectives can be taken to be of one type, e.g., multiplicative. ¶ We finally observe that dynamically the different logical cuts, as determined by the four possible combinations of introduction rules, are independent: it is not possible to simulate them internally, i.e., by only one specific combination, and structural rules.
Publié le : 2002-03-14
Classification:  03F05,  03B10,  03B35,  03F07,  03F52
@article{1190150036,
     author = {Joinet, Jean-Baptiste and Schellinx, Harold and Tortora de Falco, Lorenzo},
     title = {SN and {CR} for free-style {${\bf LK}\sp {tq}$}: linear decorations and simulation of normalization},
     journal = {J. Symbolic Logic},
     volume = {67},
     number = {1},
     year = {2002},
     pages = { 162-196},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1190150036}
}
Joinet, Jean-Baptiste; Schellinx, Harold; Tortora de Falco, Lorenzo. SN and {CR} for free-style {${\bf LK}\sp {tq}$}: linear decorations and simulation of normalization. J. Symbolic Logic, Tome 67 (2002) no. 1, pp.  162-196. http://gdmltest.u-ga.fr/item/1190150036/