증명(Proof), 귀납법(Induction)

정의4

직접 증명(direct proof) :

명제 $P,Q$에 대해 $P \equiv \mathbf{T}$를 가정할때 $Q \equiv \mathbf{T}$가 되면 $P \to Q \equiv \mathbf{T}$이므로

이와 같이 명제 $P \to Q$가 참임을 보이는 것을 직접 증명이라 한다.

동치 증명(equivalence proof) :

명제 $P_{1}, P_{2}, \cdots , P_{n}$이 $(P_1\to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{n-1} \to P_n) \land (P_n \to P_1) \equiv \mathbf{T}$이면

명제 정리로 $P_{1}, P_{2}, \cdots , P_{n}$은 논리적 동치가 되므로 이를 보이는 것을 동치 증명이라 한다.

공허한 증명(vacuous proof) : 

명제 $P,Q$에 대해 명제 진리표에 의해 $P \equiv \mathbf{F}$이면 $P \to Q \equiv \mathbf{T}$이고

$V$가 $x$에 대한 명제함수일때 $x$의 정의역이 비어있으면

$\neg V(x)$가 참이 되는 정의역에 속하는 변수 $x$가 존재하지 않으므로

한정기호 부정의 정의로 $\mathbf{F} \equiv \exists x \neg V(x) \equiv \neg \forall xV(x)$가 되어

$\forall x V(x) \equiv \neg ( \neg \forall x V(x))  \equiv \neg \mathbf{F} \equiv \mathbf{T}$이다.

위와 같이 $P \to Q \equiv \mathbf{T}$나 $\forall x V(x) \equiv \mathbf{T}$를 보이는 것을 공허한 증명이라 한다.

자명한 증명(trivial proof) :

명제 $P,Q$에 대해 명제 진리표에 의해 $Q \equiv \mathbf{T}$이면 $P \to Q \equiv \mathbf{T}$이므로 이를 자명한 증명이라 한다.

 

 

 

정의2(간접증명)

대우 증명(contrapositive proof) : 

명제 $P,Q$에 대해 $\neg Q \equiv \mathbf{T}$를 가정할때 $\neg P \equiv \mathbf{T}$가 되면 명제 정리로 $P\to Q \equiv \neg Q \to \neg P \equiv \mathbf{T}$이므로

직접 증명 대신 이와 같이 $ \neg Q \to \neg P$가 참임을 보이는 것을 대우 증명이라 한다.

귀류법 또는 모순에 의한 증명(proof by contradition) :

명제 $P,Q$와 모순 $C \equiv \mathbf{F}$에 대해 $(P \land \neg Q) \to C$가 참이면 명제 진리표에 의해 $P \land \neg Q$는 거짓이다.

따라서 드 모르간 법칙과 명제 정리로 $\mathbf{T} \equiv \neg (P \land \neg Q) \equiv \neg P \lor Q \equiv P \to Q$이므로

이와 같이 $(P \land \neg Q) \to C$가 참임을 보이는 증명 방식을 모순에 의한 증명 또는 귀류법이라 한다.

 

 

 

정리2(시작점이 $0$이상인 귀납법)

자연수집합 $\mathbb{N}$의 임의의 원소 $n_{0}\in \mathbb{N}$보다 크거나 같은 자연수 $n$에 대한 명제함수 $P$가

다음 두 조건을 만족하면 $n \ge n_{0}$인 모든 $n \in \mathbb{N}$에 대해 $P(n)$이 참이다.

1. 명제 $P(n_{0})$이 참이다.

2. $k \ge n_{0}$인 모든 $k\in \mathbb{N}$에 대해 $P(k)$가 참이면 $P(k+1)$도 참이다.

증명

$n \ge n_{0}$인 모든 $n \in \mathbb{N}$에 대해 자연수 부등식의 정의로 $n = n_0 + m_n$인 $m_n \in \mathbb{N}$이 존재하므로

$\mathbb{N}$의 원소에 대한 명제함수 $Q$를 $P(n) $ $\equiv$ $ Q(m_n)$으로 정의한다.

페아노 공리의 귀납법을 사용하여 모든 $m \in \mathbb{N}$에 대해 $Q(m) \equiv \mathbf{T}$임을 보인다.

$m = 0$일때

자연수 덧셈 정리로 $n_0 +0= n_0  = n_0 + m_{n_0}$이므로 소거법칙으로 $m_{n_0} = 0 = m$이 되어

가정 1번으로 $\mathbf{T} \equiv P(n_0) \equiv Q(m_{n_0}) \equiv Q(0)$이다.

모든 $p \in \mathbb{N}$에 대해 $Q(p) \equiv \mathbf{T}$라고 가정하면

$n_0 + m_k = k = n_0 + p$인 $k \in \mathbb{N}$에 대해 소거법칙으로 $p = m_k$이므로

$P(k) \equiv Q(m_k) \equiv Q(p) \equiv \mathbf{T}$이고 자연수 부등식의 정의로 $k \ge n_0$이 되어 가정 2번으로 $P(k+1) \equiv \mathbf{T}$이다.

따라서 자연수 덧셈 정리로

$n_0 + m_{k+1} = k + 1 = (n_0 + p) +1 = n_0 + (p +1) = n_0 + (p + (0\!+\!+)) = n_0 + ((p\!+\!+)+0) = n_0 + (p\!+\!+) \text{이고}$

소거법칙으로 $m _{k+1} = p\!+\!+$이므로 $\mathbf{T} \equiv P(k+1) \equiv Q(m_{k+1}) \equiv Q(p\!+\!+)$가 되어

모든 $m \in \mathbb{N}$에 대해 $Q(m) \equiv \mathbf{T}$이고 $n \ge n_{0}$인 모든 $n \in \mathbb{N}$에 대해 $P(n) \equiv Q(m_n) \equiv \mathbf{T}$이다.

 

 

 

정리4(강 귀납법)

자연수집합 $\mathbb{N}$의 임의의 원소 $n_{0}\in \mathbb{N}$보다 크거나 같은 자연수 $n $에 대한 명제함수 $P$가

다음 두 조건을 만족하면 $n \ge n_{0}$인 모든 $n \in \mathbb{N}$에 대해 $P(n)$이 참이다.

1. 명제 $P(n_{0})$이 참이다.

2. $k \ge n_{0}$인 모든 $k\in \mathbb{N}$에 대해 $P(n_{0}),P(n_{0}+1),\cdots, P(k)$가 모두 참이면 $P(k+1)$도 참이다.

증명

$n \ge n_{0}$인 모든 $n \in \mathbb{N}$에 대해

$n_0\le i \le n$인 모든 $i \in \mathbb{N}$가 $P(i) \equiv \mathbf{T}$이기 위한 필요충분조건이 $Q(n) \equiv \mathbf{T}$인

명제함수 $Q$를 정의하고 귀납법을 사용하여 $n \ge n_0$인 모든 $n \in \mathbb{N}$에 대해 $Q(n) \equiv \mathbf{T}$임을 보인다.

$n = n_0$이면 가정 1번으로 $P(n_0)\equiv \mathbf{T}$이므로 $Q(n_0) \equiv \mathbf{T}$이다.

$k \ge n_0$인 모든 $k \in \mathbb{N}$에 대해 $Q(k) \equiv \mathbf{T}$라고 가정하면

$P(n_{0})\equiv P(n_{0}+1)\equiv \cdots \equiv P(k) \equiv \mathbf{T}$이므로 가정 2번으로 $P(k+1) \equiv \mathbf{T}$이고

$P(n_{0})\equiv P(n_{0}+1)\equiv \cdots \equiv P(k) \equiv P(k+1)\equiv \mathbf{T}$가 되어 $Q(k+1) \equiv \mathbf{T}$이다.

따라서 $n \ge n_0$인 모든 $n \in \mathbb{N}$에 대해 $Q(n) \equiv \mathbf{T}$이므로

$P(n_{0})\equiv P(n_{0}+1)\equiv \cdots \equiv P(n) \equiv \mathbf{T}$이고 $P(n) \equiv \mathbf{T}$이다.

 

 

 

정리1(역진 귀납법)

자연수집합 $\mathbb{N}$의 임의의 원소 $n \in \mathbb{N}$보다 작거나 같은 자연수 $m$에 대한 명제함수 $P$가

다음 두 조건을 만족하면 $n \ge m$인 모든 $m \in \mathbb{N}$에 대해 $P(m)$이 참이다.

1. 명제 $P(n)$이 참이다.

2. $n \ge k +1$인 모든 $k \in \mathbb{N}$에 대해 $P(k+1)$이 참이면 $P(k)$도 참이다.

증명

$n \in \mathbb{N}$에 대한 귀납법을 사용하여 정리를 증명한다.

$n = 0$일때 $n \ge m$인 모든 $m \in \mathbb{N}$은 자연수 부등식의 정의로 $0= n = m + p$인 $p \in \mathbb{N}$가 존재하여

자연수 정리로 $m = 0 $이고 가정 1번으로 $P(0) \equiv \mathbf{T}$이므로 $0 \ge m$인 모든 $m \in \mathbb{N}$에 대해 $P(m) \equiv P(0) \equiv \mathbf{T}$이다.

모든 $r \in \mathbb{N}$에 대해 정리가 성립한다고 가정할때 $r +1 \ge m$인 모든 $m \in \mathbb{N}$에 대해 $P(m) \equiv \mathbf{T}$임을 보인다.

가정 1번으로 $P(r+1)\equiv \mathbf{T}$이고 반사성으로 $r +1 \ge r+1$이므로 가정 2번으로 $P(r) \equiv \mathbf{T}$이다.

또 가정 2번으로 $r+1 \ge k+1$인 모든 $k \in \mathbb{N}$에 대해 $P(k+1)\equiv \mathbf{T}$이면 $P(k) \equiv \mathbf{T}$이고

$r+1 = r +1$이므로 자연수 부등식의 정의로 $r +1 \ge r$이 되어

명제함수 $P$는 $P(r) \equiv \mathbf{T}$이고 추이성으로 $r \ge k+1$인 모든 $k \in \mathbb{N}$에 대해 $P(k+1)\equiv \mathbf{T}$이면 $P(k) \equiv \mathbf{T}$이다.

따라서 귀납가정으로 $r \ge m$인 모든 $m \in \mathbb{N}$에 대해 $P(m) \equiv \mathbf{T}$이고

가정 1번으로 $P(r+1)\equiv \mathbf{T}$이므로 $r+1 \ge m $인 모든 $m \in \mathbb{N}$에 대해 $P(m) \equiv \mathbf{T}$가 되어

모든 $n \in \mathbb{N}$에 대해 정리가 성립한다.

 

 

 

정리7

$0\notin S$인 자연수집합 $\mathbb{N}$의 부분집합 $S$에 대해 다음이 성립한다.

1. $S$가 모든 $k \in \mathbb{N}$에 대해 $k \notin S$일때 $k +1 \notin S$이 되는 성질을 가지면 $S$는 공집합이다.

2. $S$가 모든 $k \in \mathbb{N}$에 대해 $0,1,2,\cdots, k \notin S$일때 $k +1 \notin S$이 되는 성질을 가지면 $S$는 공집합이다.

증명

1.

$S$가 공집합이 아니라고 가정하면 $s \in S$가 존재한다.

귀납법으로 모든 $n \in \mathbb{N}$에 대해 모든 $s \in S$가 $s \ne n$임을 보인다.

$n = 0$이면 정리의 가정으로 $0\notin S$이므로 모든 $s \in S$가 $s \ne 0$이다.

모든 $k \in \mathbb{N}$에 대해 모든 $s \in S$가 $s \ne k$라고 가정할때

$k \in S$이면 모든 $s \in S$가 $s \ne k$이므로 모순이 되어 $k \notin S$이고 정리의 가정으로 $k +1 \notin S$이 되어

모든 $s \in S$는 $s \ne k+1$이다.

따라서 모든 $n \in \mathbb{N}$에 대해 모든 $s \in S$가 $s \ne n$인데 $S \subseteq \mathbb{N}$이므로 모순이 되어 $S$는 공집합이다.

2.

$S$가 공집합이 아니라고 가정하면 $s \in S$가 존재한다.

강귀납법으로 모든 $n \in \mathbb{N}$에 대해 모든 $s \in S$가 $s \ne n$임을 보인다.

$n = 0$이면 정리의 가정으로 $0\notin S$이므로 모든 $s \in S$가 $s \ne 0$이다.

모든 $k \in \mathbb{N}$에 대해 모든 $s \in S$가 $s \ne 0,1,2,\cdots, k$라고 가정할때

$0,1,2,\cdots, k \in S$이면 모든 $s \in S$가 $s \ne 0,1,2,\cdots, k$이므로 모순이 되어

$0,1,2,\cdots, k \notin S$이고 정리의 가정으로 $k +1 \notin S$이 되어 모든 $s \in S$는 $s \ne k+1$이다.

따라서 모든 $n \in \mathbb{N}$에 대해 모든 $s \in S$가 $s \ne n$인데 $S \subseteq \mathbb{N}$이므로 모순이 되어 $S$는 공집합이다.

 

 

 

정리3(자연수집합의 정렬성)

자연수집합 $\mathbb{N}$의 공집합이 아닌 임의의 부분 집합 $S$는

모든 $s \in S$에 대해 $m \le s$인 최소 원소 $m \in S$이 유일하게 존재한다.

또 자연수에 대한 명제함수 $P$에 대해 $P(n) $ $\equiv$ $ \mathbf{T}$인 $n \in \mathbb{N}$이 존재하면 

$P(n_0) \equiv \mathbf{T}$가 되는 최소 자연수 $n _0 \in \mathbb{N}$이 유일하게 존재한다.

증명

존재성

$0 \in S$일때

자연수 덧셈 정리로 모든 $s \in S$에 대해 $s = 0 + s$이고 $s \in \mathbb{N}$이므로

자연수 부등식의 정의로 $s \ge 0$이 되어 최소원소 $0 \in S$이 존재한다.

$0 \notin S$일때

모든 $n \in \mathbb{N}$에 대해 $0 ,1,2,\cdots ,n \notin S$이면 $n +1 \notin S$인 $S\subset \mathbb{N}$는 위 정리로 공집합이므로

$0 \notin S$이고 $S \ne \emptyset$인 임의의 $S\subset \mathbb{N}$는 $0 ,1,2,\cdots ,n \notin S$이면 $n +1 \in S$이 되는 $n \in \mathbb{N}$이 존재한다.

$0 ,1,2,\cdots ,n \notin S$이고 $n +1 \in S$일때 $n +1$이 $S$의 최소원소임을 $n \in \mathbb{N}$에 대한 귀납법을 사용하여 증명한다.

$n = 0$이면 $0 \notin S$이므로 모든 $s \in S$에 대해 $s \ne 0$이고 위와 같이 $s \ge 0$이므로 자연수 부등식의 정의로 $s > 0$이 되어

자연수 부등식 정리로 $s\ge 1$이고 $1\in S$을 가정하였으므로 $1= 0 + 1 \in S$은 $S$의 최소원소이다.

모든 $k \in \mathbb{N}$에 대해 가정이 성립할때 $S$가 $0 ,1,2,\cdots ,k, k+1 \notin S$이고 $k +2 \in S$이면

$0 ,1,2,\cdots ,k \notin S \cup \{ k+1 \}$이고 $k +1 \in S \cup \{ k+1 \}$이므로 $S \cup \{ k+1 \}$의 최소원소는 $k+1$이다.

모든 $s \in S$는 $s \in S\cup \{ k+1 \}$이므로 $s \ge k+1$이고

$k+1 \notin S$를 가정하였으므로 $s \ne k+1$이고 자연수 부등식의 정의로 $s > k+1$이 되어

자연수 부등식 정리로 $s \ge  k+2$이고 $k +2 \in S$를 가정하였으므로 $S$의 최소원소는 $k+2 = (k+1)+1 \in S$이다.

따라서 모든 $n \in \mathbb{N}$에 대해 $0 ,1,2,\cdots ,n \notin S$이고 $n +1 \in S$인 자연수집합의 부분집합 $S$의 최소원소가 존재하고

$0 \in S$인 자연수집합의 부분집합 $S$도 최소원소가 존재하므로

자연수집합의 공집합이 아닌 모든 부분집합은 최소원소가 존재한다.

유일성

$S$의 최소원소 $m, p \in S$가 존재하면 

모든 $s \in S$에 대해 $p\le s$이므로 $p\le m$이고 모든 $s \in S$에 대해 $m\le s$이므로 $m\le p$가 되어

자연수 부등식 정리로 $m = p$이다.

명제함수

분류공리로 $S = \{ n \in \mathbb{N} : P(n) \equiv \mathbf{T}\}$가 존재하고 $P(n) \equiv \mathbf{T}$인 $n \in S$이 존재하여 $S \ne \emptyset$이므로

정렬성으로 $P(n_0) \equiv \mathbf{T}$가 되는 최소 자연수 $n _0 \in S \subseteq \mathbb{N}$이 유일하게 존재한다.

 

 

 

정리8(무한 강하법)

모든 자연수 $n \in \mathbb{N}$에 대해 $a_n \in \mathbb{N}$이고 $a_n > a_{n+1}$이 되는 자연수열 $(a_n)_{n=0}^\infty$은 존재하지 않는다.

증명

$(a_n)_{n=0}^\infty$이 존재한다고 가정하면 집합 $\{a_n  : n \in \mathbb{N} \}$은 공집합이 아닌 자연수 집합의 부분집합이므로

정렬성으로 모든 $n \in \mathbb{N}$에 대해 $a_m \le a_n$인 $m \in \mathbb{N}$이 존재한다.

하지만 $m+1 \in \mathbb{N}$이고 가정에 의해 $a_{m+1}< a_m \le a_n$이므로 모순이 되어 $(a_n)_{n=0}^\infty$은 존재하지 않는다.

 

 

 

정리5(귀납적 정의)

임의의 집합 $A$의 임의의 원소 $a \in A$와 임의의 자연수 $n_0 \in \mathbb{N}$에 대해 $a_{n_0} = a$이고

$n\ge n_0$인 임의의 $n \in \mathbb{N}$에 대해 함수 $f_n : A \to A$이 유일하게 존재하여 $a_{n+1} = f_n(a_n)$이면

$n\ge n_0$인 임의의 $n \in \mathbb{N}$에 대해 $a_n \in A$이 유일하게 존재한다.

증명

$a_n \in A$이 유일하게 존재함을 $n\ge n_0$인 $n \in \mathbb{N}$에 대한 귀납법을 사용하여 증명한다.

$n = n_0$일때 가정에 의해 $a_{n_0} = a \in A$가 존재한다.

$a_{n_0} = a_{m+1} = f_m(a_m)$이고 $m\ge n_0$인 $m \in \mathbb{N}$이 존재한다고 가정하면

$m +1 \ge n_0 +1 > n_0$이므로 $n_0 \in \mathbb{N}$에 대해 $a_{n_0}$은 유일하게 존재한다.

$k\ge n_0$인 모든 $k \in \mathbb{N}$에 대해 $a_k \in A$가 유일하게 존재한다고 가정하면

가정으로 함수 $f_k$가 존재하여 $a_{k+1} = f_k(a_k)$로 정의하면 $a_{k+1} \in A$이 존재한다.

$a_{k+1} = a_{m+1} = f_m(a_m)$이 되는 $m\ne k$이고 $m\ge n_0$인 자연수 $m \in \mathbb{N}$이 존재한다고 가정하면

$k+1\ne m+1$이므로 $k+1 \in \mathbb{N}$에 대해 $a_{k+1} \in A$은 유일하게 존재한다.

따라서 $n\ge n_0$인 모든 $n \in \mathbb{N}$에 대해 $a_n \in A$이 유일하게 존재한다.

 

 

 

정리6(강 귀납적 정의)

임의의 집합 $A$의 임의의 원소 $a \in A$와 임의의 자연수 $n_0 \in \mathbb{N}$에 대해 $a_{n_0} = a$이고

$n\ge n_0$인 임의의 $n \in \mathbb{N}$에 대해 함수 $f_n : $ $A^{n-n_0 +1}$ $ \to A$이 유일하게 존재하여 $a_{n+1} = f_n(a_{n_0},a_{n_0+1},\cdots,a_n)$이면

$n\ge n_0$인 임의의 $n \in \mathbb{N}$에 대해 $a_n \in A$이 유일하게 존재한다.

증명

$a_n \in A$이 유일하게 존재함을 $n\ge n_0$인 $n \in \mathbb{N}$에 대한 강귀납법을 사용하여 증명한다.

$n = n_0$일때 가정에 의해 $a_{n_0} = a \in A$가 존재한다.

$a_{n_0} = a_{m+1} = f_m(a_{n_0},a_{n_0+1},\cdots,a_m)$이고 $m\ge n_0$인 $m \in \mathbb{N}$이 존재한다고 가정하면

$m +1 \ge n_0 +1 > n_0$이므로 $n_0 \in \mathbb{N}$에 대해 $a_{n_0}$은 유일하게 존재한다.

$k\ge n_0$인 모든 $k \in \mathbb{N}$에 대해 $a_{n_0},a_{n_0+1},\cdots,a_k \in A$가 유일하게 존재한다고 가정하면

가정으로 함수 $f_k$가 존재하여 $a_{k+1} = f_k(a_{n_0},a_{n_0+1},\cdots,a_k)$로 정의하면 $a_{k+1} \in A$이 존재한다.

$a_{k+1} = a_{m+1} = f_m(a_{n_0},a_{n_0+1},\cdots, a_m)$이 되는 $m\ne k$이고 $m\ge n_0$인 자연수 $m \in \mathbb{N}$이 존재한다고 가정하면

$m+1\ne k+1$이므로 $k+1 \in \mathbb{N}$에 대해 $a_{k+1} \in A$은 유일하게 존재한다.

따라서 $n\ge n_0$인 모든 $n \in \mathbb{N}$에 대해 $a_n \in A$이 유일하게 존재한다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/8#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/8#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

Robert G. Bartle - Introduction to real analysis - 9788993543766

Kenneth H. Rosen - Discrete mathematics and its applications - 9791132102229

Terence Tao - Analysis 1 - 9791156646662