수학적 귀납법과 정렬원리

  이전 읽을거리: [집합론 기초] ch4. 논리 기호

---

페아노 공리계

 

  수학자 크로네커(Leopold Kronecker, 1823~1891)는 다음의 명언을 남겼다.

 

  자연수는 신의 선물이며, 나머지는 인간의 산물이다.

 

  현대수학의 다양한 대상들은 자연수에 의지하여 존재한다. 예를들어, 실수의 존재성은 유리수에 의해 보장되고, 유리수는 정수, 정수는 자연수에 의해 존재한다. 그러나 자연수는 어쩌면 그 스스로 존재하는 듯 하다. 페아노 공리계는 자연수를 정의하는 한 가지 방법이다.

 

페아노 공리계 (Peano's axioms)
  다음을 만족하는 집합 $\mathbb{N}$ 과 함수 $s:\mathbb{N}\to\mathbb{N}$ , 대상 $1$ 이 존재한다.
  (P1) $1\in\mathbb{N}$
  (P2) $\forall n\in\mathbb{N},\;s(n)\in\mathbb{N}$
  (P3) $\forall m,n\in\mathbb{N},\;s(m)=s(n)\implies m=n$
  (P4) $\forall n\in\mathbb{N},\;s(n)\neq 0$
  (P5) $\forall A\subset\mathbb{N},\;1\in A\land(\forall a\in A,\;s(a)\in A)\implies A=\mathbb{N}$

 

  페아노 공리계의 함수 $s$ 는 따름수(succesor)라고한다. 따름수의 의미는 자연수의 덧셈의 정의에서 나타난다.

 

  Definition.  집합 $\mathbb{N}$ 의 덧셈은 다음과 같이 정의된 이항연산 $+:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ 이다.
  (1) $\forall n\in\mathbb{N},\;n+1=s(n)$
  (2) $\forall m,n\in\mathbb{N},\;m+s(n)=s(m+n)$

 

  자연수의 덧셈의 정의에 따라, 따름수란 $1$ 을 더한 "다음 수" 를 의미한다. 덧셈의 정의를 이용하여 페아노 다섯 공리를 재구성하면 다음과 같다.

 

  (P1) $\mathbb{N}$ 는 $1$ 을 포함한다.

  (P2) $\mathbb{N}$ 의 모든 원소 $n$ 에 대해 $n+1$ 은 $\mathbb{N}$ 에 속한다.

  (P3) $\mathbb{N}$ 의 모든 원소 $m,n$ 에 대해 $m+1=n+1$ 이면 $m=n$ 이다.

  (P4) $\mathbb{N}$ 의 모든 원소 $n$ 에 대해 $n+1=0$ 은 성립하지 않는다.

  (P5) $\mathbb{N}$ 의 모든 부분집합 $A$ 에 대해, $A$ 가 $1$ 을 포함하고 $A$ 의 모든 원소 $a$ 에 대해 $a+1$ 도 $A$ 에 속하면 $A=\mathbb{N}$ 이다.

 

  여기서 마지막 공리 (P5)는 귀납법 공리 또는 수학적 귀납법 원리(principle of mathmatical induction)라고 한다. 이는 직관적으로 자명하게 받아들일 수 있으며, 수학의 증명 방법의 거대한 기둥이다. 수학적 귀납법은 귀납법 공리로부터 즉시 도출된다.

 

수학적 귀납법 (Mathmatical Induction)
  자연수로 표현되는 명제 $P$ 에 대해 다음이 성립한다고 가정하자.
  (1) $P$ 는 $1$ 에 대하여 참이다.
  (2) 모든 자연수 $n$ 에 대해, 만약 $P$ 가 $n$ 에 대하여 참이면 $n+1$ 에 대하여도 참이다.
  그럼 $P$ 는 모든 자연수에 대해 참이다.

 

  Proof.  명제 $P$ 가 참이도록 하는 모든 자연수의 집합을 $A$ 라고 하자. $A$ 는 $\mathbb{N}$ 의 부분집합이다. (1)에 따르면 $A$ 는 $1$ 을 포함하고, (2)에 따르면 $A$ 의 임의의 원소 $n$ 에 대해 $n+1$ 도 $A$ 의 원소이다. (P5)에 따르면 $A=\mathbb{N}$ 이므로, 모든 자연수 $n$ 에 대해 $P$ 가 참이다.   $\square$

 

 

정렬 원리

 

  자연수 $n$ 에 대해, $n$ 보다 작은 모든 자연수의 집합을 $S_n$ 이라고 표기하고 이를 자연수의 절편(section)이라고 한다. $S_1$ 은 공집합이며, $S_{n+1}$ 은 $1$ 부터 $n$ 까지의 자연수의 집합이고 $\{1,\ldots,n\}$ 이라고도 쓴다.

 

  정렬 원리는 매우 직관적이어서 논의의 필요성을 느끼기 힘들지만, 중요한 증명에서 핵심적인 역할을 한다. 더구나 현대수학의 성숙도는 이러한 사실을 증명할 수 있을 정도로 충분하다.

 

정렬 원리 (Well-ordering principle)
  $\mathbb{N}$ 의 공집합이 아닌 부분집합은 항상 최소원소를 갖는다.

 

  Proof.  먼저 모든 $n\in\mathbb{N}$ 에 대해, "$\{1,\ldots,n\}$ 의 공집합이 아닌 부분집합이 항상 최소원소를 가짐"을 귀납법으로 보이자. $n=1$ 의 경우 $\{1\}$ 의 공집합이 아닌 부분집합은 자기 자신뿐이므로 명제가 자명하게 성립한다. 명제가 $n$ 에 대하여 성립한다고 가정하고 $n+1$ 에 대하여도 성립함을 보이자. $\{1,\ldots,n+1\}$ 의 공집합이 아닌 부분집합 $C$ 를 생각하자. 만약 $C$ 가 $n+1$ 을 포함하지 않으면 $\{1,\ldots,n\}$ 의 부분집합과 같으므로 귀납법 가정에 따라 $C$ 는 최소원소를 갖는다. $C$ 가 $n+1$ 을 포함한다고 하자. 만약 $C$ 가 원소로 $n+1$ 하나만 포함한다면, 이는 $C$ 의 최소원소이다. 그 밖의 경우에 대해 공집합이 아닌 집합인 $B=C\cap\{1,\ldots,n\}$ 을 고려하자. $B$ 는 $\{1,\ldots,n\}$ 의 부분집합이므로 귀납법 가정에 따라 최소원소 $c_0$ 를 갖는다. $C$ 의 모든 원소 $c$ 는 $\{1,\ldots,n\}$ 에 속하거나 속하지 않으며, $\{1,\ldots,n\}$ 에 속하는 경우 $c\in B$ 이므로 $c\le c_0$ 이고, $\{1,\ldots,n\}$ 에 속하지 않은 경우 어떤 $m\in B$ 에 대해 $c_0\le m$ 이며 $m<c$ 이므로 $c_0\le c$ 이다. 정리하면 $c_0$ 은 $C$ 의 최소원소이므로 귀납법에 따라 명제가 모든 자연수 $n$ 에 대하여 성립한다.

  이제 본 정리를 증명하자. $\mathbb{N}$ 의 공집합이 아닌 부분집합 $D$ 를 생각하자. $D$ 의 임의의 원소 $n$ 에 대해 $A=D\cap\{1,\ldots,n\}$ 이라고 하면 $A$ 는 $\{1,\ldots,n\}$ 의 공집합이 아닌 부분집합이다. 위의 논의에 따라 $A$ 는 최소원소 $k$ 를 갖는다. $D$ 의 모든 원소 $d$ 는 $\{1,\ldots,n\}$ 에 속하거나 속하지 않으며, $\{1,\ldots,n\}$ 에 속하는 경우 $d\in A$ 이므로 $k\le d$ 이고, $\{1,\ldots,n\}$ 에 속하지 않는 경우 $n<d$ 이며 $k\le n$ 이므로 $k\le d$ 이다. 정리하면 $k$ 는 $D$ 의 최소원소이므로 원하는 결과를 얻는다.   $\square$

 

 

강한 수학적 귀납법

 

  수학적 귀납법은 주어진 명제가 $1$ 에서 성립하고, "$n$ 에서 명제가 성립한다" 라는 가정하에 $n+1$ 에서도 성립함을 보이면 모든 자연수에 대해 성립함을 보장한다. 그러나 $n+1$ 에서 명제가 성립함을 보이기 위해 "$n$ 에서 명제가 성립한다" 라는 가정만으로 부족하다면 수학적 귀납법을 적용할 수 없다. 이러한 단점을 보완한 것이 강한 귀납법이다.

 

강한 귀납법 원리 (Strong Induction Principle)
$$\forall A\subset\mathbb{N},\;(\forall n\in\mathbb{N},\;S_n\subset A\implies n\in A)\implies A=\mathbb{N}$$

 

  Proof.  모순을 보이기 위해 모든 자연수 $n$ 에 대해 $S_n\subset A\Rightarrow n\in A$ 가 성립하고 $A\neq\mathbb{N}$ 이 성립한다고 가정하자. $\mathbb{N}\setminus A$ 는 $\mathbb{N}$ 의 공집합이 아닌 부분집합이므로 정렬원리에 따라 최소원소 $m$ 을 갖는다. 이때 $m=1$ 이라면 $S_m$ 은 공집합이므로 자명하게 $S_m\subset A$ 이고, 그 밖의 경우 $m$ 보다 작은 모든 자연수는 $\mathbb{N}\setminus A$ 에 속하지 않으므로 $A$ 에 속하여 $S_m\subset A$ 가 성립한다. 가정에 따라 $m\in A$ 이어야 하지만 $m\in\mathbb{N}\setminus A$ 이므로 모순. 따라서 원하는 결과를 얻는다.   $\square$

 

 

강한 귀납법 (Strong Induction)
  자연수로 표현되는 명제 $P$ 에 대해 다음이 성립한다고 하자.
  (1) $P$ 는 $1$ 에 대하여 참이다.
  (2) 2 이상의 모든 자연수 $n$ 에 대해, 만약 $P$ 가 $1,\ldots,n-1$ 에 대해 참이면 $n$ 에 대하여도 참이다.
  그럼 $P$ 는 모든 자연수에 대해 참이다.

 

  Proof.  명제 $P$ 가 참이도록 하는 모든 자연수의 집합을 $A$ 라고 하자. $A$ 는 $\mathbb{N}$ 의 부분집합이다. (1)에 따르면 $1\in A$ 이며, $\varnothing\subset A$ 는 항상 참이므로 $S_1\subset A\Rightarrow 1\in A$ 가 성립한다고 할 수 있다. (2)에 따르면 2 이상의 모든 자연수 $n$ 에 대해 $S_n\subset A\Rightarrow n\in A$ 가 성립한다. 이를 종합하면 모든 자연수 $n$ 에 대해 $S_n\subset A\Rightarrow n\in A$ 가 성립하며, 강한 귀납법 원리에 따라 $A=\mathbb{N}$ 이다. 따라서 모든 자연수 $n$ 에 대해 $P$ 가 참이다.   $\square$

 

 

  강한 귀납법을 활용한 한 가지 예시를 소개한다.

 

비네 공식 (Binet's formula)
  피보나치 수(Fibonacci numbers)는 초기값 $F_0=0$ , $F_1=1$ 과 점화식 $F_{n+2}=F_{n+1}+F_n$ 으로 정의되는 수열이다. 다항식 $x^2-x-1$ 의 근 $\phi=\frac{1+\sqrt{5}}{2}$ , $\psi=\frac{1-\sqrt{5}}{2}$ 에 대하여 피보나치 수의 일반항은 다음과 같다.$$F_n=\frac{\phi^n-\psi^n}{\phi-\psi}$$

 

※ $\phi$ 는 황금비로 잘 알려진 수이다.

 

  Proof.  $n=1$ 에 대하여 주어진 일반항이 성립한다. 강한 귀납법으로 증명하자. 2 이상의 자연수 $n$ 에 대하여 주어진 일반항이 $1,\ldots,n-1$ 에서 성립한다고 가정하자. 다음이 성립한다.

$$\begin{align}F_n&=F_{n-1}+F_{n+2}\\&=\frac{1}{\phi-\psi}\left(\phi^{n-1}-\psi^{n-1}+\phi^{n-2}+\psi^{n-2}\right)\\&=\frac{1}{\phi-\psi}\Big(\phi^n\left(\phi^{-1}+\phi^{-2}\right)+\psi^n\left(\psi^{-1}+\psi^{-2}\right)\Big)\end{align}$$

  이때 $\phi$ 는 다항식 $x^2-x-1$ 의 근이므로 $\phi^2-\phi-1=0$ 이다. 따라서 다음을 얻는다.

$$\phi^{-1}+\phi^{-2}=\frac{\phi+1}{\phi^2}=1$$

  이는 $\psi$ 에 대하여도 마찬가지이며, 이를 위 식에 대입하면 원하는 결과를 얻는다.   $\square$

 

 

읽어주셔서 감사합니다.

 

 

References)

[1] James R. Munkres. (2000). Topology. Pearson College Div.

[2] ProofWiki. (2022). Axiom:Peano's Axioms. https://proofwiki.org/wiki/Axiom:Peano%27s_Axioms

[3] Wikipedia. (2022). Mathematical induction. https://en.wikipedia.org/wiki/Mathematical_induction

[4] Brilliant. (2022). Strong Induction. https://brilliant.org/wiki/strong-induction/

---

  이전 읽을거리: [집합론 기초] ch4. 논리 기호