4
$\begingroup$

I am reading Dag Prawitz's "Natural Deduction: A Proof-Theoreritcal Study" and am confused by the proof of Theorem 1, Chapter 3 that:

If $\Gamma \vdash_{\mathsf{C}'} A$, then there is a deduction in $\mathsf{C}'$ of $A$ from $\Gamma$ in which the consequence of every application of the $\bot_\mathsf{C}$-rule is atomic.

where $\mathsf{C}'$ is the classical logic system without the $\lor$ or $\exists$ rules.

In the inductive step of this proof we transform the deduction $$\underline{[\lnot(B\rightarrow C)]} \\ \underline{\Sigma} \\ \underline{\bot} \\ (B\rightarrow C) \\ \Pi_1$$ 1

into

$$\underline{B \quad B \rightarrow C} \\ \qquad \qquad \underline{C \qquad \lnot C} \\ \qquad \qquad \underline{\bot} \\ \qquad \qquad [\lnot(B\rightarrow C)] \\ \qquad \qquad \underline{\Sigma}\\ \qquad \qquad \underline{\bot}\\ \qquad \qquad \underline{C}\\ \qquad \qquad \underline{(B \rightarrow C)}\\ \qquad \qquad \Pi_1$$ 2

Where my confusion arises is that Prawitz then states that the new applications of the $\bot_\mathsf{C}$ rules all have consequences which have degree less than that of $B \rightarrow C$, but to me it seems that this new proof has $\lnot(B \rightarrow C)$ as a consequence of a $\bot_\mathsf{C}$ rule and this would have a higher degree than that of $B \rightarrow C$. I'd appreciate it if someone could point out where I'm going wrong.

Also, if my formatting is confusing, I have attached the reference proofs from the book.

$\endgroup$
2
  • 1
    $\begingroup$ I strongly suspect that the hypothesis in Theorem 1 is "If $\Gamma \vdash_{\mathsf{C}'} A$" and not "If $\Gamma \vdash_{\mathsf{C}} A$", otherwise Theorem 1 may be false if $\exists$ or $\lor$ occurs in $A$. $\endgroup$ Commented Sep 10 at 19:06
  • 1
    $\begingroup$ I checked on Prawitz's book. Indeed, the hypothesis of Theorem 1 in Chapter 3 is "If $\Gamma \vdash_{\mathsf{C}'} A$". I modified the post accordingly. $\endgroup$ Commented Sep 11 at 8:59

1 Answer 1

Reset to default
4
$\begingroup$

Prawitz's transformation rewrites the derivation 1 into the derivation 2 by replacing one application of the $\bot_\mathsf{C}$-rule discharging $n \in \mathbb{N}$ occurrences of the formula $\lnot (B \to C)$ with one application of the $\bot_\mathsf{C}$-rule discharging $n$ occurrences of the formula $\lnot C$. Note that in the derivation 2, the rule inferring $\lnot(B \to C)$ from $\bot$ is not $\bot_\mathsf{C}$ but $\lnot_i$ (discharing the hypothesis $B \to C$).

If the weight of a derivation $\Pi$ is given by the finite multiset of the degrees of the conclusions of the $\bot_\mathsf{C}$-rules in $\Pi$, then the weight of 1 is strictly greater than the weight of 2 according the (well-founded) multiset ordering, because the weight of 1 is the finite multiset $[d_1, \dots]$ where $d_1$ is the degree of the formula $B \to C$ (the conclusion of the $\bot_\mathsf{C}$-rule in 1), while the weight of 2 is a finite multiset $[d_2, \dots]$ where $d_2$ is the degree of the formula $C$ (the conclusion of the $\bot_\mathsf{C}$-rule in 2), and clearly $d_1 > d_2$ (the $\dots$ in the two finite multisets stand for "the same stuff"). Hence, by successively repeating Prawitz's transformations, you finally obtain a derivation from $\Gamma$ to $A$ in which the conclusion of each application of the $\bot_\mathsf{C}$-rule is atomic.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.