0. 증명 규칙 복습
증명이란, 어떤 규칙에 따라서 문장을 나열하는 것이었습니다. 이때 증명에 사용된 규칙은 추론가능한 명제들을 증명에 나열하게 되고, 추론가능한 명제들은 건전한 논리적 귀결이었습니다. 즉, 증명은, 이전의 모든 문장들이 참일 때 이전에 나오지 않았던 새로운 참인 문장을 만들어나가는 과정이라고 생각할 수 있습니다.
1. 귀납법
induction:귀납법은 다음 명제를 말합니다.
(for all n)(P(n)->P(Sn))&&P(0)ㅑ(for all m)P(m)
이해하기 쉽게 자연어로 풀어 쓰면, 0에 대한 명제 P(0)이 참이고, 어떤 자연수 n에 대해서도 n에 대해 쓴 명제 P(n)이 참이면 Sn에 대해 쓴 P(Sn)도 참이 된다면, P(n)은 어떤 자연수에 대해서도 참이라는 것입니다.
예를 들어, 뒤에 (for all n)P(n)에 US를 적용한 (for all n)(P(n)->P(Sn))&&P(0)ㅑP(3)을 증명해 봅시다.
Proof.
| 1. | P(0) | P rule | |
| 2. | (for all n)(P(n)->P(Sn)) | P rule | |
| 3. | P(0)->P(S0) | US | 2 |
| 4. | P(0)->P(1) | T rule | 3, def of Successor |
| 5. | P(1) | T rule | 1 4 |
| 6. | P(1)->P(S1) | US | 2 |
| 7. | P(1)->P(2) | T rule | 6, def of Successor |
| 8. | P(2) | T rule | 5 7 |
| 9. | P(2)->P(S2) | US | 2 |
| 10. | P(2)->P(3) | T rule | 9, def of Successor |
| 11. | P(3) | T rule | 8 10 |
4, 7, 10은 충분히 생략해도 됩니다. 표기법의 차이라고 생각하고 넘어가셔도 좋습니다.
여기서 주목할 부분은, P(1), P(2)가 중간에 만들어지고, 그것과 같은 방식으로 P(3)가 만들어졌습니다. 0에서 1, 1에서 2, 2에서 3, ...과 같은 방식으로 순서대로 하나씩 증명이 되고, 무한히 하면 모든 자연수에서 추론가능함을 보일 수 있다는 것이 내용입니다.
2. 자연수의 크기와 최소선택원리
자연수는 크기를 비교할 수 있습니다. 자연수는 자기자신을 크기로 가지는데, 크기의 대소는 노이만식 자연수 구성에서 a is subset of b일때 b가 a 이상이라고 합니다. 기호로 <=로 쓰는데, 실제로 관계 "이상"은 부분순서관계입니다. b가 a 이상이라는 것은 a가 b 이하인 것과 동일합니다. 이상과 이하는 다른 심볼로 쓰인 같은 문장입니다.
최소선택원리란, 어떤 자연수의 부분집합 A에 대해, (exist n)(for all x)(n<=x)임을 의미합니다. 다시 쓰면 (exist n)(for all x)(P(n)&&P(x)->n<=x)임을 뜻하고, A가 {k|P(k)}인 경우입니다.
이 최소선택원리는 참임을 가정합니다. 이후 만약 ZFC라던지, 집합론에 대해 조금 더 다루게 된다면 다루게 될 내용인데, ZFC의 선택공리에서 유도될 수 있습니다. 선택공리에 적절하게 US를 적용하면 얻을 수 있습니다. 일단 참임을 가정하고 진행합니다.
최소선택원리를 자연어로 풀어 쓰면, 어떤 원소보다도 이하인 원소가 존재한다는 뜻입니다. 이때 이를 만족하는 원소를 최솟값이라고 합니다. 즉, 자연수의 부분집합에서 (for all x)(n<=x)를 만족하는 n을 최솟값이라고 하는 것입니다.
이때 최솟값은 항상 유일하게 존재합니다. 어떤 조건 P(x)를 만족하는 x가 유일하다는 것은, (for all a)(for all b)(P(a) && P(b) ->a=b)임을 뜻합니다. 이때 최솟값이 유일하다는 증명을 할 수 있습니다.
Theorm. 최솟값은 유일하다.
Proof.
| 1. | (for all i) x<=i && (for all j) y<=j | AP | |
| 2. | (for all i) x<=i | T | 1 |
| 3. | (for all j) y<=j | T | 1 |
| 4. | x<=y | US | 2 |
| 5. | y<=x | US | 3 |
| 6. | x<=y && y<=x | T | 4, 5 |
| 7. | x=y | T | 6, *** |
| 8. | (for all i) x<=i && (for all j) y=j -> x=y | CP | 1, 7 |
| 9. | (x는 최솟값 && y는 최솟값)->x=y | T | def of 최솟값 |
| 10. | (for all a)(for all b)((a는 최솟값 && b는 최솟값)-> a=b) | UG | |
| 11. | 최솟값은 유일하다. | T | def of 유일 |
***로 표시한 부분은, 이상이기도 이하이기도 한 두 원소는 동치이다 하는 원리인데, 부분순서관계임을 알고 있으므로 반대칭적인 성질을 이용해서 동치임을 추론할 수 있습니다.
3. 수학적 귀납법
induction:수학적 귀납법은 자연수에서 P(0) && (for all n)(P(n)->P(Sn))ㅑ(for all x)P(x)임을 의미합니다. 어떤 명제함수 P에 대해서도 성립합니다.
| 1. | P(0) | P | |
| 2. | (for all n)(P(n)->P(Sn)) | P | |
| 3. | !(for all x)P(x) | AP | |
| 4. | (exist x)!P(x) | T | 3 |
| 5. | (exist x) (!P(Sa) && (for all j)(!P(j) -> x<=j)) | T | 4, 최소선택원리 |
| 6. | (for all j)(!P(Sa) && (!P(j) -> Sa<=j)) | ES | 5 *** |
| 7. | P(a)->P(Sa) | US | 2 |
| 8. | !P(Sa) && (for all j)(!P(j) -> Sa<=j) | T | 6 |
| 9. | !P(Sa) | T | 8 |
| 10. | !P(a) | T | 9 |
| 11. | !P(Sa) && (!P(a) -> Sa<=a) | US | 6 |
| 12. | !P(a) -> Sa<=a | T | 11 |
| 13. | Sa<=a | T | 10, 12 |
| 14. | {a}|a <= a | T | 13, def of Successor |
| 15. | !(a=Sa) | T | def of Successor |
| 16. | a is subset of {a}|a | T | def of subset |
| 17. | a<=Sa | T | 16, def of <= |
| 18. | (Sa<=a && a<=Sa) -> a=Sa | T | def of <= : <= antisymmetric |
| 19. | Sa<=a && a<=Sa | T | 13, 17 |
| 20. | a=Sa | T | 18, 19 |
| 21. | !(a=Sa)&&a=Sa | T | 15, 20 |
| 22. | P(0) && (for all n)(P(n)->P(Sn)) ㅑ (for all x)P(x) | IP | 3, 21 |
자연어로 쉽게 풀어 설명하면, !P(x)인 x들의 집합의 최솟값 a를 생각할 때, a보다 작은 !P(x)를 만족하는 x가 존재하고, a가 최솟값이라는 조건에 모순되므로 IP를 적용해서 참임을 얻을 수 있습니다.
4. 수학적 귀납법을 이용한 증명의 예시
최근 많이 올라온 제곱의 합을 구하는 공식은 수학적 귀납법을 이용한 증명이 제일 많이 알려져 있습니다.
Theorm. 
Proof.
P(0), (for all n)P(n)->P(Sn) ㅑ (for all n) P(n)
이외에도 다양한 증명이 수학적 귀납법을 이용해 증명할 수 있습니다.
변형된 수학적 귀납법도 있는데, 생략하겠습니다. 혹시, 알고리즘에 대해 다룰 기회가 있다면 dp에서 다루도록 하겠습니다.
5. 마치며
검수해야할 내용이 많아지기도 하고, 기타 여러가지 귀찮은 작업때문에 업로드 텀이 길어지고 있습니다.
추가로, 이번 화부터 증명 부분에서 T rule의 넘버링을 생략하겠습니다. 이전에 올렸던 몇 가지 T rule들은 증명 과정에서 넘버링을 옆에 별도로 표기했으나, 진리표를 통해 충분히 보일 수 있다고 생각합니다. 사실 그 표가 사라지고 내용만 남아 참조하기 힘들어져서 그렇습니다. 그때 표와는 조금 다르지만 이미지파일로 올려보도록 하겠습니다. 이 외에 다른 T rule들은 위에서 쓴 것처럼 T rule인 이유를 간단하게 쓰겠습니다.
