논리학, 그 두 번째 이야기 | 연역 정리 ( Deduction Theorem )

연역 정리는 Formal Axiomatic Theory의 메타 정리로, $\Gamma, \mathscr{B} \vdash \mathscr{C}$이면 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}$이라는 정리이다. 즉, $\mathscr{B}$를 가정으로 두고 $\mathscr{C}$를 증명할 수 있다면 $\mathscr{B} \Rightarrow \mathscr{C}$는 정리가 된다는 것을 의미하며, 이는 수학에서 조건절의 증명이 왜 논리적으로 참이 되는지를 설명해준다. 일단 연역 정리를 증명하기에 앞서, 한 가지 보조정리를 증명하자.

 

Lemma 1.

$\mathscr{B}$가 $L$의 wff라면 $\left( \mathscr{B} \Rightarrow \mathscr{B} \right)$는 정리이다. 즉, $\vdash \mathscr{B} \Rightarrow \mathscr{B}$이다.

 

Proof.

다음과 같이 증명할 수 있다.

$$\begin{array}{rll} 1. & \mathscr{B} \Rightarrow \left( \left( \mathscr{B} \Rightarrow \mathscr{B} \right) \Rightarrow \mathscr{B} \right) & \text{(A1)} \\ 2. & \left( \mathscr{B} \Rightarrow \left( \left( \mathscr{B} \Rightarrow \mathscr{B} \right) \Rightarrow \mathscr{B} \right) \right) \Rightarrow \left( \left( \mathscr{B} \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{B} \right) \right) \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{B} \right) \right) & \text{(A2)} \\ 3. & \left( \mathscr{B} \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{B} \right) \right) \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{B} \right) & \text{1, 2, MP} \\ 4. & \mathscr{B} \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{B} \right) & \text{(A1)} \\ \hline \therefore & \mathscr{B} \Rightarrow \mathscr{B} & \text{3, 4, MP} \end{array}$$

여기서 사용된 공리꼴 (A1)과 (A2)는 이글에서의 (A1)과 (A2)이다.

이제 보조정리도 증명되었으니 연역 정리를 증명해보자.

 

Theorem 1. 연역 정리 (Deduction Theorem)

$\mathscr{B}$와 $\mathscr{C}$를 wff라고 하고 $\Gamma$를 wff의 집합이라고 하자. 만약 $\Gamma, \mathscr{B} \vdash \mathscr{C}$라면, $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다.

 

Proof.

$\mathscr{C}_1, \mathscr{C}_2, \cdots, \mathscr{C}_n$을 $\mathscr{C}$의 $\Gamma \cup \{ \mathscr{B} \}$으로부터의 증명이라고 하자. 이제 유한 귀납법을 통해 $1 \leq j \leq n$인 $j$에 대하여 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_j$임을 보일 것이다.

먼저, $\mathscr{C}_1$은 증명의 정의에 의해 공리이거나 $\Gamma \cup \{ \mathscr{B} \}$의 원소일 수밖에 없다. 이때, 공리꼴 (A1)에 의해 $\mathscr{C}_1 \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{C}_1 \right)$는 공리이다. 따라서 만약 $\mathscr{C}_1$이 공리이거나 $\Gamma$의 원소라면, MP에 의해 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_1$이다. 또한, $\mathscr{C}_1$이 $\mathscr{B}$라면, Lemma 1에 의해 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_1$이다. 따라서, 그 어떠한 경우에도 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_1$임을 알 수 있다. 따라서 $j=1$인 경우에는 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_j$이다.

이제, $1 \leq k < j$에 대하여 항상 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_k$임을 가정하자. 그러면 $\mathscr{C}_j$는 공리이거나, $\Gamma$의 원소이거나, $\mathscr{B}$이거나, $l < j$이고 $m < j$인 $\mathscr{C}_l$과 $\mathscr{C}_m$에 MP를 적용한 결과가 될 것이다. 만약 $\mathscr{C}_j$가 공리이거나, $\Gamma$의 원소이거나, $\mathscr{B}$라면, $j=1$인 경우와 같은 상황이므로 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_j$이다. 만약 $\mathscr{C}_j$가 $l < j$이고 $m < j$인 $\mathscr{C}_l$과 $\mathscr{C}_m$에 MP를 적용한 결과라면, 일반성을 잃지 않고, $\mathscr{C}_m$과 $\mathscr{C}_l \Rightarrow \mathscr{C}_j$은 같다고 가정할 수 있다. 그러면 귀납가정에 의해 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_l$이고, $\Gamma \vdash \mathscr{B} \Rightarrow \left( \mathscr{C}_l \Rightarrow \mathscr{C}_j \right)$이다. 이때, 공리꼴 (A2)에 의해 $\left( \mathscr{B} \Rightarrow \left( \mathscr{C}_l \Rightarrow \mathscr{C}_j \right) \right) \Rightarrow \left( \left( \mathscr{B} \Rightarrow \mathscr{C}_l \right) \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{C}_j \right) \right)$는 공리이므로 MP에 의해 $\Gamma \vdash \left( \mathscr{B} \Rightarrow \mathscr{C}_l \right) \Rightarrow \left( \mathscr{B} \Rightarrow \mathscr{C}_j \right)$이며, 여기서 다시 MP를 적용하면, $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_j$이다.

따라서 귀납법에 의해 $1 \leq j \leq n$인 모든 $j$에 대하여 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_j$이다. 이때, $j = n$인 경우를 살펴보면, $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}_n$이다. 이때, $\mathscr{C}_1, \mathscr{C}_2, \cdots, \mathscr{C}_n$이 $\mathscr{C}$의 $\Gamma \cup \{ \mathscr{B} \}$으로부터의 증명이므로, $\mathscr{C}_n$은 $\mathscr{C}$이다. 따라서 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다.

$\blacksquare$

 

이제 조건절의 증명은 가정으로부터 결론을 얻어내는 형태만으로도 충분하다는 사실을 얻게 되었다. 또한, 연역 정리에 공리꼴 (A3)가 전혀 쓰이지 않았다는 것을 유의하자. 이는 배중률을 거부하는 직관주의 논리에서도 연역 정리가 성립한다는 것을 의미하며, 연역 정리가 formal axiomatic theory가 아닌 보다 일반적인 체계에서 성립한다는 것을 의미한다. 또한, 연역 정리로부터 다음과 같은 따름 정리를 얻을 수 있다.

 

Corollary 1.

$\mathscr{B}$와 $\mathscr{C}$가 wff이고 $\Gamma$가 wff의 집합이라고 하자. 그러면 $\Gamma, \mathscr{B} \vdash \mathscr{C}$와 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}$는 논리적으로 동치이다.

 

Proof.

연역 정리에 의해 $\Gamma, \mathscr{B} \vdash \mathscr{C}$이면 $\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다. 이제 역을 증명하자.

$\Gamma \vdash \mathscr{B} \Rightarrow \mathscr{C}$이면 $\vdash$의 성질에 의해 $\Gamma, \mathscr{B} \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다. 또한, $\Gamma, \mathscr{B} \vdash \mathscr{B}$임은 자명하므로 MP에 의해 $\Gamma, \mathscr{B} \vdash \mathscr{C}$이다.

$\blacksquare$

 

Corollary 2.

$\mathscr{B}$와 $\mathscr{C}$가 wff라고 하자. 그러면 $\mathscr{C} \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다.

 

Proof.

$\mathscr{C}, \mathscr{B} \vdash \mathscr{C}$임은 자명하다. 따라서 연역 정리에 의해 $\mathscr{C} \vdash \mathscr{B} \Rightarrow \mathscr{C}$이다.

$\blacksquare$