Help with a modal Hilbert-style proof of (□(a>b)&◊(a&c))>◊(b&c)

Question

Can't grasp how it can be proved. To proof just propositional calculus formula (without modal operators) at first seems rather natural to me. Tried the law of importation scheme but it didn't work out.

There are a lot of axiom schemata allowed (link below) + K + Necessitation + MP + Substituition

It does not really matter what Hilbert-style calculus to use. The only two requirements:

a) no assumptions

b) no premises

set of axioms is on a p.13 http://books.google.ru/books?id=XNzzliL2cBgC&pg=PA23&lpg=PA23&dq=a+new+introduction+to+modal+logic+axioms&source=bl&ots=hOuN2jTOra&sig=dMGzFI6ZFf2RJa7GLLDNio9aM2E&hl=ru&sa=X&ei=-2y2U7n_KNOO4gSlmoGACA&ved=0CE0Q6AEwBQ#v=onepage&q=a%20new%20introduction%20to%20modal%20logic%20axioms&f=true

Answer 1

This answer address the "unsolved" problem regarding the proof of the "propositional part" of the question, using an Hilbert-style proof system (with Natural Deduction, the proof is quite easy, and has been already provided).

---

The list at page 13 of M.J.Cresswell & G.E.Hughes, A New Introduction to Modal Logic (1966) is significantly called a "list [of] valid PC wff"; we are not sure that they form a complete axiom system for PC (i.e. that they are enough to prove all tautologies).

In order to prove the formula :

$((a→b)∧(a∧c))→(b∧c)$

we need a complete Hilbert-style axiom system; I'll use that of Elliott Mendelson, Introduction to Mathematical Logic (4th ed - 1997), based on the following three axioms :

(A1) $\mathcal{B} \rightarrow ( \mathcal{C} \rightarrow \mathcal{B})$

(A2) $(\mathcal{B} \rightarrow ( \mathcal{C} \rightarrow \mathcal{D})) \rightarrow ((\mathcal{B} \rightarrow \mathcal{C}) \rightarrow (\mathcal{B} \rightarrow \mathcal{D}))$

(A3) $(\lnot \mathcal{C} \rightarrow \lnot \mathcal{B}) \rightarrow ((\lnot \mathcal{C} \rightarrow \mathcal{B}) \rightarrow \mathcal{C})$

and modus ponens as only rule of inference.

The symbol $\land$ for conjunction is not primitive; it is defined as :

$\mathcal{B} \land \mathcal{C} =_{def} \lnot (\mathcal{B} \rightarrow \lnot \mathcal{C})$.

In order to prove our formula, we need some preliminary Lemmas; you can find the proof in Mendelson's book [for some of them, see this post].

Lemma 1.8 [page 36] :

$\vdash \mathcal{B} \rightarrow \mathcal{B}$.

We need only (A1) and (A2) to prove it.

With Lemma 1.8 and using only (A1) and (A2) it is possible to prove the Deduction Theorem [Prop 1.9, page 37]:

if $\Gamma, \mathcal{B} \vdash \mathcal{C}$, then $\Gamma \vdash \mathcal{B} \rightarrow \mathcal{C}$.

With the Deduction Th it is easy to prove :

Corollary 1.10(a) [page 38] :

$\mathcal{B} \rightarrow \mathcal{C}, \mathcal{C} \rightarrow \mathcal{D} \vdash \mathcal{B} \rightarrow \mathcal{D}$.

Then Mendelson proves Lemma 1.11.(a)-(e)

$\vdash \lnot \lnot \mathcal B \rightarrow \mathcal B$

$\vdash \mathcal B \rightarrow \lnot \lnot \mathcal B$

$\vdash \lnot \mathcal B \rightarrow (\mathcal B \rightarrow \mathcal C)$

$\vdash (\lnot \mathcal C \rightarrow \lnot \mathcal B) \rightarrow (\mathcal B \rightarrow \mathcal C)$

$\vdash (\mathcal B \rightarrow \mathcal C) \rightarrow (\lnot \mathcal C \rightarrow \lnot \mathcal B)$.

We can easily derive from Lemma 1.11.(e) :

Lemma A : $\vdash (\mathcal B \rightarrow \lnot \mathcal C) \rightarrow (\mathcal C \rightarrow \lnot \mathcal B)$.

Proof

(i) $\mathcal B \rightarrow \lnot \mathcal C \vdash \lnot \lnot \mathcal C \rightarrow \lnot \mathcal B$ --- from Lemma 1.11.(e) with $\lnot \mathcal C$ in place of $\mathcal C$, by mp

(ii) $\mathcal B \rightarrow \lnot \mathcal C \vdash \mathcal C \rightarrow \lnot \mathcal B$ --- from (i) and Lemma 1.11(b) with Coroll.1.10(a)

(iii) $\vdash (\mathcal B \rightarrow \lnot \mathcal C) \rightarrow (\mathcal C \rightarrow \lnot \mathcal B)$ --- from (ii) by DT.

Now we need the equivalent of $\land$-introduction and -elimination rules; we have to derive them using the abbreviation for $\land$.

Lemma B : $\vdash (\mathcal B \land \mathcal C) \rightarrow \mathcal B$.

Proof

(i) $\vdash \lnot \mathcal B \rightarrow (\mathcal B \rightarrow \lnot \mathcal C)$ --- Lemma 1:11(c)

(ii) $\vdash \lnot (\mathcal B \rightarrow \mathcal \lnot C) \rightarrow \lnot \lnot \mathcal B $ --- from (i) and Lemma 1.11(e) by mp

(iii) $\vdash \lnot (\mathcal B \rightarrow \mathcal \lnot C) \rightarrow \mathcal B $ --- from (ii) and Lemma 1.11(a) by Coroll.1.10(a)

(iv) $\vdash (\mathcal B \land \mathcal C) \rightarrow \mathcal B $ --- from (iii) by def of $\land$.

Lemma C : $\vdash (\mathcal B \land \mathcal C) \rightarrow \mathcal C$.

Proof

(i) $\vdash \lnot \mathcal C \rightarrow (\mathcal B \rightarrow \lnot C)$ --- (A1)

(ii) $\vdash \lnot (\mathcal B \rightarrow \lnot C) \rightarrow \lnot \lnot C$ --- from (i) and Lemma 1.11(e) by mp

(iii) $\vdash \lnot (\mathcal B \rightarrow \lnot C) \rightarrow C$ --- from (ii) and Lemma 1.11(a) by Coroll.1.10(a)

iv) $\vdash (\mathcal B \land C) \rightarrow C$ --- from (iii) by def of $\land$.

Now we prove :

Lemma D : $\vdash \mathcal B \rightarrow ( \mathcal C \rightarrow (\mathcal B \land \mathcal C))$.

Proof

(i) $\mathcal B, \mathcal B \rightarrow \lnot \mathcal C \vdash \mathcal \lnot C$ --- by mp

(ii) $\mathcal B \vdash (\mathcal B \rightarrow \lnot \mathcal C) \rightarrow \mathcal \lnot C$ --- from (i) by DT

(iii) $\mathcal B \vdash \mathcal C \rightarrow \lnot (\mathcal B \rightarrow \lnot \mathcal C)$ --- from (ii) and Lemma A by mp

(iv) $\vdash \mathcal B \rightarrow (\mathcal C \rightarrow \lnot (\mathcal B \rightarrow \lnot \mathcal C))$ --- from (iii) by DT

(v) $\vdash \mathcal B \rightarrow ( \mathcal C \rightarrow (\mathcal B \land \mathcal C))$ --- from (iv) def of $\land$.

We prove :

Lemma E : $\mathcal B \rightarrow ( \mathcal C \rightarrow \mathcal D) \vdash (\mathcal B \land \mathcal C) \rightarrow \mathcal D$.

Proof

(i) $\mathcal B \rightarrow ( \mathcal C \rightarrow \mathcal D)$ --- assumed

(ii) $\mathcal B \land \mathcal C$ --- assumed

(iii) $\mathcal B$ --- from (ii) by Lemma B

(iv) $\mathcal C \rightarrow \mathcal D$ --- from (i) and (iii) by mp

(v) $\mathcal C$ --- from (ii) by Lemma C

(vi) $\mathcal D$ --- from (iv) and (v) by mp

(vii) $\mathcal B \rightarrow ( \mathcal C \rightarrow \mathcal D) \vdash (\mathcal B \land \mathcal C) \rightarrow \mathcal D$ --- from (i) and (vi) by DT.

Now our last preliminary Lemma:

Lemma F : $\vdash (\mathcal B \land \mathcal C) \rightarrow (\mathcal C \land \mathcal B)$.

Proof

(i) $\mathcal B \land C$ --- assumed

(ii) $\mathcal B$ --- from (i) by Lemma B

(iii) $\mathcal C$ --- from (i) by Lemma C

(iv) $\vdash \mathcal C \rightarrow ( \mathcal B \rightarrow (\mathcal C \land \mathcal B))$ --- Lemma D

(v) $\mathcal C \land \mathcal B$ --- from (iii), (ii) and (iv) by mp twice

(vi) $\vdash (\mathcal B \land \mathcal C) \rightarrow (\mathcal C \land \mathcal B)$ --- from (i) and (v) by DT.

---

Now that we have in place all needed "tools", we can proceed with the proof of our theorem.

Main proof

(i) $\mathcal A \rightarrow \mathcal B, \mathcal B \rightarrow \mathcal \lnot C \vdash \mathcal A \rightarrow \mathcal \lnot C$ --- from Coroll.1.10(a)

(ii) $\mathcal A \rightarrow \mathcal B, \mathcal C \rightarrow \mathcal \lnot B \vdash \mathcal C \rightarrow \lnot \mathcal A$ --- from (i) by Lemma A and Coroll.1.10(a) twice

(iii) $\mathcal A \rightarrow \mathcal B \vdash (\mathcal C \rightarrow \mathcal \lnot B) \rightarrow (\mathcal C \rightarrow \lnot \mathcal A)$ --- from (ii) by DT

(iv) $\mathcal A \rightarrow \mathcal B \vdash \lnot (\mathcal C \rightarrow \lnot \mathcal A) \rightarrow \lnot (\mathcal C \rightarrow \mathcal \lnot B)$ --- from (iii) and Lemma 1.11(e) by mp

(v) $\mathcal A \rightarrow \mathcal B \vdash (\mathcal C \land \mathcal A) \rightarrow (\mathcal C \land \mathcal B)$ --- from (iv) by def of $\land$

(vi) $\vdash (\mathcal A \rightarrow \mathcal B) \rightarrow ((\mathcal C \land \mathcal A) \rightarrow (\mathcal C \land \mathcal B))$ --- from (v) by DT

(vii) $\vdash (\mathcal A \rightarrow \mathcal B) \rightarrow ((\mathcal A \land \mathcal C) \rightarrow (\mathcal B \land \mathcal C))$ --- from (vi) and Lemma F by Coroll 1.10(a) twice

(viii) $\vdash ((\mathcal A \rightarrow \mathcal B) \land (\mathcal A \land \mathcal C)) \rightarrow (\mathcal B \land \mathcal C)$ --- from (vii) by Lemma E.

---

Comment

It is of interest to compare the above system with J.Barkley Rosser, Logic for Mathematicians (1953 - Dover reprint).

The system has $\lnot$ and $\land$ as primitive and $\supset$ is defined through [see page 15] :

$P \supset Q =_{def}\lnot (P \land \lnot Q)$.

The axioms are [see page 56 - using the abbreviation] :

1) $\quad P \supset (P \land P)$

2) $\quad (P \land Q) \supset P$

3) $\quad (P \supset Q) \supset (\lnot (Q \land R) \supset \lnot (R \land P) )$

while modus ponens is the only rule of inference.

In a manner similar to Mendelson's book, Rosser proves [pages 61-62] :

Theorem IV.4.1 : $P \supset Q, Q \supset R \vdash \lnot (\lnot R \land P)$

Theorem IV.4.2 : $\vdash \lnot (\lnot P \land P)$

Theorem IV.4.3 : $\vdash \lnot \lnot P \supset P$

Then he proves [page 63] :

Theorem IV.4.7 : $\lnot P \supset \lnot Q \vdash Q \supset P$.

Finally, we have :

Theorem IV.4.8 : $P \supset Q \vdash (R \land P ) \supset (Q \land R)$

Proof

(i) $P \supset Q \vdash \lnot (Q \land R) \supset \lnot (R \land P)$ --- axiom 3

(ii) $\lnot (Q \land R) \supset \lnot (R \land P) \vdash (R \land P) \supset (Q \land R)$ --- from Th.IV.4.7 with $Q \land R$ for $P$ and $R \land P$ for $Q$

(iii) $P \supset Q \vdash (R \land P ) \supset (Q \land R)$ from (i) and (ii) by transitivity of $\vdash$.

To complete the proof of the formula in the OP's question, we need some more work :

• to prove the commutativity of $\land$ [see Theorem IV.4.13, page 64],
• to prove the Deduction Theorem [see Theorem IV.6.1, page 65].

Answer 2

$\renewcommand{\lif}{\supset}$ First, it's important to understand the intuition behind the theorem. That will help guide you in constructing an axiomatic proof.

$$ \renewcommand{\land}{\wedge} (\Box (a \lif b) \land \Diamond(a \land c)) \lif \Diamond (b \land c) $$

With the Kripke semantics, this says "if $a \lif b$ is true in every accessible world and $a \land c$ is true in some accessible world, then $b \land c$ must be true in some accessible world." An intuition behind proof might be:

Consider the accessible world $w$ in which $a \land c$ is true. Because $a \lif b$ is true in every accessible world, it must be true in $w$ as well. Since $a$ is true (from $a \land c$), then $b$ follows by modus ponens. Since $c$ is also true (from $a \land c$), then $b \land c$ is true. Then $b\land c$ is true in some accessible world, and thus $\Diamond(b \land c)$.

Constructing axiomatic proofs from scratch is kind of a pain, and it might be easier to start with a natural deduction style proof, and then map that back to an axiomatic proof. A natural deduction style proof would be something like

• 0.
  • 1. Assume $\Box(a \lif b) \land \Diamond(a \land c)$.
  • 2. $\Box(a \lif b)$ by conjunction elimination.
  • 3. $\Diamond(a \land c)$ by conjunction elimination.
    • 4. Possibility introduction subproof with $a \land c$.
    • 5. $a \lif b$ by K-reiteration.
    • 6. $a$ by conjunction elimination.
    • 7. $b$ by conditional elimination (modus ponens).
    • 8. $c$ by conjunction elimination.
    • 9. $b \land c$ by conjunction introduction.
  • 10. $\Diamond(b \land c)$ by $\Diamond$ introduction with 3, and 4–9.
• 11. $(\Box(a \lif b) \land \Diamond(a \land c)) \lif \Diamond(b\land c)$ by conditional introduction 1–10.

What can we do on the axiomatic side? Well, if we take propositional reasoning for granted, we do, to begin:

• $\Box(a\lif b) \land \Diamond(a \land c)$ (hyp)
• $\Box(a \lif b)$ (taut. consequence)
• $(a \lif b) \lif ((a \land c) \lif (b \land c))$ (tautology)
• $\Box((a \lif b) \lif ((a \land c) \lif (b \land c)))$ (necessitation)
• $\Box(a \lif b) \lif \Box((a \land c) \lif (b \land c))$ (distribution)
• $\Box((a \land c) \lif (b \land c))$ (modus ponens)

At this point, you need to figure out what rules you've got available for handling possibility. Ideally you'd have a possibility distribution axiom like

$$ \Box(\phi \lif \psi) \lif (\Diamond\phi \lif \Diamond\psi) \tag{Possibilitation} $$

if you have that, or can derive it, then you can continue:

• $\Diamond(a \land c) \lif \Diamond(b \land c)$ (possibilitation)
• $\Diamond(a \land c)$ (taut. consequence)
• $\Diamond(b \land c)$ (modus ponens)

That's still not quite what you need, because you'd need a deduction theorem to get the conditional. That means you'll need to go back a bit and figure out how to do all of this "one-layer removed". This should be a good starting point, though.