1.3 Well Ordering Principle(The Well Ordering Principle 2.1~2.3)

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를 가정하자. 이제 이에 해당하는 분수들의 분자 집합 C를 정의하자. 이때, $m \in C$ 이므로 C는 비어있지 않다.

 Well Ordering에 의해서 여기에는 반드시 가장 작은 정수 $m_{0} \in C $가 존재한다. 따라서, 집합 C의 정의에 의해 다음을 만족하는 $n_{0} > 0$이 존재한다.

분수 $m_{0} / n_{0}$는 기약분수로 나타낼 수 없다.

 이는 m_{0}와 n_{0}가 반드시 공통 소인수 p > 1을 갖는다는 말이다. 그러나

$\frac{m_{0}/p}{n_{0}/p}=\frac{m_{0}}{n_{0}}$

이다.

  여기서 왼쪽 분수를 기약분수로 표현하는 어떤 방법이라도 $m{0}/n_{0}$에도 적용될 수 있다. 이는 다음을 암시한다.

분수 $\frac{m_{0}/p}{n_{0}/p}$는 기약분수로 나타낼 수 없다.

 따라서, C의 정의에 의해, 분자 $m_{0}/p$는 C의 원소이다. 그러나 $m_{0} / p < m_{0}$ 이므로 이는 $m_{0}$가 C의 가장 작은 원소라는 가정에 모순된다.

 집합 C가 비어있지 않는다는 가정이 모순됨을 알았다. 즉, C는 비어있다. 이는 기약분수로 나타낼 수 없는 분자는 존재하지 않고, 더 나아가서 기약분수로 나타낼수 없는 분수는 없다는 것을 의미한다.

2.2 Template for Well Ordering Proofs

모든 자연수 n에 대해 성립하는 어떤 성질 P(n)을 증명하기 위해서 Well Ording Principle을 쓰는 표준 양식은 다음과 같다.

To prove that "P(n) is true for all n ∈ N" using the Well Ordering Principle:
- Define the set C, of counterexamples to P being true. Specifically, define
 C ::= { n ∈ N | Not(P(n)) is true}.
(The notation {n | Q(n)} means "the set of all elements n for which Q(n) is true." See Section 4.1.4)
- Assume for proof by contradiction that C is nonempty.
- By the Well Ordering Principle, there will be a smallest element, n, in C.
- Reach a contradiction some how - often by showing that P(n) is actually true or by showing that there is another member of C that is smaller than n. This is the open-ended part of the proof task.
- Conclude that C must be empty, that is, no counteresamples exist.
P(n)이 모든 자연수 n에 대하여 참이라는 것을 증명하는 법 :
- P가 참인 경우에 대한 반례들의 집합을 C라고 정의한다. 즉,
C ::= { n ∈ N | Not(P(n)) is true}라고 정의한다.
( {n | Q(n)}라는 표현은 "Q(n)이 참인 모든 원소 n들의 집합:이다. 4.1.4절에서 본다)
- 모순을 이용한 증명을 위해 C를 비어있지 않는다고 가정한다.
- Well Ordering Principle에 의해 C 안에는 가장 작은 원소 n이 있을 것이다.
- 어떻게 하든 간에 모순에 도달한다. 주로 P(n)이 실제로는 사실임을 보이거나 n 보다 작은 C의 원소가 존재함을 보인다.  이 부분이 증명과정에서 열린(직접 알아내야 할) 부분이다.
- 결론적으로 C가 반드시 비어있음을 증명한다.즉, 반례가 존재하지 않는다로 결론 짓는다.

다음은 해당 양식의 예시이다.

$1+2+3 \ldots +n=n(n+1)/2$ for all nonnegative integer n (2.1)

위 명제를 증명해보자.

 모순을 이용한다. (2.1)이 거짓이라고 가정하자. 그러면 어던 정수는 반례에 해당할 것이다. 이들이 원소인 집합 C를 다음과 같이 정의하자.

$C := {n \in N | 1+2+3 \ldots +n \neq \frac{n(n+1)}{2}}$

 반례가 존재한다고 가정하면 C는 비어있지 않은 양의 정수로 이루어진 집합이다. 이때, Well Ordering Principle에 의해 C는 가장 작은 원소 c를 가진다.

 c가 가장작은 반례이기 때문에 우리는 (2.1)이 n=c일 때 거짓이고 n<c인 모든 n에 대해서는 참이라는 것을 알 수 있다.다만, n=0에서 (2.1)은 참이므로 c>0이다. 이는 c-1은 c보다 작은 양의 정수이고 c-1에서 (2.1)은 참이라는 것을 의미한다.

즉,

$1+2+3+\ldots+(c-1)=\frac{(c-1)c}{2}$

이 성립한다.

그리고 양변에 c를 더하면 우리는 다음을 얻는다.

$ 1+2+3+\ldots +(c-1)+c= \frac{(c-1)c}{2} + c=\frac{c^{2}-c+2c}{2}=\frac{c(c+1)}{2}$

이는 c에 대해서 식 (2.1)이 성립한다는 것을 의미한다. 이는 모순이다.

따라서, 증명하고자 하는 명제는 참이다.

2.3 Factoring into Primes

 우리는 이전에 Prime Factorization Theorem을 당연하게 받아들였다(Unique Facorization Theorem 혹은 Fundamental Theorem of Arithmatic 이라고도 불린다). 이 정리는 1보다 큰 모든 정수는 소수의 곱으로 이루어진 유일한 표현을 가진다는 것을 명시한다. 이는 당연하게 받아들이는 친밀한 수학적 사실이지만, 자세히 살펴보는 것으로는 확실하지가 않다. 소인수 분해의 유일성을 추후에 다루겠지만, well ordering으로 모든 1보다 큰 정수는 여러 소수들의 곱으로 표현할 수 있다는 것을 증명할 수 있다.(유일성(uniqueness)은 알 수 없다.)

Theorem 2.3.1

Every positive ineger greater than one can be factored as a product of primes.

Proof.

 증명은 well-ordering을 이용해 이루어진다.

 소수들의 곱으로 나타낼 수 없는 1보다 큰 정수들의 집합을 C라고 정의하자. 우리는 C가 비어있지 않고 모순을 유도할 수 있다고 가정한다.

 만약 C가 비어있지 않으면, well ordering에 의해 최소 원소 $n \in C$가 존재한다. n은 소수일 수 없다. 왜냐하면 소수 자신은 항이 하나인 소수들의 곱으로 간주되기 때문이다.

 그래서 n은 반드시 1 < a,b<n인 두 정수 a와 b의 곱이다.a와 b는 가장 작은 C의 원소보다 작아서 우리는 $a,b \notin C$. 다르게 표현하면 $a=p_{1}p_{2}\ldots p_{k}$으로 나타낼 수 있고 $b = q_{1}q_{2}\ldots q_{k}$ 로 나타낼 수 있다.

 따라서, $n= p_{1}p_{2}\ldots p_{k} q_{1}q_{2}\ldots q_{k}$는 소수들의 곱이고 $n \notin C$와 모순된다. 따라서 C가 비어있지 않다는 우리의 가정은 거짓이다.