×

Preservation of structural properties in intuitionistic extensions of an inference relation. (English) Zbl 1522.03317

Summary: The article approaches cut elimination from a new angle. On the basis of an arbitrary inference relation among logically atomic formulae, an inference relation on a language possessing logical operators is defined by means of inductive clauses similar to the operator-introducing rules of a cut-free intuitionistic sequent calculus. The logical terminology of the richer language is not uniquely specified, but assumed to satisfy certain conditions of a general nature, allowing for, but not requiring, the existence of infinite conjunctions and disjunctions. We investigate to what extent structural properties of the given atomic relation are preserved through the extension to the full language. While closure under the Cut rule narrowly construed is not in general thus preserved, two properties jointly amounting to closure under the ordinary structural rules, including Cut, are.
Attention is then narrowed down to the special case of a standard first-order language, where a similar result is obtained also for closure under substitution of terms for individual parameters. Taken together, the three preservation results imply the familiar cut-elimination theorem for pure first-order intuitionistic sequent calculus.
In the interest of conceptual economy, all deducibility relations are specified purely inductively, rather than in terms of the existence of formal proofs of any kind.

MSC:

03F05 Cut-elimination and normal-form theorems
03B20 Subsystems of classical logic (including intuitionistic logic)
Full Text: DOI

References:

[1] Gentzen, G.; Szabo, M. E., The Collected Papers of Gerhard Gentzen, Investigations into logical deduction, 68-131, (1969), North-Holland: North-Holland, Amsterdam · Zbl 0209.30001
[2] Kalicki, C., Infinitary propositional intuitionistic logic, Notre Dame Journal of Formal Logic, 21, 2, 216-228, (1980) · Zbl 0336.02021 · doi:10.1305/ndjfl/1093883041
[3] Lorenzen, P., Einführung in die operative Logik und Mathematik, (1955), Springer: Springer, Berlin · Zbl 0068.00801
[4] Lorenzen, P., Metamathematik, (1962), Bibliographisches Institut AG: Bibliographisches Institut AG, Mannheim · Zbl 0105.24601
[5] Martin-Löf, P., Notes on Constructive Mathematics, (1970), Almqvist & Wiksell: Almqvist & Wiksell, Uppsala
[6] Nadel, M., Infinitary intuitionistic logic from a classical point of view, Annals of Mathematical Logic, 14, 2, 159-191, (1978) · Zbl 0406.03055 · doi:10.1016/0003-4843(78)90015-3
[7] Novikoff, P. S., On the consistency of certain logical calculus, Matematičeskij Sbornik (Recueil Mathématique), 12, 2, 231-261, (1943) · Zbl 0060.02102
[8] Prawitz, D., Natural Deduction: A Proof-Theoretical Study, (1965), Almqvist & Wiksell: Almqvist & Wiksell, Uppsala · Zbl 0173.00205
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.