N does not validate uniform substitution. Many simple failures of uniform substitution can be found: p→p is valid in N, but the instance (p∧p)→(p∧p) isn't. (Verify this at our dialogical logic sandbox!) There are many other failures of uniform substitution (infinitely many, in fact).
This is a somewhat awkward feature of N. Earlier, I asked whether uniform substitution consistent with N: is the closure of N under uniform substitution consistent? Another way to put this is to ask whether uniform substitution is an admissible rule of inference for N.
The answer is “yes”; here is a simple proof, exploiting the fact that N is sub-classical. Let N′ be the closure of N under uniform substitution; we need to show that N′ is consistent. Suppose that there were a formula φ such that both φ∈N′ and ¬φ∈N′. There are formulas α and β in N such that φ is obtained by an application of uniform substitution from α and likewise ¬φ is obtained by an application of uniform substitution from β. Since α∈N, α is a tautology; and since classical logic CL is closed under uniform substitution, φ is a tautology, too. Likewise, ¬φ is a tautology. But that's impossible!
(Thanks to Benedikt Löwe for this nice solution.)
No comments:
Post a Comment