논리학, 그 열한 번째 이야기 | 명제논리에서의 귀납법 ( Induction for Propositional Logic )

수학에서는 귀납법 (Induction)이라고 불리는 논리구조를 사용하는 경우가 상당히 많다. 이번 글에서는 해당 논리 구조에 대해 다뤄볼 것이다. 여기서 말하는 귀납법은 이 글의 수학적 귀납법을 더욱 더 일반화시킨 논리구조이다. 귀납법에서 관심을 가지는 것은 어떤 집합 $U$의 부분집합 $B$를 부분집합으로 가지고 동시에 특정 연산들에 대해 닫혀있는 $U$의 부분집합 중 가장 작은 것이다. 즉, $B$에 어떤 연산들을 유한 번 적용해서 얻을 수 있는 것에 관심을 가진다. 귀납법에 대해 본격적으로 이야기하기에 앞서, 귀납법을 기술하기 위해 필요한 개념들을 알아보자.

 

Definition 1.

어떤 집합 $C \subseteq U$가 집합 $U$ 위의 $n$항 연산 $f$에 대하여 $\forall x_1, x_2, \cdots, x_n \in C, \; f(x_1, x_2, \cdots, x_n) \in C$가 성립하면, 집합 $C$가 $f$에 대하여 닫혀 있다 (Closed)고 한다.

 

Definition 2.

집합 $U$ 위의 연산의 집합 $\mathcal{F}$가 주어졌다고 하자. 이때, 주어진 집합 $B \subseteq U$에 대하여, $B \subseteq C$이고, $C$가 $\mathcal{F}$의 원소들에 대해 닫혀 있으면, $C$를 귀납적 (Inductive)이라고 한다.

 

Definition 3.

집합 $U$ 위의 연산의 집합 $\mathcal{F}$가 주어졌다고 하고, 집합 $C$가 집합 $B \subseteq U$에 대하여 귀납적인 집합들의 교집합이라고 하자. 그러면 $C$를 집합 $B$로부터 $\mathcal{F}$의 원소들에 의해 생성되었다 (Generated)고 한다.

 

Definition 4.

집합 $U$ 위의 연산의 집합 $\mathcal{F}$가 주어졌다고 하자. 이때, 집합 $C$가 집합 $B \subseteq U$에 대하여 집합 $B$로부터 $\mathcal{F}$의 원소들에 의해 생성되었으며 동시에 다음 조건들을 만족하면, 집합 $C$가 집합 $B$로부터 $\mathcal{F}$의 원소들에 의해 Freely Generated 되었다고 한다. (1) $B$와 $\mathcal{F}$의 원소들의 $C$ 위로의 축소의 상이 pairwise disjoint이다. (2) $\mathcal{F}$의 원소들의 $C$ 위로의 축소가 단사함수이다.

 

Definition 5.

집합 $U$ 위의 연산의 집합 $\mathcal{F}$와 집합 $B \subseteq U$가 주어졌다고 하자. 이때, $U$의 원소로 이루어진 유한 수열 $\left< x_1, x_2, \cdots, x_n \right>$가 각 $i \leq n$에 대하여 다음 중 하나를 만족하면 이 수열을 Contruction Sequence라고 한다. (1) $x_i \in B$ (2) 어떤 $m$항 연산 $f \in F$에 대하여 $x_i = f(x_{j_1}, x_{j_2}, \cdots, x_{j_m})$. (단, $j_1, j_2, \cdots, j_m < i$)

 

지금부터의 논의에서는 집합 $U$, 그리고 집합 $U$ 위의 연산의 집합 $\mathcal{F}$와 집합 $B \subseteq U$가 주어졌다고 가정하며, 집합 $C$는 집합 $B$로부터 $\mathcal{F}$의 원소들에 의해 생성된 집합이라고 가정한다.

 

그러면 이제 $B$에 $\mathcal{F}$의 원소들을 유한 번 적용하여 얻은 원소들의 집합이 $B$로부터 생성된 집합임을 보이도록 하자. 다음 정리를 보자.

 

Theorem 1.

집합 $C_n$을 $x$를 마지막 원소로 가지는 길이 $n$의 construction sequence가 존재하는 $x \in U$의 집합이라고 정의하고, 그러한 $C_n$의 합집합을 $C_*$라고 하자. 그러면 $C_* = C$가 성립한다.

 

Proof.

이 글에서는 논의의 편의성을 위해 $\mathcal{F} = \{f,g\}$이고, $f$는 이항 연산, $g$는 단항 연산이라고 가정하자. 보다 일반적인 경우에 대해서는 추후 일차논리에 대해 이야기할 때에 다루도록 하겠다.

먼저 $C \subseteq C_*$임을 보이자. 이를 보이기 위해서는 $C_*$가 귀납적이라는 것만 보이면 충분하다. 즉, $B \subseteq C_*$이고 동시에 $C_*$가 $f$와 $g$에 대하여 닫혀 있음을 보이면 된다. 먼저 $B \subseteq C_*$인 것을 보이자. $C_1 = B$이므로 $B = C_1 \subseteq C_*$이다. 이제 $C_*$가 $f$와 $g$에 대하여 닫혀 있음을 보이면 충분하다.

먼저, $x,y \in C_*$에 대하여 $x \in C_n$, $y \in C_m$임을 가정하자. 그러면 $g(x) \in C_{n+1}$, $f(x,y) \in C_{n+m+1}$임이 자명하므로 $f(x,y), g(x) \in C_*$임을 알 수 있다. 따라서 $C_*$는 $f$와 $g$에 대하여 닫혀 있으며, 이로 인해 $C \subseteq C_*$임이 보여진다.

이제 $C_* \subseteq C$임을 보이자. 이를 위해서는 $x$를 마지막 원소로 가지는 construction sequence가 존재하면 이는 임의의 귀납적인 집합의 원소가 됨을 보이면 된다. 이때, $x$를 마지막 원소로 가지는 construction sequence는 $B$의 원소에 $f$와 $g$를 유한 번 적용하여 $x$를 만드는 방법을 제공하며, 따라서 $x \in C_*$이면, $x$를 원소로 가지지 않고 $B$를 부분집합으로 가지면 필연적으로 $f$와 $g$에 대하여 닫혀 있지는 않게 된다. 즉, $x \in C_*$임은 $x$가 임의의 귀납적인 집합의 원소임을 의미하며, $C$의 정의에 의해 $C_* \subseteq C$임이 보여진다.

$\blacksquare$

 

Theorem 2. 귀납 원리 ( Inductive Principle )

집합 $S \subseteq C$가 집합 $B$를 부분집합으로 가지고 $\mathcal{F}$의 원소들에 대하여 닫혀 있다면, $S = C$이다.

 

Proof.

$S$가 $B$를 부분집합으로 가지고 $\mathcal{F}$의 원소들에 대하여 닫혀 있으므로 $S$는 귀납적인 집합이며, 따라서 $C$의 정의에 의해 $C \subseteq S$임을 알 수 있다. 그런데, $S \subseteq C$이므로 $S = C$이다.

$\blacksquare$

 

위에서 등장한 Theorem 1과 Theorem 2는 얼핏 보면 같은 얘기를 하는 것으로 보일 수 있지만, 사실은 약간 다르다. 예를 들어 $B = \{ \varnothing \}$이라고 하면, 자연수의 정의에 의해 $C = \mathbb{N}$임을 알 수 있다. 이때 Theorem 1은 $\varnothing = 0$에 유한 번의 successor function $s$를 적용하였을 때 임의의 자연수를 나타낼 수 있음을 의미하며, Theorem 2는 자연수의 집합 $\mathbb{N}$이 successor function $s$에 대하여 닫혀 있으며 $\varnothing = 0$을 원소로 가짐을 의미한다. 즉, 흔히 알고 있는 수학적 귀납법은 Theorem 2의 특수한 경우이며, Theorem 1의 특수한 경우는 아니다. 물론 Theorem 1을 통해 수학적 귀납법을 증명할 수는 있다. 약간 말장난처럼 느껴질 수도 있지만, 이 두 정리는 같은 맥락의 이야기를 하고 있으나 분명히 다른 얘기를 하고 있다는 사실을 알아두자. 또한, 한 가지 더 얘기하자면 위의 논의에서 등장한 $\mathcal{F}$가 유한집합일 필요는 없다. $\mathcal{F}$가 무한집합일 때에도 위의 논의는 성립하며, 이러한 일반화된 경우에 대해서는 일차논리를 소개한 후 다루도록 하겠다. 이 글의 내용은 술어논리에서 중요한 정리인 Unique Readability Theorem을 증명하는 데에 사용되는 Recursion Theorem을 증명할 때 이용되며, 이 둘은 다음 글에서 소개할 것이다.