Skip header navigation

University of Stirling

×

Article

Subformula and separation properties in natural deduction via small Kripke models

Citation
Milne P (2010) Subformula and separation properties in natural deduction via small Kripke models. The Review of Symbolic Logic, 3 (2), pp. 175-227. https://doi.org/10.1017/S175502030999030X

Abstract
Various natural deduction formulations of classical, minimal, intuitionist, and intermediate propositional and first-order logics are presented and investigated with respect to satisfaction of the separation and subformula properties. The technique employed is, for the most part, semantic, based on general versions of the Lindenbaum and Lindenbaum–Henkin constructions. Careful attention is paid (i) to which properties of theories result in the presence of which rules of inference, and (ii) to restrictions on the sets of formulas to which the rules may be employed, restrictions determined by the formulas occurring as premises and conclusion of the invalid inference for which a counterexample is to be constructed. We obtain an elegant formulation of classical propositional logic with the subformula property and a singularly inelegant formulation of classical first-order logic with the subformula property, the latter, unfortunately, not a product of the strategy otherwise used throughout the article. Along the way, we arrive at an optimal strengthening of the subformula results for classical first-order logic obtained as consequences of normalization theorems by Dag Prawitz and Gunnar Stalmarck.

Keywords
; Modality (Logic)

Journal
The Review of Symbolic Logic: Volume 3, Issue 2

StatusPublished
Author(s)Milne, Peter
Publication date31/12/2010
URLhttp://hdl.handle.net/1893/2804
PublisherCambridge University Press for the Association for Symbolic Logic
ISSN1755-0203
Scroll back to the top