I am kind of stuck on page 48 on exercise 2.2b in Hughes and Cresswell; In case you don't have the book at hand here's the question:

Let K** be K but with N and K replaced by

LT: L( p→ p),

R*: ⊢ a → b ⇒ ⊢ La → Lb


K2*: (Lp&Lq) → L(p&q).

Show that K and K** have the same theorems.

What I thought is that in 2.2a we have showed that LT+R* ⊢ N, so it's enough to show that LT+R*+N+K2* ⊢ K.

Now I thought of old trick of math to look from the end back to the start of the proof, i.e:

We need to prove:

L(p → q) → (Lp → Lq)

But I don't see how to use the other rules and axioms, any hints?

  • It's not enough to show that the axioms of K** imply the axioms of K (that would only prove that the theorems of K are a subset of the theorems of K**), you also have to show the reverse. (Also: formatting your question better might help.)
    – Eliran
    Apr 30 '16 at 8:12
  • Yes, I know but in part a of this question I have shown that LT+R |- N and that N|- LT, and since R is DR1 in K system I've showed that K and K* have the same theorems in in 2.2a. Now for 2.2b I am left with only showing that K** implies K since it's evident that K implies K**. Apr 30 '16 at 8:36
  • @EliranH do we have latex capabilities in the stackexchange? Apr 30 '16 at 8:37
  • No, unfortunately not (because it's in beta I guess).
    – Eliran
    Apr 30 '16 at 8:44
  • @EliranH then how to edit my post for better formatting? Apr 30 '16 at 8:49

I contacted one of the authors of the textbook, Max Cresswell and he kindly suggested me a solution to the problem.

All I need to prove is that K follows from K**.

So here's a proof:

  1. ((p->q)&p)->q PC axiom.

  2. L((p->q)&p)->Lq 1,R*.

  3. (L(p->q)&Lp)->L((p->q)&p) K2*.

  4. L(p->q)->(Lp->L((p->q)&p)) 3,PC.

  5. L(p->q)->(Lp->Lq) 2,4, PC.

Where PC is axiom of propositional logic, and in 5 I used a sort of hypothetical syllogism.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.