📂집합론

수학적 귀납법

법칙 ¹

$$ \left[ p(1) \land \left( p(n) \implies p(n+1) \right) \right] \implies \forall n \in \mathbb{N} : p(n) $$ 명제 $p(n) (n=1,2,3, \cdots )$ 에 대해 $p(1)$ 이 참이고 $p(n)$ 을 가정했을 때 $p(n+1)$ 이 성립하면 $p(n)$ 은 참이다.

설명

어떤 식이 자연수에 대해 성립할 때 특히 큰 위력을 발휘하는 증명법으로, 페아노 제5공리라고도 불리며 혹은 ‘수학적’이라는 말을 떼고 그냥 귀납법이라고도 한다. 본래 귀납법이란 현상이나 실체를 경험적으로 모아 어떤 결론을 내리는 것인데, 수학에선 이런 풀이가 없기 때문에 그냥 귀납법이라고 해도 어련히 수학적 귀납법이라고 알아듣는다.

수학적 귀납법은 이해하기 전엔 어렵고 이해하면 너무나 쉬운 증명법이다. 페아노 제5공리라는 이명에서도 알 수 있듯이 ‘공리’라고 할 수 있을만큼 당연한 논리기 때문이다. 수학적 귀납법 수학적 귀납법은 흔히 도미노에 많이 비유된다:

• (1) 도미노의 첫 블럭은 넘어진다. 보통 첫 블럭이 넘어지는 것은 너무나 당연한 사실이다. 왜냐면 당신이 직접 넘어뜨리면 그만이기 때문이다. 그와 마찬가지로, 증명을 할때도 보통은 명제에서 $1$ 을 대입하는 것으로 쉽게 보일 수 있다.
• (2) 앞 블럭이 넘어지면서 뒷 블럭을 넘어뜨린다. $n$ 번째 블럭이 넘어진다고 한다면, 이 블럭은 넘어지면서 $(n+1)$ 번째 블럭도 넘어뜨린다. 도미노에선 블럭들을 일렬로 늘어놓고 앞 블럭이 뒷 블럭을 넘어뜨리기 때문에 사실일 것이다. 이것을 보이는 게 수학적 귀납법의 본질이자 가장 어려운 부분이다.
• (3) 위에서 말한대로라면, 첫 블럭을 넘어뜨리면 모든 블럭이 넘어진다.
  • 당신이 첫번째 블럭을 넘어뜨렸다고 하자.
  • (2)에 따라, $1$ 번째 블럭이 $2$ 번째 블럭을 넘어뜨린다.
  • 또 다시 (2)에 따라, $2$ 번째 블럭은 넘어지면서 $3$ 번째 블럭을 넘어뜨린다.
  • 또 다시 (2)에 따라, $n$ 번째 블럭은 넘어지면서 $(n+1)$ 번째 블럭을 넘어뜨린다.
  • 이렇게 모든 블럭들은 그 다음 블럭을 넘어뜨리기 때문에, 블럭이 얼마나 많든 모두 넘어진다.

다시 수학적 귀납법의 이야기로 돌아오자면, $p(1)$ 이 성립할 때 $p(1+1)$, 즉 $p(2)$ 이 성립한다. $p(2)$ 이 성립할 때, $p(2+1)$ 이 성립하고 $p(n)$ 이 성립할 때 $p(n+1)$ 이 성립한다.

근데 $p(n)$ 이 성립하는걸 가정하면 순환 논증 아닌가?

처음 수학적 귀납법을 접하면 $p(n)$ 이 성립하는 걸 왜 가정해도 되는지 모르겠다고 하는 경우가 있고, 필자 역시 고등학교 때 이 부분이 헷갈렸다. 그런데 실제로 우리가 보이는 것은 $p(n)$ 이 성립하는 것 그 자체가 아니라 $p(n)$ 이 성립할 때 $p(n+1)$ 도 성립한다는 것을 보이는 것이다. 그래서 수학적 귀납법을 간접증명법의 하나라 한다.

• 까놓고 말해서 실제로 모든 $n$ 에 대해서 $p(n)$ 이 성립하지 않더라도 알 바 아니다. 거짓인 가정에서 거짓인 결론이 도출되더라도 그 사이의 논리에 문제가 없으면 된다.
• 만약 그것이 성립한다면, $p(1)$ 이 성립하므로 모든 자연수에 대해 성립한다는 것이 진짜 결론이다. 사실상 증명이 참이냐 거짓이냐 하는 부분은 여기서 결정된다. 적어도 하나는 참인 명제 $p(1)$ 가 존재해줘야 모든 자연수에 대한 $p(n)$ 를 정당화할 수 있다.