Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In my homework I was asked to prove that a deduction system for modal logic with $\rightarrow$, $\neg$ and $\square$, with 4 axioms and 2 inference rules (MP and a $\square$-generalization rule), is weakened and turned incomplete once you take away the generalization rule.

Now, since I don't want you to solve my homework for me, I just want a hint about the possible approaches to prove that a deduction system is incomplete (not necessarily a modal logic system even).

So far I tried taking a counterexample and showing the resulting formal proof sequence will be infinite, but the my proof was just growing exponentially complex (rather than rely on induction).

share|improve this question
1  
Find a different semantics for your modal logic such that the deduction system remains sound, but what you want to prove is false. –  Zhen Lin Mar 11 '12 at 22:10
    
What does "different semantics" mean for, say, the Hilbert system? For example, will redefining $\to$ to have a different truth table mean "different semantics"? –  Ilya Mar 11 '12 at 22:15
1  
Here is a concrete example: cs.toronto.edu/~yuvalf/until.pdf. Your problem should be easier. –  Yuval Filmus Mar 11 '12 at 22:44
    
@Ilya: Yes. Actually, you may have to enlarge the set of your truth values as well. –  Zhen Lin Mar 11 '12 at 22:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.