도미노 쓰러뜨리기

도미노를 열 개쯤 세워 놓고 첫 번째를 살짝 밀어 보세요. 끝까지 넘어집니다.

이제 가운데 하나를 멀찍이 떼어 놓고 다시 밀어 보세요. 거기서 멈춥니다. 「앞이 넘어지면 뒤도 넘어진다」가 한 곳에서만 깨져도 그 뒤는 하나도 안 넘어집니다.

그리고 첫 번째를 안 밀면요? 아무 일도 안 일어납니다. 두 가지가 다 있어야 합니다.

1부터 까지의 합이 임을 보입시다.

① 첫 도미노 — 일 때 왼쪽은 1, 오른쪽은 . 같습니다.

② 다음 도미노 — 에서 참이라 하고 을 봅니다.
.
꼴 그대로입니다. 끝났습니다.

귀납법은 두 걸음입니다.

기초 — 가장 작은 자리에서 참임을 실제로 보인다.
귀납 — 에서 참이면 에서도 참임을 보인다.

흔한 함정 셋 —
① 기초를 건너뛴다. 둘째 걸음만으로는 아무것도 증명되지 않습니다.
② 가정을 결론으로 쓴다. 「 에서 참」만 쓸 수 있고 「모든 에서 참」은 못 씁니다.
③ 둘째 걸음이 첫 자리에서 통하지 않는다. 에서 논증이 성립하는지 꼭 확인합니다.

페아노 공리의 다섯째가 곧 귀납법입니다. 「1을 담고, 어떤 수를 담으면 그다음 수도 담는 집합은 자연수 전체다」.

이것은 정렬 원리(자연수의 공집합 아닌 부분집합에는 항상 최소원이 있다)와 서로 같은 말입니다. 한쪽을 인정하면 다른 쪽이 따라 나옵니다.

더 넓히면 초한귀납법이 됩니다. 자연수를 넘어 순서수 전체에서 같은 논법을 씁니다. 그때는 「바로 앞이 없는 자리」가 있어서, 「앞의 것이 모두 참이면 이것도 참」이라는 꼴로 바꿔 씁니다.