서두르지 말고 쉬지 말자

Every nonempty set of nonnegative integers has a smallest element.모든 비어있지 않은 자연수의 집합은 최소 원소를 가진다.이 문장은 The Well Ordering Principle로 알려져 있다. 이 원리는 이산수학에서 중요한 증명규칙 중 하나를 제공한다.2.1 Well Ordering Proofs 우리는 이미 Well Ordering Pinciple을 당연하게 받아들었다. 예를 들여, $\sqrt 2$가 유리수임을 증영할 때 $\sqrt 2$를 양의 정수 m,n으로 이루어진 기약분수 m/n으로 가정했는데 ,어떻게 이런 가정이 항상 가능할까? 기약분수 꼴로 나타낼 수 없는 양의 정수 m,n으로 이루어진 분수 m/n를 가정하자. 이제 이에 해당하는 분수..

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명의 사람들 중 한명이라고 하자. 여기에는 두가지 경우가 있다.x를 제외한 5명의 사람들 중 최소한 3명은 x..