Prove that the calculus of natural deduction using the signature ${\neg, \vee}$ is complete.

Question

I am trying to solve Exercise 2 of Section 1.4 in A Concise Introduction to Mathematical Logic by Wolfgang Rautenberg. The exercise establishes the following calculus with 6 basic rules:

$$ \mathrm{(IS)}\quad\frac{}{\alpha\vdash\alpha}\\ \mathrm{(MR)}\quad\frac{X\vdash\alpha}{X'\vdash\alpha}\quad(X'\supseteq X)\\ \mathrm{(\vee1)}\quad\frac{X\vdash\alpha}{X\vdash\alpha\vee\beta}\\ \mathrm{(\vee2)}\quad\frac{X,\alpha\vdash\gamma\ |\ X,\beta\vdash\gamma}{X,\alpha\vee\beta\vdash\gamma}\\ \mathrm{(\neg1)}\quad\frac{X\vdash\alpha,\neg\alpha}{X\vdash\beta}\\ \mathrm{(\neg2)}\quad\frac{X,\alpha\vdash\beta\ |\ X,\neg\alpha\vdash\beta}{X\vdash\beta} $$

Now I am supposed to prove that $X\vdash\alpha\iff X\vDash\alpha$. The direction $\Rightarrow$ was easy enough for me as it just corresponds to the soundness of $\vdash$, which is easy to show. For the other direction, the idea is that $X\nvdash\alpha$ implies that $X,\neg\alpha$ is consistent. And if we then take a maximally consistent extension $Y$ of $X,\neg\alpha$ (as by Lindenbaum's theorem), we need to provide a Lemma that shows the satisfiability of $Y$, and therefore the satisfiability of $X,\neg\alpha$, and therefore finally $X\nvDash\alpha$.

The proof has already been done for the negation operator in the book, so I only need to do it for the disjunction operator. I got as far as figuring out that I need to prove that, for a maximally consistent $Y$:$$ Y\vdash\alpha\vee\beta\iff Y\vdash\alpha\quad\mathrm{or}\quad Y\vdash\beta $$

Here, the $\Leftarrow$ direction is trivial, but I have absolutely no clue how to derive the other direction from the basic rules.

Answer 1

You have to mimick the proof of Lemma 4.5 [page 28]. A maximally consistent set $X$ is satisfiable, supplementing the case for $\lor$:

Define $w$ by $w \vDash p ⇔ X \vdash p$ and show that for all $α$,

(∗) $X \vdash α ⇔ w \vDash α$.

The proof is by induction and we have to supplement the part already available in the textbook with the new case, showing that: $X \vdash \alpha \lor \beta ⇔ w \vDash α \lor \beta$.

(i) if $w \vDash α \lor \beta$, then either $w \vDash α$ or $w \vDash \beta$.

By IH, either $X \vdash α$ or $X \vdash \beta$. In both cases, applying $(\lor 1)$, we have $X \vdash \alpha \lor \beta$.

(ii) f $w \nvDash α \lor \beta$, then $w \nvDash α$ and $w \nvDash \beta$, and thus $w \vDash \lnot α$ and $w \vDash \lnot \beta$

By IH, $X \vdash \lnot α$ and $X \vdash \lnot \beta$.

Now assume $X \vdash α \lor \beta$; using $X \vdash \lnot \alpha$ we have $X, \alpha \vdash \lnot \alpha$.

But $X, \alpha \vdash \alpha$, and thus, by $(\lnot 1)$ we have $X, \alpha \vdash \gamma$.

Similarly: $X, \beta \vdash \gamma$.

Now, using $(\lor 2)$, we get $X, \alpha \lor \beta \vdash \gamma$.

Finally, using assumption $X \vdash \alpha \lor \beta$, we conclude with $X \vdash \gamma$, i.e. $X$ is inconsistent, contrary to assumption.

Thus: $X \nvdash \alpha \lor \beta$.

Answer 2

You can't show the other direction, because it is not true.

First, you already showed the system is sound, i.e. we have $X \vdash \alpha \Rightarrow X \vDash \alpha$

Now take $X = A \lor B$, $\alpha = A$, and $\beta = B$ for atomic statements $A$ and $B$.

By IS we have $A \lor B \vdash A \lor B$.

However, we cannot have $A \lor B \vdash A$, for then by soundness we would have $A \lor B \vDash A$, but clearly $A \lor B \not \vDash A$.

Likewise, since $A \lor B \not \vDash B$ we have $A \lor B \not \vdash B$

Answer 3

Here is my finished proof by extending Lemma 4.4 and Lemma 4.5 in the book:

Lemma 4.4: A maximally consistent set X has the property:

$$ X\vdash\alpha\vee\beta\iff X\vdash\alpha\quad\mathrm{or}\quad X\vdash\beta $$

Proof: If $X\vdash\alpha$ or $X\vdash\beta$, then by ($\vee1$) $X\vdash\alpha\vee\beta$. This proves the $\Leftarrow$ direction. For $\Rightarrow$, we do a proof by contradiction:

$X\vdash\alpha\vee\beta$. Now assume "$X\vdash\alpha$ or $X\vdash\beta$" is not true, so since $X$ is maximally consistent, $X\vdash\neg\alpha$ and $X\vdash\neg\beta$. Then by (MR), $X,\alpha\vdash\neg\alpha$ and $X,\beta\vdash\neg\beta$. But $X,\alpha\vdash\alpha$ and $X,\beta\vdash\beta$. So by ($\neg1$), $X,\alpha\vdash\bot$ and $X,\beta\vdash\bot$. Therefore, by ($\vee2$), $X,\alpha\vee\beta\vdash\bot$. So since $X$ is maximally consistent: $X\vdash\neg(\alpha\vee\beta)$. But since $X\vdash\alpha\vee\beta$, $X$ is now inconsistent. Therefore we have a contradiction and have proven

$$ X\vdash\alpha\vee\beta\Rightarrow X\vdash\alpha\quad\mathrm{or}\quad X\vdash\beta $$

Lemma 4.5: A maximally consistent set X is satisfiable.

Proof: Define $w$ by $w\vDash p\iff X\vdash p$. We will show for all $\alpha$,

$$ (*)\quad X\vdash\alpha\iff w\vDash\alpha $$

Now my added induction step for $\vee$:

$$ \begin{align*} X\vdash\alpha\vee\beta&\iff X\vdash\alpha\quad\mathrm{or}\quad X\vdash\beta&\mathrm{(Lemma\ 4.4)}\\ &\iff w\vDash\alpha\quad\mathrm{or}\quad w\vDash\beta&\mathrm{(induction\ hypothesis)}\\ &\iff w\vDash\alpha\vee\beta&\mathrm{(definition)} \end{align*} $$