1.5 Proof by Induction
증명에는 두 가지 type이 있다. Section 1.4에서는 몇 가지 formal proof를 소개한 바 있다. 이 증명은 logic의 rule로부터 이루어졌으므로, logic의 내부에서 일어났다고 말할 수 있다. 이러한 방식의 증명을 internal proof라고 한다. 따라서 formal proof의 시야는 한정되어 있는데, 오직 logic 내에서 쓰여진 sentence만을 증명할 수 있기 때문이다.
이에 반해, logic 그 자체에 대해 쓰여진 무언가를 증명하고 싶다1고 하자. Logic 스스로를 언급(state)하는 그러한 statement들은 logic 내에서는 언급될 수도, 증명될 수도 없다. 이러한 statement에는 external proof가 필요하다. External proof는 meta-mathematical이라고도 한다.
이 Section에서는 external proof의 한 방법으로 induction을 소개한다. Propositional logic의 모든 formula에 대해 성립하는 어떤 성질을 증명하고 싶다고 하자. 어떻게 그걸 ‘모든’ formula에 대해 보일 수 있을까? 모든 formula $F$를 각각 확인할 체계적인 방법이 필요하다. 이에 앞서, 우리는 비슷한 문제를 해결하는 방법을 이미 알고 있다.
Mathematical Induction
수학적 귀납법은 ‘모든’ 자연수에 대한 증명 방법을 제공한다.
예를 들어, $11^{n}-4^{n}$이 모든 자연수 $n$에 대해 $7$로 나누어 떨어진다는 것을 보이고 싶다고 하자. 수학적 귀납법에서는 이를 두 단계로 나누어 해결한다.
$\qquad$1. $n=1$에서 statement가 참임을 보인다.
$\qquad$2. 만약 $n=m$인 어떤 자연수 $m$에 대해 statement가 성립한다면, $n=m+1$에서도 성립한다는 것을 보인다.
이 예시에서는 $n=1$일 때 $11-4=7$이므로 첫 번째 단계가 성립.
$11^{m+1}-4^{m+1}=11^{m+1}-11 \cdot 4^{m}+7 \cdot 4^{m}=11(11^{m}-4^{m})+7 \cdot 4^{m}$으로부터, $11^{m}-4^{m}$이 $7$로 나누어 떨어지면, $11^{m+1}-4^{m+1}$도 나누어 떨어진다는 것을 알 수 있다. 증명 끝.
Propositional logic과 관련된 수학적 귀납법의 예시는 Proposition 1.5.2부터 시작한다. 이는 De Morgan’s Rules의 일반화이다.
Notation 1.5.1
$F_{1}, \dots F_{n}$이 formula들이라고 하자.
\[\bigwedge_{i=1}^{n} F_{i} := F_{1} \wedge F_{2} \wedge \cdots \wedge F_{n}\]
\[\bigvee_{i=1}^{n} F_{i} := F_{1} \vee F_{2} \vee \cdots \vee F_{n}\]
Proposition 1.5.2
$F_{1}, \dots F_{n}$이 formula들이라고 하자.
\[\neg\Bigg(\bigwedge_{i=1}^{n} F_{i}\Bigg) \equiv \Bigg(\bigvee_{i=1}^{n} \neg F_{i}\Bigg)\quad \textrm{and}\quad\neg\Bigg(\bigvee_{i=1}^{n} F_{i}\Bigg) \equiv \Bigg(\bigwedge_{i=1}^{n} \neg F_{i}\Bigg) \]
Proof.
첫 번째부터. $n$에 대한 induction.
먼저 $n=1$을 가정,$ \neg(\bigwedge_{i=1}^{1} F_{i}) \equiv (\bigvee_{i=1}^{1} \neg F_{i})$을 보여야 한다. $``\bigwedge”$, $``\bigvee”$의 정의에 의해, 이는 $\neg (F_{1}) \equiv (\neg F_{1})$와 같고, (C1)에 의해 참.
[Induction Hypothesis] $m \geq 1$일 때, 임의의 formula $F_{1}, \dots F_{m}$에 대해
\[\neg\Bigg(\bigwedge_{i=1}^{m} F_{i}\Bigg) \equiv \Bigg(\bigvee_{i=1}^{m} \neg F_{i}\Bigg)\]
이 성립한다고 가정하자. 다음을 보이고자 한다.
\[\neg\Bigg(\bigwedge_{i=1}^{m+1} F_{i}\Bigg) \equiv \Bigg(\bigvee_{i=1}^{m+1} \neg F_{i}\Bigg)\]
$``\bigwedge”$의 정의에 의해,
\[\neg\Bigg(\bigwedge_{i=1}^{m+1} F_{i}\Bigg) \equiv \neg\Bigg(\Bigg(\bigwedge_{i=1}^{m} F_{i}\Bigg)\wedge F_{m+1}\Bigg)\]
De Morgan’s Rule로부터,
\[\neg\Bigg(\bigwedge_{i=1}^{m+1} F_{i}\Bigg) \equiv \Bigg(\neg\Bigg(\bigwedge_{i=1}^{m} F_{i}\Bigg)\vee \neg F_{m+1}\Bigg)\]
induction hypothesis을 우변에 대입하면,
\[\neg\Bigg(\bigwedge_{i=1}^{m+1} F_{i}\Bigg) \equiv \Bigg(\Bigg(\bigvee_{i=1}^{m} \neg F_{i}\Bigg)\vee \neg F_{m+1}\Bigg) \tag{$\dagger$} \]
마지막으로, $\bigvee$의 정의로부터,
\[\neg\Bigg(\bigwedge_{i=1}^{m+1} F_{i}\Bigg) \equiv \bigvee_{i=1}^{m+1} \neg F_{i}\]
따라서, 임의의 $n$에 대해 $ \neg(\bigwedge_{i=1}^{n} F_{i}) \equiv (\bigvee_{i=1}^{n} \neg F_{i})$가 성립한다.
두 번째 동치 명제는 첫 번째를 이용. $F_{i}$를 $\neg F_{i}$로 치환하면,
\[ \bigvee_{i=1}^{m+1} \neg \neg F_{i} \equiv \neg \Bigg( \bigwedge_{i=1}^{m+1} \neg F_{i} \Bigg)\]
두 formula가 동치이므로, negation을 취해도 동치.
\[ \neg \Bigg( \bigvee_{i=1}^{m+1} \neg \neg F_{i} \Bigg) \equiv \neg \neg \Bigg( \bigwedge_{i=1}^{m+1} \neg F_{i} \Bigg)\]
Double negation에 의해, $\neg(\bigvee_{i=1}^{n} F_{i}) \equiv (\bigwedge_{i=1}^{n} \neg F_{i})$. $\square$
이제 Distributivity도 일반화시킬 수 있다.
Proposition 1.5.3
$\{F_{1}, \dots F_{n}\}$, $\{G_{1}, \dots G_{m}\}$이 formula들의 finite set이라고 하자. 다음 equivalence가 성립한다.
\[ \Bigg( \Bigg( \bigwedge_{i=1}^{n} F_{i} \Bigg) \vee \Bigg( \bigwedge_{j=1}^{m} G_{j} \Bigg) \Bigg) \equiv \Bigg( \bigwedge_{i=1}^{n} \Bigg( \bigwedge_{j=1}^{m} (F_{i} \vee G_{j}) \Bigg) \Bigg) \]
\[ \Bigg( \Bigg( \bigvee_{i=1}^{n} F_{i} \Bigg) \wedge \Bigg( \bigvee_{j=1}^{m} G_{j} \Bigg) \Bigg) \equiv \Bigg( \bigvee_{i=1}^{n} \Bigg( \bigvee_{j=1}^{m} (F_{i} \wedge G_{j}) \Bigg) \Bigg) \]
Proof.
첫 번째 명제만 보인다. 먼저, $B=\bigwedge_{j=i}^{m} G_{j}$라고 하고, 다음 명제를 보이자.
\[\Bigg( \Bigg( \bigwedge_{i=1}^{n} F_{i} \Bigg) \vee B \Bigg) \equiv \bigwedge_{i=1}^{n} (F_{i} \vee B)\]
$n=1$일 때는 당연하게 성립하고, $\bigwedge_{i=1}^{n+1} F_{i} = (\bigwedge_{i=1}^{n} F_{i}) \wedge F_{i+1}$이므로 distributivity rule에 의해
\[ \begin{align*} \Bigg( \Bigg( \bigwedge_{i=1}^{n+1} F_{i} \Bigg) \vee B \Bigg) &\equiv \Bigg( \Bigg( \Bigg(\bigwedge_{i=1}^{n} F_{i}\Bigg) \wedge F_{n+1} \Bigg) \vee B \Bigg) \\ &\equiv \Bigg( \Bigg( \bigwedge_{i=1}^{n} F_{i} \Bigg) \vee B \Bigg) \wedge ( F_{n+1} \vee B) \\ &\equiv \Bigg(\bigwedge_{i=1}^{n} ( F_{i} \vee B)\Bigg) \wedge ( F_{n+1} \vee B) \\ &\equiv \bigwedge_{i=1}^{n+1} ( F_{i} \vee B) \end{align*}\]
위 식에서 세 번째 equivalence는 induction hypothesis를 적용한 것. 이제 다시 $B=\bigwedge_{j=i}^{m} G_{j}$로 되돌리고 $m$에 대해 수학적 귀납법을 한 번 더 사용하면 된다.
두 번째 명제는 첫 번째 명제에 $F_{i}$ 대신 $\neg F_{i}$, $G_{j}$ 대신 $\neg G_{j}$를 취하고 Proposition 1.5.2를 이용하면 끝. $\square$
한 가지, Proposition 1.5.2의 증명에서 약간 미심쩍은 부분이 있다. $(\dagger)$에서 우리는 만약 $G’ \equiv G$이면, $(G \vee F) \equiv (G’ \vee F)$라고 주장하고 있다. 이 부분은 잠시 후 Theorem 1.5.4에서 정당화된다.
Induction on the Complexity of Formulas
어떤 성질 $\mathcal{P}$가 모든 formula $F$에 대해 성립함을 보이고 싶다.
먼저, 모든 atomic formula들이 성질 $\mathcal{P}$를 가짐을 보인다. 이는 mathematical induction에서 $n=1$인 경우를 보이는 것과 대응된다. 이러한 atomic case를 induction basis로 두고, 성질 $\mathcal{P}$가 formula $G$, $H$에서 성립한다고 가정. 이것이 induction hypothesis. 우리의 목표는 성질 $\mathcal{P}$가 $\neg G$, $G \wedge H$, $G \vee H$, $G \rightarrow H$, $G \leftrightarrow H$에서도 성립하는 것을 보이는 것이다. 이것으로 $\mathcal{P}$가 모든 formula에 대해 성립한다는 결론이 나온다.
이상의 과정을 induction on the complexity of $F$라고 한다.
Theorem 1.5.4 [Substitution Theorem]
$F \equiv G$라고 가정. $H$를 $F$를 subformula로 가지는 formula라고 하자.
$H$ 내에서 나타나는 $F$를 $G$로 치환해 얻어진 formula를 $H’$라고 하자. 그러면 $H \equiv H’$이다.
Proof.
$H$에 대한 induction on the complexity.
[Base step] 먼저 $H$가 atomic이라고 가정. 그러면 $H$의 모든 subformula는 $H$ 자신뿐이므로, $F=H$이고, 이로부터 $H’=G$. $F \equiv G$이므로 $H \equiv H’$.
[Induction Hypothesis] $F$를 subformula로 포함하고 있는 formula $H_{1}$, $H_{2}$에 대해 정리의 결론이 성립한다고 가정한다. $H_{1}$, $H_{2}$에서 등장하는 $F$를 $G$로 치환한 formula $H’_{1}$, $H’_{2}$에 대해, $H’_{1} \equiv H_{1}$, $H’_{2} \equiv H_{2}$이다.
[Main Proof] $H= \neg H_{1}$이라고 하자. 그러면 $H’= \neg H’_{1}$. $H’_{1} \equiv H_{1}$이므로, $\neg H’_{1} \equiv \neg H_{1}$. 따라서 $H \equiv H’$이다.
이제 $H$가 다음 중 하나라고 가정 : $H_{1} \wedge H_{2}$, $H_{1} \vee H_{2}$, $H_{1} \rightarrow H_{2}$, $H_{1} \leftrightarrow H_{2}$.
$F$가 $H$의 subformula이므로 $F$는 $H_{1}$의 subformula이거나, $H_{2}$의 subformula이거나, 혹은 $H$ 그 자체일 것이다. $F=H$이면 이는 atomic case와 같다. 따라서 $F$를 $G$로 치환하는 과정은 $H_{1}$ 또는 $H_{2}$ 내부에서 발생한다고 가정할 수 있다. WLOG, $H_{1}$에서 발생한다고 하자.
$H=H_{1} \wedge H_{2}$이면, $H’=H’_{1} \wedge H_{2}$이다. 이 경우 :
\[ \begin{align*} &H_{1} \wedge H_{2} \textrm{ is true iff} \\ &\textrm{both } H_{1} \textrm{ and } H_{2} \textrm{ are true iff} \\ &\textrm{both } H’_{1} \textrm{ and } H_{2} \textrm{ are true (since } H_{1} \equiv H’_{1} \textrm{) iff} \\ &H’_{1} \wedge H_{2} \textrm{ are true.} \end{align*}\]
따라서 $H_{1} \wedge H_{2} \equiv H’_{1} \wedge H_{2}$이다. $H=H_{1} \wedge H_{2}$이므로, $H \equiv H’$을 얻는다.
$H=H_{1} \vee H_{2}$이면, $H’=H’_{1} \vee H_{2}$이다. $\vee$의 정의에 의해, $H \equiv \neg (\neg H_{1} \wedge \neg H_{2})$이고 $H’ \equiv \neg (\neg H’_{1} \wedge \neg H_{2})$. 이제 이전 경우들 $(\neg, \wedge)$에 의해 $H \equiv H’$를 얻는다.
마찬가지로 $H=H_{1} \rightarrow H_{2}$, $H=H_{1} \leftrightarrow H_{2}$라고 가정했을 때도 이전 경우들을 이용하면 $H \equiv H’$를 얻을 수 있다.
그러므로 $F$를 subformula로 갖는 임의의 formula $H$에 대해 $H \equiv H’$가 성립한다. $\square$
사실, 위 정리의 $`` \equiv “$를 $`` \textrm{provably equivalent}”$로 대체해도 정리는 성립한다!
Theorem 1.5.5
$F$와 $G$가 provably equivalent라고 가정. $H$를 $F$를 subformula로 가지는 formula라고 하자.
$H$ 내에서 나타나는 $F$를 $G$로 치환해 얻어진 formula를 $H’$라고 하자. 그러면 $H$와 $H’$는 provably equivalent이다.
Proof.
Theorem 1.5.4와 비슷하다. $H$에 대한 induction on the complexity.
Induction hypothesis는 $H_{1}$과 $H’_{1}$이 provably equivalent, $H_{2}$와 $H’_{2}$이 provably equivalent.
이제 $H$와 $H’$이 provably equivalent가 되는 5가지 경우를 모두 입증하면 된다. Section 1.4의 Table을 이용하자.2 $\square$
Mathematical induction에서의 induction step은 $n=m$에서 문장이 참이라면 $n=m+1$에서도 참임을 보이는 것.
Induction on complexity에서의 induction step은 $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$ 다섯 개로 구성. Theorem 1.5.4의 증명에서 보듯 $\vee$, $\rightarrow$, $\leftrightarrow$는 $\neg$, $\wedge$로부터 빠르게 보여진다. 이는 $\vee$, $\rightarrow$, $\leftrightarrow$가 $\neg$, $\wedge$의 용어로 정의되었기 때문. 이로부터 induction step의 다른 형태를 생각할 수 있겠다.
어떤 성질 $\mathcal{P}$가 모든 formula에 대해 성립함을 보이고 싶다. Induction on complexity에 따르면, 먼저 성질 $\mathcal{P}$가 모든 atomic formula에 대해 성립함을 보이고(base step), 상기 다섯 경우 대신 세 가지 경우만을 보인다(induction step). 먼저 $\mathcal{P}$가 동치 아래에서 보존됨을 보인다. 즉 만약 $F \equiv G$이고 $G$가 성질 $\mathcal{P}$를 가지면, $F$도 그러함을 보인다. 이것이 참이면, 남은 건 $\neg$, $\wedge$에 대해 생각하는 것 뿐. Propositional logic의 모든 formula는 $\neg$와 $\wedge$만을 사용한 어떤 formula와 동치이기 때문이다.
이 방법을 이용한 Induction on complexity는 다음 Section에서 쓰이게 된다.