1.2 Proof Methods(What is a Proof 1.7~1.9)

1.7. Proof by Cases

 복잡한 증명을 여러 경우들로 나누고 따로 증명하는 것은 흔하고 유용한 증명 전략이다. 이 문제 예제는 인상깊어서 한번 다뤄 보겠다.

 

예제

Every collection of 6 people includes a club of 3 people or a group of 3 strangers. 이라는 정리를 증명해 보자.

두 사람이 만났다 만나지 않았다 둘 중 하나의 상태일수만 있는데, 그룹 안의 모든 사람이 서로 만났다면 우리는 이 그룹을 club이라고 하고, 그룹 안의 모든 사람이 서로 만나지 않았다면 이 그룹을 group of stranger라고 한다.

 

증명.

x를 6명의 사람들 중 한명이라고 하자. 여기에는 두가지 경우가 있다.

1. x를 제외한 5명의 사람들 중 최소한 3명은 x를 만났다.
2. 5명의 사람들 중에 최소한 3명이 x를 만나지 않았다.

 이때, 두 가지 경우 중 하나는 반드시 성립한다. 왜냐하면 5명의 사람을 x와 만났는지 여부에 따라 나눌 때 반드시 둘 중 한가지 경우가 생기기 때문이다. (이 두 가지 경우는 모든 경우를 포함하는데,  두 경우는 각각 P이다와 not P 꼴이므로 이는 대부분의 경우 자명하다.)

1번 경우 : 최소한 3명은 x를 만났다.

이 경우는 다시 2가지 경우로 나뉜다.

1. 3명은 모두 서로가 서로와 만나지 않았다. 그렇다면 이 3명은 서로 모르는 3명의 그룹이된다. -> 정리가 성립한다.
2. 3명 중 적어도 한 쌍은 서로가 서로와 만났다. 따라서, 서로가 서로와 만난 두사람과 x를 묶으면 3명으로 이루어진 club이 된다.-> 정리가 성립한다.

이는 해당 정리가 1번 경우에서 성립한다는 것을 암시한다.

2번 경우  : 최소한 3명은 x를 만나지 않았다.

이 경우는 다시 2가지 경우로 나뉜다.

1. 3명은 모두 서로가 서로를 만났다. 따라서, 3명이 하나의 club을 이룬다. -> 정리가 성립한다.
2. 3명 중 적어도 한 쌍이 서로 만나지 않았다. 그렇다면 x와 그 쌍을 포함하면 3명으로 이루어진 낯선사람의 그룹이 된다. -> 정리가 성립한다.

이는 해당 정리가 2번 경우에서 성립하는 것을 암시한다. 그러므로 모든 경우에서 이 정리는 성립한다.

1.8. Proof by Contradiction

 Proof by contradiction 또는 indirect proof에서 우리는 만약 어떤 명제가 거짓이라면 몇몇 거짓인 사실은 진실이 될 수 있다는 것을 보인다. 거짓인 사실은 진실이 될 수 없기 때문에, 그 명제는 반드시 참이다.

 Proof by contradicion은 항상 실행가능한 시도이다. 그러나 우회적인 증명은 조금 난해할 수 있기 때문에 직접적인 증명이 존재한다면 일반적으로 더 선호된다.

명제 P를 proof by contradiction으로 증명한다면 다음 절차를 따르자.

1. Write, "We use proof by contradiction"
2. "Suppose P is false"
3. Deduce something known to be false (a logical contradiction)
4.Write, "This is a contradiction. Therefore, P must be true."

1.9. Good Proofs in Practice

 증명이라는 개념은 계속 변화한다. 연구 논문에서의 증명은 일반적으로 이해하기 어렵고 소수의 전문가들만이 이해할 수 있다. 반대로, 이 수업의 초반 증명들은 수학자들에게 지루하게 여겨질 것이다. 실제로 우리가 좋은 증명이라고 받아들이는 것은 우리가 이 수업 초반에 좋은 증명이라고 받아들이는 것과 달라질 것이다. 그렇게 되더라도, 우리는 좋은 증명을 작성하는 일반적인 팁을 제공하려고 한다.

1. State your game plan 사고의 일반적인 흐름을 알려주며 시작하는 것이 좋다. "우리는 여러 경우로 나눠 각 경우를 분석할 것이다.", "우리는 모순을 밝혀서 이를 증명할 것이다." 처럼 말이다.
2. Keep a linear flow 주장의 각 단계는 하나의 이상의 이해가능한 순서를 따라가야 한다.
3. A proof is an essay not a calculation 증명을 무슨 적분 계산하는 것 처럼하는 사람들이 있다. 이들은 결과를 설명없이 표현만 늘어놔서 보이려고 한다. 이것보다는 몇 가지 방정식이 들어있는 essay처럼 작성하는 것이 바람직하다. 완전한 문장을 사용해라
4. Avoid excessive symbolism 과도하게 수학 기호를 사용하는 것보다는 언어로 설명하는 것이 합리적이라면 그렇게 해라.
5. Revise and simplify 독자들이 감사해 할 것이다.
6. Introduce notation thoughtfully 가끔식 주장이 변수 정의, 새로운 개념 고안, 새로운 용어 정의로 아주 간단해질 때가 있다. 그라나 이를 매우 신중하게 해야 한다. 그리고, 새로운 변수, 용어 혹은 표기법의 의미를 반드시 정의해야 하며, 그냥 갑자기 사용하기 시작해서는 안된다.
7. Structure long proofs 만약 증명이 자주 언급되지만 증명은 아직 안된 사실을 필요로 한다면, preliminary lemma로 따로 두는게 좋다. 같은 주장을 반복할 때도 general lemma로 두어서 반복을 피하자.
8. Be wary of the "obvious" 증명에서 무언가가 정말로 자명한 사실이라면 그냥 넘어가도 된다. 하지만 그것이 나뿐만 아니라 독자에게도 자명하게 여겨지는 사실인지를 기억해야 한다.(보통의 경우 그렇지 않다.)
9. Finish 당신은 증명의 어느 부분에서 중요한 사실들을 확립할 것이다.