Expressive power and incompleteness of propositional logics
Journal of Philosophical Logic 39 (2):159-171 (2010)
| Abstract | Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesSara Negri (2002). Varieties of Linear Calculi. Journal of Philosophical Logic 31 (6):569-590.
Ross Thomas Brady (forthcoming). Free Semantics. Journal of Philosophical Logic.
Sara Negri (2011). Proof Analysis: A Contribution to Hilbert's Last Problem. Cambridge University Press.
L. Humberstone & D. Makinson (2012). Intuitionistic Logic and Elementary Rules. Mind 120 (480):1035-1051.
Torben Braüner (2004). Two Natural Deduction Systems for Hybrid Logic: A Comparison. Journal of Logic, Language and Information 13 (1):1-23.
Ewa Orlowska (1992). Relational Proof System for Relevant Logics. Journal of Symbolic Logic 57 (4):1425-1440.
Heinrich Wansing (2006). Connectives Stranger Than Tonk. Journal of Philosophical Logic 35 (6):653 - 660.
Yannis Delmas-Rigoutsos (1997). A Double Deduction System for Quantum Logic Based on Natural Deduction. Journal of Philosophical Logic 26 (1):57-67.
M. W. Bunder (1982). Deduction Theorems for Weak Implicational Logics. Studia Logica 41 (2-3):95 - 108.
Hartley Slater (2008). Harmonising Natural Deduction. Synthese 163 (2):187 - 198.
Analytics
Monthly downloads |
Added to index2009-10-28Total downloads56 ( #17,848 of 550,802 )Recent downloads (6 months)1 ( #63,425 of 550,802 )How can I increase my downloads? |
My notes
Discussion
